7. 压缩列表

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

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

7.1 压缩列表的构成

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

7.2 压缩列表节点的构成

每个压缩列表节点都由previous_entry_length, encoding, content三个部分组成

每个压缩列表节点可以保存一个字节数组或者一个整数值，其中，字节数组可以是以下3中长度的其中一种：

长度小于等于63（2^6-1）字节的字节数组

长度小于等于16383(2^14-1)字节的字节数组

长度小于等于429496(2^32-1)字节的字节数组

整数值可以是以下六种长度的其中一种：

4位长，介于0-12之间的无符号整数

1字节长的有符号整数

3字节长的有符号整数

int16_t类型整数

int32_t类型整数

int64_t类型整数

7.2.1 previous_entry_length

节点的previous_entry_length属性以字节为单位，记录了压缩列表中前一个节点的长度。previous_entry_length长度为1字节或5字节：

如果前一字节的长度小于254字节，那么previous_entry_length的长度为1字节：前一节点的长度就保存在这一个节点中

如果前一字节的长度大于等于254字节，那么previous_entry_length的长度为5字节：其中属性的第一字节就会被设置为0xFE(十进制值254)，而之后的四个字节则用于保存前一节点长度。

压缩列表的从表尾向表头遍历操作的原理实现：只要又一个执行某个节点起始地址的指针，就可以通过这个指针以及这个节点的previous_entry_length属性，程序就可以一直回溯向前一个节点，最终达到压缩列表的表头节点。

7.2.2 encoding

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

7.2.3 content

负责保存节点的值，节点的值可以是一个字节数组或者整数，值的类型和长度由节点的encoding属性决定。

7.3 连锁更新

在特殊情况下产生的连续多次空间扩展操作，例如e1-eN节点长度均介于250-253字节之间，previous_entry_length用一个字节保存长度值。现有一个长度大于254字节的new节点插入到e1节点之前,e1的previous_entry_length节点为了保存new的长度值要从1字节扩展到5字节，导致自身长度大于254字节，所以后续的所有节点都需要空间扩展。

除了添加节点会引起连锁更新，删除节点也会引发连锁更新

因为连锁更新在最坏情况下需要对压缩列表执行N次空间重分配操作，而每次空间重分配的最坏复杂度为O(N)，所以连续更新的最坏复杂度为O(N^2)