Redis 中的数据结构:双链表

Redis 实现了通用的双链表作为其基础数据结构之一。双链表是 redis 列表类型的实际存储方式之一,同时双链表还被其它功能模块广泛使用。它由三部分组成:

  • 节点
  • 迭代器
  • 链表自身

节点如下:

1
2
3
4
5
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;

包含指向前驱、后继节点的指针及当前节点存储的值。这个值的类型为 void* ,说明 redis 并不限制链表存储的数据类型。

链表的定义如下:

1
2
3
4
5
6
7
8
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;

list 中保存了指向表头和表尾的指针,因此在执行 LPUSHRPUSHRPOP 等命令时是非常快的(θ(1));其中还保存了 len 值,因此 LLEN 命令的执行也是非常快的。

double_link_list.svg

另外,它还保存了三个函数指针 dup、free 和 match 用来复制、释放和对比链表,这样做是因为节点值的类型是不确定的,具体的实现方法交由用户代码灵活扩展处理。比如如果用户定义了 match 函数的实现,则采用它来替换默认使用 == 的比较策略:

1
2
3
4
5
6
7
8
9
10
11
if (list->match) {
if (list->match(node->value, key)) {
listReleaseIterator(iter);
return node;
}
} else {
if (key == node->value) {
listReleaseIterator(iter);
return node;
}
}

类似地,释放一个链表时会优先调用指定的 free 函数后再完成其它释放过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void listRelease(list *list)
{
unsigned long len;
listNode *current, *next;
current = list->head;
len = list->len;
while(len--) {
next = current->next;
if (list->free) list->free(current->value);
zfree(current);
current = next;
}
zfree(list);
}

迭代器的结构如下:

1
2
3
4
typedef struct listIter {
listNode *next;
int direction;
} listIter;

其中,direction 可以向前或向后:

1
2
#define AL_START_HEAD 0
#define AL_START_TAIL 1

可以通过:

1
listIter *listGetIterator(list *list, int direction);

获得迭代器,通过:

1
listNode *listNext(listIter *iter);

进行遍历。另外,还可以将指针移到表头或表尾:

1
2
void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);

(使用的源码基于 redis 3.0.5)

若是喜欢这篇文章,可以随便给个赏钱:)