[TOC] ## 概述 Redis中的List是一个有序（按加入的时序排序）的数据结构，一般有序我们会采用数组或者是双向链表，其中双向链表由于有前后指针实际上会很浪费内存。3.2版本之前采用两种数据结构作为底层实现： * 压缩列表ziplist * 双向链表linkedlist ## ziplist的结构 ziplist的数据结构及解释如下：  `ziplist`的节点信息如下： ``` typedef struct zlentry { // prevrawlen ：前置节点的长度 // prevrawlensize ：编码 prevrawlen 所需的字节大小,有1字节和5个字节两种。 unsigned int prevrawlensize, prevrawlen; // len ：当前节点值的长度 // lensize ：编码 len 所需的字节大小 unsigned int lensize, len; // 当前节点 header 的大小 // 等于 prevrawlensize + lensize unsigned int headersize; // 当前节点值所使用的编码类型 unsigned char encoding; // 指向当前节点的指针 unsigned char *p; } zlentry; ``` 返回一个zlenrty ``` static zlentry zipEntry(unsigned char *p) { zlentry e; // e.prevrawlensize 保存着编码前一个节点的长度所需的字节数 // e.prevrawlen 保存着前一个节点的长度 // T = O(1) ZIP_DECODE_PREVLEN(p, e.prevrawlensize, e.prevrawlen); // p + e.prevrawlensize 将指针移动到列表节点本身 // e.encoding 保存着节点值的编码类型 // e.lensize 保存着编码节点值长度所需的字节数 // e.len 保存着节点值的长度 // T = O(1) ZIP_DECODE_LENGTH(p + e.prevrawlensize, e.encoding, e.lensize, e.len); // 计算头结点的字节数 e.headersize = e.prevrawlensize + e.lensize; // 记录指针 e.p = p; return e; } ``` ## ziplist的原理 ziplist是使用连续的内存块存储的： * zlbytes：表示整个ziplist占用的字节数，一般用于内存重分配或者计算列表尾端 * zltail：到达列表最后一个节点的偏移量，方便直接找到尾部节点 * zllen：列表节点的数量 * entryX：列表中的各节点 * zlend：作用就是用来标记列表尾端，占用一个字节 >注意zllen用16个比特位存储，也就是说起长度最大表示65535，所以如果长度超过这个值，只能够通过节点遍历来确定列表元素数量 每个节点`zlentry`是如何存储的，完整的`zlentry`由以下几个部分组成： * `prevrawlen`： 记录前一个节点所占内存的字节数，方便查找上一个元素地址 * `unsigned int lensize, len`： lensize表示编码 len 所需的字节大小，len表示当前节点值的长度 * `unsigned int headersize`： 当前节点 header 的大小，等于 prevrawlensize + lensize * `unsigned char encoding`： 当前节点值所使用的编码类型 >ziplist数据结构中`prevrawlen`是变长编码的，如果上一个节点长度小于254个字节，则只是用一个字节存储prevrawlen，如果大于等于254，那么第一个字节用254标记，后面四个字节表示上一个节点长度 ## ziplist 的优缺点 * `ziplist`存储在一段连续的内存上，所以存储效率很高。但是，它不利于修改操作，插入和删除操作需要频繁的申请和释放内存。特别是当`ziplist`长度很长的时候，一次`realloc`可能会导致大批量的数据拷贝。 * 双向链表`linkedlist`便于在表的两端进行`push`和`pop`操作，在插入节点上复杂度很低，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。 ziplist 最大的确定就是*连锁更新问题* 因为在`ziplist`中，每个`zlentry`都存储着前一个节点所占的字节数，而这个数值又是变长编码的。假设存在一个压缩列表，其包含 e1、e2、e3、e4.....，e1 节点的大小为 253 字节，那么 e2.prevrawlen 的大小为 1 字节，如果此时在 e2 与 e1 之间插入了一个新节点 e，e 编码后的整体长度（包含 e1 的长度）为 254 字节，此时 e2.prevrawlen 就需要扩充为 5 字节；如果 e2 的整体长度变化又引起了 e3.prevrawlen 的存储长度变化，那么 e3 也需要扩.......如此递归直到表尾节点或者某一个节点的 prevrawlen 本身长度可以容纳前一个节点的变化。其中每一次扩充都需要进行空间再分配操作。删除节点亦是如此，只要引起了操作节点之后的节点的 prevrawlen 的变化，都可能引起连锁更新，引发内存 realloc。 连锁更新在最坏情况下需要进行 N 次空间再分配，而每次空间再分配的最坏时间复杂度为 O(N)，因此连锁更新的总体时间复杂度是 O(N^2)。 基于上述来看ziplist的缺点大于优点，所以*3.2版本之后采用了另外一个数据结构为quicklist* ## 应用场景 * 压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。redis数据列表`list`操作，在列表中添加一个或多个值`RPUSH`: ``` redis> RPUSH lst 1 3 5 10086 "hello" "world" (integer)6 redis> OBJECT ENCODING lst "ziplist" ``` * 当一个哈希键只包含少量键值对，比且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做哈希键的底层实现。 ``` redis> HMSET profile "name" "Jack" "age" 28 "job" "Programmer" OK redis> OBJECT ENCODING profile "ziplist" ``` >哈希键里面包含的所有键和值都是小整数值或者短字符串 ps: 以上截图来自《Redis设计与实现一书》