刚入行那会儿我一直有个困惑教材里AVL树讲得那么细平衡因子的计算比红黑树的五条性质更像正经数据结构可一到工业级代码红黑树的使用阵容却夸张得吓人。JDK的TreeMap、C标准库的std::map、Linux内核的rbtree连nginx的定时器都用它。AVL明明看起来更平衡为什么就被挤到了角落后来我才想明白答案就藏在统计性能这四个字里。红黑树赢的从来不是某一项极端指标而是在一堆真实操作的混合负载下维护平衡的总代价更小、更可控。这篇文章就把这件事彻底讲透。1. 先搞清楚一个关键事实AVL和红黑树维护的平衡根本是两码事1.1 AVL的平衡是绝对数值约束AVL树规定任意节点的左右子树高度差绝对值不能超过1。这个约束非常直白任何一个节点的左高和右高只要差到2这棵树就是非法的必须立刻修正。所以AVL本质上维护的是一个局部绝对高度差的强不变量。为了实现这个不变量每个节点要么存一个平衡因子取值-1、0、1要么直接存整棵子树的高度每次插入或删除之后都必须沿着祖先路径重新计算这些值。也就是说AVL的每次更新操作都有一个固定的向上回溯动作——不管最后要不要旋转这个路径总得走一遍。1.2 红黑树的平衡是路径上的颜色约束红黑树的五条性质看起来多但真正决定平衡的只有两条红色节点的孩子必须是黑色不允许出现连续两个红节点以及从任意空节点到根节点的路径上黑色节点数量相同也就是黑高相等。这两条合起来的意思是最长路径最多也就是把黑高铺满之后每两个黑节点之间再塞一个红节点所以最长路径不会超过黑高的两倍。它根本不关心某一棵子树和另一棵子树谁高谁矮只要全局颜色分布满足规则就行。打个比方AVL像是一个强迫症患者看到任何左右不对称都要立刻矫正红黑树更像一个粗线条的管理者只要整体不超过某个容忍范围绝不动手。这个性格差异直接决定了后面所有性能差距。1.3 高度差距其实没有想象中那么大从最坏情况看数学结论是AVL树高度不超过1.44 log2(n2) - 1.33红黑树高度不超过2 log2(n1)。以100万个节点为例log2(10^6)约等于19.9AVL最坏约27层红黑树最坏约40层。单看这个最坏值AVL的查找上限确实更优。但注意这是最坏情况的高度需要Fibonacci树那种极端结构才逼得出来。随机数据下两者的平均高度都相当接近基本都在log2 n附近红黑树很少长到2倍黑高的极端形态。所以红黑树查找比AVL慢很多是被最坏情况吓出来的误解真实世界的平均差距很小。对比项AVL树红黑树平衡手段左右子树高度差 ≤ 1黑高相同 不允许连续红节点最坏高度≤ 1.44 log2(n2)≤ 2 log2(n1)查找平均代价略低略高但差距很小节点额外信息平衡因子或高度通常1字节1个颜色位插入旋转次数至多1次但回溯更新平衡因子可能O(log n)至多2次约一半情况0次旋转删除旋转次数最坏O(log n)次至多3次更新代价的长尾删除可能触发连环旋转结构变动有常数上界2. 更新的真实代价旋转次数才是性能分水岭颜色翻转只是辅助2.1 旋转为什么贵很多人只盯着旋转次数没想过一次旋转到底做了什么。单旋转大概要改3处指针双旋转要改更多之后还要重新计算涉及子树的平衡因子或者高度字段。这还没完AVL旋转完之后还要继续向上确认祖先节点的平衡因子有没有变化。在现代CPU上这些指针追跳和字段更新的指令成本远高于一次节点值的比较。而且旋转往往会让刚经过的路径结构发生改变如果这段路径是缓存热点指针改写对缓存也不友好。相比之下红黑树的颜色翻转只是把一个bit从红变黑或者从黑变红完全不涉及指针结构变动。所以评估一棵平衡树的更新成本重点不是它转了几圈而是它做指针结构变动的频率有多高。2.2 AVL插入看起来只有一次旋转病根在路径回溯AVL插入的教科书结论是最多旋转一次。因为一旦在某处旋转子树高度会恢复成插入前的高度祖先的平衡因子不再变化可以立即收工。听起来很不错对吧但真正的成本在走到旋转点之前的那段路上。插入叶子之后AVL必须沿着父指针一路向上逐个更新平衡因子直到遇到某个节点它的平衡因子从±1变成0才能提前停下。如果一路上都是平衡因子从0变成±1那就得一直走到根。换句话说每次插入即使完全不旋转也要承担O(log n)次平衡因子更新和一次完整的回溯过程。少量插入无所谓海量插入时这个回溯路径上的常数开销比红黑树高不少。2.3 AVL删除最坏O(log n)次旋转才是真正的坑如果说插入还只是路径回溯重删除就是AVL真正的滑铁卢。删除节点后AVL同样要向上回溯一旦发现某节点失衡就旋转。麻烦在于这次旋转哪怕做对了子树的高度也可能比删除前又少了1于是它的祖先又会重新失衡。上一层的祖先旋转完再上一层的祖先可能又失衡……最坏情况下一次删除会触发从被删节点一路到根的多达O(log n)次旋转。想构造这种场景并不难Fibonacci树的某些叶子删除就能引发整条路径连环转。删除操作的吞吐越重要AVL的这个弱点就越致命。这也是为什么在很多实时系统里AVL的尾延迟会偶尔冒尖——不是每次删除都出问题但只要出一次就是一条路径上的连锁反应。2.4 红黑树插入大量情况白捡最坏也只要两次旋转红黑树插入先把新节点涂成红色然后看父节点父节点是黑色直接完事连回溯都不用因为红色节点不会破坏任何性质。父节点是红色才需要看叔叔节点的情况叔叔是红色把父节点和叔叔节点变黑、祖父节点变红然后从祖父节点继续往上处理。这一路走的是颜色翻转路线全程不碰指针结构。叔叔是黑色或空做一次单旋转或者两次旋转重新染色收工。这个流程里旋转次数最多只有2。而且随机插入时父节点是黑色的情况占比很高大量插入根本连修正循环都不进。红黑树插入是典型的大概率低成本最坏有常数上界。2.5 红黑树删除CLRS里那个复杂循环真正转的只有3次红黑树删除的修正循环确实啰嗦很多人在实现到这个步骤时容易把方向搞反或者少处理一种情况。但它的精华在于循环里大量操作其实是颜色翻转和指针移动真正改变树结构的旋转累计最多3次就结束。即便修正过程要一直上溯到根那也只是反复翻转颜色昂贵操作的上界被锁死了。用工程的话说单次删除的最坏代价可控不会出现AVL那种O(log n)次连环旋转。对于要求稳定延迟的场景这一点几乎是决定性的。3. 统计性能好的本质松弛的平衡约束换来了均摊优势3.1 用2-3-4树的视角看红黑树其实是在偷懒红黑树有一个很漂亮的同构解释把每个黑色节点和挂在它身上的红色孩子合并当成一个包含多个键的大节点整棵树就变成了一棵2-3-4树。红节点相当于2-3-4树节点里额外的键位。向红黑树插入一个红节点对应的是向2-3-4树的某个节点加一个键。如果这个节点还没满什么都不用做如果满了4节点要变成5键才需要分裂——分裂在红黑树里通常表现为颜色翻转只有几何位置不顺手时才补上一两次旋转。换句话说红黑树的旋转只在抽象节点真正溢出时发生而AVL的旋转只要左右子树高度差一到2就触发。前者在统计上频繁得多。这就是红黑树统计性能好的第一个来源同样的平衡目标红黑树用了更懒惰、更省事的维护方式。它把平衡的概念从数值上解耦出来换成了一套可以本地化处理的颜色规则。3.2 均摊视角统计性能看的是一段操作而不是一次操作把统计性能翻译成算法语言就是均摊分析和期望分析。单次操作谁快谁慢说明不了问题一个包含大量插入和删除的连续操作序列的总代价才重要。红黑树这边插入均摊下来的旋转次数小于1单次删除的旋转次数被常数3锁死AVL那边插入均摊虽然也只有常数次旋转但每次插入都要走一遍平衡因子更新的回溯路径删除更是可能触发O(log n)次旋转。把一串操作整体结算红黑树的指针结构变动总量更小、上界更紧这就是统计性能好的直接证据。更直白一点说AVL把大量成本放在了每次更新都不完全一样、有时需要全局级联的尾巴上红黑树则把这个尾巴剪短了。均摊意义下红黑树每次更新涉及的指针改写次数是常数级别的这种可预期性对性能分析非常重要——不管你用什么分布去压测它都不会突然给你来一下狠的。3.3 查找端那点差距不值得用更新端的劣势去换再回到查找。AVL在查找上的理论优势来自它更矮的最坏高度。但在实际数据分布下两者平均高度差距很小单次成功查找往往只差一个常数级的层数换算成CPU时间可能就几纳秒。而更新操作一旦发生旋转代价是几十纳秒到几百纳秒级别的指针操作删除的连环旋转还会带来明显的延迟抖动。用查找端小赢去换更新端大输在混合读写的工作负载里显然不划算。工程系统里大多数容器类结构的读写比并没有极端到只读红黑树自然成为更稳的默认值。另外还有一个细节树高度和实际查找时间并不是简单的一一对应。查找过程中的分支预测、缓存命中率同样影响巨大。AVL少走的那一层半层经常被一次缓存未命中吃掉所以真实Benchmark里两者的查找性能差距往往比理论数字更小。4. 工程世界的投票为什么STL、Java和Linux内核都选了红黑树4.1 主流选择几乎全在红黑树这边C标准库的std::map、std::set主流实现libstdc、libc底层就是红黑树Java的TreeMap、TreeSet从1.2开始就是红黑树Linux内核专门维护了一个rbtree实现被CFS调度器、epoll的批量监听结构等大量使用nginx的定时器管理、连接ID索引也是红黑树。这些场景的共同点是什么操作集合里插入、删除、查找都很频繁而且系统在长时间运行中无法容忍某一次删除突然引发O(log n)次旋转带来的延迟尖刺。红黑树提供的是查找O(log n)、更新O(log n)但旋转次数常数上界的稳定预期。对跑在真实生产环境里的系统来说这种稳定性比微弱的理论查找优势值钱得多。4.2 但也有反例读多写少时AVL并不是不能打红黑树赢了工业界的默认席位不代表AVL一无是处。如果你的场景是内存中的索引更新极少主要瓶颈是查找路径上的高度那AVL更矮的最坏高度就是实打实的优势。这时候换成AVL单次查找可能少走一两层在高频只读场景下确实能测出收益。数据库、文件系统里的很多索引模块在热数据常驻内存几乎不写的分支里就愿意选更严格的平衡结构。这也解释了为什么AVL至今没有被彻底淘汰它在特定读写比下有自己的立足之地。作为工程师最忌讳的就是拿着一个结论到处套理解场景才是第一位的。4.3 存储和实现的隐性成本AVL要在每个节点存平衡因子或高度字段通常是1个字节红黑树只需1个颜色位。虽然两者都能塞进指针低位或者复用现有字段但AVL在每次旋转后要重新计算子树高度涉及取左右孩子高度再比较的指令红黑树旋转后只要翻转颜色逻辑简单不少。放进热点路径里这些指令差距会被放大。我自己的经验是红黑树实现容易写错尤其删除的分支情况很多第一版非常容易漏掉某个case。如果你是自己手写容器且没有强烈的性能需求第一版老老实实选AVL会更稳等Benchmark明确指出瓶颈在更新操作再迁移到红黑树也不迟。反过来也是一样——不要为了听起来更高级而手写红黑树去替换标准库的std::map收益经常是负的。5. 我的实测心得与选型建议5.1 一次实时场景的教训我之前维护过一个小型定时器模块最初用的是严格平衡的结构而不是红黑树。平时测延迟中位数很漂亮但一到高峰期批量清理过期定时器偶尔会出现单次操作延迟明显偏高。后来把压测数据打出来发现就是删除触发了连环旋转。换成红黑树之后尾延迟平滑了很多。那次之后我学到一个词统计性能不只是平均数的胜利更是长尾的胜利。很多时候一个数据结构的长期表现是由它最差的那几次操作决定的而不是由中位数决定的。红黑树把单次更新的结构变动锁死在常数范围内等于主动剪掉了长尾。5.2 给不同场景的简单建议通用内存键值容器、事件驱动、内核模块默认红黑树理由就是前面写的这些。只读或极高读写比的索引认真测一下AVL不用有心理负担它的查找上限确实更优。数据量大且有磁盘或外存因素考虑B树家族这个讨论已经不在二叉树的范畴里了。不管选哪种动手之前先做性能剖析拿自己的数据测别拿别人的Benchmark当圣旨。5.3 我现在跟人讲这个问题的第一句话红黑树比AVL统计性能好不是因为它更平衡恰恰是因为它不那么平衡。它牺牲了最坏高度的一小部分换来了更新操作中旋转次数的常数上界以及颜色翻转这种廉价机制让平衡维护变得可预期。统计性能这四个字说到底比的是长期、混合负载下的总账而不是某一项指标的极端值。想清楚这一点再回头看JDK和STL的选择就一点都不意外了。
红黑树为何比AVL树更受欢迎？统计性能与工程选择的真相
刚入行那会儿我一直有个困惑教材里AVL树讲得那么细平衡因子的计算比红黑树的五条性质更像正经数据结构可一到工业级代码红黑树的使用阵容却夸张得吓人。JDK的TreeMap、C标准库的std::map、Linux内核的rbtree连nginx的定时器都用它。AVL明明看起来更平衡为什么就被挤到了角落后来我才想明白答案就藏在统计性能这四个字里。红黑树赢的从来不是某一项极端指标而是在一堆真实操作的混合负载下维护平衡的总代价更小、更可控。这篇文章就把这件事彻底讲透。1. 先搞清楚一个关键事实AVL和红黑树维护的平衡根本是两码事1.1 AVL的平衡是绝对数值约束AVL树规定任意节点的左右子树高度差绝对值不能超过1。这个约束非常直白任何一个节点的左高和右高只要差到2这棵树就是非法的必须立刻修正。所以AVL本质上维护的是一个局部绝对高度差的强不变量。为了实现这个不变量每个节点要么存一个平衡因子取值-1、0、1要么直接存整棵子树的高度每次插入或删除之后都必须沿着祖先路径重新计算这些值。也就是说AVL的每次更新操作都有一个固定的向上回溯动作——不管最后要不要旋转这个路径总得走一遍。1.2 红黑树的平衡是路径上的颜色约束红黑树的五条性质看起来多但真正决定平衡的只有两条红色节点的孩子必须是黑色不允许出现连续两个红节点以及从任意空节点到根节点的路径上黑色节点数量相同也就是黑高相等。这两条合起来的意思是最长路径最多也就是把黑高铺满之后每两个黑节点之间再塞一个红节点所以最长路径不会超过黑高的两倍。它根本不关心某一棵子树和另一棵子树谁高谁矮只要全局颜色分布满足规则就行。打个比方AVL像是一个强迫症患者看到任何左右不对称都要立刻矫正红黑树更像一个粗线条的管理者只要整体不超过某个容忍范围绝不动手。这个性格差异直接决定了后面所有性能差距。1.3 高度差距其实没有想象中那么大从最坏情况看数学结论是AVL树高度不超过1.44 log2(n2) - 1.33红黑树高度不超过2 log2(n1)。以100万个节点为例log2(10^6)约等于19.9AVL最坏约27层红黑树最坏约40层。单看这个最坏值AVL的查找上限确实更优。但注意这是最坏情况的高度需要Fibonacci树那种极端结构才逼得出来。随机数据下两者的平均高度都相当接近基本都在log2 n附近红黑树很少长到2倍黑高的极端形态。所以红黑树查找比AVL慢很多是被最坏情况吓出来的误解真实世界的平均差距很小。对比项AVL树红黑树平衡手段左右子树高度差 ≤ 1黑高相同 不允许连续红节点最坏高度≤ 1.44 log2(n2)≤ 2 log2(n1)查找平均代价略低略高但差距很小节点额外信息平衡因子或高度通常1字节1个颜色位插入旋转次数至多1次但回溯更新平衡因子可能O(log n)至多2次约一半情况0次旋转删除旋转次数最坏O(log n)次至多3次更新代价的长尾删除可能触发连环旋转结构变动有常数上界2. 更新的真实代价旋转次数才是性能分水岭颜色翻转只是辅助2.1 旋转为什么贵很多人只盯着旋转次数没想过一次旋转到底做了什么。单旋转大概要改3处指针双旋转要改更多之后还要重新计算涉及子树的平衡因子或者高度字段。这还没完AVL旋转完之后还要继续向上确认祖先节点的平衡因子有没有变化。在现代CPU上这些指针追跳和字段更新的指令成本远高于一次节点值的比较。而且旋转往往会让刚经过的路径结构发生改变如果这段路径是缓存热点指针改写对缓存也不友好。相比之下红黑树的颜色翻转只是把一个bit从红变黑或者从黑变红完全不涉及指针结构变动。所以评估一棵平衡树的更新成本重点不是它转了几圈而是它做指针结构变动的频率有多高。2.2 AVL插入看起来只有一次旋转病根在路径回溯AVL插入的教科书结论是最多旋转一次。因为一旦在某处旋转子树高度会恢复成插入前的高度祖先的平衡因子不再变化可以立即收工。听起来很不错对吧但真正的成本在走到旋转点之前的那段路上。插入叶子之后AVL必须沿着父指针一路向上逐个更新平衡因子直到遇到某个节点它的平衡因子从±1变成0才能提前停下。如果一路上都是平衡因子从0变成±1那就得一直走到根。换句话说每次插入即使完全不旋转也要承担O(log n)次平衡因子更新和一次完整的回溯过程。少量插入无所谓海量插入时这个回溯路径上的常数开销比红黑树高不少。2.3 AVL删除最坏O(log n)次旋转才是真正的坑如果说插入还只是路径回溯重删除就是AVL真正的滑铁卢。删除节点后AVL同样要向上回溯一旦发现某节点失衡就旋转。麻烦在于这次旋转哪怕做对了子树的高度也可能比删除前又少了1于是它的祖先又会重新失衡。上一层的祖先旋转完再上一层的祖先可能又失衡……最坏情况下一次删除会触发从被删节点一路到根的多达O(log n)次旋转。想构造这种场景并不难Fibonacci树的某些叶子删除就能引发整条路径连环转。删除操作的吞吐越重要AVL的这个弱点就越致命。这也是为什么在很多实时系统里AVL的尾延迟会偶尔冒尖——不是每次删除都出问题但只要出一次就是一条路径上的连锁反应。2.4 红黑树插入大量情况白捡最坏也只要两次旋转红黑树插入先把新节点涂成红色然后看父节点父节点是黑色直接完事连回溯都不用因为红色节点不会破坏任何性质。父节点是红色才需要看叔叔节点的情况叔叔是红色把父节点和叔叔节点变黑、祖父节点变红然后从祖父节点继续往上处理。这一路走的是颜色翻转路线全程不碰指针结构。叔叔是黑色或空做一次单旋转或者两次旋转重新染色收工。这个流程里旋转次数最多只有2。而且随机插入时父节点是黑色的情况占比很高大量插入根本连修正循环都不进。红黑树插入是典型的大概率低成本最坏有常数上界。2.5 红黑树删除CLRS里那个复杂循环真正转的只有3次红黑树删除的修正循环确实啰嗦很多人在实现到这个步骤时容易把方向搞反或者少处理一种情况。但它的精华在于循环里大量操作其实是颜色翻转和指针移动真正改变树结构的旋转累计最多3次就结束。即便修正过程要一直上溯到根那也只是反复翻转颜色昂贵操作的上界被锁死了。用工程的话说单次删除的最坏代价可控不会出现AVL那种O(log n)次连环旋转。对于要求稳定延迟的场景这一点几乎是决定性的。3. 统计性能好的本质松弛的平衡约束换来了均摊优势3.1 用2-3-4树的视角看红黑树其实是在偷懒红黑树有一个很漂亮的同构解释把每个黑色节点和挂在它身上的红色孩子合并当成一个包含多个键的大节点整棵树就变成了一棵2-3-4树。红节点相当于2-3-4树节点里额外的键位。向红黑树插入一个红节点对应的是向2-3-4树的某个节点加一个键。如果这个节点还没满什么都不用做如果满了4节点要变成5键才需要分裂——分裂在红黑树里通常表现为颜色翻转只有几何位置不顺手时才补上一两次旋转。换句话说红黑树的旋转只在抽象节点真正溢出时发生而AVL的旋转只要左右子树高度差一到2就触发。前者在统计上频繁得多。这就是红黑树统计性能好的第一个来源同样的平衡目标红黑树用了更懒惰、更省事的维护方式。它把平衡的概念从数值上解耦出来换成了一套可以本地化处理的颜色规则。3.2 均摊视角统计性能看的是一段操作而不是一次操作把统计性能翻译成算法语言就是均摊分析和期望分析。单次操作谁快谁慢说明不了问题一个包含大量插入和删除的连续操作序列的总代价才重要。红黑树这边插入均摊下来的旋转次数小于1单次删除的旋转次数被常数3锁死AVL那边插入均摊虽然也只有常数次旋转但每次插入都要走一遍平衡因子更新的回溯路径删除更是可能触发O(log n)次旋转。把一串操作整体结算红黑树的指针结构变动总量更小、上界更紧这就是统计性能好的直接证据。更直白一点说AVL把大量成本放在了每次更新都不完全一样、有时需要全局级联的尾巴上红黑树则把这个尾巴剪短了。均摊意义下红黑树每次更新涉及的指针改写次数是常数级别的这种可预期性对性能分析非常重要——不管你用什么分布去压测它都不会突然给你来一下狠的。3.3 查找端那点差距不值得用更新端的劣势去换再回到查找。AVL在查找上的理论优势来自它更矮的最坏高度。但在实际数据分布下两者平均高度差距很小单次成功查找往往只差一个常数级的层数换算成CPU时间可能就几纳秒。而更新操作一旦发生旋转代价是几十纳秒到几百纳秒级别的指针操作删除的连环旋转还会带来明显的延迟抖动。用查找端小赢去换更新端大输在混合读写的工作负载里显然不划算。工程系统里大多数容器类结构的读写比并没有极端到只读红黑树自然成为更稳的默认值。另外还有一个细节树高度和实际查找时间并不是简单的一一对应。查找过程中的分支预测、缓存命中率同样影响巨大。AVL少走的那一层半层经常被一次缓存未命中吃掉所以真实Benchmark里两者的查找性能差距往往比理论数字更小。4. 工程世界的投票为什么STL、Java和Linux内核都选了红黑树4.1 主流选择几乎全在红黑树这边C标准库的std::map、std::set主流实现libstdc、libc底层就是红黑树Java的TreeMap、TreeSet从1.2开始就是红黑树Linux内核专门维护了一个rbtree实现被CFS调度器、epoll的批量监听结构等大量使用nginx的定时器管理、连接ID索引也是红黑树。这些场景的共同点是什么操作集合里插入、删除、查找都很频繁而且系统在长时间运行中无法容忍某一次删除突然引发O(log n)次旋转带来的延迟尖刺。红黑树提供的是查找O(log n)、更新O(log n)但旋转次数常数上界的稳定预期。对跑在真实生产环境里的系统来说这种稳定性比微弱的理论查找优势值钱得多。4.2 但也有反例读多写少时AVL并不是不能打红黑树赢了工业界的默认席位不代表AVL一无是处。如果你的场景是内存中的索引更新极少主要瓶颈是查找路径上的高度那AVL更矮的最坏高度就是实打实的优势。这时候换成AVL单次查找可能少走一两层在高频只读场景下确实能测出收益。数据库、文件系统里的很多索引模块在热数据常驻内存几乎不写的分支里就愿意选更严格的平衡结构。这也解释了为什么AVL至今没有被彻底淘汰它在特定读写比下有自己的立足之地。作为工程师最忌讳的就是拿着一个结论到处套理解场景才是第一位的。4.3 存储和实现的隐性成本AVL要在每个节点存平衡因子或高度字段通常是1个字节红黑树只需1个颜色位。虽然两者都能塞进指针低位或者复用现有字段但AVL在每次旋转后要重新计算子树高度涉及取左右孩子高度再比较的指令红黑树旋转后只要翻转颜色逻辑简单不少。放进热点路径里这些指令差距会被放大。我自己的经验是红黑树实现容易写错尤其删除的分支情况很多第一版非常容易漏掉某个case。如果你是自己手写容器且没有强烈的性能需求第一版老老实实选AVL会更稳等Benchmark明确指出瓶颈在更新操作再迁移到红黑树也不迟。反过来也是一样——不要为了听起来更高级而手写红黑树去替换标准库的std::map收益经常是负的。5. 我的实测心得与选型建议5.1 一次实时场景的教训我之前维护过一个小型定时器模块最初用的是严格平衡的结构而不是红黑树。平时测延迟中位数很漂亮但一到高峰期批量清理过期定时器偶尔会出现单次操作延迟明显偏高。后来把压测数据打出来发现就是删除触发了连环旋转。换成红黑树之后尾延迟平滑了很多。那次之后我学到一个词统计性能不只是平均数的胜利更是长尾的胜利。很多时候一个数据结构的长期表现是由它最差的那几次操作决定的而不是由中位数决定的。红黑树把单次更新的结构变动锁死在常数范围内等于主动剪掉了长尾。5.2 给不同场景的简单建议通用内存键值容器、事件驱动、内核模块默认红黑树理由就是前面写的这些。只读或极高读写比的索引认真测一下AVL不用有心理负担它的查找上限确实更优。数据量大且有磁盘或外存因素考虑B树家族这个讨论已经不在二叉树的范畴里了。不管选哪种动手之前先做性能剖析拿自己的数据测别拿别人的Benchmark当圣旨。5.3 我现在跟人讲这个问题的第一句话红黑树比AVL统计性能好不是因为它更平衡恰恰是因为它不那么平衡。它牺牲了最坏高度的一小部分换来了更新操作中旋转次数的常数上界以及颜色翻转这种廉价机制让平衡维护变得可预期。统计性能这四个字说到底比的是长期、混合负载下的总账而不是某一项指标的极端值。想清楚这一点再回头看JDK和STL的选择就一点都不意外了。
