引子老王的较真还记得上一篇里那位被翻盘太慢逼得换上B树、终于把几十亿数据压进三四层的老王吗B树那句多叉胖节点把树压成矮胖墩让老王大开眼界。可这位爱较真的老王事后却越想越不踏实半夜爬起来又琢磨上了等等上一篇说平衡二叉树’二叉’太瘦高要30多层B树’多叉’矮胖只要3层。可这’多叉’到底好在哪不就是把树变矮了点吗而且——一个节点分2个岔查找时’砍一半’分1000个岔查找时不也得在那1000个’路标’里挨个找一遍吗这一进一出到底是赚了还是亏了我得拿出真凭实据把这笔账一分一厘地算清楚老王这股较真的劲头问到了一个特别容易被忽略、却又至关重要的核心问题上“二叉和多叉”在性能上到底差在哪分岔越多就一定越好吗这中间藏着怎样的账上一篇我们知道了多叉树更矮这个结论可这一篇我们要陪老王把这背后的账彻彻底底地算明白——你会发现这笔账远比树变矮了要精彩、要深刻得多。老王重新搬出小板凳和算盘“走着这次咱们不讲结论只算账”第一章先算高度账——多叉到底能矮多少我们先算第一笔也是最直观的一笔账同样数量的数据分岔数不同树的高度差多少这里有个关键的数学规律请记住它一棵树能装多少数据由两个因素决定分岔数 m每个节点分几个岔高度 h树有多少层大致关系是能装的数据量 ≈ m^hm的h次方。反过来推要装下 N 个数据需要的高度就是高度 h ≈ log_m(N)——以分岔数m为底对N取对数。关键就藏在这个底数 m上我们代入具体数字看一场触目惊心的对比——同样要装下10亿10⁹个数据┌──────────────┬──────────┬──────────────────────┐ │ 分岔数 m │ 需要高度 │ 计算 │ ├──────────────┼──────────┼──────────────────────┤ │ 2 (二叉) │ 约30层 │ log₂(10亿) ≈ 30 │ │ 10 (十叉) │ 约9层 │ log₁₀(10亿) 9 │ │ 100 (百叉) │ 约5层 │ log₁₀₀(10亿) ≈ 4.5 │ │ 1000 (千叉) │ 约3层 │ log₁₀₀₀(10亿) 3 │ └──────────────┴──────────┴──────────────────────┘看明白了吗分岔数 m是藏在对数底数里的底数越大对数值就越小树就越矮。从二叉到千叉分岔数翻了500倍可换来的回报是惊人的——层数从30层骤降到了3层整整矮了10倍老王看着这张表眼睛瞪得溜圆“我的天同样是10亿数据二叉树要垒30层千叉树只要3层这差距也太悬殊了”第一笔高度账算完了结论很明确分岔越多树越矮。可老王立刻追问出了那个最尖锐的问题——“树是矮了可每个节点变胖了啊查找时在一个塞了1000个路标的胖节点里翻找难道不要花时间吗这笔’胖节点账’你还没算呢”问得好这正是这篇文章最精彩的地方。第二章再算胖节点账——分岔多了节点内部不是更慢老王的质疑非常在理。我们把查找一个数据的总功夫拆成两部分来算查找总功夫 走过的层数×在每一层节点内部查找的功夫走过的层数就是树高 h ——分岔越多它越小好事每层节点内部查找的功夫在一个胖节点的那一排路标里找——分岔越多路标越多它越大坏事这就是矛盾的核心分岔变多一个变小、一个变大到底谁占上风我们来算笔细账。假设节点内部是老老实实挨个比较线性查找。那么分岔数为 m 时每层内部最多比较m 次总层数是log_m(N)总比较次数 ≈ m × log_m(N)我们代入 N 10亿算算总比较次数┌──────────────┬─────────┬──────────────┬──────────────────┐ │ 分岔数 m │ 层数h │ 每层比较m次 │ 总比较 m × h │ ├──────────────┼─────────┼──────────────┼──────────────────┤ │ 2 (二叉) │ 30 │ 2 │ 60 │ │ 10 │ 9 │ 10 │ 90 │ │ 100 │ 4.5 │ 100 │ 450 │ │ 1000 │ 3 │ 1000 │ 3000 │ └──────────────┴─────────┴──────────────┴──────────────────┘咦结果让人大跌眼镜如果节点内部是挨个比较那么——分岔越多总比较次数反而越多二叉树只要60次比较千叉树竟要3000次老王一拍大腿“我就说嘛分岔多了胖节点内部翻找太费劲这买卖根本不划算B树是不是搞错了”别急老王如果故事到这里就结束那确实是二叉树赢了。但B树之所以是B树恰恰因为它解决了这个问题——这正是理解多叉到底好在哪的真正关键第三章关键的反转——这笔账分场景算结果完全不同老王刚才的算法犯了一个致命的疏忽他默认节点内部挨个比较和走一层的代价是一样的。可在真实世界里它俩的代价天差地别这里就要请出上一篇那个贯穿始终的关键背景——“速度鸿沟”。3.1 重新认识两种代价天壤之别回顾速度鸿沟节点内部的比较是在**内存或CPU缓存**里进行的——快如闪电纳秒级走过一层从一个节点跳到下一层节点在B树的硬盘场景里意味着要去硬盘翻一次页——慢如蜗牛毫秒级两者的代价相差成千上万倍明白了这一点老王刚才那笔账就要彻底重算了因为总比较次数根本不是重点翻盘次数也就是层数h才是真正烧钱的大头3.2 在硬盘场景下重算这笔账我们给两种代价标上真实的价码走一层翻一次盘昂贵记作 10000 个单位时间节点内比较一次廉价记作 1 个单位时间。现在重算总耗时总耗时 层数×翻盘代价 总比较次数×比较代价┌──────────────┬─────────────────────┬──────────────────┬─────────────┐ │ 分岔数 m │ 翻盘耗时(h×10000) │ 比较耗时(总比较×1) │ 总耗时 │ ├──────────────┼─────────────────────┼──────────────────┼─────────────┤ │ 2 (二叉) │ 30 × 10000 30万 │ 60 │ ≈ 30万 │ │ 1000 (千叉) │ 3 × 10000 3万 │ 3000 │ ≈ 3.3万 │ └──────────────┴─────────────────────┴──────────────────┴─────────────┘反转发生了在硬盘场景下千叉树约3.3万比二叉树约30万快了将近10倍为什么因为真正烧钱的是翻盘。千叉树虽然在内部多比较了3000次可这3000次比较加起来3000单位也微不足道——它换来的是翻盘次数从30次降到3次省下了整整27次昂贵翻盘27万单位用廉价的内存比较去换昂贵的硬盘翻盘这笔买卖赚翻了老王恍然大悟一拍脑门“我懂了我刚才那笔账算错错在把’内部比较’和’翻盘’当成一样贵了真实世界里翻盘贵得离谱内部比较几乎免费——所以拼命减少翻盘压低层数哪怕内部多比较点也是天大的划算”3.3 还能更妙内部也不必挨个比较更何况B树节点内部那一排路标是有序排列的所以根本不用挨个比较可以用我们之前学过的二分查找——在1000个有序路标里最多比较约log₂(1000) ≈ 10次就能定位千叉树重新精算内部比较 每层内部用二分查找最多约10次而非1000次 总比较 3层 × 10次 30次而非3000次 内部那点比较更加微不足道了至此账彻底算清了多叉树在硬盘大数据场景下是碾压性的胜利。它把要命的翻盘次数压到极低而代价内部多比较几次几乎可以忽略不计。第四章那……分岔越多越好吗——物极必反的智慧老王彻底服气了可他这个爱较真的人又冒出一个新念头“既然多叉这么好那我把分岔搞到100万、1亿岂不是树只要1层一步到位、天下无敌”慢着老王这就走到另一个极端了。分岔并非越多越好这里藏着一个微妙的度。我们来看看分岔无限增大会出什么问题4.1 极端一分岔太多胖节点自己都装不下了别忘了一个节点是要被一次性读进内存或读进一个硬盘页的。硬盘每次读取有一个固定的页大小比如4KB或16KB。一个节点能存多少路标是受这个页大小物理限制的如果你硬要一个节点存100万个路标它根本塞不进一个硬盘页——结果就是读一个节点本身反而要翻好几次盘这就本末倒置、得不偿失了。4.2 极端二退化成了数组想象一下如果分岔数 m 大到等于数据总量 N那么——整棵树就只有1层所有数据全挤在这一个节点里。这时候它还是树吗不它退化成了一个巨大的有序数组查找它就等于在一个大数组里查找那棵树的分层导航优势荡然无存。4.3 黄金法则让一个节点 一个硬盘页所以B树选择分岔数的真正智慧是一个精妙的匹配黄金法则让一个节点的大小恰好等于一个硬盘页的大小。这样每翻一次盘读一个页就刚好读出一个完整的节点——不多读、不少读每一次昂贵的翻盘都物尽其用在这个前提下把节点尽量塞满分岔尽量多就能让树尽量矮。分岔太少(如二叉)树太高 → 翻盘太多 → 慢 分岔适中(填满一页)树矮 每次翻盘物尽其用 → 最快 分岔太多(超过一页)节点装不下 → 读一个节点反要多次翻盘 → 又慢了 最优解让一个节点刚好填满一个硬盘页恍然大悟原来分岔多少不是越大越好而是有一个由硬件硬盘页大小决定的黄金分岔数。B树的设计者正是让节点大小精准匹配硬盘页才找到了那个树最矮、翻盘又物尽其用的最佳平衡点。这是一种看硬件下菜碟的极致务实。第五章终极总结——一张表看懂二叉 vs 多叉老王把这几天算的账全部浓缩成了一张表贴在墙上┌────────────┬──────────────────┬──────────────────────┐ │ │ 二叉树(分2岔) │ 多叉树(分上千岔) │ ├────────────┼──────────────────┼──────────────────────┤ │ 树的高度 │ 高(10亿→30层) │ 矮(10亿→3层) │ │ 翻盘次数 │ 多(30次) │ 少(3次) │ │ 单节点大小 │ 小(存1个数据) │ 大(存上千个,填满页) │ │ 内部比较 │ 少(每层比1-2次) │ 多(每层比几~几十次) │ │ 适合场景 │ 数据全在内存 │ 数据在硬盘(大数据) │ │ 谁是瓶颈 │ 比较次数(CPU) │ 翻盘次数(硬盘I/O) │ └────────────┴──────────────────┴──────────────────────┘老王对着这张表悟出了全文的题眼原来’二叉好还是多叉好’根本没有标准答案——它全看你的’瓶颈’在哪儿如果数据全在内存里比较’是瓶颈那二叉树的简洁就够好可一旦数据大到要存硬盘翻盘’成了要命的瓶颈那就必须用多叉树拼命压低层数、减少翻盘——哪怕节点内部多比较几次也在所不惜关键不是’分几个岔’,而是——‘你到底在跟谁较劲’尾声分几个岔的智慧亦是人生的智慧老王这场较真从多叉到底好在哪的疑问出发算了高度账、算了胖节点账又在速度鸿沟前完成惊天反转最后悟出黄金分岔数的物极必反——终于把这笔二叉与多叉的账算得明明白白。但当我们合上算盘会发现这分几个岔的背后竟也盘算着几分耐人寻味的人生哲理。第一看似吃亏的选择可能正是大赚的智慧。多叉树主动让节点变胖、内部多比较几次单看这一步简直是吃亏可它换来的是翻盘次数的暴跌、整体效率的飞升。这何尝不是人生的智慧我们常常在某个局部斤斤计较——不肯多花一点功夫、不愿在小处吃一点亏。可真正的高手懂得在廉价的地方慷慨地多投入一点去换取昂贵的瓶颈上的巨大节省。算账不能只盯着眼前这一笔敢在小处吃亏往往是为了在大处大赚。这是一种着眼全局的格局。第二没有绝对的好只有是否匹配你的瓶颈。二叉好还是多叉好答案是看场景——内存里二叉够用硬盘上必须多叉。脱离了瓶颈在哪去争论谁更好是毫无意义的。这给我们一个深刻的提醒生活里也没有放之四海皆准的最优解。别人成功的方法未必适合你某个被奉为圭臬的真理换个场景就可能失灵。真正的清醒是先看清我此刻真正的瓶颈是什么再去选那个最匹配它的方案——而不是盲目追随某个看起来最好的答案。对症才能下药。第三“物极必反”最好的不在两个极端而在那个匹配点。分岔不是越少越好二叉太高也不是越多越好撑爆硬盘页而是有一个由硬件决定的黄金匹配点。这正是中国人讲了千年的中庸智慧——过犹不及。太多的事情我们容易一条道走到黑要么畏缩不前要么用力过猛。而真正的智慧往往不在某个极端的尽头而在那个与现实条件恰好匹配的平衡点上。找到那个刚刚好比一味地更多或更少难得多也高明得多。下次当你惊叹于数据库从几十亿条记录里唰地一下翻出你要的答案时请记得——在那看不见的深处有人曾为一个节点该分几个岔反复算账、精心权衡让每一个胖节点都恰好填满一个硬盘页让每一次昂贵的翻盘都物尽其用才换来了你眼前那份理所当然的飞快。“二叉还是多叉”就是这门关于看清瓶颈、舍小取大、恰好匹配的、精细而深刻的智慧。它告诉我们没有绝对的好坏只有匹配与否敢在廉价处多花方能在昂贵处大省而最优的答案永远不在极端而在那个与现实恰好匹配的平衡点。它像一句朴素的箴言提醒着我们——别只盯着眼前一笔的亏要算清全局那笔赚别争论抽象的谁更好要看清此刻瓶颈在哪别一味追求更多或更少要找那个恰好匹配的点——一个懂得看瓶颈下菜、于匹配处发力的人才能像那棵分岔得恰到好处的树任凭数据如海、难题如山也总能以最省的力气翻到那个最对的答案。这就是藏在一个节点分几个岔背后的那笔账最深、也最美的浪漫。