1.简介
当一个列表键包含了数量比较多的元素,又或者列表中包含的元素都是比较长的字符串时,Redis就会使用链表作为列表键的底层实现。
除了链表键之外,发布与订阅、慢查询、监视器等功能也用到了链表,Redis服务器本身还使用链表来保存多个客户端的状态信息,以及使用链表来构建客户端输出缓冲区。
2.链表和链表节点的定义和实现
链表节点的结构如下:
typedef struct listNode{
//前置节点
struct listNode *prev;
//后置节点
struct listNode *next;
//节点的值
void *value;
} listNode;
多个listNode可以通过prev和next指针组成双端链表,如下图:
list链表的结构如下:
typedef struct list{
//头结点
listNode *head;
//尾结点
listNode *tail;
//链表的节点数量
unsigned long len;
//节点值复制函数
void *(*dup)(void *ptr);
//节点值的释放函数
void (*free)(void *ptr);
//节点值的对比函数
int (*match)(void *ptr, void *key);
} list;
在Redis中,我们使用list结构来持有链表,如下图是一个list和三个listNode节点组成的链表:
Redis链表特性:
- 双端:链表节点有prev和next指针,获取前置节点和下一节点实践复杂度都是O(1);
- 无环:表头节点的prev和表尾节点的next都指向NULL,对链表的访问以NULL终止;
- 带表头指针和表尾指针;
- 带节点计数器;
- 多态:使用void*指针来保存节点的值。
参考书籍:Redis设计与实现
原创文章,作者:纸飞机-JAVA追梦,如若转载,请注明出处:https://www.zfjsec.com/1912.html