Redis 核心数据结构深度解析：压缩列表、跳表、快速列表与 Listpack

Redis 作为高性能的内存数据库，其优秀的性能很大程度上得益于精心设计的数据结构。本文将深入探讨 Redis 中四种重要的底层数据结构：压缩列表（Ziplist）、跳表（Skiplist）、快速列表（Quicklist）和 Listpack，分析它们的实现原理、优缺点以及适用场景。

1. 压缩列表（Ziplist）

实现原理

压缩列表是 Redis 为了节省内存而设计的一种特殊编码的双端链表结构。它将所有元素连续存储在一块内存中，通过特殊的编码方式来减少内存开销。

压缩列表（Ziplist）结构

+---------+----------+----------+-----+----------+----------+---------+
| zlbytes | zltail   | zllen    | ... | entries  | ...      | zlend   |
+---------+----------+----------+-----+----------+----------+---------+
    4B        4B         2B             变长字段              1B

entry 结构

+----------+----------+----------+
| prevlen  | encoding | content  |
+----------+----------+----------+
| 1-5字节  | 1-4字节  | 变长字段 |

每个字段的详细说明：

zlbytes：整个压缩列表占用的字节数（包括zlbytes、zltail、zllen、zlend和所有entry，占4字节）
zltail：到达表尾节点的偏移量，用于从尾部快速定位（占4字节）
zllen：节点数量，当小于UINT16_MAX时准确，否则需要遍历计算（占2字节）
entries：实际存储的节点数据（变长字段）
zlend：压缩列表的结束标记，固定值0xFF（占1字节）

每个 entry 包含：

prevlen：前一节点的总字节长度（即前一节点整个entry的物理存储大小，包括其prevlen、encoding和content）（1-5字节）
encoding：当前节点的编码方式（1-4字节）
content：实际存储的数据

连锁更新问题详解

压缩列表中最著名的问题就是连锁更新（Cascading Update），这是理解 ziplist 性能特性的关键。

prevlen 字段的存储机制

每个元素通过 prevlen 字段存储前驱节点的长度：

1字节格式：当长度 < 254 字节时，直接用1字节存储长度值
5字节格式：当长度 ≥ 254 字节时，首字节固定为 0xFE，后跟4字节存储实际长度

连锁更新的发生机制

当发生插入或删除操作时，如果导致某个节点的长度跨越 254 字节阈值，就会触发连锁更新：

1. 扩容连锁更新：节点长度从小于254字节变为大于等于254字节

初始状态：
[Node0][Node1][Node2]
 253B   253B   253B

各节点的 prevlen 字段：
Node0: 无prevlen（首节点）
Node1: prevlen=1字节（记录Node0总长度253）
Node2: prevlen=1字节（记录Node0总长度为253）

现在在首节点前插入一个 253 字节的新节点：
插入后状态变化：

步骤1：插入新节点
[NewNode][Node0][Node1][Node2]
   253B   253B   253B   253B

步骤2：Node0的prevlen需要更新
由于NewNode长度为253字节(<254)，Node0的prevlen变为1字节
Node0的总长度变为：253 + 1(新prevlen) = 254字节

步骤3：连锁更新开始
Node0长度变为254字节(≥254)，Node1的prevlen必须从1字节扩容到5字节
Node1的prevlen从1字节变为5字节(0xFE前缀+4字节)

步骤4：Nod1总长度变化
Node1总长度变为：253 + 5(新prevlen) = 258字节

步骤5：继续连锁更新
Node1长度变为258字节(≥254)，后续节点的prevlen也需要扩容...

缩容连锁更新：节点长度从大于等于254字节变为小于254字节

初始状态：
[OldNode][Node0][Node1][Node2]
  254B    254B   254B   254B

各节点的 prevlen 字段：
OldNode: 无 prevlen（首节点）
Node0: prevlen=5字节（记录OldNode总长度254）
Node1: prevlen=5字节（记录Node0总长度254）
Node2: prevlen=5字节（记录Node1总长度254）

现在删除OldNode节点：
删除后状态变化：

步骤1：删除OldNode节点
[Node0][Node1][Node2]
 254B   254B   254B

步骤2：Node0的prevlen需要更新
由于删除了OldNode节点，Node0作为新的首节点，Node0无prevlen
Node0的总长度变为：254 - 5(旧prevlen) = 249字节

步骤3：连锁更新开始
Node0长度变为249字节(<254)，Node1的prevlen必须从5字节缩容到1字节
Node1的prevlen从5字节(0xFE前缀+4字节)变为1字节

步骤4：Nod1总长度变化
Node1总长度变为：254 - 4(prevlen减少4个字节) = 250字节

步骤5：继续连锁更新
Node1长度变为250字节(<254)，**后续节点**的prevlen也需要缩容...

连锁更新的性能影响

时间复杂度：

最坏情况：O(N) - 需要更新所有后续节点
平均情况：O(N/2) - 平均需要更新一半的节点

空间复杂度：

可能导致内存使用量临时增加（需要额外的4字节*N个节点）

连锁更新的触发条件

插入操作：
- 在长度接近254字节的节点前插入较大节点
- 导致后续节点长度跨越阈值
删除操作：
- 删除节点导致前驱节点长度变化
- 可能触发缩容连锁更新
更新操作：
- 修改节点内容导致长度变化
- 跨越254字节阈值

优点

内存效率极高：连续存储，无额外指针开销
CPU缓存友好：数据在内存中连续存放，提高缓存命中率
存储紧凑：通过变长编码减少存储空间
实现简单：结构相对简单，易于理解和维护

缺点

连锁更新问题：当某个节点长度变化时，可能导致后续所有节点都需要更新
查找效率低：只能顺序查找，时间复杂度为 O(n)
插入删除开销大：需要移动后续所有数据
扩展性差：随着数据量增加，性能急剧下降

适用场景及具体阈值

Redis Hash：当元素数量不超过 512 个且所有值大小都不超过 64 字节时
Redis List：当元素数量不超过 512 个且所有值大小都不超过 64 字节时
Redis ZSet：当元素数量不超过 128 个且所有值大小都不超过 64 字节时

这些阈值可以通过以下配置参数调整：

# Hash 相关配置
hash-max-ziplist-entries 512
hash-max-ziplist-value 64

# List 相关配置  
list-max-ziplist-entries 512
list-max-ziplist-value 64

# ZSet 相关配置
zset-max-ziplist-entries 128
zset-max-ziplist-value 64

2. 跳表（Skiplist）

实现原理

跳表是一种随机化的数据结构，通过多层链表实现快速查找。每个节点包含多个指针，指向不同层级的后续节点。
每个跳表只有一个头节点，这是跳表数据结构的基本设计原则。头节点作为跳表的入口点，不存储实际数据，而是通过多层指针连接各层节点。
头节点是虚拟节点(virtual node)，不包含实际数据元素，仅作为各层链表的起始点。这种设计使得头节点可以统一管理所有层的指针结构

Level 3: -∞ ----------------------------> 17 ----------------------------> +∞
          |                               |                               |
Level 2: -∞ ----------> 6 ----------> 17 ----------> 25 ----------> +∞
          |             |             |             |             |
Level 1: -∞ ----> 3 ----> 6 ----> 7 ----> 9 ----> 12 ----> 17 ----> 25 ----> +∞
          |       |       |       |       |        |        |        |       |
Level 0: -∞ --> 1 --> 3 --> 4 --> 6 --> 7 --> 9 --> 12 --> 17 --> 19 --> 21 --> 25 --> 26 --> +∞

跳表最大层次

Redis 中跳表的最大层次在不同版本中有所不同：

Redis 5.0 及之前版本：最大默认层次设置为 64 层
Redis 7.0 及之后版本：最大默认层次调整为 32 层

这个值由 ZSKIPLIST_MAXLEVEL 常量定义。选择 32 层（相比之前的 64 层）的原因是：

对于实际应用场景已经足够：32 层可以支持 2^32 个元素的高效查找
在内存使用和查询性能之间取得更好的平衡
减少内存开销：层级减少一半，索引节点数量相应减少
提供稳定的 O(log n) 时间复杂度保证

层次选择采用概率算法，每层被选中的概率为 25%，确保层级分布合理。

超过最大层数的处理

Redis跳表在节点层数超过当前最大限制时，通过动态扩展头节点层数（增加头节点的指针数组长度，比如在上面的结构中 Level 2 增加 30的节点）而非截断新节点层数，既保持了跳表的高效查询特性，又避免了层数截断带来的性能损耗。

优点

查找效率高：平均时间复杂度为 O(log n)
插入删除高效：平均时间复杂度为 O(log n)
实现相对简单：相比平衡树更容易实现和调试
支持范围查询：天然支持范围查找操作
性能稳定：操作性能不受数据分布影响

缺点

内存开销大：需要维护多层指针，内存使用量较大
随机化特性：性能依赖于随机数生成质量
空间复杂度高：最坏情况下空间复杂度为 O(n²)
维护成本：需要维护多层索引结构

适用场景

Redis ZSet：当元素数量超过 128 个或值大小超过 64 字节时的主要实现
需要频繁范围查询：如获取某个范围内的所有元素
对查找性能要求较高：如需要快速定位特定元素的场景

3. 快速列表（Quicklist）

实现原理

快速列表是 Redis 3.2 引入的数据结构，结合了链表和压缩列表的优点。它将大量元素分段存储在多个压缩列表中，通过双向链表连接这些段。

+--------+    +--------+    +--------+    +--------+
| Node1  |<-->| Node2  |<-->| Node3  |<-->| Node4  |
+--------+    +--------+    +--------+    +--------+
    |             |             |             |
    v             v             v             v
+---------+   +---------+   +---------+   +---------+
| Ziplist |   | Ziplist |   | Ziplist |   | Ziplist |
+---------+   +---------+   +---------+   +---------+
| Elem1   |   | Elem4   |   | Elem7   |   | Elem10  |
| Elem2   |   | Elem5   |   | Elem8   |   | Elem11  |
| Elem3   |   | Elem6   |   | Elem9   |   | Elem12  |
+---------+   +---------+   +---------+   +---------+

适用场景

Redis List：Redis 3.2+版本改为使用quicklist实现，不再使用 ziplist 或 linkedlist（双向链表），结合了两者的优点。
默认配置：每个 quicklist node 的 ziplist 大小限制为 8KB（可通过配置调整）

优点

内存效率高：继承了压缩列表的内存优势
操作性能好：避免了单个压缩列表过长的问题
扩展性好：可以动态调整分段大小
平衡设计：在内存使用和性能之间取得良好平衡
无连锁更新：解决了压缩列表的连锁更新问题

缺点

实现复杂：相比单一数据结构更加复杂
内存碎片：可能存在一定的内存碎片
参数调优：需要合理设置分段大小等参数
维护开销：需要维护链表和压缩列表的双重结构

4. Listpack

实现原理

Listpack 是 Redis 7.0 引入的新数据结构，用于替代 ziplist。它采用更灵活的变长编码方式，彻底解决了连锁更新问题。

Listpack 结构

+----------+--------+-----+----------+-----+----------+
| lpbytes  | numele | ... | elementN | ... | lp-end   |
+----------+--------+-----+----------+-----+----------+
| 4 bytes  |4 bytes | ... | variable | ... | 1 byte   |

element 结构

+----------+----------+
| encoding | content  |
+----------+----------+
| 1-5字节  | 变长字段 |

每个字段的详细说明：

lpbytes：整个 listpack 占用的字节数（包括自身，占4字节）
numele：元素个数（占4字节）
elementN：实际存储的元素（变长字段）
lp-end：结束标记，固定值0xFF（占1字节）

每个 element 包含：

encoding：当前节点的编码方式（1-5字节）
content：实际存储的数据

Listpack 如何解决连锁更新问题

Listpack 通过移除 prevlen 字段来彻底解决连锁更新问题：

Ziplist:
[prevlen][encoding][content] [prevlen][encoding][content]...
   ↓        ↓        ↓        ↓        ↓        ↓
  [1B]     [1B]     [data1]  [1B]     [1B]     [data2]

Listpack:
[encoding][content][encoding][content]...
   ↓        ↓        ↓        ↓
  [1B]    [data1]   [1B]     [data2]

关键改进：

移除后向指针：不再存储前一个节点的长度
独立编码：每个元素独立编码，互不影响
简化结构：整体结构更加简洁

Listpack 替换 Ziplist 的具体阈值

Redis 7.0+ 中，Listpack 替代了 Ziplist，使用以下配置参数：

# Hash 使用 listpack 的阈值
hash-max-listpack-entries 512
hash-max-listpack-value 64

# List 使用 listpack 的阈值
list-max-listpack-size -2

# ZSet 使用 listpack 的阈值
zset-max-listpack-entries 128
zset-max-listpack-value 64

优点

无连锁更新：元素长度变化不会影响其他元素
内存效率高：更紧凑的编码方式
实现简单：相比 ziplist 更容易理解和维护
性能稳定：避免了 ziplist 的最坏情况性能问题
编码灵活：支持多种数据类型的高效编码

缺点

版本要求高：仅在 Redis 7.0+ 中可用
查找效率：仍需顺序查找，时间复杂度为 O(n)
适用范围有限：主要用于特定数据类型
生态成熟度：相比其他结构使用时间较短

适用场景

Redis 7.0+ 中 Hash：当元素数量不超过 512 个且所有值大小都不超过 64 字节时
Redis 7.0+ 中 List：作为 quicklist（快速列表）底层编码结构
Redis 7.0+ 中 ZSet：当元素数量不超过 128 个且每个值大小不超过 64 字节时

编码转换阈值总结

数据类型	编码方式	转换阈值
Hash	ziplist/listpack → hashtable	元素数>512 且所有值大小>64字节
List Redis 3.2 之前	ziplist → linkedlist	元素数>512 且所有值大小>64字节
List Redis 3.2 之后	quicklist	没有转换处理
ZSet	ziplist/listpack → skiplist + hash	元素数>128 且所有值大小>64字节

性能对比分析

数据结构	查找复杂度	插入复杂度	内存效率	连锁更新	适用场景
Ziplist	O(n)	O(n) 最坏	高	存在	小数据量
Skiplist	O(log n)	O(log n)	中等	无	有序数据
Quicklist	O(n)	O(1)	高	无	大List
Listpack	O(n)	O(1)	高	无	Redis 7.0+

总结

Redis 的这些核心数据结构各有特色，它们在不同的场景下发挥着重要作用：

Ziplist/Listpack 提供了极致的内存效率，但存在连锁更新问题（ziplist）或查找效率问题
Skiplist 提供了优秀的查找性能，适合有序数据场景
Quicklist 在内存效率和操作性能之间取得了良好平衡