redis压缩列表

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

另外，当一个哈希键值包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么redis就会使用压缩列表来做哈希键的底层实现。

压缩列表的构成

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

属性	类型	长度	用途
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

节点的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)