Redis内置数据结构之链表

「 REDIS 」 二月 22, 2020

Redis内置数据结构之链表

文章字数 4k 阅读约需 4 mins. 阅读次数 1000000

编写Redis的C语言没有内置链表数据结构，因此Redis构建了自己的链表实现。

应用

  1. 列表键、发布、订阅、慢查询、监视器等功能
  2. 保存多个客户端的状态信息
  3. 构建客户端输出缓冲区（output buffer）

链表和链表节点的实现

在adlist.h中，每个链表节点用一个listNode结构体表示：

1
2
3
4
5
6
7
8
typedef struct listNode{
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

多个listNode通过prev和next指针组成双端链表。

在adlist.h中使用list来持有链表，方便操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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结构体和三个listNode结构体组成的链表：

图1 由list结构和listNode结构组成的链表

Redis链表实现的特性总结：

  1. 双端：prev和next指针使得获取某个节点的前置节点和后置节点的复杂度都是O(1)。
  2. 无环：表头节点的prev和表尾节点的next都指向NULL，对链表的访问以NULL为终点。
  3. 带head和tail：程序获取表头节点和表尾节点的复杂度都为O(1)。
  4. 带链表长度计数器：使用list的len属性进行计数，程序获得节点数量的复杂度为O(1)。
  5. 多态：节点使用void*指针来保存节点值，list的dup、free、match三个属性都为函数指针，可以将其设置为类型特定函数，所以Redis链表可以用于保存各种不同类型的值并实现各种类型操作。

Justin Han

This world will be changed certainly
0%