压缩列表(ziplist)是列表键和哈希键的底层实现之一。当一个列表键值包含少量列表项，并且每个列表项要么是小整数值，要么是长度比较短的字符串，那么Redis就会使用压缩列表做列表键的底层实现。
另外，当一个哈希键值包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么redis就会使用压缩列表来做哈希键的底层实现。
压缩列表的构成
压缩列表是Redis为了节约内存而开发的，是由一系列编码的连续内存块组成的顺序列(sequential)数据结构。一个压缩列表可以包含任意多个节点(entry)，每个节点可以保存一个字节数组或者一个整数值。
| zlbytes | zltail | zllen | entry1 | entry2 | … | entryN | zlend |
|---|---|---|---|---|---|---|---|
| 属性 | 类型 | 长度 | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4字节 | 记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重新分配，或者计算zlend的位置时使用 |
| zltail | uint32_t | 4字节 | 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无需遍历整个压缩列表就可以确定表尾节点的地址 |
| zllen | uint16_t | 2字节 | 记录了压缩列表包含的节点数量：当这个值小于UNIT16_MAX(65525)时，这个属性的值就是压缩列表包含的节点数量；当这个值等于UNIT16_MAX时，节点的真实数量需要遍历整个压缩列表才能计算得出 |
| entryX | 列表节点 | 不定 | 压缩列表包含的各个节点，节点的长度有节点保存的内容决定 |
| zlend | 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字节：其中第一字节设置成0xFE(254)，而之后的4个字节则用于保存前一节点的长度。
因为节点的previous_entry_length属性记录了前一个节点的长度，所以程序可以通过指针运算，根据当前节点的起始地址计算出前一个节点的起始地址。
encoding
节点的encoding属性记录了节点的content属性所保存数据的类型及长度：
- 1字节、2字节或者5字节长，值的最高位位00、01、或者10的字节数组编码：这种编码表示节点的content属性保存着字节数组，数组的长度由编码除去最高两位之后的其他位记录
- 1字节长，值的最高位以11开头的整数编码：这种编码表示节点的content属性保存着整数值，整数值的类型和长度由除去最高两位之后的其他位记录
字节数组编码
| 编码 | 编码长度 | content保存的值 |
|---|---|---|
| 00bbbbbb | 1字节 | 长度小于等于63字节的字节数组 |
| 01bbbbbb xxxxxxxx | 2字节 | 长度小于等于16383字节的字节数组 |
| 10bbbbbb xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx | 5字节 | 长度小于等于494967295字节的字节数组 |
整数编码
| 编码 | 编码长度 | 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属性决定。
连锁更新
因为previous_entry_length长度变化引发的后续节点都需要更新并重新分配内存。
API
- ziplistNew：创建一个新的压缩列表，O(1)
- ziplistPush：创建一个包含给定值的新节点，并将这个新节点添加到压缩列表的表头或者表尾，平均O(N)，最坏O(N^2)
- ziplistInsert：将包含给定值的新节点插入到给定节点之后，平均O(N)，最坏O(N^2)
- ziplistIndex：返回压缩列表给定索引上的节点，O(N)
- ziplistFind：在压缩列表中查找并返回包含了给定值的节点，因为节点的值可能是一个字节数组，所以检查节点值和给定值是否相同的复杂度为O(N)，而查找整个列表的复杂度为O(N^2)
- ziplistNext：返回给定节点的下一个节点，O(1)
- ziplistPrev：返回给定节点的前一个节点，O(1)
- ziplistGet：获取给定节点保存的值，O(1)
- ziplistDelete：从列表中删除给定的节点，平均O(N)，最坏O(N^2)
- ziplistDeleteRange：删除压缩列表在给定索引上的连续多个节点，平均O(N)，最坏O(N^2)
- zpilistBlobLen：返回压缩列表目前占用的内存数，O(1)
- zplistLen：返回压缩列表目前包含的节点数量，节点数量小于65535时为O(1)，大于65535时为O(N)