Redis Zset 数据结构演进史

跳表 + 字典的完美组合

Redis 2.0

Zset 诞生 + ziplist

2010 年,Zset(有序集合)诞生。底层使用 ziplist 实现, member 和 score 成对存储,按 score 有序排列。

// ziplist 存储结构
|...|score1|member1|score2|member2|...|

• 按 score 升序排列
• member + score 连续存储
• 二分查找定位
紧凑内存 O(log n) 范围查询 小数据友好
Redis 2.4

阈值机制确立

确立 ziplist 的使用条件。当元素数量不超过 zset-max-ziplist-entries 且每个元素长度不超过 zset-max-ziplist-value 时使用 ziplist。

// ziplist 限制条件
元素数 ≤ 128
member 长度 ≤ 64 bytes

任意一条不满足 → 转换为 skiplist + dict
自动编码转换 128 元素阈值
Redis 2.8

ZRANGEBYSCORE 优化

优化 ZRANGEBYSCORE 等范围查询命令的性能。 ziplist 的二分查找机制确保 O(log n) 的范围定位。

// 范围查询复杂度
ziplist:
  定位: O(log n)
  返回连续元素: O(m) [m=返回数量]

skiplist:
  定位: O(log n)
  返回连续元素: O(log n + m)
范围查询优化 ZSET 命令完善
Redis 3.0 ⭐ 核心变革

skiplist + dict 组合

革命性突破!引入 skiplist(跳表)和 dict(字典)组合作为 Zset 的高性能底层实现。 skiplist 保证有序,dict 保证 O(1) 单点查询。

skiplist 跳表

• 节点按 score 有序
• 多层链表加速查找
• O(log n) 范围查询
• O(log n) 插入/删除

dict 字典

• member → score 映射
• O(1) ZSCORE 查询
• O(1) ZREM 删除
• 哈希表实现
// zset 结构 (Redis 3.0+)
dict *dict member→score
skiplist *zsl score→member
关键: 指向同一个 zskiplistNode
双索引结构 O(1) 单点查询 O(log n) 范围
Redis 4.0

参数调整与优化

调整 zset-max-ziplist-entries 从 128 → 128(保持), 优化跳表的随机层数生成算法,保持结构稳定。

// Redis 4.0 配置
zset-max-ziplist-entries 128
zset-max-ziplist-value 64 bytes
跳表优化 渐进式 rehash
Redis 6.2

阈值大幅提升

将 zset-max-ziplist-entries 从 128 → 128, 但优化了内部实现,提升 ZRANK/ZREVRANK 等排名查询的性能。

// ZRANK vs ZSCORE
ZRANK:
  跳表中定位 → O(log n)
  返回成员排名

ZSCORE:
  字典中查找 → O(1)!
  返回分数
O(log n) 排名查询 O(1) 分值查询
Redis 7.0+ ⭐ 底层升级

listpack 替换 ziplist

Redis 7.0 将 Zset 的 ziplist 替换为 listpack。 skiplist + dict 组合保持不变,只是 ziplist 部分升级为 listpack。

// Redis 7.0 Zset 编码
小数据: listpack
  • 无级联更新
  • 内存更紧凑

大数据: skiplist + dict
  • O(log n) 范围查询
  • O(1) 单点查询
listpack 编码 无级联更新 向后兼容

skiplist + dict 双索引结构

同一份数据,两种访问路径:字典 O(1) 查询 + 跳表 O(log n) 范围

skiplist 跳表结构
L3
L3
L2
L2
L2
L2
L2
L1
L1
L1
L1
L1
L1
L1
L0: Alice
L0: Bob
L0: Carol
L0: Dave
L0: Eve
score: 85 score: 90 score: 95 ★ score: 100 score: 110
查找 Carol (score: 95) 的路径:
L3: Head → L3 →
L2: → → L2 →
L1: → → → → L1 →
L0: Alice → Bob → Carol ✅
// skiplist 优势
✓ ZRANGE / ZREVRANGE → O(log n + m)
✓ ZRANK / ZREVRANK → O(log n)
✓ ZRANGEBYSCORE → O(log n + m)
✓ 按序遍历高效
// dict 优势
✓ ZSCORE → O(1) ⭐
✓ ZREM → O(1) ⭐
✓ SISMEMBER 同款逻辑
✓ member 存在性判断
// 为什么需要两个结构?
需求1: "按分数范围查成员" → skiplist 擅长
需求2: "查某成员分数" → dict 擅长

解法: 两个结构指向同一份 zskiplistNode, 增删改时同步更新,内存开销翻倍但性能双赢!

Zset 编码对比

内存效率

listpack/ziplist ★★★★★
skiplist+dict ★★★☆☆

单点查询 (ZSCORE)

listpack/ziplist O(n)
skiplist+dict O(1) ⭐

范围查询 (ZRANGE)

listpack/ziplist O(log n + m)
skiplist+dict O(log n + m)

适用场景

listpack <128 元素
skiplist+dict 大数据量

演进总结

Redis Zset 的演进是"鱼与熊掌兼得"的典范:

按序存储(范围查询)+ O(1) 查询(单点定位)= skiplist + dict

核心设计哲学:
空间换时间 — 两份索引,但都是指针
自动切换 — 小数据用 listpack 省内存
各司其职 — skiplist 管有序,dict 管去重+快速查询

这就是为什么 Zset 能同时支持"排行榜"(ZRANGE)和"实时分数"(ZSCORE)两种高频场景。