压缩列表
当一个列表键只包含少量列表项，并且每个列表项要么是小整数值，要么是长度比较短的字符串，那么redis就会使用压缩列表来作为列表键的实现。
压缩列表的实现
压缩列表是由一系列特殊编码的连接内存块组成的顺序数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。
压缩列表
| 属性 | 类型 | 长度 | 用途 |
|---|---|---|---|
| zlbytes | unit32_t | 4字节 | 记录整个压缩列表占用的内存字节数：在对列表进行内存重分配或者计算zlend的位置使用 |
| zltail | unit32_t | 4字节 | 记录压缩列表表尾节点距离压缩列表起始地址有多少字节：通过这个偏移量，程序无需遍历整个列表就可以确定表尾节点的地址 |
| zllen | unit16_t | 2字节 | 记录压缩列表包含的节点数量，当这个值小于UNIT16_MAX(65535)时，这个属性的值就是压缩列表包含的节点的数量；当等于这个值时，节点的真实数量需要遍历整个列表才能计算出 |
| entryN | 列表节点 | 不定 | 压缩列表的各个节点，长度由节点保存的内容决定 |
| alend | unit8_t | 1字节 | 特殊值0xFF，用于标记压缩列表的末端 |
压缩列表节点
字节数组可以是以下三种长度之一：
- 小于等于63(2^6 -1)字节的字节数组；
- 小于等于16383(2^14 -1)字节的字节数组；
- 小于等于4294967295(2^32 -1)字节的字节数组；
整数值可以是以下六种长度之一：
- 4位长，介于0至12之间的无符号整数；
- 1字节长的有符号整数
- 3字节长的有符号整数
- int16_t类型整数
- int32_t类型整数
- int64_t类型整数
每个节点都由previous_entry_length、encoding、content三个部分组成。
previous_entry_length
节点的previous_entry_length属性以字节为单位，记录了压缩列表中前一个字节的长度。previous_entry_length属性的长度可以是1个字节或者5个字节。
- [ ] 如果前一节点的长度小于254字节，那么previous_entry_length的长度就为1字节。
- [ ] 如果前一节点的长度大于等于254字节，那么previous_entry_length的长度就为5字节。
encoding
节点的encoding属性记录了节点的content属性保存的数据的类型以及长度。
字节数组编码如下表：
| 编码 | 编码长度 | content属性保存的值 |
|---|---|---|
| 00bbbbbb | 1字节 | 长度小于等于63字节的字节数组 |
| 01bbbbbb xxxxxxxx | 2字节 | 长度小于等于16383字节的字节数组 |
| 10------ aaaaaaaa bbbbbbbb cccccccc dddddddd | 5字节 | 长度小于等于4294967295字节的字节数组 |
整数编码如下表：
| 编码 | 编码长度 | content属性保存的值 |
|---|---|---|
| 11000000 | 1字节 | int16_t类型整数 |
| 11010000 | 1字节 | int32_t类型整数 |
| 11100000 | 1字节 | int64_t类型整数 |
| 11110000 | 1字节 | 24位有符号整数 |
| 11111110 | 1字节 | 8位有符号整数 |
| 1111xxxx | 1字节 | 使用这一编码的节点没有对应的content属性，因为编码本身的xxxx四位已经保存了一个介于0至12之间的值，所以无需content属性 |
content
节点content属性负责保存节点的值，节点的值可以是一个字节数组或者整数，值得长度和类型由节点的encoding属性决定。
连锁更新
这种情况发生在插入和删除操作中，例如压缩列表中有N个节点大小都小于254个字节，当我们需要插入一个大于254自己的新节点时，后续节点的previous_entry_length属性由原来的1字节变为5字节，出现连锁的变化。更新需要重新分配内存空间，最坏的复杂度为O(N^2)。但是这种更新并不一定发生，可能性比较低。
压缩列表API
| 函数 | 作用 | 复杂度 |
|---|---|---|
| ziplistNew | 创建一个新的压缩列表 | O(1) |
| ziplistPush | 创建一个包含给定值得新节点，并将这个节点添加到压缩列表的表头或者表尾 | 平均O(N)，最坏O(N^2) |
| ziplistInsert | 将包含给定值的新节点插入到给定节点之后 | 平均O(N)，最坏O(N^2) |
| ziplistIndex | 返回压缩列表给定索引上的节点 | O(N) |
| ziplistFind | 在压缩列表中查找并返回包含了给定值的节点 | O(N^2) |
| ziplistNext | 返回给定节点的下一个节点 | O(1) |
| ziplistPrev | 返回给定节点的上一个节点 | O(1) |
| ziplistGet | 获取给定节点保存的值 | O(1) |
| ziplistDelete | 从压缩列表中删除给定的节点 | 平均O(N)，最坏O(N^2) |
| ziplistDeleteRange | 删除压缩列表在给定索引上的连续多个节点 | 平均O(N)，最坏O(N^2) |
| ziplistBlobLen | 返回压缩列表目前占用的内存字节数 | O(1) |
| ziplistLen | 返回压缩列表目前包含的节点数目 | 节点少于65535时为O(1)，大于时为O(N) |
