上一篇【第15篇】 跳跃表——Redis有序集合的快速通道下一篇【第17篇】整数集合——Redis集合的省内存利器上一篇文章我们详细拆解了跳跃表的实现原理。这篇文章我们要回答一个被问了无数遍的灵魂问题Redis的有序集合ZSet为什么用跳跃表而不用红黑树每次有人在社区提这个问题总有大神跳出来引用Antirez的一句话就完事了。但说实话光看结论是不够的真正理解背后的工程权衡才能在面对自己项目的技术选型时做出正确判断。今天我们就把跳跃表和平衡树家族放到擂台上好好打一场。一、平衡树家族巡礼AVL树、红黑树和B树在对比之前我们先快速复习一下平衡树家族的几位大佬。AVL树严格平衡的处女座AVL树是1962年由Adelson-Velsky和Landis发明的名字就这么来的是最早的自平衡二叉搜索树。它的核心规则很简单粗暴任何节点的左右子树高度差平衡因子的绝对值不超过1。AVL树示例每个节点标注了平衡因子 30(0) / \ 20(0) 40(1) / / \ 10(0) 35(0) 50(0)AVL树在查找上是最优的树的高度始终控制在 O(logN)。但问题在于插入和删除时为了维持严格的平衡可能需要进行多次旋转最坏情况下需要 O(logN) 次旋转。红黑树妥协的艺术红黑树Red-Black Tree是1972年Rudolf Bayer发明的后来被Leo Guibas和Robert Sedgewick重新命名。它放松了AVL树的严格平衡要求换来了更高效的插入删除性能。红黑树的五条规则每个节点要么红色要么黑色根节点是黑色每个叶节点NIL节点是黑色红色节点的两个子节点都是黑色不能有连续红色节点从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点红黑树示例 30(B) / \ 20(R) 40(B) / / \ 10(B) 35(R) 50(R)红黑树通过颜色标记来维持一种近似平衡——它的树高最多是 O(2logN)比AVL树稍高但插入删除时最多只需要3次旋转远优于AVL树的 O(logN) 次。B树/B树磁盘时代的王者B树是1970年代Rudolf Bayer发明的对又是他专为磁盘存储设计。B树是其变体所有数据都存储在叶子节点叶子节点通过链表串联。B树示例阶数3 [30|60] / | \ [10,20] [40,50] [70,80,90] | | | 数据页 数据页 数据页B树的核心优势在于减少磁盘I/O次数——每个节点可以包含多个key一棵3层B树可以存储上百万条数据而磁盘IO只需要3次。二、跳跃表 vs 红黑树终极对决好了各位选手已经登场现在开始正面对决。核心指标对比表对比维度跳跃表红黑树胜出者查找复杂度O(logN) 期望O(logN) 最坏红黑树最坏保证更好插入复杂度O(logN) 期望O(logN)平手删除复杂度O(logN) 期望O(logN)平手范围查询O(logN M) 天然支持O(logN M) 但需中序遍历跳跃表实现复杂度约200行C代码约500-1000行C代码跳跃表内存开销每节点多层指针每节点2指针颜色位父指针跳跃表略高层数多时并发友好性天然适合CAS无锁操作需要精心设计才能支持跳跃表Cache局部性较差跳跃访问较好局部遍历红黑树插入顺序保持天然有序链表需要额外处理跳跃表代码可维护性直观易懂旋转逻辑复杂跳跃表踩坑提示很多人觉得查找最坏O(logN)很重要但实际上Redis是内存数据库N通常不大百万级以内跳跃表的期望O(logN)和红黑树的最坏O(logN)在实际中差距微乎其微。真正拉开差距的是范围查询和实现复杂度。范围查询跳跃表的杀手锏Redis有序集合最常用的操作之一就是范围查询# 按分数范围查询ZRANGEBYSCORE myzset6090# 按排名范围查询ZRANGE myzset010# 按字典序范围查询ZRANGEBYLEX myzset[a(z跳跃表做范围查询的过程查找score60的起始位置 Level 3: Head --------- 70 --------- NULL Level 2: Head -- 30 -- 70 -- 90 -- NULL Level 1: Head -- 10 -- 30 -- 50 -- 70 -- 90 -- NULL Level 0: Head -- 5 -- 10 -- 25 -- 30 -- 50 -- 60 -- 70 -- 90 -- NULL ^找到60! 然后沿着底层链表向右遍历: 60 -- 70 -- 90停止只需要两步先O(logN)定位起始位置再O(M)沿链表顺序遍历。底层链表天然有序不需要任何额外操作。红黑树做范围查询的过程红黑树要实现同样的功能需要先找到起始节点O(logN)然后做中序遍历。中序遍历在二叉树上并不直观——需要用栈或者Morris遍历来实现而且实际代码中还要处理迭代器状态实现起来比跳跃表复杂得多。三、Antirez怎么说Redis的作者Salvatore Sanfilippo大家都叫他Antirez在2010年的博客中明确解释过为什么选择跳跃表There are a few reasons:Skiplists are simpler to implement, debug, and reason about.Skiplists are memory-efficient in practice.They provide good range query performance.They are easy to implement in a way that is cache-friendly for range queries.翻译过来就是四点实现简单跳跃表的代码量大约是红黑树的1/3到1/2更容易写对、更容易维护内存效率好虽然在理论上每节点有多个指针但通过概率控制层数Redis中最大32层实际平均1-2层内存开销可控范围查询优秀底层有序链表天然支持可调整性可以通过修改概率参数来权衡空间和时间Antirez还特别提到了一个很务实的原因跳跃表的实现代码更加可读当一个开源项目的核心数据结构更简单、更易理解时社区贡献者更容易参与维护和优化。踩坑提示Antirez的选择是基于Redis特定场景的权衡并不意味着跳跃表在所有场景下都优于红黑树。比如Java的TreeMap用红黑树、ConcurrentSkipListMap用跳表各有各的道理。四、Java世界的实践TreeMap vs ConcurrentSkipListMapJava标准库同时提供了两种有序Map的实现这个对比非常能说明问题// TreeMap - 基于红黑树TreeMapString,IntegertreeMapnewTreeMap();treeMap.put(c,3);treeMap.put(a,1);treeMap.put(b,2);// 范围查询MapString,IntegersubMaptreeMap.subMap(a,c);// [a, c)// ConcurrentSkipListMap - 基于跳跃表ConcurrentSkipListMapString,IntegerskipMapnewConcurrentSkipListMap();skipMap.put(c,3);skipMap.put(a,1);skipMap.put(b,2);// 线程安全的范围查询MapString,IntegersubMapskipMap.subMap(a,c);// [a, c)特性TreeMap红黑树ConcurrentSkipListMap跳表线程安全否是并发策略需要外部同步无锁CAS单线程性能略快略慢范围查询支持支持适用场景单线程有序Map高并发有序Map注意这个规律需要高并发时跳表是更好的选择。这是因为跳表的结构天然适合CASCompare-And-Swap无锁操作——插入时只需要修改几个指针不涉及全局的结构调整。而红黑树的旋转操作会同时影响多个节点要实现无锁并发非常困难。这也是LevelDB、RocksDB等存储引擎选择跳表作为内存索引的原因。五、B树/B树与跳跃表不同场景的不同选择我们再来看B树家族。B树是数据库索引的标准选择但它和跳跃表适用的场景完全不同┌─────────────────────────────────────────────────────────┐ │ 数据存储层次 │ ├─────────────┬───────────────────────────────────────────┤ │ │ │ │ CPU缓存 │ 纳秒级访问几十KB │ │ │ → 跳跃表的指针跳跃访问问题不大 │ │ │ → 红黑树的局部性更好 │ │ │ │ ├─────────────┼───────────────────────────────────────────┤ │ │ │ │ 内存 │ 纳秒到微秒级GB级别 │ │ │ → 跳跃表Redis ZSet的选择 │ │ │ → 红黑树Java TreeMap的选择 │ │ │ │ ├─────────────┼───────────────────────────────────────────┤ │ │ │ │ 磁盘 │ 毫秒级TB级别 │ │ │ → B树MySQL InnoDB的选择 │ │ │ → 跳跃表完全不适用 │ │ │ │ └─────────────┴───────────────────────────────────────────┘B树的设计核心是减少磁盘I/O每个节点包含多个key充分利用磁盘页的大小通常16KB3层B树可以索引千万级数据磁盘IO只需3次叶子节点链表支持范围扫描而跳跃表在磁盘场景下完全不适用——每个节点的指针指向内存中随机位置一次查询可能需要数十次磁盘IO。反过来B树在纯内存场景下也显得过重——维护多key节点和节点分裂合并的复杂度在内存访问纳秒级完成的情况下没有太大意义。六、Redis跳跃表的工程优化Redis的跳跃表实现并不是教科书上的原始版本而是做了很多工程优化6.1 span字段快速计算排名Redis的跳跃表节点除了标准的forward指针外还增加了一个span字段typedefstructzskiplistNode{sds ele;// 成员对象doublescore;// 分值structzskiplistNode*backward;// 后退指针structzskiplistLevel{structzskiplistNode*forward;// 前进指针unsignedlongspan;// 跨度本层到下一个节点的距离}level[];}zskiplistNode;span记录了当前层中从当前节点到下一个节点之间底层链表跨越了多少个节点。这个设计让ZRANK命令的时间复杂度从 O(N) 降到了 O(logN)——查找过程中把路径上的span累加即可。span示例 Level 1: Head ---(span2)--- 30 ---(span3)--- 70 ---(span1)--- NULL Level 0: Head -- 10 -- 20 -- 30 -- 40 -- 50 -- 70 -- 90 -- NULL 查找 rank(50) 的路径 1. Head(0) → 30累计span 2 2. 30(2) → 70span3但7050回退 3. 30(2) → 40累计span 21 3 4. 40(3) → 50累计span 31 4 5. 50的rank 4 ✓6.2 backward指针逆向遍历Redis在跳跃表的最底层维护了一个双向链表通过backward指针支持ZREVRANGE等逆序操作。Level 0: Head ⇄ 10 ⇄ 30 ⇄ 50 ⇄ 70 ⇄ 90 ↑forward ↑backward6.3 同分元素按字典序排列Redis有序集合允许相同分数的多个元素存在此时按元素的字典序字典序比较SDS字符串排列127.0.0.1:6379ZADD myzset100apple100banana100cherry(integer)3127.0.0.1:6379ZRANGE myzset0-11)apple2)banana3)cherry跳跃表在比较节点时先比较scorescore相同时比较ele的字典序确保顺序一致性。6.4 概率控制层数Redis使用概率p 1/4来决定新节点的层数标准教材版本通常用p 1/2层数概率分布p1/4 Level 0: 100% 所有节点都在 Level 1: 25% 1/4的节点 Level 2: 6.25%1/16的节点 Level 3: 1.56%1/64的节点 ...选择p 1/4而不是p 1/2是一个空间换时间的权衡——更低的概率意味着更少的指针开销虽然层数更多但平均性能差异很小。七、什么场景下需要考虑替换skiplistRedis目前没有提供替换ZSet底层实现的配置项但了解跳跃表的局限性有助于做出架构决策极端内存节省场景如果ZSet中存储了海量元素亿级别且内存是瓶颈可以考虑使用Redis的专有数据结构优化调整zset-max-ziplist-value和zset-max-ziplist-entries让小ZSet使用ziplist考虑其他存储方案将大ZSet分片到多个key中或者使用RedisModule扩展自定义数据结构使用Stream代替部分有序集合场景Redis 5.0 的Stream在消息队列场景下可以替代部分ZSet的用法需要更强一致性保证的场景跳跃表是单线程操作的Redis本身就是单线程如果需要在多线程环境中使用有序集合跳表的CAS友好性就变成了真正的优势。踩坑提示Redis 7.0之后ZSet的底层在元素较少时会使用listpack而不是 ziplist但大量元素的核心实现仍然是skiplist。不需要为此做任何配置调整Redis会自动切换。八、总结让我们用一个终极对比表来收尾┌──────────────────────────────────────────────────────────────────┐ │ 数据结构选型决策树 │ │ │ │ 需要有序集合吗 │ │ ├─ 否 → 用Hash或Set │ │ └─ 是 ↓ │ │ 数据在磁盘还是内存 │ │ ├─ 磁盘 → B树MySQL、PostgreSQL │ │ └─ 内存 ↓ │ │ 需要并发访问吗 │ │ ├─ 是 → 跳跃表ConcurrentSkipListMap、LevelDB │ │ └─ 否 ↓ │ │ 范围查询多吗 │ │ ├─ 多 → 跳跃表Redis ZSet │ │ └─ 少 → 红黑树TreeMap也OK │ │ 实现简单重要吗 │ │ ├─ 是 → 跳跃表 ✓ │ │ └─ 否 → 两者都行 │ └──────────────────────────────────────────────────────────────────┘Redis选择跳跃表不是因为跳跃表在理论上碾压红黑树而是在Redis的具体场景下内存存储、单线程、大量范围查询、需要简洁可维护的代码跳跃表是最务实的工程选择。没有银弹只有权衡。这才是技术选型的正确态度。上一篇【第15篇】 跳跃表——Redis有序集合的快速通道下一篇【第17篇】整数集合——Redis集合的省内存利器