一、3.0以前的列表实现
链表是由许多内存碎片组成,而压缩列表是为了节约内存而开发的,由一系列特殊编码的连续内存块组成的顺序型数据结构,这个和各种语言的数组类似。当redis的列表包含了比较多的元素时,或者包含的元素都是比较长的字符串时,会使用链表来存储数据结构;而当包含了少量的列表项,并且每个元素要么是小整数值,要么是长度比较短的字符串时,会使用压缩列表来作为列表键的底层实现。
linkedlist(链表)
1、链表的实现
每个链表节点使用一个adlist.h/listNode结构来表示:
typedefstructlistNode { // 前置节点指针structlistNode*prev; //后置节点指针structlistNode*next; //节点的值的指针void*value; } listNode;
多个listNode可以通过pre(前置)和next(后置)组成双端链表;
虽然仅仅使用多个listNode结构可以组成链表,但使用adlist.h/list来持有链表的话,操作起来会更方便:
typedefstructlist { //头部节点指针listNode*head; //尾部节点指针listNode*tail; //节点值复制void*(*dup)(void*ptr); //节点值释放void (*free)(void*ptr); //节点值对比int (*match)(void*ptr, void*key); //链表所包含的节点数量unsignedlonglen; } list;
list结构为链表提供了表头指针head、表尾指针tail以及链表长度计数器len,而dup、free、match则是用于实现多态链表所需的类型特定函数。
2、链表的特性:
- 双端:带有prev和next指针,获取某个节点的前置节点和后置节点的复杂度都是O(1)
- 无环:prev指针和next指针都指向NULL
- 带表头指针和表尾指针:通过list结构的head和tail指针,程序获取链表的表头节点和表尾节点的复杂度为O(1)
- 带链表长度计数器:获取链表中节点数量的复杂度为O(1)
- 多态:链表节点使用void*指针保存节点值,通过dup、free、match为节点值设置类型特定函数,所以链表可以保存各种不同类型的值
ziplist(压缩列表)
1、压缩列表的构成
2、压缩列表节点的构成
2.1 previous_entry_length
2.2 encoding
节点的encoding记录了节点的content属性所保存数据的类型以及长度:
2.3 content
3、连锁更新
二、3.2以后的列表实现
1、quicklist的数据结构
typedefstructquicklist { //quicklist的链表头quicklistNode*head; //quicklist的链表尾quicklistNode*tail; //所有压缩列表中的总元素个数unsignedlongcount; //链表节点的个数 quicklistNodeunsignedlonglen; ... } quicklist;
2、quicklistNode的结构
typedefstructquicklistNode { //指向前节点的指针structquicklistNode*prev; //前一个quicklistNode//指向后节点的指针structquicklistNode*next; //后一个quicklistNode//quicklistNode指向的压缩列表unsignedchar*zl; //压缩列表的的字节大小unsignedintsz; //压缩列表的元素个数unsignedintcount : 16; //ziplist中的元素个数 .... } quicklistNode;
可以看到 node节点有指向前节点和后节点的指针,以及节点的元素保存的不是单纯的元素值,而是保存了一个压缩链表,所以有个指向压缩链表的指针*zl
在向quicklist添加一个元素的时候,不会像普通的链表那样,直接新建一个链表节点。而是会检查插入位置的压缩链表是否能容纳该元素,如果能够容纳,那么就直接保存到quicklistNode结构里面的压缩列表,如果不能容纳,才会新建一个Node结构。
quicklist会控制quicklistNode结构里面的压缩列表的大小或者元素个数,用来规避潜在的连锁更新的风险,但是并没有完全解除。