最近公司在做一个排行榜服务技术群里有人抛了个问题底层有序集合到底用红黑树还是跳表两拨人吵得不可开交一拨说Redis的ZSET都用跳表跟着大厂走准没错另一拨说Java的TreeMap从JDK 1.2就在用红黑树几十年工程验证还不够吗最后争论变成了谁抄谁的口水战问题本身反而没人答了。其实这个问题没有标准答案。红黑树和跳表都能做到O(log n)级别的查找、插入、删除都支持有序遍历都能实现范围查询。但在工程落地的细节上两者的性格差异非常大。这篇内容我想从底层原理、真实系统的选型以及我自己踩过的坑三个角度把这道经典的选择题聊透。不管你是面试前临时抱佛脚还是真要在生产环境里做技术选型这篇文章都值得花十分钟看完。1. 先回答为什么纠结红黑树与跳表在系统里的位置先把话说清楚这两个东西不是替代关系而是路径不同的解法。它们解决的是同一类问题——维护一组有序数据并支持高效的增删改查。红黑树是二叉搜索树的平衡版。普通二叉搜索树在极端情况下会退化成链表插入顺序稍微刁钻一点查询就变成O(n)。红黑树通过给节点染色和旋转保证任意节点的左右子树高度差不超过一倍也就是最长路径不会超过最短路径的两倍。这句话翻译成人话就是不管数据怎么插树始终维持在一个还算平衡的状态最坏情况下的查询复杂度也是O(log n)。跳表就特别反直觉。它干脆不做平衡这件事而是靠随机化来碰运气。每一层链表是下一层的索引每个节点以固定概率晋升到上一层。你插入节点时掷一次骰子决定它出现在哪几层。从概率上讲跳表的查询期望复杂度是O(log n)插入删除也基本是这个量级。那选择纠结的根源在哪在于很多场景里这两个东西表现都很好但工作方式完全不同。红黑树是确定性算法同样的输入最终形态完全一致跳表是随机化算法同样的输入跑两遍可能生成不同的结构但性能表现都在一个量级上。再往底层挖它们的差异体现在几个容易被忽视的地方实现复杂度、内存布局、并发友好性、调试难度。这些点决定了同一个场景里工程师会给出完全不同的选型。我在面试候选人的时候经常问一个问题Redis的ZSET为什么用跳表而不是红黑树很多人的回答是因为跳表实现简单这个答案只对了一半。真正深入一点Redis作者antirez在早年博客里说过几个理由跳表的范围查询代码写起来更直观、调试更容易而且在做了无锁化的改造之后并发性能非常好。这些维度在纯算法分析里根本看不到。所以在聊选型之前我们先抛开哪个更高级的滤镜把两个结构的真实工作原理摊开来说透。2. 红黑树解剖五个性质如何撑起一棵伪平衡树2.1 五个性质的工程含义红黑树的定义是五条性质网上随便一搜就有但很多人背完就忘了因为不知道每条性质到底防止了什么。面试时我经常先问这个。这五条性质很重要但容易被忽视我这里就用大白话把每条的真实作用讲清楚。性质一节点只有红色和黑色两种颜色。这个好理解不需要展开。性质二根节点是黑色。这条主要是为了边界统一避免根节点染红之后还要不停调整。性质三所有叶子节点NIL空节点都是黑色。这条看起来废话实际是给红黑树的空指针补一个黑色身份方便统一计算黑高。代码实现里通常用一个共享的NIL节点省空间不用判断空指针。性质四红色节点的两个子节点都必须是黑色等价于红色节点不能连续出现。这一条是最服务于平衡的它限定了极端情况下一条路径上能连续出现的红节点数量。性质五从任意节点到其每个叶子节点的路径包含相同数目的黑色节点。这就是传说中的黑色平衡也是红黑树名字的来源。有了这些性质就能推导出红黑树的核心不变量从根到任意叶子节点最长路径上的节点数最多是最短路径的两倍。两倍听起来很宽松但已经足够把高度控制在O(log n)级别同时避免了AVL树那种一个节点插错就全局旋转的折腾。这也是为什么红黑树在插入删除场景多的工程系统里更吃香它牺牲了一点平衡换来更少的结构调整。2.2 我一直记的插入调整口诀你只要有颜色变、旋转转两个操作逻辑插入过程就不难分析。插入新节点时先把它涂成红色。为什么红色节点不影响黑高相当于不破坏性质五把问题尽量控制在局部。这样一来主要需要处理的就只剩性质四——红节点不能连续。处理时看叔叔节点父节点的兄弟节点的颜色分两大类四种情况叔叔是红色直接变色。把父节点和叔叔节点涂黑把祖父节点涂红然后问题上升到祖父节点继续处理。这就是把局部多余的红色往上推一层。叔叔是黑色转一下再配对旋转。当新节点是父节点的右子节点时先通过对祖父节点的左旋变成LL形态消除了旋转方向的不一致再对祖父做一次右旋并改变相关节点颜色恢复全部性质。删除比插入麻烦。删除一个红色节点直接摘掉就行黑高不受影响。真正麻烦的是删除黑色节点因为路径上的黑节点少了性质五被破坏需要引入双黑概念来调整。此时兄弟节点的颜色、兄弟子节点的颜色组合出四种情况。原理简单说就是先变色如果没能恢复平衡就借助旋转提升黑色高度。记忆起来确实痛苦这也是红黑树令人望而生畏的地方。2.3 实现红黑树付出了什么样的工程代价理论归理论工程里实现红黑树真心不轻松。我把这个算作沉默的代价。一套完整的红黑树插入删除代码加上辅助的旋转函数、插入修复、删除修复轻松超过两百行。难点不在逻辑一次写对而在于边界非常多。叔父节点为空怎么办祖父节点是根节点怎么办删除后修复时兄弟节点的两个子节点全是黑的怎么办每一条都是单独看很合理、合在一起就记不住的分支。调试红黑树则是另一种折磨。树结构在变化之后光靠肉眼根本看不出哪里违反了性质。我以前调试时写过一个校验器反复遍历检查五个性质任何一条被破坏就用断言的输出来定位是哪一步修正漏了。插删除场景一多BUG的类型就非常考验经验积累。所以你会发现现代工程里很少有人在业务代码里手写红黑树。大部分是调用现成实现比如Java的TreeMap、C的std::map。这也是红黑树难和红黑树工程可用这两个事实长期共存的原因难的活底层库帮你干了你只用接API。3. 跳表的随机化思维怎么用概率换实现简单跳表的设计思路跟红黑树完全不同。红黑树追求平衡这个确定性目标跳表则拥抱随机这个不确定性的来源。3.1 从单链表到多层索引的演进想象一个有序单链表你要找某个值只能从头到尾一个个比复杂度O(n)。跳表的想法很朴素每隔几个节点增加一层索引让查找过程中可以直接跳过去一大段。最经典的理解方式是模拟二分查找的手感。最底层是全部节点上一层的节点数大约是底层的一半再上一层再减半以此类推。查找时从最高层往下走每层都在快速逼近目标最终落到底层精确匹配。因为查询平均跳过的节点数是常数量级总复杂度自然落到O(log n)。跳表节点结构里除了值还有一个索引节点数组存的是每一层的下一个节点指针。每个节点到底出现在哪些层决定性机制是随机。3.2 晋升概率p和时间空间的折衷插入一个节点时先在底层插入之后抛硬币决定是否晋升到上一层。一般实现里用random()和阈值比较每次晋升概率设为1/2也可以用1/4或别的值工程里p通常在0.25到0.5之间。晋升概率对应着空间和时间之间的权衡p越大跳表的层数越高索引节点占总节点比例增大内存开销升得越快。p1/2时每个节点平均有2个指针p1/4时每个节点平均只有1.33个指针。p越大每一层的跳跃感越弱查找步数减少但为了这个减少消耗的额外指针空间也越多。我实测过p1/4和p1/2在查询性能上的差别在数据量几十万级别时差距几乎可以忽略但内存使用差不少。所以说并不存在最好的p只有最适合你当前配置的p。3.3 跳表在工程里好使的隐藏原因跳表实现简单这个概念不是说代码量真的比红黑树少多少而是它每一行都很直观。插入操作就是普通链表插入只是需要同时处理多层的指针更新删除同理不需要旋转、变色不需要逐层回溯调整平衡。还有三个工程属性是红黑树非常吃力的第一是无锁化改造容易。红黑树的旋转会涉及多个节点的指针变更不对整棵树加锁很难保证原子性。跳表的插入删除只影响局部层级的相邻节点通过CAS操作修改指针就能实现无锁并发这就是Java的ConcurrentSkipListMap能大幅度降低锁竞争的本质原因。第二是范围查询代码直观。红黑树做范围查询必须中序遍历还要借助额外的栈或Morris遍历代码写起来绕。跳表找到起点后顺着最底层的单向链表一路向右走就行这个行为方式完美契合了查一个区间这一高频需求。第三是调试时有天然的形状参照物。跳表的每一层链表清晰可见断点打在哪一层、哪个节点都容易定位。红黑树旋转之后形状大变断点打下去看当前上下文很难猜出全局状态。4. 关键差异盘点从读写复杂度到工程维护成本光讲原理不够直观我把红黑树和跳表在一个工程视角下的关键差异整理成了一张表。这里面的结论不是理论最优值而是普遍工程实现下的综合表现。对比维度红黑树跳表查找复杂度O(log n) 最坏情况O(log n) 期望情况插入复杂度O(log n) 最坏情况O(log n) 期望情况删除复杂度O(log n) 最坏情况O(log n) 期望情况范围查询中序遍历实现绕底层链表直接遍历实现简洁确定性完全确定同输入同结构随机结构每次可能不同内存占用2个指针颜色标记平均2个或更多指针由晋升概率决定实现难度高插入删除分支多较低逻辑更直白无锁并发改造非常困难旋转涉及多个点相对容易CAS可覆盖主要操作最坏情况风险理论最坏有界理论可能退化为链表概率极低调试难度高旋转后结构混乱低层级结构清晰缓存局部性较差节点散落在堆中较差节点同样非连续适用的语言生态Java TreeMap、C std::map等Redis ZSET、并发跳表等几个维度单独拿出来解读一下。确定性。红黑树的形状完全由插入顺序决定同一种数据流跑到任何一台机器上最终形态完全一致。跳表则每次生成的可能都不同。如果你们的系统对结果可复现性有硬要求比如日志分析后需要完全一致的快照内容那跳表会让你抓狂反之如果只是要求最终内容有序跳表完全够用。内存占用。这个问题比想象中复杂。红黑树每个节点两个指针加一个颜色位跳表平均指针数是(1/(1-p))如果p1/2就是2个。看上去差不多但跳表还有随机生成的层数不确定性偶尔会出现一个节点上了十几层的情况拉高整体内存。不过红黑树的颜色位在多数实现里是放在节点里的一字节标记实际对齐后未必省内存。我建议你按自己的数据量先压测对比不要凭印象下结论。缓存局部性。这两个结构都是指针追指针的链式结构节点在堆里随机分布CPU预取基本失效。如果你要处理的数据规模恰好需要高频访问而内存又紧张跳表和红黑树都不是最佳选择应该考虑B树或连续数组的存储结构。这个点解决了很多人为什么我的内存结构扫描起来这么慢的疑问。5. 现实系统怎么选MySQL索引、Redis ZSET、Java并发的答案理论对比再怎么周全都不如看看生产系统里的答案来得直接。下面三个案例正好对应三类完全不同的选型思路。5.1 MySQL为什么选B树顺便回答B树是红黑树吗先说热词里那个问题B树不是红黑树。两者没有血缘关系。红黑树是二叉树B树是多叉树B树的每个节点可以存放大量键值和子节点指针。为什么数据库不用红黑树核心原因不是红黑树不够快而是树的高度。红黑树即使平衡得不错高度依然大约是O(log n)。一棵两千万条记录的树高度大约在25到30层。数据库的磁盘IO是按页读写的一次IO拉回一页数据到内存如果数据不在这个页里就要再来一次IO。红黑树的每个节点可能散落在不同的磁盘页找一条记录可能要发起20多次IO这个代价在硬盘上是毁灭性的。B树解法是压缩每层节点数量让一个节点容纳几百个键值树的高度直接降到三四层。查找一条数据最多三五次磁盘IO通过叶子节点之间的链表指针直接做范围扫描。这就是数据库这种读写磁盘的存储系统必须选B树而不选红黑树的本质原因。红黑树在数据库里不是完全消失而是用在了数据库进程内部的内存数据结构上比如内存排序、缓冲区管理。5.2 Redis的ZSET为什么用跳表Redis的有序集合ZSET底层是dict加zskiplist的组合。dict存键值映射用于快速查分zskiplist存有序的成员和分数用于排序操作。选跳表而不用红黑树Redis作者给出过几个理由我实践下来还是很认可的跳表的范围查询代码实现简单清晰ZRANGEBYSCORE这种命令直接依赖这个特性跳表在并发场景下做无锁改造比红黑树容易得多Redis后续如果要扩展多线程模型这个优势会被进一步放大跳表的结构调试起来直观作者本人维护成本低。再有就是性能基本打平。Redis官方曾经做过对比跳表在分数区间查询场景下并不比红黑树差数据量又不是天文数字差别很难感知。对一个追求代码可维护性的中间件来说哪个更简单易维护往往比哪个理论上快一点更重要。5.3 Java生态TreeMap与ConcurrentSkipListMap的取舍Java标准库是两个结构都有选择逻辑特别有意思现实中的例子很有代表性。TreeMap底层是红黑树同步安全上没做并发处理。单线程读多写少的内存场景TreeMap用起来非常顺手还支持NavigableMap的各种有序方法。我的配置文件解析、URL路径匹配、状态码映射这类轻量级需求首选就是TreeMap。ConcurrentSkipListMap底层是跳表官方明确说是为并发访问设计的替代方案。它提供的是无锁读和无阻塞写比给TreeMap套个synchronized锁的吞吐量高很多。高并发场景下比如实时风控规则集、低频路由表更新我实际写下来最省心的是ConcurrentSkipListMap它天然实现了弱一致性的迭代器不会抛ConcurrentModificationException。很多工程师问底层列表更新不频繁是不是用TreeMap加锁就够了我的建议是分水岭在并发读写是否存在竞争。只要有多个线程同时在写有序集合就直接考虑并发跳表不要犹豫。锁竞争是系统吞吐量最大的敌人之一。5.4 操作系统和基础库里的红黑树跟数据库场景不同操作系统的内核内存管理、定时器管理里大量使用红黑树。内核里的数据结构是内存中的不需要磁盘IO同时系统对最坏情况延迟有硬性要求比如中断处理里的定时器必须保证任何情况下都能在O(log n)时间完成调度红黑树的确定性在这里又成了优势。这也说明了为什么红黑树在调度器里无可替代而跳表在缓存和中间件里越来越常见——因为一个追求确定性保证一个追求实现和并发便利。6. 我的几次选型实践与最终决策清单前面讲了这么多系统里的答案下面说说我自己用下来的具体的例子。只有落到实际代码里的经验才是真经验。做一个网关服务时要维护一组按优先级排序的规则每个规则带一个通配符模式每来一个请求都要从上往下匹配命中就返回对应动作。规则数量不大最多几千条但更新频率不低业务人员随时可能增删规则。我最初想当然用TreeMap按优先级作为key存规则列表。后来发现规则是按优先级字段排序的但同优先级内部还要按更新时间排序TreeMap没法优雅处理这种复合排序。后来我改成跳表底层节点存规则对象排序规则实现自定义比较器插入时自然落到正确位置请求过来时从最小优先级开始向后顺序匹配查到第一条命中规则就返回这个遍历路径非常符合跳表的底层链表结构。整个实现不到两百行没有复杂的旋转调整测试也顺利。这是我第一次深刻体会跳表在自定义排序顺序遍历场景下的价值。另一个配置中心模块里需要维护一组对象ID到配置快照的映射支持随机查询和有序遍历。这个场景数据是只读的启动时加载好运行中极少变动。我直接选了TreeMap理由很简单单线程环境红黑树的确定性性能表现稳定而且利用Java的NavigableMap接口做区间查询也更顺手。这个模块上线后没有因为这部分出现任何性能问题。从实际回调看理解TreeMap的红黑树结构对排查问题时的心态很有帮助。踩过几次坑后我沉淀出一个自己的决策清单分享给你数据完全在内存、没有并发写优先用红黑树实现的有序映射。代码现成、稳定性验证充分、工具链齐全。高并发写多读多、且顺序遍历要求高直接选跳表优先用ConcurrentSkipListMap这类现成实现。范围查询频繁且范围查询的代码可读性对你来说很重要跳表更合适。对最坏情况延迟有硬性约束红黑树更让人安心。需要实现自定义排序逻辑且想在代码里直观控制遍历顺序跳表更容易改。如果数据量会超过内存容量涉及磁盘IO那红黑树和跳表都不选直接转向B树或LSM树设计。另外关于手写还有一个建议除非你是在学习或者做语言底层库不要在生产代码里手写这两个结构。红黑树的手写难度高出天际跳表演示代码看起来简单但真要处理满层指针更新和内存分配策略同样不轻松。选现成类库把精力留给解决业务问题。最后再分享一个关于性能的小技巧。无论选哪种都可以在压测时把数据量放大10倍以上再观察劣化曲线。跳表的随机化决定了它在数据量大之后层数分布的不均衡可能造成局部性能波动红黑树则通常比较平稳唯一可能出问题的是反复删除插入后树的形态变化引发更多的旋转。这两种情况都和你设定的p值或者数据特征相关压测不出来就是隐患。我遇到过跳表在p0.25时内存省了但查询慢了一点的情况后来换回0.5马上变成稳定的低延迟。这个参数值得你在自己的场景里反复试几次。 
长河君 · 2026/10/2 10:05:17 · 阅读 1.2k 红黑树与跳表：有序集合选型对比与工程实践
最近公司在做一个排行榜服务技术群里有人抛了个问题底层有序集合到底用红黑树还是跳表两拨人吵得不可开交一拨说Redis的ZSET都用跳表跟着大厂走准没错另一拨说Java的TreeMap从JDK 1.2就在用红黑树几十年工程验证还不够吗最后争论变成了谁抄谁的口水战问题本身反而没人答了。其实这个问题没有标准答案。红黑树和跳表都能做到O(log n)级别的查找、插入、删除都支持有序遍历都能实现范围查询。但在工程落地的细节上两者的性格差异非常大。这篇内容我想从底层原理、真实系统的选型以及我自己踩过的坑三个角度把这道经典的选择题聊透。不管你是面试前临时抱佛脚还是真要在生产环境里做技术选型这篇文章都值得花十分钟看完。1. 先回答为什么纠结红黑树与跳表在系统里的位置先把话说清楚这两个东西不是替代关系而是路径不同的解法。它们解决的是同一类问题——维护一组有序数据并支持高效的增删改查。红黑树是二叉搜索树的平衡版。普通二叉搜索树在极端情况下会退化成链表插入顺序稍微刁钻一点查询就变成O(n)。红黑树通过给节点染色和旋转保证任意节点的左右子树高度差不超过一倍也就是最长路径不会超过最短路径的两倍。这句话翻译成人话就是不管数据怎么插树始终维持在一个还算平衡的状态最坏情况下的查询复杂度也是O(log n)。跳表就特别反直觉。它干脆不做平衡这件事而是靠随机化来碰运气。每一层链表是下一层的索引每个节点以固定概率晋升到上一层。你插入节点时掷一次骰子决定它出现在哪几层。从概率上讲跳表的查询期望复杂度是O(log n)插入删除也基本是这个量级。那选择纠结的根源在哪在于很多场景里这两个东西表现都很好但工作方式完全不同。红黑树是确定性算法同样的输入最终形态完全一致跳表是随机化算法同样的输入跑两遍可能生成不同的结构但性能表现都在一个量级上。再往底层挖它们的差异体现在几个容易被忽视的地方实现复杂度、内存布局、并发友好性、调试难度。这些点决定了同一个场景里工程师会给出完全不同的选型。我在面试候选人的时候经常问一个问题Redis的ZSET为什么用跳表而不是红黑树很多人的回答是因为跳表实现简单这个答案只对了一半。真正深入一点Redis作者antirez在早年博客里说过几个理由跳表的范围查询代码写起来更直观、调试更容易而且在做了无锁化的改造之后并发性能非常好。这些维度在纯算法分析里根本看不到。所以在聊选型之前我们先抛开哪个更高级的滤镜把两个结构的真实工作原理摊开来说透。2. 红黑树解剖五个性质如何撑起一棵伪平衡树2.1 五个性质的工程含义红黑树的定义是五条性质网上随便一搜就有但很多人背完就忘了因为不知道每条性质到底防止了什么。面试时我经常先问这个。这五条性质很重要但容易被忽视我这里就用大白话把每条的真实作用讲清楚。性质一节点只有红色和黑色两种颜色。这个好理解不需要展开。性质二根节点是黑色。这条主要是为了边界统一避免根节点染红之后还要不停调整。性质三所有叶子节点NIL空节点都是黑色。这条看起来废话实际是给红黑树的空指针补一个黑色身份方便统一计算黑高。代码实现里通常用一个共享的NIL节点省空间不用判断空指针。性质四红色节点的两个子节点都必须是黑色等价于红色节点不能连续出现。这一条是最服务于平衡的它限定了极端情况下一条路径上能连续出现的红节点数量。性质五从任意节点到其每个叶子节点的路径包含相同数目的黑色节点。这就是传说中的黑色平衡也是红黑树名字的来源。有了这些性质就能推导出红黑树的核心不变量从根到任意叶子节点最长路径上的节点数最多是最短路径的两倍。两倍听起来很宽松但已经足够把高度控制在O(log n)级别同时避免了AVL树那种一个节点插错就全局旋转的折腾。这也是为什么红黑树在插入删除场景多的工程系统里更吃香它牺牲了一点平衡换来更少的结构调整。2.2 我一直记的插入调整口诀你只要有颜色变、旋转转两个操作逻辑插入过程就不难分析。插入新节点时先把它涂成红色。为什么红色节点不影响黑高相当于不破坏性质五把问题尽量控制在局部。这样一来主要需要处理的就只剩性质四——红节点不能连续。处理时看叔叔节点父节点的兄弟节点的颜色分两大类四种情况叔叔是红色直接变色。把父节点和叔叔节点涂黑把祖父节点涂红然后问题上升到祖父节点继续处理。这就是把局部多余的红色往上推一层。叔叔是黑色转一下再配对旋转。当新节点是父节点的右子节点时先通过对祖父节点的左旋变成LL形态消除了旋转方向的不一致再对祖父做一次右旋并改变相关节点颜色恢复全部性质。删除比插入麻烦。删除一个红色节点直接摘掉就行黑高不受影响。真正麻烦的是删除黑色节点因为路径上的黑节点少了性质五被破坏需要引入双黑概念来调整。此时兄弟节点的颜色、兄弟子节点的颜色组合出四种情况。原理简单说就是先变色如果没能恢复平衡就借助旋转提升黑色高度。记忆起来确实痛苦这也是红黑树令人望而生畏的地方。2.3 实现红黑树付出了什么样的工程代价理论归理论工程里实现红黑树真心不轻松。我把这个算作沉默的代价。一套完整的红黑树插入删除代码加上辅助的旋转函数、插入修复、删除修复轻松超过两百行。难点不在逻辑一次写对而在于边界非常多。叔父节点为空怎么办祖父节点是根节点怎么办删除后修复时兄弟节点的两个子节点全是黑的怎么办每一条都是单独看很合理、合在一起就记不住的分支。调试红黑树则是另一种折磨。树结构在变化之后光靠肉眼根本看不出哪里违反了性质。我以前调试时写过一个校验器反复遍历检查五个性质任何一条被破坏就用断言的输出来定位是哪一步修正漏了。插删除场景一多BUG的类型就非常考验经验积累。所以你会发现现代工程里很少有人在业务代码里手写红黑树。大部分是调用现成实现比如Java的TreeMap、C的std::map。这也是红黑树难和红黑树工程可用这两个事实长期共存的原因难的活底层库帮你干了你只用接API。3. 跳表的随机化思维怎么用概率换实现简单跳表的设计思路跟红黑树完全不同。红黑树追求平衡这个确定性目标跳表则拥抱随机这个不确定性的来源。3.1 从单链表到多层索引的演进想象一个有序单链表你要找某个值只能从头到尾一个个比复杂度O(n)。跳表的想法很朴素每隔几个节点增加一层索引让查找过程中可以直接跳过去一大段。最经典的理解方式是模拟二分查找的手感。最底层是全部节点上一层的节点数大约是底层的一半再上一层再减半以此类推。查找时从最高层往下走每层都在快速逼近目标最终落到底层精确匹配。因为查询平均跳过的节点数是常数量级总复杂度自然落到O(log n)。跳表节点结构里除了值还有一个索引节点数组存的是每一层的下一个节点指针。每个节点到底出现在哪些层决定性机制是随机。3.2 晋升概率p和时间空间的折衷插入一个节点时先在底层插入之后抛硬币决定是否晋升到上一层。一般实现里用random()和阈值比较每次晋升概率设为1/2也可以用1/4或别的值工程里p通常在0.25到0.5之间。晋升概率对应着空间和时间之间的权衡p越大跳表的层数越高索引节点占总节点比例增大内存开销升得越快。p1/2时每个节点平均有2个指针p1/4时每个节点平均只有1.33个指针。p越大每一层的跳跃感越弱查找步数减少但为了这个减少消耗的额外指针空间也越多。我实测过p1/4和p1/2在查询性能上的差别在数据量几十万级别时差距几乎可以忽略但内存使用差不少。所以说并不存在最好的p只有最适合你当前配置的p。3.3 跳表在工程里好使的隐藏原因跳表实现简单这个概念不是说代码量真的比红黑树少多少而是它每一行都很直观。插入操作就是普通链表插入只是需要同时处理多层的指针更新删除同理不需要旋转、变色不需要逐层回溯调整平衡。还有三个工程属性是红黑树非常吃力的第一是无锁化改造容易。红黑树的旋转会涉及多个节点的指针变更不对整棵树加锁很难保证原子性。跳表的插入删除只影响局部层级的相邻节点通过CAS操作修改指针就能实现无锁并发这就是Java的ConcurrentSkipListMap能大幅度降低锁竞争的本质原因。第二是范围查询代码直观。红黑树做范围查询必须中序遍历还要借助额外的栈或Morris遍历代码写起来绕。跳表找到起点后顺着最底层的单向链表一路向右走就行这个行为方式完美契合了查一个区间这一高频需求。第三是调试时有天然的形状参照物。跳表的每一层链表清晰可见断点打在哪一层、哪个节点都容易定位。红黑树旋转之后形状大变断点打下去看当前上下文很难猜出全局状态。4. 关键差异盘点从读写复杂度到工程维护成本光讲原理不够直观我把红黑树和跳表在一个工程视角下的关键差异整理成了一张表。这里面的结论不是理论最优值而是普遍工程实现下的综合表现。对比维度红黑树跳表查找复杂度O(log n) 最坏情况O(log n) 期望情况插入复杂度O(log n) 最坏情况O(log n) 期望情况删除复杂度O(log n) 最坏情况O(log n) 期望情况范围查询中序遍历实现绕底层链表直接遍历实现简洁确定性完全确定同输入同结构随机结构每次可能不同内存占用2个指针颜色标记平均2个或更多指针由晋升概率决定实现难度高插入删除分支多较低逻辑更直白无锁并发改造非常困难旋转涉及多个点相对容易CAS可覆盖主要操作最坏情况风险理论最坏有界理论可能退化为链表概率极低调试难度高旋转后结构混乱低层级结构清晰缓存局部性较差节点散落在堆中较差节点同样非连续适用的语言生态Java TreeMap、C std::map等Redis ZSET、并发跳表等几个维度单独拿出来解读一下。确定性。红黑树的形状完全由插入顺序决定同一种数据流跑到任何一台机器上最终形态完全一致。跳表则每次生成的可能都不同。如果你们的系统对结果可复现性有硬要求比如日志分析后需要完全一致的快照内容那跳表会让你抓狂反之如果只是要求最终内容有序跳表完全够用。内存占用。这个问题比想象中复杂。红黑树每个节点两个指针加一个颜色位跳表平均指针数是(1/(1-p))如果p1/2就是2个。看上去差不多但跳表还有随机生成的层数不确定性偶尔会出现一个节点上了十几层的情况拉高整体内存。不过红黑树的颜色位在多数实现里是放在节点里的一字节标记实际对齐后未必省内存。我建议你按自己的数据量先压测对比不要凭印象下结论。缓存局部性。这两个结构都是指针追指针的链式结构节点在堆里随机分布CPU预取基本失效。如果你要处理的数据规模恰好需要高频访问而内存又紧张跳表和红黑树都不是最佳选择应该考虑B树或连续数组的存储结构。这个点解决了很多人为什么我的内存结构扫描起来这么慢的疑问。5. 现实系统怎么选MySQL索引、Redis ZSET、Java并发的答案理论对比再怎么周全都不如看看生产系统里的答案来得直接。下面三个案例正好对应三类完全不同的选型思路。5.1 MySQL为什么选B树顺便回答B树是红黑树吗先说热词里那个问题B树不是红黑树。两者没有血缘关系。红黑树是二叉树B树是多叉树B树的每个节点可以存放大量键值和子节点指针。为什么数据库不用红黑树核心原因不是红黑树不够快而是树的高度。红黑树即使平衡得不错高度依然大约是O(log n)。一棵两千万条记录的树高度大约在25到30层。数据库的磁盘IO是按页读写的一次IO拉回一页数据到内存如果数据不在这个页里就要再来一次IO。红黑树的每个节点可能散落在不同的磁盘页找一条记录可能要发起20多次IO这个代价在硬盘上是毁灭性的。B树解法是压缩每层节点数量让一个节点容纳几百个键值树的高度直接降到三四层。查找一条数据最多三五次磁盘IO通过叶子节点之间的链表指针直接做范围扫描。这就是数据库这种读写磁盘的存储系统必须选B树而不选红黑树的本质原因。红黑树在数据库里不是完全消失而是用在了数据库进程内部的内存数据结构上比如内存排序、缓冲区管理。5.2 Redis的ZSET为什么用跳表Redis的有序集合ZSET底层是dict加zskiplist的组合。dict存键值映射用于快速查分zskiplist存有序的成员和分数用于排序操作。选跳表而不用红黑树Redis作者给出过几个理由我实践下来还是很认可的跳表的范围查询代码实现简单清晰ZRANGEBYSCORE这种命令直接依赖这个特性跳表在并发场景下做无锁改造比红黑树容易得多Redis后续如果要扩展多线程模型这个优势会被进一步放大跳表的结构调试起来直观作者本人维护成本低。再有就是性能基本打平。Redis官方曾经做过对比跳表在分数区间查询场景下并不比红黑树差数据量又不是天文数字差别很难感知。对一个追求代码可维护性的中间件来说哪个更简单易维护往往比哪个理论上快一点更重要。5.3 Java生态TreeMap与ConcurrentSkipListMap的取舍Java标准库是两个结构都有选择逻辑特别有意思现实中的例子很有代表性。TreeMap底层是红黑树同步安全上没做并发处理。单线程读多写少的内存场景TreeMap用起来非常顺手还支持NavigableMap的各种有序方法。我的配置文件解析、URL路径匹配、状态码映射这类轻量级需求首选就是TreeMap。ConcurrentSkipListMap底层是跳表官方明确说是为并发访问设计的替代方案。它提供的是无锁读和无阻塞写比给TreeMap套个synchronized锁的吞吐量高很多。高并发场景下比如实时风控规则集、低频路由表更新我实际写下来最省心的是ConcurrentSkipListMap它天然实现了弱一致性的迭代器不会抛ConcurrentModificationException。很多工程师问底层列表更新不频繁是不是用TreeMap加锁就够了我的建议是分水岭在并发读写是否存在竞争。只要有多个线程同时在写有序集合就直接考虑并发跳表不要犹豫。锁竞争是系统吞吐量最大的敌人之一。5.4 操作系统和基础库里的红黑树跟数据库场景不同操作系统的内核内存管理、定时器管理里大量使用红黑树。内核里的数据结构是内存中的不需要磁盘IO同时系统对最坏情况延迟有硬性要求比如中断处理里的定时器必须保证任何情况下都能在O(log n)时间完成调度红黑树的确定性在这里又成了优势。这也说明了为什么红黑树在调度器里无可替代而跳表在缓存和中间件里越来越常见——因为一个追求确定性保证一个追求实现和并发便利。6. 我的几次选型实践与最终决策清单前面讲了这么多系统里的答案下面说说我自己用下来的具体的例子。只有落到实际代码里的经验才是真经验。做一个网关服务时要维护一组按优先级排序的规则每个规则带一个通配符模式每来一个请求都要从上往下匹配命中就返回对应动作。规则数量不大最多几千条但更新频率不低业务人员随时可能增删规则。我最初想当然用TreeMap按优先级作为key存规则列表。后来发现规则是按优先级字段排序的但同优先级内部还要按更新时间排序TreeMap没法优雅处理这种复合排序。后来我改成跳表底层节点存规则对象排序规则实现自定义比较器插入时自然落到正确位置请求过来时从最小优先级开始向后顺序匹配查到第一条命中规则就返回这个遍历路径非常符合跳表的底层链表结构。整个实现不到两百行没有复杂的旋转调整测试也顺利。这是我第一次深刻体会跳表在自定义排序顺序遍历场景下的价值。另一个配置中心模块里需要维护一组对象ID到配置快照的映射支持随机查询和有序遍历。这个场景数据是只读的启动时加载好运行中极少变动。我直接选了TreeMap理由很简单单线程环境红黑树的确定性性能表现稳定而且利用Java的NavigableMap接口做区间查询也更顺手。这个模块上线后没有因为这部分出现任何性能问题。从实际回调看理解TreeMap的红黑树结构对排查问题时的心态很有帮助。踩过几次坑后我沉淀出一个自己的决策清单分享给你数据完全在内存、没有并发写优先用红黑树实现的有序映射。代码现成、稳定性验证充分、工具链齐全。高并发写多读多、且顺序遍历要求高直接选跳表优先用ConcurrentSkipListMap这类现成实现。范围查询频繁且范围查询的代码可读性对你来说很重要跳表更合适。对最坏情况延迟有硬性约束红黑树更让人安心。需要实现自定义排序逻辑且想在代码里直观控制遍历顺序跳表更容易改。如果数据量会超过内存容量涉及磁盘IO那红黑树和跳表都不选直接转向B树或LSM树设计。另外关于手写还有一个建议除非你是在学习或者做语言底层库不要在生产代码里手写这两个结构。红黑树的手写难度高出天际跳表演示代码看起来简单但真要处理满层指针更新和内存分配策略同样不轻松。选现成类库把精力留给解决业务问题。最后再分享一个关于性能的小技巧。无论选哪种都可以在压测时把数据量放大10倍以上再观察劣化曲线。跳表的随机化决定了它在数据量大之后层数分布的不均衡可能造成局部性能波动红黑树则通常比较平稳唯一可能出问题的是反复删除插入后树的形态变化引发更多的旋转。这两种情况都和你设定的p值或者数据特征相关压测不出来就是隐患。我遇到过跳表在p0.25时内存省了但查询慢了一点的情况后来换回0.5马上变成稳定的低延迟。这个参数值得你在自己的场景里反复试几次。