为什么 Redis ZSet 用跳表而不用红黑树？

它的本质是在内存数据结构选型中Salvatore Sanfilippo (Redis 作者) 选择了实现简单、代码可读性高、范围查询友好的跳表 (SkipList)而非虽然理论复杂度相同但实现极其复杂、调试困难的红黑树。对于 Redis 这种单线程、高并发、需要频繁进行范围查询的场景跳表是“性价比”最高的选择。如果把数据结构比作交通工具红黑树精密的 F1 赛车。速度极快结构紧凑但引擎复杂维修调试/修改极难稍微动错一个零件就爆缸Bug。跳表多层高架桥。虽然占用的空间稍大指针多但结构直观修路修改代码容易且从上层往下看范围遍历非常顺畅。Redis 的选择Redis 不需要 F1 的极致极限速度两者差异在纳秒级被网络 IO 掩盖它更需要好维护、好扩展、范围查询快。所以选了高架桥。一、范围查询效率跳表的天然优势ZSet 的核心操作除了ZADD/ZREM还有大量的范围查询如ZRANGE,ZRANGEBYSCORE,ZREVRANGE。1. 红黑树的范围查询机制找到起始节点O(log⁡N)O(\log N)O(logN)。进行中序遍历In-order Traversal。问题中序遍历需要依赖父指针或栈来回溯。在二叉树中节点在内存中是不连续的指针跳跃导致Cache Miss率高。如果要获取前 1000 个元素需要多次指针跳转效率较低。2. 跳表的范围查询机制找到起始节点O(log⁡N)O(\log N)O(logN)。沿着最底层的双向链表向后遍历。优势链表节点虽然在物理内存不连续但逻辑上是线性的。更重要的是跳表的底层链表结构使得顺序访问非常直观和高效。获取前 1000 个元素只需沿着指针走 1000 步无需回溯无需栈。 核心洞察在 Redis 的业务场景中范围查询的频率极高。跳表的线性遍历特性比红黑树的树形遍历更符合 CPU 的预取机制尽管两者都有 Cache 问题但跳表代码更局部化。二、实现复杂度Redis 作者的务实哲学这是最关键的原因。Redis 作者 Salvatore 曾在博客中明确解释过。1. 红黑树的复杂性旋转操作插入和删除时需要进行左旋、右旋、变色。Case 众多有 4-5 种不同的失衡情况需要处理。代码量实现一个无 Bug 的红黑树需要数百行复杂的 C 代码。调试难度一旦出错很难排查是哪次旋转出了问题。2. 跳表的简单性核心逻辑随机生成层数。从最高层开始查找找到位置后插入。更新前后指针。代码量核心逻辑不到 100 行 C 代码。可读性极高。任何中级程序员都能看懂并修改。Redis 价值观Simple is Better。Redis 源码以优雅著称引入复杂的红黑树会破坏这种美感增加维护成本。3. 官方引用“From an algorithmic point of view, skip lists and balanced trees are equally efficient… However, skip lists are much easier to implement, debug, and get right.”— Salvatore Sanfilippo三、并发友好性未来的扩展潜力虽然 Redis 目前是单线程的但数据结构的设计需要考虑未来。1. 红黑树的锁粒度红黑树在插入/删除时需要调整树结构旋转这涉及多个节点的修改。在多线程环境下为了保证一致性可能需要整棵树加锁或者使用复杂的细粒度锁/RCU实现难度极大。2. 跳表的锁粒度跳表的插入/删除主要影响局部节点。更容易实现细粒度锁例如只锁定受影响的那一段链表。虽然 Redis 没用到但这种可扩展性是跳表的一个潜在优势。四、内存开销跳表的“浪费”可以接受1. 内存对比红黑树每个节点需要 3 个指针左、右、父 颜色标记。跳表每个节点需要多个前驱/后继指针取决于层数。平均层数约为log⁡2N\log_2 Nlog2​N的常数倍。通常跳表比红黑树多占用30%-50%的指针内存。2. 为什么 Redis 不在乎内存便宜现代服务器内存充足。对象头开销大Redis 的zskiplistNode还存储了sds字符串指针、double分数等。相比之下指针增加的开销占比并不大。配置可调可以通过调整ZSKIPLIST_MAXLEVEL和ZSKIPLIST_P来控制内存与性能的平衡。 总结原子化辨析维度红黑树 (Red-Black Tree)跳表 (SkipList)Redis 的选择理由时间复杂度O(log⁡N)O(\log N)O(logN)O(log⁡N)O(\log N)O(logN)平手范围查询中序遍历较慢链表遍历极快跳表胜(ZRange 常用)实现难度极难(旋转/变色)简单(随机层数)跳表胜(易维护)代码行数~200 行~50-80 行跳表胜(简洁)内存占用低略高可接受(内存便宜)并发扩展难 (锁竞争大)较易(局部锁)潜在优势Cache 友好差 (指针跳跃)中等(底层线性)跳表略优终极心法工程学的本质不是追求理论最优而是追求综合性价比。红黑树是学院派的完美跳表是工程派的务实。在 Redis 的世界里代码的可读性和范围查询的效率比节省那几个字节的内存更重要。别迷信复杂算法简单往往更强大。于理论中见均衡于工程中见取舍以简单为美解复杂之牛于系统设计中求实用之真。行动指令阅读源码查看 Redis 源码中的t_zset.c重点看zslInsert和zslDelete函数感受其简洁之美。对比实现尝试自己写一个红黑树和一个跳表体会两者代码量的巨大差异。思维升级记住当你面临技术选型时问自己我真的需要那 5% 的性能提升去换取 50% 的维护成本吗