为什么 Zset 用跳表而不用红黑树
这个问题 Redis 作者 antirez 在邮件列表里亲自回答过，核心不是”跳表性能碾压红黑树”，两者的平均时间复杂度都是 O(log n)，量级上是一样的。真正的原因更偏工程权衡,可以从这几个角度看。
范围查询是跳表的天然优势
Zset 最常用的操作之一是 ZRANGEBYSCORE、ZRANGE 这类按 score 区间取一批元素的操作。跳表本质上是一个带多级索引的有序链表,找到区间起点后,顺着最底层（level 0)的链表指针一路遍历下去就行了,复杂度是 O(log n + m)（m 是区间内元素个数),代码逻辑非常直观。
红黑树虽然中序遍历也能得到有序序列,但树结构做”从某个节点开始连续取 m 个”这种操作并不天然,要么维护额外的父指针往上回溯再往下找,要么用栈模拟中序遍历,实现复杂度和代码可读性都不如跳表。
实现复杂度和正确性
红黑树的插入、删除为了维持”红黑性质”（比如任意路径黑节点数相同）,需要处理多种旋转（左旋/右旋）和变色的场景,情况分支多,容易写错,调试和维护成本高。
跳表的插入只需要:随机生成一个层数,然后在每一层找到插入位置修改指针,不涉及全局的重新平衡,逻辑简单很多,出 bug 的概率更低。对于 Redis 这种要保证稳定性的基础设施来说,”简单、好维护、不容易出错”本身就是很重要的工程考量,这也是 antirez 原话里提到的理由之一:跳表实现起来足够简单,而且改起来也容易,对可读性友好。
内存与性能是同一量级,跳表不吃亏
跳表每个节点要存多层指针,平均下来每个节点的期望层数是 O(log n)（Redis 用固定概率 1/4 决定是否升层),整体内存开销和红黑树的父子指针+颜色标记这些额外开销是同一数量级,并不存在跳表明显更费内存的问题。而且跳表的常数因子较小(没有旋转操作的开销),实际工程表现不比红黑树差。
顺带一提:Zset 不是单靠跳表
容易被忽略的一点是,Zset 在数据量较大时,内部其实是跳表（skiplist）+ 哈希表（dict）两种结构组合使用：dict 负责 member → score 的映射,保证 ZSCORE（按成员查分数）是 O(1);skiplist 负责按 score 排序,支撑 ZRANK、ZRANGE 这类有序区间操作。两者共享同一份元素,只是索引方式不同,分别解决”点查询快”和”范围查询快”这两个不同的需求,单独用哪一种都覆盖不了 Zset 的全部操作场景。
而当 Zset 元素少（默认 128 个以内)且每个元素长度也小（默认 64 字节以内)时,Redis 会用 ziplist/listpack 这种更省内存的压缩列表编码,此时没有跳表和哈希表,是线性遍历,因为数据量小,O(n) 遍历比维护复杂结构更划算,超过阈值才转换成 skiplist+dict 的组合。
一句话总结
跳表和红黑树在时间复杂度上打平,但跳表在范围查询实现的直观性和代码实现/维护的简单性上明显占优,这是 Redis 团队权衡后的选择,不是纯粹为了追求极致性能。
如果你感兴趣,还可以往下聊跳表的层数是怎么随机生成的（为什么概率取 1/4 而不是 1/2)、Zset 编码转换的具体阈值配置,或者对比一下 Redis 用跳表和 LevelDB/RocksDB 用 LSM-Tree 这种设计取舍的差异。
概率不是1/2么？为什么是1/4？
概率为什么是 1/4 而不是 1/2
先纠正一下前提：跳表理论上 p 取多少都可以,William Pugh 在提出跳表的论文里确实举了 p=1/2 的例子作为最直观的说明,但他同时分析论证了 p=1/4（甚至 1/e≈0.37)在综合性能上其实更优。Redis 在 t_zset.c 里定义的 ZSKIPLIST_P 就是 0.25,不是 1/2,这是有意选的,不是笔误。
关键权衡:空间 vs 时间
跳表每个节点会不会往上一层升,是按概率 p 独立抛硬币决定的（能到第 1 层再抛一次决定能不能到第 2 层,以此类推)。这带来两个直接后果:
平均每个节点占用的指针数（也就是内存开销）,期望值是 1/(1-p)：
- p = 1/2 时,
1/(1-0.5) = 2,平均每个节点要维护 2 个指针; - p = 1/4 时,
1/(1-0.25) ≈ 1.33,平均每个节点只要维护约 1.33 个指针。
也就是说,同样规模的数据,p=1/4 比 p=1/2 大概能省下 1/3 的指针内存开销。
再看查找效率,Pugh 论文给出的期望查找比较次数近似是 log_{1/p}(n) / p：
- p = 1/2 时约等于
2 · log₂n; - p = 1/4 时约等于
2 · log₂n（log₄n · 4 = (log₂n/2)·4 = 2·log₂n)。
两者算出来的系数几乎一样!也就是说 p 从 1/2 降到 1/4,查找性能几乎没有损失,但内存开销明显下降。这正是 Pugh 论文的结论:p=1/4（或者更极端的 1/e）在时间和空间的综合表现上比 p=1/2 更划算,p=1/2 只是”更容易讲清楚原理”的教学版本,不是工程上的最优选择。
为什么 Redis 在意这个权衡
Redis 是内存数据库,内存本来就是最贵、最紧俏的资源,能省则省。既然 p=1/4 能在查找速度几乎不受影响的前提下省下可观的指针内存,自然是更划算的选择。这和前面聊到的”小对象用压缩编码省内存”是同一种设计哲学:性能过得去的前提下,优先省内存。
对应的,Redis 里 ZSKIPLIST_MAXLEVEL 定为 32,是因为 p=1/4 时,层数增长得比 p=1/2 慢（越往上概率衰减越快: 1/4, 1/16, 1/64…),32 层理论上足以支撑远超实际使用规模的数据量（官方注释里给出的估计是能支撑到 2^64 级别的元素数,实际不可能用到这么高)。
一句话总结
p 越小,节点晋升到高层的概率越低,平均指针数越少、越省内存,但每层能跳过的节点变少,搜索时需要更多层间比较；p=1/2 是最直观但不是最优的选择,p=1/4 是 Pugh 论文和 Redis 实测都验证过的”查找性能几乎不掉、内存开销明显更省”的甜蜜点,所以 Redis 选了 1/4。