链表在 Redis 的应用
由于 Redis 的 c 语言没有内置链表结构类型, 因此 Redis 自身实现了一套链表结构. 链表主要应用在几个方面:
应用于较长的 list 结构中
发布与订阅
监视器
保存多个客户端状态信息等等
链表在 Redis 中的实现
我们翻到源码 src/adlist.h 中的 listNode 结构体, 这个结构体也就是链表节点的实现:
- /*
- * 双端链表节点
- */
- typedef struct listNode {
- // 前置节点
- struct listNode *prev;
- // 后置节点
- struct listNode *next;
- // 节点的值
- void *value;
- } listNode;
可以看到, 如果画成图, 那么多个 listNode 就会变成这样的一个链表:
image.PNG
为了操作更方便, Redis 还实现了一个链表 list, 源码位于 src/adlist.h 的 list 结构体:
- /*
- * 双端链表结构
- */
- typedef struct list {
- // 表头节点
- listNode *head;
- // 表尾节点
- listNode *tail;
- // 节点值复制函数
- void *(*dup)(void *ptr);
- // 节点值释放函数
- void (*free)(void *ptr);
- // 节点值对比函数
- int (*match)(void *ptr, void *key);
- // 链表所包含的节点数量
- unsigned long len;
- } list;
其中, 比较难看懂的应该就是 dup,free,match 三个字段, 我们分别解释一下这三个字段的作用:
dup: 主要是用来复制链表节点所保存的值
free: 主要是用来释放链表节点的内存空间
match: 用来比对节点值, 通常用来查找某个值是否在链表中
那么, 为什么要抽出这三个成独立的字段呢? 答案就是为了多态, 我们都知道 void * 在 C 语言是表示任意类型的指针, 加上链表节点的 value 也是用 void * 保存的, 因此通过 dup,free,match 三个字段函数就可以操作各种类型的值, 也让链表节点能够保存任何类型的值了.
Redis 中链表的特性总结
总体来说, Redis 的链表结构非常简单高效, 主要体现以下几方面:
双端链表. 每个链表节点 listNode 都包含了 prev 和 next 字段, 用来指向该节点前一个节点和后一个节点, 这样可以使得节点查找前一个和后一个节点的计算复杂度变为 O(1).
无环. listNode 的 prev 和 next 字段都是指向 NULL, 因此链表是无环的.
带表头的表尾指针. 链表 list 带有 head 和 tail 指针, 使得查找链表的表头和表尾节点的计算复杂度变为 O(1).
链表长度计算器. 链表 list 有一个字段 len, 使得计算链表长度的复杂度变为 O(1), 而不用通过遍历链表来获取总长度.
来源: http://www.jianshu.com/p/867891c09bfe