2.4 跳表：Sorted Set的排序引擎

2.4 跳表：Sorted Set的排序引擎

本节摘要：Sorted Set 底层是"跳表加 dict"双结构：跳表按分数维护有序性，提供对数级的插入、删除与范围查找；dict 记成员到分数的映射，让单点查分 O(1)。这套组合拳让排行榜类需求天然毫秒级。

从链表到跳表

有序链表查找只能从头走，O(n)。跳表的思路是给部分节点加"高速层"：上层是下层的抽稀快车道，查找时先在高层次快速推进，逼近目标再下降——像高速公路转省道再转县道。

在跳表中查找分数 55 的路径

新节点层数由抛硬币式随机决定（每层以四分之一概率继续升层），期望层数是对数级，因此查找、插入、删除平均都是 O(logN)。没有 rebalance 这种大动作，实现比平衡树简单一个量级——这是 Redis 放弃红黑树选跳表时列出的官方理由之一。

手推一次跳表查询

光看图不过瘾，拿一组真实分数推一遍。设榜内分数与层数如下（层数由随机决定，建表时已定）：

层数3：            55 ──────────────────── 90
层数2：      30 ── 55 ────── 70 ────────── 90
层数1： 10 ─ 30 ─ 55 ─ 70 ─ 82 ─ 90 ─ 96

查询目标：82
第3层：从头节点出发，右望是55，55<82，跳过去；再右望是90，90>82，停，下降
第2层：右望是70，70<82，跳过去；再右望是90，90>82，停，下降
第1层：右望是82，命中，共走了4步
​

逐层复盘：高层是"抽稀快车道"，负责大步逼近；每次"下一步会越过目标"就下降一层，把精度换回来。走过的节点数是"层数加每层跳过的节点数"，两者都是对数量级，这就是 O(logN) 的直观来源。删除与插入走同一条下降路径，找到位置后只在各层局部改指针——没有全局再平衡，这是它比平衡树实现简洁的根本原因。

变式思考：如果分数 82 不存在，同样的路径会停在"最后一个小于 82 的节点"上——ZRANGEBYSCORE 的范围定位就是这么实现的，查区间的左端点一次、右端点一次，中间顺序读链表即可。跳表的查询、排名、范围三个能力，用的其实是同一条下降路径。

编码转换亲历

Sorted Set 小数据时同样不用跳表。阈值与 Hash 一致，可亲手验证：

> ZADD mini 10 a 20 b 30 c
> OBJECT ENCODING mini
"listpack"        # 少量成员：紧凑排列，省掉跳表与dict的头部开销
# 继续加入成员超过128个（默认阈值）……
> OBJECT ENCODING mini
"skiplist"        # 升级为跳表加dict双结构
> ZSCORE mini b
"20"
​

解读：listpack 阶段一切命令照常工作，编码切换对上层完全透明——这是 Redis 类型系统的一贯承诺。变式：把 zset-max-listpack-entries 类阈值调小（比如 8），小实验更容易触发转换，教学环境常用。

双结构协作

跳表按分数定位快，但"查某成员的分数"要顺着走；于是 Sorted Set 同时挂一张 dict 记成员到分数：

> ZADD rank:2026 8700 li 9200 wang 7600 zhao
> ZSCORE rank:2026 wang        # 走 dict，O(1)
"9200"
> ZRANK rank:2026 wang         # 排名，跳表跨度累计，O(logN)
(integer) 2
> ZINCRBY rank:2026 300 li     # 改分 = dict 改映射加跳表挪位置
> ZREVRANGE rank:2026 0 2 WITHSCORES   # 前三名，范围查找 O(logN 加 k)
​

三个排行榜实战细节

同分排序。分数相同时按成员字典序排。想让同分者按时间先后来，常用技巧是分数拼时间戳：真实分数乘一大常数，加上"最大时间戳减当前时间"作小数位，新纪录分数略高自然靠前。

分页。ZRANGE 的 offset 参数在大偏移时依然要跳过前面元素，深翻页用 ZRANGEBYSCORE 带 limit 从上次分数续查，避免 OFFSET 10 万这种写法。两种写法的差距有量级之分：

# 深分页的错误示范：先定位再跳过十万条
> ZREVRANGE rank 100000 100009
# 正确姿势：带上次查询的最后一条分数
> ZRANGEBYSCORE rank (last_score -inf LIMIT 0 10
# 从上次分数处直接定位，步数回到对数级
​

解读：错误写法的复杂度是 O(logN 加 offset 加 count)，offset 十万时定位的十来步完全被"跳过十万步"淹没；正确写法把游标（上一页的最后分数）当作定位锚点，复杂度回到 O(logN 加 count)。凡是"翻页"需求，优先想"上一页的边界值能不能当锚"，这是跳表场景下比 OFFSET 更亲结构的分页方式。

周期清榜。按天分键（rank 加日期后缀）比一个键反复删除干净得多，过期交给第 5 章的 TTL 机制自动回收。

顺带说清 ZRANK 与 ZREVRANK 的关系：前者按升序数名次，后者按降序。排行榜业务几乎只用 ZREVRANK，它内部走的是跳表的反向遍历加跨度累计——同一棵跳表，正着走是"从低到第几名"，反着走是"从高到第几名"，两个视角共用一份结构，这也是双结构设计之外的另一处"一份数据多副面孔"。

⚠️ 常见坑：单键成员数上百万后，ZADD 依旧是 O(logN) 不慌，但 ZRANGE 全量导出、与相关的 ZUNIONSTORE 大键运算会同时伤 CPU、内存和网络。大榜拆分（按地区、按类目）是第一选择。

大榜还要会算内存账：skiplist 编码下每个成员除自身数据外，要付跳表多层节点的指针与跨度字段、dict 条目的开销，粗算每成员数百字节起。百万成员的单键轻松吃掉数百 MB，主从全量同步时这个键的传输时长也以分钟计。排错时的验证顺序：先 DBSIZE 与 MEMORY USAGE 定位嫌疑键，再 OBJECT ENCODING 确认它已升到 skiplist 编码，最后看该键的写入频率判断能不能按业务维度拆。榜单类需求在评审阶段就做"预计成员数乘单成员开销"的乘法，比上线后拆键从容得多。

本节要点回顾

• 跳表 = 多层抽稀的有序链表，期望 O(logN) 且无需再平衡
• 层数随机生成，这是它实现简洁的根本原因
• 跳表加 dict 双结构：排序走跳表，点查走 dict
• 排行榜的坑多在边界：同分序、深分页、超大键
• 范围类需求优先 Sorted Set，这是它区别于 Hash 与 Set 的存在意义