ch7.md

压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表现，并且每个列表项要么就是小整数值，要么就是长度较短的字符串，那么Redis就会使用压缩列表来实现列表键。

当一个哈希键只包含少量键值对，并且每个键值对要么是小整数值，要么是长度较短的字符串，Redis就会使用压缩列表来实现哈希键。

7.1 压缩列表的构成

压缩列表是Redis为了节约内存而开发的，由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。一个压缩列表可以包含多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。

压缩列表的各组成部分：

zlbytes | zltail | zllen | entry1 | entry2 | … | entryN | zlend

其中，

属性	类型	长度	用途
zlbytes	uint32_t	4字节	记录压缩列表占用的内存字节数：在内存重分配，或计算zlend的位置时使用
zltail	uint32_t	4字节	记录表尾结点距离起始地址的字节数：通过这个偏移量，程序可以直接确定表尾结点的地址
zllen	uint16_t	2字节	记录节点数量：但这个属性小于UINT16_MAX（65535）时，这个属性的值就是节点的数量。如果等于UINT16_MAX，节点的真实数量要遍历整个压缩列表才能得到
entryX	列表节点	不定	各个节点，节点的长度由保存的内容决定
zlend	uint8_t	1字节	特殊值0xFF，标记压缩列表的尾端

7.2 压缩列表节点的构成

压缩列表的节点可以保存一个字节数组或者一个整数值。压缩节点的各个组成部分：

previous_entry_length | encoding | content

previous_entry_length

previous_entry_length以字节为单位，记录前一个节点的长度。previous_entry_length属性的长度可以是1字节或5字节：

1. 若前一节点的长度小于254字节，那么previous_entry_length属性的长度就是1字节。前一节点的长度保存在其中。
2. 若前一节点的长度大于254字节，那么previous_entry_length属性的长度就是5字节：其中属性的第一个字节被设置为0xFE（十进制254），而之后的四个字节则用于保存前一节点的长度。

程序可以通过指针运算，根据当前节点的起始地址来计算出前一个结点的起始地址。压缩列表的从尾向头遍历就是据此实现的。

encoding

节点的encoding记录了节点的content属性所保存的数据的类型和长度：

• 1字节、2字节或者5字节长，值的最高位为00、01或10的是字节数组编码：这种编码表示节点的content保存的是字节数组，数组的长度由编码除去最高两位置后的其他位记录。
• 1字节长。值的最高位以11开头的是整数编码：表示content保存着整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录。

content

content保存节点的值，可以使字节数组或整数，值的类型和长度由encoding属性决定。

保存字节数组“hello world”的节点：

previoid_entry_length	encoding	content
...	00001011	"hello world"

保存整数10086的节点：

previoid_entry_length	encoding	content
...	11000000	10086

7.3 连锁更新

因为previoid_entry_length的长度限制，添加或删除节点都有可能引发「连锁更新」。在最坏的情况下，需要执行N次重分配操作，而每次空间重分配的最坏复杂度是O(N)，合起来就是O(N^2)。

尽管如此，连锁更新造成性能问题的概率还是比较低的：

1. 压缩列表里有多个连续的、长度介于250和253字节之间的节点，连锁更新才有可能触发。
2. 即使出现连锁更新，只要需要更新的节点数量不多，性能也不会受影响。

7.4 压缩列表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)
ziplistBlobLen	返回压缩列表占用的内存字节数	O(1)
ziplistLen	返回包含的节点数量	节点数量小于65535时为O(1)，否则为O(N)

导航

目录

上一章：6. 整数集合

下一章：8. 对象