016.压缩列表

压缩列表的最大特点，就是被设计成一种内存紧凑型的数据结构，占用一块连续的内存空间，不仅可以利用 CPU 缓存，而且会针对不同长度的数据，进行相应编码，可以有效地节省内存开销

但是，也有缺陷：

• 不能保存过多元素，否则查询效率会降低
• 新增或修改某个元素时，压缩列表占用的内存空间需要重新分配，甚至可能引发连锁更新的问题

因此，Redis 对象（List 对象、Hash 对象、Zset 对象）包含的元素数量较少，或元素值不大时才会使用压缩列表

压缩列表结构设计

在表头有 3 个字段：

• zlbytes：总占用字节数
• zltail：尾部节点距起始地址的字节数，即：尾部节点偏移量
• zllen：总节点数量

在结尾有 1 个标记：

• zlend：标记压缩列表的结束点，固定值 0xFF

在压缩列表中：

• 要查找定位第一个元素和最后一个元素，可以通过表头三个字段直接定位，复杂度是 O(1)
• 而查找其他元素时，只能逐个查找，复杂度就是 O(N)，因此不适合保存过多的元素

压缩列表节点（entry）的构成：

• prevlen：「前一个节点」的长度，目的是为了实现从后向前遍历
• encoding：当前节点数据的「类型和长度」，类型主要有两种：字符串和整数
• content：当前节点的实际数据

content 的类型和长度决定了 prevlen 和 encoding 的空间占用大小（为了节省内存）

prevlen：

• 如果前一个节点的长度小于 254 字节，prevlen 用 1 字节的空间保存这个长度值
• 如果前一个节点的长度大于等于 254 字节，prevlen 用 5 字节的空间保存这个长度值

encoding：

连锁更新

• 压缩列表新增或修改元素时，如果空间不够，压缩列表占用的内存空间就需要重新分配
• 插入较大元素时，可能导致后续元素的 prevlen 占用空间都发生变化，从而引起「连锁更新」，导致每个元素的空间都要重新分配
  • 就像多米诺牌效应一样，前一个元素导致下一个元素的 prevlen 空间占用变大，下一个元素的整体空间占用变大，又导致下下个元素的 prevlen 空间占用变大，…
  • 连锁更新一旦发生，就会导致压缩列表占用的内存空间要多次重新分配

总结

• 压缩列表是 Redis 为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类似于数组
• 压缩列表不适合保存过多的元素，因为：
  • 查找非首尾元素的时间复杂度是 O(N)
  • 如果保存的元素数量增加或元素数据变大，会导致内存重新分配，最糟糕的是会有「连锁更新」问题