二京东云开发者| Redis数据结构-List、Hash、Set及Sorted Set的结构实现 _生活百科

1 引言之前介绍了Redis的数据存储及String类型的实现，接下来再来看下List、Hash、Set及Sorted Set的数据结构的实现。
2 ListList类型通常被用作异步消息队列、文章列表查询等；存储有序可重复数据或做为简单的消息推送机制时，可以使用Redis的List类型。对于这些数据的存储通常会使用链表或者数组作为存储结构。

使用数组存储，随机访问节点通过索引定位时间复杂度为O(1) 。但在初始化时需要分配连续的内存空间；在增加数据时，如果超过当前分配空间，需要将数据整体搬迁移到新数组中。
使用链表存储，在进行前序遍历或后续遍历，当前节点中要存储前指针和后指针，这两个指针在分别需要8byte共16byte空间存储，存在大量节点会因指针占用过多空间。链表虽然不需要连续空间存储可以提高内存利用率，但频繁的增加和删除操作会使内存碎片化，影响数据读写速率。

如果我们能够将链表和数组的特点结合起来就能够很好处理List类型的数据存储。
2.1 ZipList3.2之前Redis使用的是ZipList，具体结构如下：

二京东云开发者| Redis数据结构-List、Hash、Set及Sorted Set的结构实现

文章插图

zlbytes: 4byte 记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配，或者计算 zlend 的位置时使用。
zltail：4byte 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen：2byte 记录了压缩列表包含的节点数量：当这个属性的值小于 UINT16_MAX（65535）时，这个属性的值就是压缩列表包含节点的数量；当这个值等于UINT16_MAX 时，节点的真实数量需要遍历整个压缩列表才能计算得出。
entry X：压缩列表包含的各个节点，节点的长度由节点保存的内容决定。包含属性如下：
prerawlen：记录前一个节点所占内存的字节数，方便查找上一个元素地址
len：data根据len的首个byte选用不同的数据类型来存储data
data：本元素的信息
zlend: 尾节点恒等于255

ziplist是一个连续的内存块，由表头、若干个entry节点和压缩列表尾部标识符zlend组成，通过一系列编码规则，提高内存的利用率，使用于存储整数和短字符串。每次增加和删除数据时，所有数据都在同一个ziplist中都会进行搬移操作。如果将一个组数据按阈值进行拆分出多个数据，就能保证每次只操作某一个ziplist 。3.2之后使用的quicklist与ziplist 。
2.2 QuickListquicklist就是维护了一种宏观上的双端链表(类似于B树)，链表的节点为对ziplist包装的quicklistNode，每个quciklistNode都会通过前后指针相互指向，quicklist包含头、尾quicklistNode的指针。

typedef struct quicklist {quicklistNode *head;quicklistNode *tail;unsigned long count;/* total count of all entries in all ziplists */unsigned long len;/* number of quicklistNodes */int fill : QL_FILL_BITS;/* fill factor for individual nodes */unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */...} quicklist;

*head：表头节点
*tail：表尾节点
count：节点包含entries数量
len：quicklistNode节点计数器
fill：保存ziplist的大小，配置文件设定
compress：保存压缩程度值，配置文件设定

quicklistNode：

typedef struct quicklistNode {struct quicklistNode *prev;struct quicklistNode *next;unsigned char *zl;unsigned int sz;/* ziplist size in bytes */unsigned int count : 16;/* count of items in ziplist */。。。} quicklistNode;