Redis 压缩列表

当一个列表键值包含少量的列表项，并且每个列表项都是小整数值、或者比较短的字符串，那么redis就会用压缩列表来做列表键的底层实现。

当以哈希键只包含少量的键值对，且每个键值对都是小整数值、或者比较短的字符串，redis也会用压缩列表做哈希键的实现。

1 结构

压缩列表是为了节约内存定义的结构，是一个由连续内存组成的顺序型数据结构。

2 压缩节点

每个压缩节点可以保存一个字节数组或者一个整数值。一个压缩列表可以包含任意多的节点，每个节点可以保存一个任意长度（最大2^32-1长度）字节数组或者一个任意类型的整数。

previous_entry_length：以字节为单位，记录前一个节点的长度，通过可以计算出前一节点的起始地址，实现从表尾遍历到表头。

encoding 记录节点content的数据类型和长度，前两位区分content的类型字节数组和整数值，后面类型记录对应的长度。

content 内容为字节数组或整数值。

3 连锁更新

当出现连续的长度在250字节-到253字节范围内的节点，如果将一个大节点放在这组节点的前面，就会导致后面的每个节点都得进行一次内存重分配，造成连锁更新问题。

在最坏情况下，需要进行N次空间重分配操作，每次分配的最坏时间复杂度为O(N),所以连锁更新的时间复杂度为O(N^2)。

但是连续更新的发生几率比较低，只有出现多个连续的、长度在范围内的才有可能引发。即使出现连锁更新，但只要被更新的节点数量不多，就不会对性能造成影响。