在 Redis 的面试中，有一个问题几乎成了必考题：Redis 的 ZSet（有序集合）底层为什么用跳表（skiplist）而不是红黑树？ 很多人第一反应是“因为跳表简单”，但面试官想听的显然不止这一句。这个问题背后牵扯到数据结构设计、工程取舍、范围查询效率以及 Redis 作者 antirez 的个人偏好等多个层面。下面我们就从多个角度把这个问题彻底讲清楚。
先明确 ZSet 的底层结构
在 Redis 中，ZSet 有两种编码方式：
- ziplist / listpack：当元素数量较少且成员长度较短时使用，本质是一个紧凑的连续内存结构。
- skiplist + dict：当数据量超过阈值（
zset-max-ziplist-entries默认 128，zset-max-ziplist-value默认 64）时，ZSet 会转换为跳表加字典的组合结构。
注意，ZSet 并不是单独使用跳表，而是 跳表 + 哈希表 一起使用：
- dict：维护 member 到 score 的映射，使得
ZSCORE查询 O(1)。 - skiplist：按 score 排序，支持范围查询和排名操作。
所以问题准确地说应该是：为什么 Redis 选择跳表而不是红黑树来作为 ZSet 的有序索引结构？
原因一：跳表实现简单，代码可维护性高
这是最常被提到的原因，但需要说清楚“简单”体现在哪里。
红黑树是一种自平衡二叉搜索树，插入和删除时需要处理多种旋转情况（左旋、右旋、变色），代码逻辑复杂，边界条件多。以 Linux 内核的 rbtree 为例，光是插入修复函数就有几十行，涉及多种 case 判断。
而跳表的实现要直观得多：它本质上是在有序链表上建立多级索引，插入时通过随机函数决定层数，删除时断开对应指针即可。Redis 的跳表实现 t_zset.c 中，核心插入和删除逻辑加起来不过百来行，且没有复杂的平衡操作。
对于 Redis 这种追求代码简洁、易于维护和调试的项目来说，跳表在工程上的优势非常明显。antirez 本人也曾在多个场合表示，他更喜欢跳表是因为它更容易理解和实现。
原因二：范围查询是 ZSet 的核心场景
ZSet 最常用的命令是什么？ZRANGE、ZRANGEBYSCORE、ZREVRANGE、ZRANGEBYLEX。这些全都是范围查询。
跳表在范围查询上有天然优势：
- 跳表的底层是一个有序链表，找到起始节点后，只需要沿着底层链表向后遍历即可，缓存局部性非常好。
- 红黑树虽然也能做范围查询（中序遍历），但需要在树节点之间不断跳转，指针跳跃导致缓存不友好，实际性能往往不如跳表。
更重要的是，跳表的范围查询实现非常自然：定位到起点后顺序遍历，代码简单且可预测。红黑树做范围查询需要依赖中序后继指针或栈式遍历，实现和调优都更麻烦。
原因三：跳表更容易支持排名和区间操作
ZSet 有一个非常重要的能力：按排名查询，比如 ZRANK、ZREVRANK、ZRANGE start stop。
Redis 的跳表在每个节点中维护了一个 span 字段，表示当前节点到下一个节点之间跨越了多少个底层节点。通过累加 span，可以在 O(log N) 时间内计算出某个元素的排名，也可以根据排名快速定位元素。
这种“带跨度”的设计在跳表中非常自然，只需要在插入和删除时更新沿途节点的 span 即可。而在红黑树中，要实现类似功能通常需要额外维护子树大小（size），虽然也能做到，但实现复杂度和出错概率都更高。
原因四：并发和锁的考量（虽然 Redis 是单线程）
Redis 的命令执行是单线程的，所以严格来说跳表和红黑树都不需要考虑并发加锁问题。但跳表在并发场景下的优势仍然值得一提，因为它反映了跳表结构本身的灵活性。
在并发环境中，跳表的插入和删除只需要修改局部指针，影响范围小，更容易实现无锁或细粒度锁。红黑树的旋转操作可能影响较大范围的节点，并发控制更复杂。虽然这不是 Redis 选择跳表的直接原因，但说明跳表在工程设计上确实更“友好”。
原因五：性能并不输红黑树
很多人误以为红黑树比跳表快，其实在平均情况下两者都是 O(log N) 的插入、删除和查找复杂度。
- 红黑树：查找稳定 O(log N)，但常数因子受树高和旋转影响。
- 跳表：期望 O(log N)，通过随机层数实现概率平衡，实际性能与红黑树相当，甚至在某些场景下因为缓存友好而更快。
Redis 官方做过相关测试，跳表在 ZSet 的典型操作上表现优异，完全满足性能要求。既然性能相当，那选择实现更简单的跳表就是理所当然的。
原因六：内存占用可以接受
有人会说跳表因为多级索引会浪费内存。确实，跳表每个节点平均需要 1/(1-p) 个指针（Redis 中 p=0.25，平均约 1.33 个指针），比红黑树每个节点多存一个指针略多。但 Redis 在跳表节点中还存储了 span 和 backward 指针，总体内存开销在可接受范围内。
而且 Redis 在数据量小时会使用 ziplist/listpack，只有数据量大时才转跳表，这时内存开销相对于整体数据量来说并不突出。用少量内存换取实现简单和范围查询高效，这笔账是划算的。
总结：一张表看清核心差异
| 维度 | 跳表 | 红黑树 |
|---|---|---|
| 实现复杂度 | 低，易维护 | 高，旋转逻辑复杂 |
| 范围查询 | 优秀，缓存友好 | 一般，指针跳跃多 |
| 排名操作 | 天然支持（span） | 需额外维护 size |
| 平均复杂度 | O(log N) | O(log N) |
| 内存开销 | 略高 | 略低 |
| 并发友好度 | 较好 | 一般 |
面试怎么答
如果面试官问“Redis 为什么用跳表不用红黑树”，你可以这样组织回答：
- 先说明 ZSet 底层是跳表 + 哈希表，不是单独用跳表。
- 核心原因有三点：实现简单、范围查询高效、排名操作天然支持。
- 补充性能对比：两者平均复杂度相同，跳表在缓存局部性上更优。
- 点出工程取舍：Redis 追求代码简洁可维护，跳表更符合这一哲学。
这样回答既有深度又有层次，基本能覆盖面试官的考察点。记住，面试考的不是“跳表比红黑树好”，而是你能否从工程取舍的角度理解技术选型。
未经允许不得转载：任鹏个人博客 » Redis 为什么用跳表而不用红黑树实现有序集合
