Redis ZSet 为什么使用跳表？和红黑树有什么区别？

简化版

Redis ZSet 需要同时支持按成员查分数和按分数范围查询。大规模 ZSet 常用 dict + skiplist：dict 提供 member 到 score 的快速查找，skiplist 提供按 score 排序、范围查询和排名操作。跳表实现简单、范围遍历方便，性能期望接近平衡树。

详细版

ZSet 的核心能力包括：

ZSCORE：按 member 查 score。
ZADD：插入或更新分数。
ZRANGE / ZRANGEBYSCORE：按排序范围取数据。
排行榜：取 Top N、查 rank。

哈希表适合按 member 查找，但不适合有序范围查询；跳表适合按 score 有序访问，插入、删除、查找期望复杂度 O(logN)。Redis 选择跳表而不是红黑树，主要因为跳表实现相对简单，范围遍历直接，维护排名跨度也方便。

完整版教学

一、ZSet 的需求不是单一查找

ZSet 不是普通 Set，它的每个 member 都带一个 score，并按 score 排序。业务上最典型的场景是排行榜：写入用户分数、查询用户排名、查询 Top 100。

如果只用哈希表，ZSCORE user1 很快，但无法高效按 score 排序；如果只用有序结构，按 member 精确查找又不够快。因此 Redis 把两类结构组合起来。

记忆钩子：ZSet 是“双索引结构”，dict 管 member，skiplist 管 score。

二、dict 在 ZSet 里负责什么

dict 负责从 member 快速找到 score。比如 ZSCORE rank user:7，Redis 不需要在有序链路里一层层找，可以通过哈希表快速定位。

dict:
user:1 -> 98
user:2 -> 87
user:7 -> 91

这让更新分数时也更方便：先知道旧分数，再在跳表里删除旧节点并插入新节点。没有 dict 的话，按 member 找旧节点会很麻烦。

三、skiplist 怎么支持有序范围

跳表由多层有序链表组成。最底层包含全部节点，上层是抽样出来的“快速通道”。查找时从高层开始，能跳过大量节点。

Level 3: 10 ---------------- 80
Level 2: 10 ------ 50 ------ 80
Level 1: 10 -- 30 -- 50 -- 70 -- 80

查找 score=70 时，不必从 10 一个个走到底。插入和删除只需要调整若干层指针，期望复杂度是 O(logN)。

四、带数字理解跳表复杂度

假设 ZSet 有 100 万个节点。如果顺序链表查找，最差可能走 100 万步；如果跳表层级分布合理，查找路径大约是几十步数量级。

N = 1,000,000
顺序扫描：最多约 1,000,000 次移动
跳表查找：期望约 log2(N) ≈ 20 层级步量级

实际实现里还有跨度、score 相同按 member 排序等细节，但核心思想就是用多层索引换取快速定位。

五、为什么不用红黑树

红黑树也能提供 O(logN) 查找、插入、删除，并支持有序遍历。Redis 选择跳表，常见解释是跳表实现更简单，范围查询遍历更自然，维护 rank 所需的 span 也比较直观。

对比项	跳表	红黑树
实现复杂度	相对简单	旋转和颜色维护复杂
范围遍历	链表向后走很自然	中序遍历也可行
性能	期望 O(logN)	严格 O(logN)
排名维护	span 设计直观	需要维护子树大小

面试不要说红黑树“不行”，更准确是二者都能做，Redis 选择了更符合实现和范围遍历需求的跳表。

六、ZSet 的 listpack 编码别漏掉

不是所有 ZSet 都用 skiplist。元素少、member 较短时，Redis 可以用 listpack 紧凑存储，节省内存。只有超过阈值后才转成 skiplist 等结构。

这体现了 Redis 的典型策略：小数据优先省内存，大数据优先保复杂度。比如一个 ZSet 只有 5 个元素，用跳表和 dict 的指针开销可能比数据本身还大。

小 ZSet -> listpack
大 ZSet -> dict + skiplist

七、排行榜场景怎么落地

排行榜常用 ZADD 写分数，ZREVRANGE key 0 99 WITHSCORES 查 Top 100，ZREVRANK 查用户名次。需要注意 key 的规模和更新频率。

如果一个全球榜有几千万 member，单个 ZSet 会非常大，内存、备份、复制和删除都可能成为问题。工程上可以按业务维度拆榜，比如日榜、周榜、分区榜，或者将冷数据落库。

场景	建议
实时 Top N	ZSet 很适合
超大历史榜	分桶或落库
多条件复杂排序	可能需要数据库或搜索系统

八、常见误区与追问

误区：ZSet 底层只有跳表。 大规模 ZSet 常用 dict + skiplist，小 ZSet 可能用 listpack。
误区：跳表一定比红黑树快。 二者复杂度接近，Redis 更看重实现简单和范围遍历方便。
误区：score 相同就无法排序。 Redis 会在 score 相同的情况下按 member 做确定性排序。
追问：为什么需要 dict？ 为了按 member 快速查 score，并辅助更新旧分数。
追问：跳表查询复杂度为什么是期望 O(logN)？ 层级通过随机策略形成近似指数级索引，平均能跳过大量节点。
追问：排行榜如何避免大 Key？ 按时间、地域、业务维度拆分，限制榜单长度，冷数据归档。

九、加强记忆

记住“member 找 score 靠 dict，score 排序靠 skiplist”。ZSet 的强大来自双结构协作，而不是单个神奇结构。

回答红黑树对比时要稳：不是红黑树不能用，而是跳表更简单、范围遍历更顺手，适合 Redis 的实现选择。

简化版

详细版