树系列第 13 篇：从内存到磁盘——为什么需要 B 树

欢迎来到“树系列”第 13 篇。第 11、12 篇我们把红黑树从头到脚拆了一遍：五条性质背后的直觉、黑高的算法、插入修复的三种情况、删除修复的双黑问题，还有 2-3-4 树视角下的统一解释。按理说，红黑树已经是平衡树里的“优等生”了——Java 的 TreeMap、C++ 的 std::map、Linux 内核的进程调度器都选了它。可你有没有想过一个奇怪的问题：MySQL、PostgreSQL、MongoDB 这些数据库的索引，为什么几乎不用红黑树？ 同样是“查找键、插键、删键”，同样是 O(log n)，数据库偏偏选择了另一种长相完全不同的树——B 树。本篇要回答的，就是这个问题：当数据结构从内存搬到磁盘，什么变了？为什么“平衡”突然不重要了，“矮”才是第一优先级？B 树又是怎么用“一个节点多存几个键”这种朴素招数，把树的层数从三十层压到四五层的？

在进入正题之前，先把本篇的立场说清楚：B 树不是红黑树的“升级版”，两者解决的是不同约束下的同一个问题。红黑树面对的是“指针跳转很便宜、节点很小”的内存世界；B 树面对的是“一次访问很贵、一拿就是一整块”的磁盘世界。理解了这个世界观的差异，B 树的每一处设计——多路、大节点、叶子同层——就都变得顺理成章，而不是需要死记的教条。

0 本篇路线图

本篇的整体思路是先制造矛盾，再解决矛盾。第 1 节讲一个具体的故事：一张一亿条记录的表，在内存里用红黑树明明好好的，为什么数据库不这么干？第 2 节是全文最关键的背景知识，我们用量级数字看清内存与磁盘的差距，理解“按块读写”和“顺序读 vs 随机读”这两条磁盘世界的铁律。第 3 节把两条铁律翻译成树的语言：磁盘上每往下一层都是一次 IO，所以“矮”比“平衡”重要得多，红黑树的二十多层对磁盘来说太深了。第 4 节给出解决方案的直觉：一个节点多存几个键、多带几个孩子，把二叉变成 m 叉，层数立刻从 log₂n 降到 logₘn。第 5 节给出 B 树的严格定义：阶数、键数范围、叶子同层，并和二叉搜索树逐条对照。第 6 节算一笔具体的账：m=100 时，十亿条数据只需要四五层，配一张计算表让你自己也能心算。第 7 节把“大节点”和“磁盘页”接上头，解释为什么一次 IO 读入整个节点是划算的。第 8 节提供可动手体验的可视化 iframe。第 9 节澄清几个流传很广的误解。最后是速查表、自测题和下一篇预告。

路线图是一条严格的因果链：前面每一节暴露出的问题，都由后面一节解决。看懂这条链，你就知道 B 树的每个设计都不是孤立的技巧。

注意这张图里的箭头方向就是文章的论证方向：第 2 节的“IO 差距”是第 3 节“矮更重要”的原因，而第 3 节的“矮”又直接推出第 4 节的“多路”。B 树的每一个设计，都能在这条链上找到它要解决的问题。

1 一亿条记录的故事

1.1 内存里的红黑树：一切正常

先从一个具体场景出发。假设你有一张用户表，里面存着一亿条用户记录，每条记录带一个整数主键 id 和其他字段。业务上最常见的操作之一，就是按 id 查某条记录：SELECT * FROM users WHERE id = 8848。为了不扫描整张表，你需要一个索引——本质上就是一个从 id 到记录位置的映射。

如果这张表整个住在内存里，用红黑树做这个映射，会发生什么？一亿条记录，n 约等于 10⁸，红黑树的高度大约是多少？log₂(10⁸) ≈ 26.6，也就是说从根走到叶子，平均要经过 27 层左右的节点；最坏情况下，红黑树允许最长路径达到最短路径的两倍，所以最坏层数可以到 50 多层。每次从父节点走到孩子节点，不过是一次内存指针跳转，耗时大约 100 纳秒（0.1 微秒）。27 层乘 0.1 微秒，一次查找大约 3 微秒。

3 微秒意味着什么？它意味着单线程每秒可以轻松完成几十万次这样的查找，多线程加缓存优化之后还能更快。对于内存数据库、缓存系统来说，这个速度完全够用。红黑树在这个场景里表现优异，而且它的插入、删除也都有稳定的 O(log n) 上界，不会像裸 BST 那样退化。看起来一切都很完美。

这里的关键是“每层代价”只有 100 纳秒：即便层数多到 27，总耗时依然在微秒量级。下一节把同样这棵树搬到磁盘上，每层代价变成毫秒量级，同一个“27”就会变成灾难。

1.2 数据库的困境：数据放不下

那数据库为什么不用红黑树？第一个直白的原因：数据放不进内存。一亿条记录，假设每条 200 字节，就是 20 GB。如果索引再存一份键和指针，又得加几个 GB。20 多 GB 的内存不是买不起，但你要知道数据库通常不只有一张表：一亿用户的表、十亿订单的表、几十亿日志的表，全都想常驻内存的话，内存账单会飞速膨胀。而同样 20 GB 的磁盘存储，成本只有内存的几十分之一。

更本质的问题是：磁盘上的数据，不能按内存的方式访问。内存可以按字节随机访问，磁盘却有自己的脾气——它按块读写，而且每次访问的延迟比内存慢几个数量级。于是“把红黑树整个搬到磁盘上”这个想法，在纸面上行得通，实际跑起来却是灾难。灾难是怎么发生的？我们先用最简单的模型感受一下。

红黑树是“节点 + 指针”的结构：每个节点存一个键、两个孩子指针。如果这棵树存在磁盘上，节点就要分布在磁盘的不同位置。查找一个键时，你需要从根节点出发，根据比较结果跳向某个孩子；跳之前必须先把这个孩子所在的磁盘块读进内存。换句话说，树的每一层，都需要一次磁盘随机 IO。

1.3 数据库为什么不用红黑树

一次磁盘随机 IO 要多久？机械硬盘大约 5～10 毫秒，就算用上当前最快的 NVMe 固态硬盘，随机读 4KB 的小块也要大约 20～100 微秒。我们取一个中间值：就算 0.1 毫秒一次。红黑树平均 27 层，一次查找就是 27 次随机 IO：27 × 0.1 毫秒 ≈ 2.7 毫秒。听起来好像也还行？别忘了这是固态硬盘的乐观估计；如果是机械硬盘，27 × 10 毫秒 ≈ 270 毫秒——一次单点查询就要 0.27 秒，一秒只能查三四次，而生产数据库的要求是每秒处理几万甚至几十万次查询。

这就是数据库不把红黑树当索引的根本原因：红黑树的高度是按“指针跳转便宜”设计的，而磁盘上的每一次下探都要付出一次完整 IO 的代价。树有多高，查找就要做多少次 IO；在内存里毫不在乎的层数，搬到磁盘上就成了致命的延迟。

这张图的因果链值得记住：不是树的结构变了，而是“每下一层”的单价变了。数据结构本身没有变坏，变坏的是它赖以生存的访问成本模型。

故事到这里就讲完了：不是红黑树不好，而是它“生在内存、活在内存”，遇到磁盘就水土不服。接下来两节，我们把磁盘的脾气彻底搞清楚，因为 B 树的所有设计都建立在这两条铁律之上。

1.4 数据规模再放大：从亿到万亿

有人可能觉得“一亿条”还不够刺激，我们顺手把规模推到万亿（10¹²）看看。红黑树 log₂(10¹²) ≈ 40，也就是说内存里走 40 层指针，磁盘上就要 40 次随机 IO；机械硬盘 40 × 10 毫秒 = 400 毫秒，一个查询半秒钟，这在任何生产系统里都是不可接受的。B 树呢？m = 100 时，log₁₀₀(10¹²) = 6，加上根节点也就 6～7 层；就算 m = 1000，log₁₀₀₀(10¹²) = 4，四五次 IO 就够。数据量扩大一千倍，B 树的层数只增加一两层——这个“对数底数”的威力，就是数据库敢于宣称“万亿级数据也能毫秒级查询”的底气来源。

这里顺便澄清一个常见困惑：log₂n 和 logₘn 都是 O(log n)，为什么我们如此在意常数？因为在内存里，O(log n) 的常数是“几十次纳秒级比较”，无所谓；在磁盘上，常数直接变成“几十次毫秒级 IO”，必须压到个位数。算法分析里常被忽略的常数，在 IO 世界里就是生死线。

1.5 那内存数据库为什么还敢用红黑树

既然 B 树这么好，为什么 Redis、Memcached 这类内存数据库还是大量使用哈希表、跳表、甚至类似红黑树的结构？答案就在本篇反复强调的前提里：它们的访问成本模型是“内存模型”。内存里一次指针跳转约 100 纳秒，跳 30 层也才 3 微秒，红黑树完全够用；而哈希表在内存里等值查找更快，跳表对并发友好、实现简单。换句话说，内存数据库没有“磁盘页”这个约束，也就没有“必须把节点装满一页”的压力，B 树在内存里的优势只剩“缓存友好”一项，并不足以全面碾压其他结构。

这给我们的启发是：数据结构没有“全局最优”，只有“某个成本模型下的最优”。同一个 B 树，放在磁盘上是救星，放在纯内存场景里可能只是“还不错”；反过来，红黑树在内存里是标准答案，搬到磁盘上就成了灾难。学习时先问清楚“这个结构假设了什么访问成本”，比记住任何结论都重要。

2 内存 vs 磁盘：差几个数量级

2.1 数字先说话

要理解 B 树，先要把“内存快、磁盘慢”这句废话变成一组具体的数字。因为只有看清数量级，你才会相信“少一次 IO”值得用任何数据结构技巧去换。下面这张表是计算机存储体系的典型延迟，不需要背，只需要感受它们的相对关系：

存储层级	典型延迟	比上一级慢约
CPU 寄存器	约 1 纳秒	基准
L1 缓存	约 1 纳秒	与寄存器同量级
L2 缓存	约 4 纳秒	4 倍
L3 缓存	约 15 纳秒	4 倍
内存（DRAM）	约 100 纳秒	7 倍
NVMe 固态硬盘随机读	约 20～100 微秒	200～1000 倍
机械硬盘随机读	约 5～10 毫秒	5 万～10 万倍

这里的换算关系值得反复强调：1 毫秒 = 1000 微秒 = 100 万纳秒。内存一次访问 100 纳秒，机械硬盘一次随机访问 10 毫秒，两者相差 10 万倍。用生活化的说法，内存访问一次的时间，相当于机械硬盘访问一次时间的十万分之一。你平时觉得“数据库有点慢，等等就好了”，等的其实就是在攒这十万倍。

这张表还有一个隐藏结论：缓存与内存之间的差距远小于内存与磁盘之间的差距。从 L1 到内存差了大约 100 倍，从内存到磁盘差了 1000～10 万倍。所以计算机科学家们早就达成共识：内存层次的优化是“锦上添花”，磁盘层次的优化才是“生死攸关”。B 树就是为这最后一档差距而生的。

注意 SSD 虽然已经是固态介质，随机读依然要 20～100 微秒，比内存慢两到三个数量级；机械硬盘则慢五到六个数量级。B 树优化的不是缓存层，而是最底下这档最贵的访问。

2.2 按块读写：扇区与页

第二个关键事实是：磁盘和内存的读写粒度完全不同。内存按字节寻址，你读一个字节、四个字节、八个字节，成本差不多；但磁盘不能这样。机械硬盘的最小读写单位是扇区（sector），传统上 512 字节，现代大容量盘多为 4KB；操作系统和文件系统则按更大的页（page，通常 4KB）来管理数据；数据库系统又往往用更大的页，常见 8KB、16KB，InnoDB 默认 16KB。

这意味着什么？意味着你读 1 个字节和读一整页（4KB），耗时几乎一模一样。IO 延迟的大头在“寻道、旋转、传输准备”这些动作上，而不在数据量上。读 1 字节，你必须先定位到那个字节所在的扇区/页，把整块数据搬进内存，然后才能取用其中任意部分。既然如此，聪明的做法就变成了：每次 IO 尽量多带一点有用的数据回来，让这次昂贵的“出门”物有所值。

这块示意图里的“块 0～块 3”就是文件在磁盘上的物理摆放方式。B 树把“一个节点”做成“一块”，正是为了让这次昂贵的 IO 带回一个能直接使用、内部信息完整的结构，而不是只带回几十字节的键。

把“按块读写”和“随机访问慢”叠加起来，就得到了磁盘世界的第一条铁律：一次 IO 是昂贵的、粗粒度的，所以算法要尽量少发起 IO，并且每次 IO 都要满载而归。后面你会看到，B 树的节点设计简直就是为这条铁律量身定做的。

2.3 顺序读与随机读：差距同样悬殊

第三条要建立的认识是“顺序读 vs 随机读”。同样读 1MB 数据，如果这 1MB 在磁盘上是连续排列的，机械硬盘能以每秒 100～200MB 的速度流式读完；如果是散落在 1000 个不同位置的 1KB 小片，机械硬盘每秒只能完成几十到几百次随机 IO，有效吞吐可能连 1MB/s 都不到——差了两三个数量级。

为什么顺序读这么快？机械硬盘的磁头在连续读时只需要平滑移动，几乎不需要“重新定位”；固态硬盘没有磁头，但它的闪存组织方式同样偏爱顺序访问，而且控制器可以轻松预取连续数据、做并行化。反过来，随机读意味着每次都要“重新出发”：硬盘要找到新位置、建立新的传输状态，之前的一切预读、缓存优化全部失效。

数据库工程师因此总结出一条经验：顺序 IO 是朋友，随机 IO 是敌人。日志写入之所以快，是因为它是纯粹的追加、纯顺序；索引查找之所以难优化，是因为它天然随机。B 树的存在，本质上就是把“一次查找需要 27 次随机 IO”压缩成“几次随机 IO”，同时利用大节点让每次随机 IO 都带回大量后续有用的键。

这两条路径的差别最终会落进数据库的预读机制：顺序读可以被预取器成批拉入内存，随机读则完全无法预判。B 树在查找阶段只做几次随机读，而在范围扫描阶段（B+ 树的叶子链）又把读变成顺序读，两头都占了。

2.4 两个生活比喻：翻书与仓库取货

前面这些数字有点干，我们用两个比喻把它们串起来。

内存访问就像翻书。书就摊在你面前，你想看哪一行，目光移过去就行，快、便宜、随意。哪怕翻到第 500 页，也只是“目光一移”的事——当然，如果书有 500 页那么多，翻页还是要点时间的，但相对而言代价可以忽略。

磁盘随机访问就像从仓库取货。货架离你的工位有段距离，每次要取某样东西，你得走到货架前、找到货位、搬下来、走回来。这个“来回”的固定成本很高，而且不管你取的是一个小螺丝还是一整箱货，路费和时间是差不多的。于是聪明的仓库管理员会想：第一，尽量减少来回次数；第二，每次去，尽量搬一整箱回来，把箱子里可能用得上的东西都带回来。

把这两个比喻翻译回数据结构：红黑树是“翻书式”的结构，节点小、指针跳转便宜，层数多一点也不怕；B 树是“仓库式”的结构，一次取货很贵，所以树必须矮，而且每个“货箱”（节点）要尽量装得多。这就是 B 树设计哲学的全部起点。

2.5 带宽与容量：磁盘的另一张底牌

延迟之外，带宽和容量这两张底牌也值得看清，因为它们解释了“为什么不把整个索引都放进内存”。先说带宽：内存的带宽在数十 GB/s 量级，NVMe 固态硬盘的顺序带宽在 3～7 GB/s，机械硬盘只有 100～200 MB/s。差距依然存在，但顺序读的带宽其实没有延迟那么绝望——真正绝望的是随机读：机械硬盘随机读的吞吐常常只有顺序读的百分之一，因为每读一小块都要重新定位。

再说容量和价格。同样一笔预算，能买到的磁盘容量通常是内存的几十倍：一台普通服务器配 128～512 GB 内存很常见，但磁盘阵列动辄几 TB 到几十 TB。数据库的黄金法则是“数据尽量放内存、不得不落盘的才落盘”，可惜对大多数业务来说，全量数据就是落盘的命。索引作为数据的一部分，也必须默认“活在磁盘上、按页调入内存”，而不是假设自己可以整体常驻。

2.6 为什么不能靠“加大缓存”解决问题

有人会想：既然内存快，那我给数据库配一个大大的缓存，把所有热点页都留在内存里，B 树不就多余了吗？这个想法不算错，但缓存解决的是“重复访问”问题，解决不了“首次访问”问题。一个十亿行的表，索引键有十亿个，哪怕只有 1% 的键被反复访问，那也是千万个不同页面；更别说批量导入、冷查询、全表扫描会不断把新页拉进缓存，把旧页挤出去。

数据库缓冲池（buffer pool）确实能把根节点、上层节点这些“必由之路”长期留在内存，让大多数查找只打最后两层磁盘；但剩下的冷路径、新页面，仍然要老老实实走磁盘 IO。B 树的功劳，恰恰是把这些“躲不掉的 IO”从 30 次压到 4～6 次。缓存和 B 树不是竞争关系，而是互补关系：缓存让“常走的路”变快，B 树让“必须走的路”变短。

2.7 扇区、文件系统页、数据库页：三层“块”

“块”这个概念其实分三层，初学者经常混在一起。最底层是硬件扇区：机械硬盘和 SSD 固件层面的读写单位，通常 512 字节到 4KB，物理决定，改不了。中间层是操作系统页：文件系统和虚拟内存按页管理数据，主流是 4KB，由内核决定。最上层是数据库页：InnoDB 默认 16KB、PostgreSQL 默认 8KB，由数据库软件决定。

数据库为什么要用更大的页？因为数据库知道自己的访问模式：每次 IO 都要“带回来一个完整的 B 树节点”，8KB、16KB 的页正好装得下几百到上千个键；而 4KB 的系统页装不了那么多，一个节点就可能跨页，反而增加管理复杂度。数据库读写时通常绕过文件系统缓存（direct IO 或专用缓冲池），自己管理页的淘汰和刷盘，就是为了避免“文件系统缓存一层、数据库缓存一层”的双重拷贝和不确定性。

理解这三层页，你就能看懂很多数据库参数的来龙去脉：页大小、扇区对齐、innodb_page_size、fill factor，本质都是在回答同一个问题——“我的 B 树节点，应该和哪一层块对齐，一次 IO 应该带回多少键”。

3 “矮”比“平衡”更重要

3.1 磁盘上的每一次下探，都是一次 IO

现在把第 2 节的知识和树的结构合在一起。一棵树存在磁盘上时，节点就是磁盘上的数据块。查找一个键的过程是：读根节点（IO 1），比较后决定去哪个孩子；读孩子节点（IO 2），再比较、再下探……直到到达叶子或找到键。

关键观察来了：每次从父节点走向孩子，都必须先把孩子所在的块读进内存，也就是一次磁盘 IO。为什么不能把整棵树一次读进内存？因为树可能几十 GB，内存装不下；就算装得下，第一次全量加载也慢得离谱，而且数据还在不断更新。所以正常的工作方式是“用到哪个节点，才读哪个节点”，这就注定了树高等于一次查找的 IO 次数。

用一个具体的例子感受这句话的分量。假设查找目标藏在树的最底层，红黑树有 30 层：读根节点算第 1 次 IO，然后比较、读第 2 层，再比较、读第 3 层……一直到第 30 层才拿到答案。这 30 次 IO 之间没有任何一次可以“顺手”完成，因为每次都必须先知道上一层的比较结果，才知道下一块数据在哪里。也就是说，这 30 次 IO 是严格串行的，无法并行、无法预取、无法绕过。而如果树只有 5 层，同样的查找最多 5 次串行 IO——不是快了 6 倍，而是把“延迟账单”直接砍到六分之一，这就是“矮”的直接价值。

换句话说，对于磁盘上的树，树高不是“层数”，而是“延迟账单”。高度为 h 的树，单点查找最坏做 h 次 IO；高度减半，查找延迟就减半。所以在这里，优化的目标非常朴素：把树压矮，能压多矮压多矮。

3.2 红黑树：内存里的优等生，磁盘上的差生

红黑树在内存里是优等生，因为它的平衡规则保证了高度 O(log₂n)，且维护成本低。但把“O(log₂n)”这几个字展开成具体数字，磁盘世界就笑不出来了。

设 n = 10⁹（十亿条记录）。log₂(10⁹) ≈ 29.9，也就是说，即使树形理想，平均也要走大约 30 层；红黑树允许最长路径达到最短路径的两倍，所以最坏情况可以到 50～60 层。n = 10⁸（一亿条）时，平均约 27 层。这就是第 1 节故事里那个数字的来源。

30 层 × 每层一次随机 IO，是什么概念？机械硬盘上：30 × 10 毫秒 = 300 毫秒；固态硬盘上乐观估计：30 × 0.1 毫秒 = 3 毫秒。数据库每秒要处理成千上万个查询，而仅仅一次索引查找就花掉 3～300 毫秒，剩下的连接、解析、排序、写入全都不用做了。结论不是“红黑树坏了”，而是红黑树的平衡指标选错了维度：它优化的是指针跳转次数，而磁盘世界真正要优化的是 IO 次数，两者都叫“层数”，但代价差了十万倍。

这里要特别强调的是“串行”：查找必须等上一层比较完才知道下一块在哪，所以 30 次 IO 不能靠并行省时间，只能靠“少几层”来省。这也解释了为什么数据库把树高当成第一指标，而不是比较次数。

3.3 平衡的目标要重新定义

第 8 篇到第 12 篇，我们反复强调“平衡”的价值：二叉树如果退化成链，查找就从 O(log n) 变成 O(n)。这个结论在内存和磁盘上都成立，但磁盘上它只是底线，不是追求。在磁盘上，“足够矮”远比“绝对平衡”重要。一棵树哪怕左右子树高度偶尔差个一两层，只要整体层数从 30 压到 5，性能就是 6 倍的提升；反过来，一棵绝对完美平衡但层数 30 的树，仍然要被磁盘吊打。

所以 B 树的平衡策略也换了一种味道：它不是像 AVL 那样小心翼翼地维持“左右高度差 ≤ 1”，而是直接规定所有叶子必须在同一层。这个规定比任何平衡因子都简单粗暴，却也绝对有效：树的高度就是层数，不可能出现“某条路径特别长”的退化。代价是插入、删除时要维护“叶子同层”这个全局不变量——具体怎么做，第 14 篇讲分裂和合并时会看到。

3.4 一句话总结本节

把本节压缩成一句话：在磁盘上，树高就是 IO 次数，IO 次数就是延迟；所以“矮”是第一目标，平衡只是实现“矮”的手段之一。红黑树证明了“高度 O(log₂n)”在内存里够用，但 30 这个常数对磁盘太大。下一步，我们就要问：有没有办法让同样十亿条数据，树只有四五层？答案是：别再把节点设计成只装一个键了。

3.5 红黑树放在磁盘上：能用，但不划算

再补一个严谨的注脚：红黑树并不是“完全不能在磁盘上用”。如果节点也按页对齐，把几百个红黑树节点塞进一页，磁盘上的红黑树也能工作，甚至有些文件系统、内核结构真的这么干过。问题在于它“不划算”：每页塞进很多节点后，页内结构复杂，更新时要重写整页；更关键的是，红黑树的高度下限就是 log₂n，无论怎么优化页内布局，层数都不可能降到 logₘn 那个量级——除非你改变“一个节点一个键”的前提，而那恰恰就是 B 树。

所以“红黑树在磁盘上不行”的准确说法是：红黑树的树形结构决定了它的层数下限太高，而磁盘把每一层都标上了昂贵的价格。不是不能活，是活不起。B 树没有抱怨价格，它直接把“层数”这个需求量砍掉了一个数量级。

3.6 一次磁盘 IO 内部发生了什么

为了让你对“一次 IO 很贵”有更实在的体感，这里拆开一次机械硬盘随机读的时间账。假设要读 4KB：先是寻道（seek），磁头移动到目标磁道，约 2～4 毫秒；再是旋转延迟（rotational latency），盘片转到目标扇区，7200 转的盘平均约 4 毫秒；然后是传输，把 4KB 数据读出来，约 0.05 毫秒。加起来约 6～10 毫秒，其中传输只占 1% 不到——数据量几乎不参与决定延迟，这就是“读 1 字节和读 4KB 一样贵”的物理根源。

固态硬盘没有机械运动，但延迟也远高于内存：一次随机读要经过控制器排队、闪存页读取、纠错（ECC）等环节，常见 20～100 微秒。而且 SSD 的写入更麻烦，闪存要先擦除再写入，擦除单位（块）比读单位（页）大得多，所以 SSD 上的随机写尤其昂贵，数据库因此格外珍惜写 IO。知道了这些内部过程，你就明白为什么“少一次 IO”值得用任何手段去换：那不是少一次比较，而是少一次几毫秒的物理寻道。

4 多路树的直觉

4.1 一个节点为什么只能装一个键

先问一个看起来傻、其实很关键的问题：二叉树的节点为什么只装一个键、只带两个孩子？答案既不是数学必然，也不是“树本来就该这样”，而是历史惯性加内存假设：在内存世界里，节点小意味着指针跳转便宜，把键分散到更多小节点里没有任何坏处；教科书为了教学方便，也习惯从二叉讲起。

但请你想一想磁盘世界的账：一次 IO 读 4KB 和读 1KB 耗时几乎相同。如果每个节点只装一个键，那一次 IO 带回来的 4KB 里，绝大多数空间都是“浪费”的——你只用了其中几十字节的键和指针。更糟的是，为了装下 n 个键，你需要 n 个节点，树必然有 log₂n 层，也就是 log₂n 次 IO。

既然一次 IO 反正要搬一整块回来，为什么不干脆让一个节点装很多键、带很多孩子？这样一次 IO 读回来的整块数据里，全是能用的东西：几十个键可以立刻在内存里比较，几十个孩子指针指向下一层。树的“宽度”变大了，“高度”自然就矮了。这个想法朴素到几乎不需要数学：同样的 n 个键，塞进更宽的节点里，层数必然减少。

4.2 多路节点长什么样

多路节点（multi-way node）的结构很容易想象：它内部是一个有序的键数组，以及比键多一个的孩子指针数组。比如一个节点存 3 个键 k₁ < k₂ < k₃，它就带着 4 个孩子指针 c₀、c₁、c₂、c₃，含义是：

• c₀ 指向的子树里，所有键都小于 k₁；
• c₁ 指向的子树里，所有键都大于 k₁ 且小于 k₂；
• c₂ 指向的子树里，所有键都大于 k₂ 且小于 k₃；
• c₃ 指向的子树里，所有键都大于 k₃。

这个“键把值域切成一段段，每段对应一个孩子”的模式，和二叉搜索树完全同构：二叉搜索树是 1 个键切 2 段，多路节点是 d 个键切 d+1 段。所以多路树仍然是一棵“有序树”，中序遍历依然得到递增序列，只是每个节点内部多了一次内存里的顺序比较。

这张图揭示了“多路”和“有序”如何共存：只要键按升序排列，孩子数比键数多 1，中序遍历仍然是递增序列。B 树的所有操作——查找、分裂、合并——都在维护这个“键分隔区间”的不变式。

4.3 从 log₂n 到 logₘn：层数数学

现在用数学看收益。一棵满的二叉树，高度 h 能容纳的叶子数（或者说最底层的“位置数”）是 2ʰ；一棵每个节点最多 m 个孩子（m 叉）的树，高度 h 能容纳的位置数是 mʰ。反过来说，容纳 n 个键，二叉树需要高度约 log₂n，m 叉树只需要约 logₘn。

对数公式有一个简单的直觉：底数每扩大一倍，同样数据量下高度就显著变矮。log₂(10⁹) ≈ 30，而 log₁₀₀(10⁹) = 9 ÷ 2 = 4.5——也就是说，一个节点最多带 100 个孩子时，十亿条数据的树只需要四五层。这不是魔法，只是“每个节点多装一些”的直接后果。

这里的“容量”说的是最底层能放多少个叶子位置：二叉树每层翻一倍，四叉树每层翻四倍。把 2 换成 100，就是 B 树的日常——层数增长从此追不上数据量增长。

4.4 节点变大，比较变多，但那是内存的事

有人会担心：节点里存 99 个键，找孩子之前不得先做一堆比较吗？没错，但请看清楚这些比较发生在哪里——发生在内存里。一次 IO 把整个节点（比如 16KB）读进内存之后，在 99 个键里找目标位置，用二分查找只需要大约 7 次比较，每次比较不到 1 纳秒，合计不到 10 纳秒。而这次 IO 本身花了 20 微秒到 10 毫秒。10 纳秒对比 10 毫秒，相差一百万倍。

所以“节点内比较多”在磁盘世界里根本不是问题，甚至可以说是免费的：只要把比较都集中到内存里做，IO 次数才是唯一值得心疼的指标。这个认识是 B 树“大节点”设计的底气：宁可在内存里多做一百次比较，也不肯多发起一次磁盘 IO。

4.5 直觉小结

多路树的直觉可以浓缩成三句话：第一，一次 IO 能带回一整块，所以节点应该尽量装满；第二，节点越宽，树越矮，IO 次数越少；第三，节点内的比较发生在内存里，便宜得可以忽略。带着这三句话，我们终于可以给 B 树下定义了——它不是某一种具体的树，而是把“多路 + 矮 + 叶子同层”这几个原则制度化的一族树的统称。

4.6 一次 IO 的“利用率”账

为了把“节点要装满”这句话算成具体的钱，我们算一笔利用率账。假设磁盘页是 4KB，每个“键 + 指针”单元占 16 字节，那么一页最多装 256 个单元。如果这页装的是一个红黑树节点（1 个键、2 个指针，占 48 字节左右），那么这次 IO 带回来的 4KB 里，只有大约 1.2% 是真正有用的数据，其余 98.8% 都被浪费了。如果这页装的是一个 B 树节点（最多 255 个键、256 个指针），利用率可以超过 90%。

换个说法：同样一次 IO，红黑树只能推进“一个决策”（去左还是去右），B 树却能在内存里完成“最多 256 个键的二分查找”，一口气排除掉一整块值域。一次出门办一件事和一次出门把整箱货搬回来，这就是利用率账的本质。B 树从来没有让单次 IO 变便宜，它只是让每次 IO 都变得更值钱。

4.7 那 m 能不能无限大

如果“节点越宽树越矮”，那 m 取一万、一百万行不行？理论上可以，工程上不行，原因有三个。第一，页容量是硬约束：节点必须装进一个（或少量）磁盘页，一页 8KB、16KB，减去键和指针的固定开销，m 的天花板就在几百到几千。第二，节点内查找成本会随 m 增长：虽然 log₂m 次比较增长很慢，但 m 大到百万级别时，二分查找需要的缓存行也会增多，内存比较不再是“免费”的。第三，更新成本：节点越宽，一次插入/删除需要搬移的键越多，分裂/合并波及的键也越多，写放大更严重。

所以工程上 m 不是越大越好，而是“刚好把一页装满”最好：键短、页大，m 就上千；键长、页小，m 就一两百。这个“由页大小反推 m”的过程，正是第 7 节要展开的内容。先记住结论：m 的取值是页容量、内存比较、写放大三方面权衡的结果，而不是越大约好。

把这张图记在心里，“为什么节点要装满”就不再是教条：一页能装的键越多，一次 IO 能排除的区间就越大，需要下探的层数就越少。B 树的大节点，本质上是把“IO 利用率”和“树高”两笔账同时做优。

5 B 树的定义

5.1 先看一棵具体的 B 树

定义之前，先看一棵真实的 B 树，阶数（order）m = 5，也就是每个节点最多 5 个孩子、最多 4 个键。为了画得清楚，图中每个节点用矩形表示，内部按升序列出键。根节点是 [20, 40]，它有三个孩子：左孩子存小于 20 的键，中孩子存 20 到 40 之间的键，右孩子存大于 40 的键。

看这棵树时请盯住三条特征：键有序、孩子数 = 键数 + 1、叶子全部同层。前两条保证“有序查找”，第三条保证“任何一次查找的 IO 次数都不超过树高”——这正是第 5.5 节要展开的“绝对平衡”。

请观察这棵树的三个特征：第一，每个节点里的键是有序的；第二，每个内部节点的孩子数恰好比键数多 1；第三，所有叶子（最底层那些节点）都位于同一深度——没有哪个叶子比别的叶子高一层或低一层。第三点正是 B 树“绝对平衡”的体现，它比红黑树的“近似平衡”强得多，也比 AVL 的“高度差 ≤ 1”更严格。

5.2 阶数 m 与键数范围

B 树的标准定义用“阶数 m”描述节点规模。不同教材对 m 的用法略有差异，最常见的一种约定是：

1. 每个节点最多有 m 个孩子，因此最多有 m−1 个键；
2. 除根节点和叶子外，每个节点至少有 ⌈m/2⌉ 个孩子，因此至少有 ⌈m/2⌉−1 个键；
3. 根节点至少 2 个孩子（除非整棵树只有根一个节点）；
4. 所有叶子在同一层；
5. 节点内部键升序排列，键把子树的值域切成互不重叠的区间。

还有另一种常见定义用“最小度数 t”（minimum degree），等价关系是 m = 2t。也就是说每个节点至少 t 个孩子、至多 2t 个孩子。教材里两种写法都常见，阅读时注意分辨即可，本质是同一个对象。

为什么要规定“至少半满”？这是 B 树保持“矮”的机制。如果允许节点无限瘦下去，一个节点只装一个键，B 树就退化成了普通二叉搜索树，层数回到 log₂n；如果允许节点无限胖下去，当然很好，但节点再胖也装不进一页磁盘。规定“至少半满”则是为了在删除后能通过“借键”“合并”控制空间利用率，同时保证任何时刻树的高度都有对数级别的上限。第 14 篇会看到，正是这条下界让删除时的合并操作有了明确的触发条件。

5.3 键区间与查找过程

在 B 树里查找一个键 x 的过程，和二叉搜索树只有一步之差：在二叉搜索树里，每个节点只有一次比较，结果决定“去左还是去右”；在 B 树里，节点内是一段有序数组，先在内存里用二分查找找到 x 应该在哪个区间，再顺着对应的孩子指针下探。如果某个节点里直接找到了 x，查找成功；如果一路下探到叶子仍然没有找到，查找失败。

算法：B 树查找（伪代码）
输入：根节点 root，目标键 x
输出：x 所在节点或“不存在”

node = root
while node 不是叶子:
    在 node 的键数组中二分查找 x
    若找到，返回该节点；
    否则得到区间 i，令 node = node.children[i]
在 node 的键数组中二分查找 x
若找到，返回该节点；否则返回“不存在”

注意这个过程中，每次循环只做一次磁盘 IO：把 node 所在块读进内存。节点内的二分查找、区间判断全部在内存完成，不产生新的 IO。所以一次查找的总成本就是“层数 × 单次随机 IO”，一个非常干净的公式。

注意失败的查找（例如找 46）也会走同样的 3 次 IO：因为所有叶子同层，成功和失败的代价完全一致。数据库喜欢这种“可预测的最坏情况”，查询计划的成本估算才有意义。

5.4 与二叉搜索树的对应关系

把 B 树和二叉搜索树放在一起对照，你会发现它们其实是同一族“有序查找树”的两种极端：

属性	二叉搜索树	B 树（阶 m）
每节点键数	恰好 1	⌈m/2⌉−1 到 m−1
每节点孩子数	恰好 2	⌈m/2⌉ 到 m
树高	log₂n 量级	logₘn 量级
平衡方式	颜色/平衡因子等旋转维护	强制叶子同层 + 分裂合并
查找每次下探	内存指针跳转	磁盘随机 IO
节点内查找	一次比较	内存二分查找

从这个表可以看出，B 树不是“另一个物种”，而是把二叉查找树的“节点内部”横向扩展开：一个 B 树节点，可以理解成一棵被“压扁”的微型二叉子树，其键数组的中序遍历顺序依然保持。如果你把每个多路节点重新展开成一棵二叉平衡子树，甚至可以得到一棵等价的“B 树化”二叉搜索树——这就是为什么 2-3-4 树（m=4 的 B 树）能和红黑树一一对应，第 12 篇结尾我们其实已经悄悄用过这个思想了。

5.5 所有叶子同层：B 树的“绝对平衡”

最后再强调一次“所有叶子同层”这条规则。它意味着从根到任何一个叶子的路径长度完全相同，不存在“某条路径短、某条路径长”的差异。这和 AVL 的“高度差 ≤ 1”、红黑树的“最长路径 ≤ 2 倍最短路径”都不一样：B 树要求的是字面意义上的等高。

为什么敢下这么重的手？因为在磁盘上，叶子同层带来的收益极其直接：所有查找的 IO 次数上界都一样，而且这个上界就是整棵树的高度。数据库的延迟承诺、查询计划的成本估算，都需要稳定可预测的 IO 次数，B 树的“绝对等高”让这一切变得简单。代价当然也有：为了维持等高，插入时节点满了要分裂，删除时节点空了要合并或借键，这些操作会沿着树向上传播。它们不便宜，但全部加起来，也比红黑树那种“每层一次 IO、共三十层”便宜得多。

5.6 在示例树上完整走一遍查找

定义看完，最好亲手走一遍。回到第 5.1 节那棵阶数 m = 5 的 B 树，我们来查找键 33。第一步，读根节点 [20, 40]，在内存里比较：33 大于 20 且小于 40，所以落在中间的孩子指针，指向 [25, 30, 35]；第二步，读 [25, 30, 35]，33 大于 30 且小于 35，走向第三个孩子，指向 [32, 33]；第三步，读 [32, 33]，在节点内二分查找，命中 33。整个过程 3 次 IO、3 次内存二分，节点内部比较的次数加起来不超过十几次。

再走一次失败的查找，找 46。根节点 [20, 40]：46 大于 40，走向右孩子 [45, 50, 55, 60]；在这个节点里，46 大于 45 且小于 50，走向第二个孩子 [47, 48]；在这个节点里没有 46，而且它已经是叶子，于是返回“不存在”。同样是 3 次 IO，失败查找和成功查找的代价完全一致——这正是“所有叶子同层”带来的可预测性。

你可能会注意到一个细节：查找过程中，我们从头到尾没有访问过任何“不相关的节点”，每次都能借助节点内的键数组精确排除一大片键。二叉搜索树是“每次排除半个键”，B 树是“每次排除一整段区间”，而且排除动作全部在内存里完成。这就是“多路”在查找效率上的直观体现。

5.7 插入一个键会怎样：分裂的直觉预告

定义讲完了，如果到此为止，你会觉得 B 树“不过如此”——但维持“所有叶子同层 + 键数有上下界”这两条规则，比看起来难得多。用一个预告提前感受一下：向一个已经满了的节点插入键会发生什么？

假设 m = 5，某个节点已经有 4 个键 [10, 20, 30, 40]，现在要插入 25。节点满了，不能再塞。B 树的答案是分裂：把节点从中间劈开，中间键（这里是 30）上提到父节点，左右各形成一个新节点。于是原来的一个满节点变成三个：父节点多了一个键、多了一个孩子，左右两个兄弟各装一半。如果父节点也满了，就继续向上分裂，最坏一路分裂到根；当根也被劈开时，树长高一层——但请注意，根分裂是唯一让 B 树变高的操作，而且所有叶子依然同层。

分裂的精髓在于“中间键上提”而不是“随便挑一个键上提”：只有中间键能同时充当左半区间的右边界和右半区间的左边界，上提后两棵子树依然满足键区间约束。这个规则在第 14 篇的插入走查中会反复出现。

删除则相反：节点键数跌破下界时，先向兄弟“借键”，借不到就与兄弟合并，合并可能让父节点少一个键，于是继续向上传播，最坏把树变矮一层。这一借一合、一分一裂，就是第 14 篇的主角。现在你只需要建立两个直觉：“满则裂、空则并”是 B 树维持规则的唯一手段，以及这些操作虽然会向上传播，但每次只影响一条路径，总代价仍然是 O(logₘn) 次 IO——与红黑树修复的传播结构惊人地相似。

5.8 B 树家族：2-3-4 树、B+ 树、B* 树

B 树不是一棵树，而是一个家族。你其实已经见过它的两个亲戚：第 12 篇里的 2-3-4 树，就是阶数 m = 4 的 B 树——每个节点最多 3 个键、4 个孩子，而且它和红黑树可以互相转换，这就是为什么当时我们用“2-3-4 树的视角”理解红黑树的分裂与合并，二者居然严丝合缝。

家族里另外两个重要的成员是 B+ 树和 B* 树。B+ 树我们已经多次预告：内部节点只存键、数据全在叶子、叶子链表串联，是主流数据库索引的最终形态。B* 树则更冷门：它在节点全满时不是立刻分裂，而是先尝试把键分给兄弟，让两个节点都保持较高占用率，代价是实现更复杂、更新路径更长。内存数据库有时还用 T 树——本质是“AVL 树 + 节点内数组”的混合体，牺牲一些平衡性换取缓存友好，但它仍然是内存模型下的设计，与磁盘 B 树不同路。

把这些名字串起来看，规律就清楚了：所有“B 字头”的树都在回答同一个问题——如何用多路节点、页对齐、低 IO 次数组织有序数据；不同变体的差别，只是“键放哪、叶子怎么连、满了怎么办”这些策略选项的不同组合。第 14 篇会把最常用的 B+ 树细节补齐。

6 具体数字账：十亿条数据到底几层

6.1 满节点情况下的层数

理论讲得再多，不如算一笔具体的账。设 B 树的阶数 m = 100，也就是每个节点最多 100 个孩子、最多 99 个键。假设节点都保持“满”的理想状态（每个节点 99 键、100 孩子），那么：

• 第 1 层：根节点，最多 99 个键；
• 第 2 层：最多 100 个节点，每个 99 个键，共约 9900 个键；
• 第 3 层：最多 100² = 10000 个节点，共约 99 万个键；
• 第 4 层：最多 100³ = 100 万个节点，共约 9900 万个键；
• 第 5 层：最多 100⁴ = 1 亿个节点，共约 99 亿个键。

所以十亿条数据（n = 10⁹），在节点全满的情况下只需要 4 层就能装下所有键——准确地说，到第 4 层已经能装约 9900 万，第 5 层能装 99 亿，所以十亿数据落在 5 层以内，实际查找时从根走到叶子最多 4～5 次 IO。这个数字和红黑树的 30 次形成鲜明对比：同样是十亿条数据，IO 次数从 30 降到了 5 以内，哪怕每次 IO 都按机械硬盘的 10 毫秒算，单次查找也从 300 毫秒降到 50 毫秒以内；用固态硬盘算，则是从 3 毫秒降到 0.5 毫秒以内。

注意这个“×100”就是 B 树与红黑树的分水岭：二叉树每层容量 ×2，数据量每翻一倍就得多一层；B 树每层容量 ×100，数据量要乘 100 层数才加一。数据从百万涨到十亿（×1000），B 树只多一两层。

6.2 更一般的计算表

把上面的推导推广到任意数据量，结论是：满节点时，树高 h 满足 mʰ⁻¹ 大致覆盖数据量，即 h ≈ 1 + logₘn。下面这张表列出了 m = 100 时不同数据量对应的层数（含根节点），以及红黑树在相同数据量下的平均层数，供你直观对比：

数据量 n	log₂n（红黑树平均层数）	m=100 的 B 树层数（约）
10³	10	2
10⁴	13	3
10⁶	20	3～4
10⁸	27	4～5
10⁹	30	4～5
10¹²	40	6～7

注意一个令人惊讶的事实：数据量从一百万涨到十亿，涨了一千倍，B 树的层数只从 3～4 涨到 4～5，几乎没怎么变。这正是“多路”的威力：每多一层，容量乘以 m（100），而不是二叉树的 2。数据库里“亿级数据只有 3～4 层 B 树”的说法，就是这么来的。

6.3 半满的最坏情况

有人会较真：上面算的是“节点全满”的理想情况，如果节点都贴着下界 ⌈m/2⌉ = 50 个孩子，层数会不会暴涨？答案是会变高一点，但不多。最坏情况下每个节点只有约 50 个孩子，树高大约是 1 + log₅₀n：十亿数据算出来是 1 + log₅₀(10⁹) ≈ 1 + 5.1 ≈ 6 层。也就是说，即使所有节点都只有一半满，十亿条数据的 B 树也不会超过 6 层——依然远优于红黑树的 30 层。

这个“半满也能打”的性质来自 B 树对节点容量的下界约束：每个内部节点至少 ⌈m/2⌉ 个孩子，意味着高度有 logₘₙ 量级的上界，常数最多比满节点情况多 1～2 层。数据库索引在长期随机插入删除后，节点平均占用率通常在 65%～70% 左右，对应的实际层数仍然只有 4～6 层。所以“B 树大约四五层”不是一个只存在于教科书理想条件下的幻觉，而是工程里真实发生的数字。

6.4 把账算到 IO 延迟上

最后把层数换算成延迟，直观感受收益。假设十亿条数据，每次随机 IO 用固态硬盘的 100 微秒计算：

结构	层数	每次查找的 IO 次数	预计延迟
红黑树（磁盘版）	约 30	约 30	约 3 毫秒
B 树 m=100	约 5	约 5	约 0.5 毫秒

如果换成机械硬盘（10 毫秒/次）：红黑树约 300 毫秒，B 树约 50 毫秒。别忘了数据库里还有缓存：根节点和上面几层几乎永远驻留内存，实际打到磁盘的往往只有最后 1～2 层。这意味着真实世界的单点查询，B 树索引常常只需要 1～2 次磁盘 IO，甚至 0 次（全在内存缓冲池命中）。红黑树呢？30 层里能缓存的也只是顶层，剩下的 20 多次 IO 躲不掉。这就是“矮”在工程上的全部意义。

6.5 用手算验证一遍层数公式

怕公式记不住？没关系，层数账其实只需要小学乘法。原理一句话：每一层最多能装下的键数 = 上一层的节点数 × 每节点键数。我们拿 m = 100、每节点 99 键来手算：

• 第 1 层（根）：99 个键；
• 第 2 层：根最多 100 个孩子，每个 99 键，最多 99 × 100 ≈ 10⁴ 个键；
• 第 3 层：最多 100² = 10⁴ 个节点，每个 99 键，最多约 10⁶ 个键；
• 第 4 层：最多 100³ = 10⁶ 个节点，最多约 10⁸ 个键；
• 第 5 层：最多 100⁴ = 10⁸ 个节点，最多约 10¹⁰ 个键。

所以：一百万条数据（10⁶），第 3 层就能装下，实际是 3～4 层；一亿条（10⁸），第 4 层装下，4～5 层；十亿条（10⁹），第 5 层装下，4～5 层。你会发现规律是“数据量每乘 100，层数才加 1”——这就是 m 叉树的指数底座。你甚至可以现场口算：任意数据量 n，先算 n 是 100 的几次方，再加一层根，就是大致层数。10⁹ = 100⁴·⁵，所以 4～5 层；10¹² = 100⁶，所以 6～7 层。

再补充一个反直觉的对比：数据量从 10⁶ 涨到 10⁹，涨了一千倍，B 树的层数只从 3～4 涨到 4～5；而红黑树的层数从 20 涨到 30。这中间的差距就是“底数”的差距：底数是 2 时，数据量每翻倍层数加 1；底数是 100 时，数据量每翻 100 倍层数才加 1。一千倍的数据增长，在红黑树那里是 10 层，在 B 树这里只有 1 层。数据库的容量扩展之所以“无感”，靠的就是这层“对数底数”的缓冲。

右侧三条虚线是这张图的核心：数据量从百万级涨到十亿级，B 树的高度几乎原地踏步。相比红黑树要从 20 层涨到 30 层，这个“底数”优势就是数据库容量扩展无感的来源。

7 B 树的“大节点”如何匹配磁盘页

7.1 一个节点 = 一页

第 6 节的数字账里有个隐含前提：每个节点得真的装得下那么多键和指针，而且装在一个磁盘块里。B 树的工程实现正是这么做的：节点大小按磁盘页/数据库页设计，一个节点恰好占一页（或多个连续页）。MySQL InnoDB 默认页 16KB，PostgreSQL 默认页 8KB，很多文件系统页 4KB；B 树节点就按这个尺寸来切。

为什么“一个节点 = 一页”这么重要？因为一次磁盘 IO 的最小有效单位就是页。如果节点比页小，一次 IO 读回来的整页里只有一小块是节点，浪费；如果节点比页大很多，读一个节点要多次 IO，又把节点内部查找的便宜优势抵消了。让节点和页对齐，就能保证每次 IO 恰好带回一个完整的、可以直接使用的节点，不多不少。

这张图要传达的工程原则是“粒度匹配”：节点的粒度就是页的粒度。这样每次 IO 带回来的数据能完整支撑一次节点内查找，既不会浪费带宽，也不会为了一个节点反复读页。

7.2 一页能装多少个键

我们来算一个具体的工程数字。假设键是 8 字节的整数，孩子指针 8 字节，那么一个 16KB 的节点大约能装 16000 ÷ 16 ≈ 1000 个“键+指针”单元，也就是说 m 可以取到 1000 左右（键数最多约 999，孩子最多 1000）。把这个 m 代进层数公式：log₁₀₀₀(10⁹) = 3，十亿条数据只需要 3 层！这就是为什么很多数据库教材里会出现“十亿数据，B 树 3 层”的经典说法——它既不是夸张，也不是玄学，纯粹是页大小、键大小和指针大小做除法得出的结论。

如果键是更长的字符串，比如平均 64 字节，加上指针一页只能装约 200 个键，m ≈ 200，十亿数据的层数也就 4 层左右。不管怎么算，结论都一样：只要节点对齐页，层数就在个位数。

7.3 一次 IO 读入，内部比较全在内存

节点与页对齐后，一次查找的完整流程是：

1. 读根节点：根通常常驻内存，0 次 IO；
2. 在内存里二分查找，确定去哪个孩子；
3. 需要时发一次 IO，把目标孩子所在页整个读入内存缓冲池；
4. 重复第 2、3 步，直到命中或到达叶子。

整个过程里，IO 次数只等于下探层数，而节点内部的键比较全部在内存完成。数据库还会把“刚用过的页”留在缓冲池里：热门的中间层节点、根节点、经常被访问的叶子页，都可能在内存里命中，进一步把平均 IO 次数压到 1～2 次。

这张图解释了“B 树索引为什么平均只要 1～2 次 IO”：数据库把根和上层节点长期留在缓冲池，真正的磁盘访问大多发生在最后两层。缓存和 B 树是互补的——缓存让常走的路变快，B 树让必须走的路变短。

7.4 缓存友好与局部性

大节点还有一个容易被忽略的好处：缓存局部性。红黑树每个节点很小，随机分散在内存/磁盘各处，缓存命中率天然低；B 树一个节点就是一块连续内存，读进内存后整个数组都在缓存行覆盖范围内，CPU 处理完这个节点之前，几乎不需要再碰别的内存。顺序扫描时，B 树的叶子节点更是相邻页连续排列，可以像读日志一样顺序预取，这就是 B+ 树（第 14 篇的主角）进一步把数据集中到叶子的原因之一。

简单说：B 树用“节点大”换来了“IO 少 + 缓存友好”，代价只是节点内多几次内存比较。在磁盘世界里，这笔交易划算得没有任何悬念。

7.5 写入也一样按页来：脏页与写放大

说完读，再说写。数据库里插入、删除一个键时，也要把受影响的节点读进内存、修改、再写回磁盘。写回的单位同样是页：一个节点只要改了一个键，整个节点所在的页都要重写。这看起来像浪费——改 16 字节却要写 16KB？没错，这确实是一种“写放大”，但它恰恰是“按块读写”规则的必然结果：磁盘不支持只写页里的一小段，最小写入单位就是整页。

B 树的应对之道是让这种浪费“可控且值得”：因为一个页就是一个完整的节点，重写整页意味着把“决策所需的全部键”都更新到位；而红黑树如果按页组织，一页里可能塞了几十个互不相干的小节点，改一个节点就可能殃及同页的其他节点，页面更新频繁且混乱。数据库引擎还会用缓冲池统一管理脏页：修改先落在内存页里，多个小修改攒成一页，再由后台线程批量刷盘；崩溃恢复用日志（WAL）保证“先记日志、后写数据”，避免半页写入破坏索引。

写放大的代价最终会体现为“每秒能刷多少页”的吞吐上限，这也是数据库调优时关注 innodb_page_size、页填充率（fill factor）的原因。但请记住总账：B 树把单次读写都控制在“一页、一次 IO、一个节点”的粒度上，付出的写放大是固定倍数；红黑树在磁盘上不仅要面对同样的页写入规则，还要先多付几十次读 IO——谁更划算，一目了然。

7.6 一页之内：键数组为什么要紧凑

还有一个实现层面的细节值得提：B 树节点内部的键和指针通常连续存放，形成紧凑数组，而不是链表。为什么？因为节点读进内存后，CPU 要在这个数组上做二分查找；数组的缓存局部性最好——连续的内存行能一次载入多个键，二分查找的每一步都在缓存里完成。如果节点内部用链表或散乱的小结构，每次比较都可能触发缓存缺失，把“免费的节点内查找”变得不再免费。

这个细节解释了 B 树工程实现中的很多选择：节点先分配一整块连续内存、键数组保持紧凑有序、插入删除时用 memmove 做局部搬移而不是重排整棵树。内存里的连续性和磁盘上的页对齐，本质上是同一个原则的两面：数据要成块、成段地组织，让每次访问都能覆盖尽可能多的有用信息。

7.7 节点里到底存什么：键、指针还是记录

一个常被问到的细节是：B 树节点里除了键，还存什么？答案取决于 B 树的变体。经典 B 树（也叫 B 树索引）里，每个键可以附带一条指向记录的指针（或记录所在页的页号），也就是说内部节点也能“命中即返回”。而 B+ 树把这条规矩改了：内部节点只存键和孩子指针，所有记录（或指向记录的指针）都放在叶子节点，叶子之间用链表串起来。

为什么数据库主流选择后者？因为把数据全部集中在叶子，带来两个实实在在的好处：一是内部节点可以装更多键，同样一页能容纳的“键+孩子指针”更多，树更矮；二是范围查询时，叶子链表让你拿到第一个命中后，可以顺着链表顺序扫下去，不需要反复回跳内部节点。代价是等值查找多一次“下到叶子”的 IO——但对磁盘来说，这一层的代价远远小于范围查询节省的几十次随机 IO。

此外还有“聚簇索引”与“二级索引”的区分：聚簇索引的叶子直接存整行数据（InnoDB 主键索引就是这样），二级索引的叶子只存“主键值”，查到后再回表。这些细节虽然超出本篇范围，但底层逻辑仍然是同一套 IO 账：每存一层间接，就多一次潜在的 IO；每次回表，就多一次随机读。理解了账，数据库的索引设计就不再是黑盒。

8 动手体验：搜索算法可视化

文字和图表之外，强烈建议你动手玩一玩可视化。下面的 iframe 是本博客的搜索算法可视化实验室，虽然它展示的是通用搜索算法，但“每一步访问一个位置”的节奏，能让你直观感受到“下探一次 = 访问一次”的成本模型：把访问位置想象成磁盘页，把步数想象成 IO 次数，你就能体会为什么树矮一寸、性能高一截。

如果你手边有任意数据库，也可以做一个实验：造一张一亿行左右的表（或用数据库自带的性能测试工具），建一个主键索引，然后反复执行单点查询，观察查询计划里的“rows examined”和响应时间。你会发现，无论表多大，通过 B 树索引的单点查询都只需要访问常数级别的节点——这正是本篇所有推理的工程印证。

8.1 可视化怎么“看”出 IO 成本

打开上面的 iframe 后，建议你换一种“观法”：先选择规模较大的数据（比如上千个元素），然后打开“单步”模式，观察算法每执行一步，高亮位置是怎么跳的。想象每一个高亮位置都是一次磁盘随机 IO，那么一次搜索的“步数”就是 IO 次数。你会立刻发现：每一步都横跨很远的距离、每次访问都要重新定位，这正是随机 IO 的感觉。B 树把这种“远距离跳跃”压缩到 4～5 次，靠的正是把大量相邻数据收进同一个节点，让一次访问覆盖一大片。

8.2 动手改一改：页大小对层数的影响

如果你愿意进一步动手，可以做一个简单的“纸上实验”：固定 10 亿个键，分别假设一页能装 100、500、1000 个键，用第 6 节的方法手算层数。你会发现：装 100 个键时约 5 层，装 500 个键时约 4 层，装 1000 个键时 3 层。层数对“每节点键数”极其敏感，而每节点键数又由页大小和键宽决定——这就是为什么数据库文档里总是强调“页越大，同样数据量下树越矮，但每页的内存开销也越大”，调优永远是在这二者之间找平衡。

8.3 三个值得自己做的延伸实验

如果想把本篇的直觉焊死在脑子里，推荐三个延伸实验，都不需要写复杂代码。第一个：找一张真实的表，用 EXPLAIN 看主键查询的访问方式，确认它走的是索引而不是全表扫描，再对比 WHERE 不带索引列时的行数——你会直观看到“树”和“扫全表”的差距。第二个：用任意语言实现一个“页式 B 树查找”的最小版本：把键分成若干页，每页存 100 个键，用文件读写模拟磁盘，统计一次查找读了多少页；再实现一个二叉搜索树版，同样按页存，对比页读取次数。第三个：把同一个数据集分别按“有序插入”和“随机插入”喂给裸 BST 和 B 树，观察树高变化——B 树无论插入顺序如何，层数都纹丝不动，这正是“叶子同层 + 满则裂”带来的确定性。

做完这三个实验，你对本篇的理解就不再是“听过 B 树”，而是“亲手验证过 B 树”。强烈建议至少完成第一个实验，它只需要一条 SQL。

9 为什么不是别的结构：有序数组、哈希表、跳表

讲到这里，一个合理的疑问是：为了让“查找”更快，世界上明明还有有序数组、哈希表、跳表这些选项，为什么数据库最后几乎都选了 B 树？这一节我们把候选者逐个请上来，看看它们在磁盘世界里各自输在哪里。这不是为了贬低它们——在内存世界里，这些结构都活得很好；我们只是想看清，B 树究竟满足了一组怎样的“组合需求”。

9.1 有序数组 + 二分查找

第一种候选是把所有键排好序，存进一个大数组，查找时用二分查找。这个方案的优点是极度紧凑：数据连续存放，顺序扫描快如闪电，二分查找本身也只要 O(log₂n) 次比较。但把二分查找搬到磁盘上，问题立刻暴露：二分查找每次“取中位”访问的都是数组里一个随机位置，而数组可能跨越成千上万个磁盘页，于是每次比较几乎都是一次随机 IO。n = 10⁹ 时，一次查找约 30 次随机 IO——和红黑树一样深，甚至因为数组里没有“上层节点”的概念，连缓存都救不了多少。

更致命的是插入和删除：有序数组的中间插入要把后面所有元素整体后移，最坏 O(n) 次页移动。对于一张每秒要写入几万行的业务表，这是不可接受的。所以有序数组只在“数据几乎不变、按序批量构建、只读查询”的场景里发光，比如排序后的静态快照、列式存储的压缩数据块。它适合做“归档索引”，不适合做“活索引”。

9.2 哈希索引

第二种候选是哈希表。按主键哈希到桶里，单点查找平均 O(1)，看起来完美解决“查找慢”的问题。哈希索引在内存里确实无敌，但数据库的世界里，查询远不止“等值查找”一种：WHERE id BETWEEN 100 AND 200、ORDER BY id、前缀匹配、范围扫描，全都依赖键的顺序关系。哈希函数把键打散得毫无规律，相邻的键散落在不同的桶里，这些查询一个都做不了。

更隐蔽的问题是局部性：哈希表里相邻的键，在磁盘上完全不相邻，范围查询退化成大量随机 IO；碰撞链也让一个桶的数据散落多处。而数据库索引不仅要“找到一条”，还要经常“顺着顺序走一截”。B 树/B+ 树因为键有序排列，既能等值查找，又能范围查找，还能顺序扫描，哈希表做不到这一点。这也是为什么数据库里哈希索引永远只是 B 树的补充：它服务“等值查询”这一种特殊场景，而 B 树服务全部场景。

9.3 跳表

第三种候选是跳表（skip list）。跳表用多层链表模拟“跳跃查找”：底层链表包含所有键，上面每一层按概率跳过一部分节点，查找时从最高层出发，逐层下降。在内存里，跳表是红黑树的有力竞争者，Redis 的有序集合就用它。但搬到磁盘上，跳表的软肋很明显：查找路径上的每一步，都要跳到链表里一个“随机”的节点，而每个节点在磁盘上的位置彼此无关。n = 10⁹ 时，查找需要约 30 次“跳跃”，也就是约 30 次随机 IO——和红黑树同一个量级。

跳表还有局部性差的问题：链表节点分散在磁盘各处，顺序扫描时无法连续预读；层与层之间的指针也增加了存储开销。虽然理论上可以设计“页式跳表”，但工程上不如 B 树直接：B 树天生就是“整页整页”组织的，不需要额外改造。

9.4 为什么最后是 B 树

把三个候选者的失败原因放一起，B 树胜出的原因就浮出水面了：它同时满足了四组需求——矮（IO 次数少）、有序（支持范围查询和排序输出）、动态（插入删除只影响局部路径）、块友好（节点天然对齐磁盘页）。这四件事分开看，每个候选者都能做到一两件，但只有 B 树把所有条件同时握在手里。

需求	有序数组	哈希表	跳表	B 树
查找 IO 少（矮）	否，约 30 次	是，约 1 次	否，约 30 次	是，约 4～6 次
键有序，支持范围查询	是	否	是	是
插入删除高效	否，O(n)	是	是	是
节点对齐磁盘页	是	否	否	是

这张图把“为什么是 B 树”压缩成了一个组合条件：查找 IO 少、键有序、插入删除高效、节点对齐页。前三个候选者都在某一个条件上输掉，B 树则把这四个条件同时握在手里——这也是第 14 篇讲 B+ 树时反复使用的判断框架。

当然，“数据库选 B 树”不等于“所有场景都用 B 树”：内存型数据库可能选跳表或红黑树，分析型数据库可能用列存和位图，写入密集的日志场景可能用 LSM 树（LevelDB、RocksDB、Cassandra 的选择）。这些选择各有各的 IO 账。但“通用关系型数据库的主索引”这个位置，B 树和它的表亲 B+ 树，至今几乎没有对手。理解了本篇的“矮 + 有序 + 块友好”三条标准，你以后看到任何新的索引结构，都能自己算这笔账了。

9.5 面试追问：把理解变成表达

B 树是面试高频题，面试官最喜欢顺着三个方向追问。第一个方向是“为什么不用二分查找”：要答出“二分查找每一步都是随机 IO，层数还是 log₂n，而且插入删除是 O(n)”，再补一句“静态只读数据用有序数组没问题，动态数据不行”。第二个方向是“B 树和 B+ 树的区别”：要答出“B+ 树内部节点只存键、数据全在叶子、叶子之间用链表相连，范围查询和顺序扫描更快，页利用率更高”，并说清楚这正是第 14 篇的内容。第三个方向是“怎么估算一棵 B 树的层数”：给出一页能装的键数 m、数据量 n，现场用 logₘn 心算——能当场算出来，说明你真的理解了本篇的数字账。

还有两个容易踩的坑值得一提。其一是把“B 树节点大小”和“树高”混为一谈：节点变大确实让树变矮，但页变大也让每次 IO 传更多数据、缓冲池能缓存的页变少，所以工程上不是越大越好。其二是把“IO 次数少”等同于“延迟低”：IO 次数少是延迟低的必要不充分条件，还要考虑缓冲池命中率、锁等待、网络和 CPU 开销。面试时主动说出这两层权衡，通常比背定义更能打动人。

10 几个流传很广的误解

10.1 B 不是 Binary，B 树不是二叉树的“B”

最常见的误解是“B 树 = Binary Tree 的缩写”。B 树显然不是二叉树，所以这个解释从一开始就不成立。关于 B 树的 B 到底代表什么，学术界没有定论：提出者 Rudolf Bayer 和 Edward McCreight 在 1972 年的论文里没有解释字母含义，民间流传的说法有 Balanced（平衡）、Boeing（波音，当时作者在波音研究所工作）、Bayer（作者姓氏）、Broad（宽阔）等。主流观点倾向于“B 就是 B，不特指任何单词”。考试或面试里，最安全的说法是：B 树是多路平衡查找树，B 不代表 Binary。

10.2 B 树比红黑树在任何场景都更强

这个说法只对了一半。B 树在“数据在磁盘/外部存储、以块为单位访问”的场景里完胜红黑树；但在纯内存场景里，结论要反过来。Java 的 TreeMap、C++ 的 std::map、Python 的有序集合底层都选红黑树或类似结构，而不是 B 树，原因有三：

第一，内存里指针跳转便宜，红黑树的“层数多”不再是主要矛盾，而它的“每次更新只动常数个节点、不需要像 B 树那样分裂合并”反而更简单；第二，内存分配器按小对象分配，红黑树节点小、更新局部，缓存行为虽不完美但够用；第三，标准库的接口是通用有序映射，红黑树的实现经过几十年打磨，简单可靠。

当然，现代工程也有“内存版 B 树”出现，比如 C++ 的 B-tree 容器、数据库内存引擎，它们利用“一个节点装多个键”的缓存友好性，在纯内存里也能赢过红黑树。但这属于实现层面的竞争，不是“红黑树错了”。正确的结论是：结构没有绝对的优劣，只有“访问成本模型”的匹配问题。内存便宜，红黑树够用；磁盘昂贵，B 树必须上场。

10.3 数据库索引就是 B 树

这个说法也不准确。关系型数据库最常用的是 B+ 树——它是 B 树的变种：内部节点只存键、不存数据，所有数据都集中在叶子节点，叶子之间用链表串联，特别适合范围查询和顺序扫描。MySQL InnoDB、PostgreSQL 的默认索引、SQLite、MongoDB 的默认索引，用的都是 B+ 树而不是经典 B 树。

那本篇为什么只讲 B 树？因为 B+ 树的“数据只存叶子”“叶子链表”这些设计，都是在 B 树“多路、矮、页对齐”的骨架上做的增量优化。先把 B 树为什么存在讲透，第 14 篇讲分裂、合并和 B+ 树时，你才能看到每一步变化背后的 IO 账。另外，很多传统教材和面试题里的“B 树”，讲的其实就是 B+ 树的亲戚，两者先分清、再比较，才不会混。

10.4 “十亿数据 3 层”是营销话术

不是话术，但也不能无条件当真。前面算过：16KB 页、8 字节键 + 8 字节指针，m 约 1000，满节点时十亿数据确实 3 层。但工程现实是：键可能很长、页可能更小、节点占用率只有六七成，所以真实层数常常是 4～6 层。而且“3 层”指的是索引树高度，不是查询延迟：磁盘 IO 本身、缓冲池命中率、锁和事务开销都会影响最终延迟。“3 层”是对数量级的陈述，不是对毫秒数的承诺。

10.5 B 树只适合“大”数据

还有一个反向误解：数据少时 B 树没用。实际上，即使只有一万条数据，B 树依然能工作得很好；数据库不会因为表小就切换索引结构，因为维护一套索引逻辑的成本远高于“多一层少一层”的收益。小表的 B 树往往整个根节点加一层子节点都驻留内存，查询照样是微秒级。B 树的价值在数据量大的时候最刺眼，但它并不是大数据专属的数据结构。

10.6 B 树只出现在数据库索引里

最后一个误解是“B 树是数据库的私产”。事实上，B 树无处不在：文件系统的目录索引（NTFS 的 B+ 树、ext4 的 htree）、操作系统的页缓存管理、NoSQL 引擎（RocksDB 的 MemTable 之外还有 LSM 的层次化设计）、搜索引擎的倒排索引辅助结构、版本管理系统的对象存储，都能看到 B 树家族的身影。凡是有“大量数据 + 必须按顺序访问 + 底层按块存储”的地方，B 树就会自然长出来。理解这一点，你就不会把 B 树当成“数据库知识点”，而会把它当成“存储系统的基本功”。

11 本篇小结与速查表

在速查表之前，用一小段话把全篇串起来。本篇的起点是一个看似矛盾的现象：红黑树在内存里那么优秀，数据库却不用它。解开矛盾的钥匙是“访问成本模型”的切换：内存里一次指针跳转只要 100 纳秒，磁盘上一次随机 IO 要 0.1～10 毫秒，两者相差 5～6 个数量级；磁盘还按页读写、偏爱顺序访问。于是“树高 = 延迟”这个等式在磁盘上变得生死攸关：红黑树 30 层 = 30 次随机 IO，数据库等不起。B 树的回答是改变树的形状——一个节点存多个键、多个孩子，把层数从 log₂n 压到 logₘn；再让节点大小对齐磁盘页，使一次 IO 恰好带回一个完整节点，节点内的比较全部在内存完成。十亿条数据、m = 100，B 树只要 4～5 层；页更大时甚至可以 3 层。而“所有叶子同层”这条看似霸道的规则，正是 B 树把“矮”变成硬保证的机制。下一站，我们将看到这套骨架如何支撑插入分裂、删除合并，以及为什么数据库最终青睐把数据全部放进叶子的 B+ 树。

离开之前，给你留一份“行动清单”：第一，能背出内存、SSD、HDD 三档延迟的数量级（100 纳秒 / 0.1 毫秒 / 10 毫秒）；第二，能解释“树高 = IO 次数”以及为什么 IO 次数是磁盘树的第一指标；第三，能手算任意 n 和 m 的层数（logₘn 加一层）；第四，能说清 B 树与红黑树的适用边界，以及 B+ 树“数据只在叶子”的设计动机。四条都过关，第 14 篇的分裂、合并和 B+ 树，你会学得异常轻松。

最后再说一句心里话：很多人学 B 树时被“阶数、分裂、合并”这些术语劝退，觉得它是一套全新的、更难的体系。但本篇想传递的真正信息是，B 树并不比红黑树更难，它只是换了一套评判标准：红黑树在“比较次数”上精打细算，B 树在“IO 次数”上精打细算。一旦你把目光从内存转到磁盘，B 树的每一个设计都顺理成章——多路是为了矮，矮是为了少 IO，大节点是为了匹配页，叶子同层是为了让 IO 次数可预测。理解了这四条，术语只是外壳，第 14 篇要讲的操作，不过是把这些原则落地的例行公事。

问题	一句话答案
为什么红黑树在磁盘上不行？	磁盘上每下一层树 = 一次随机 IO，红黑树 30 层意味着 30 次 IO，延迟爆炸
内存和磁盘差多少？	内存约 100 纳秒，机械硬盘随机读约 5～10 毫秒，相差 5～6 个数量级
磁盘读写的最小单位？	扇区（512B～4KB）、操作系统页（通常 4KB）、数据库页（8/16KB），读 1 字节和读整页耗时几乎相同
顺序读和随机读差多少？	机械硬盘下吞吐差两三个数量级；随机读每次都要“重新出发”
B 树为什么矮？	一个节点存多个键、多个孩子，层数从 log₂n 降到 logₘn
B 树的“绝对平衡”指什么？	所有叶子必须位于同一层
阶数 m 限制了什么？	每个节点最多 m 个孩子、m−1 个键；非根内部节点至少 ⌈m/2⌉ 个孩子
m=100、十亿数据几层？	满节点约 4～5 层，半满最坏约 6 层
节点大小怎么定？	对齐磁盘页/数据库页，一次 IO 恰好读入一个节点
节点内比较贵吗？	不贵，发生在内存，和一次 IO 相比可以忽略
B 代表 Binary 吗？	不是，B 树是多路树，B 的原始含义无定论
数据库索引用的是经典 B 树吗？	主流用 B+ 树：内部只存键、数据在叶子、叶子链表支持范围扫描

12 自测题

13 下一篇预告

本篇回答了“为什么需要 B 树”，但 B 树的故事才刚开个头：插入时节点满了怎么办？删除时节点空了怎么办？“所有叶子同层”这个硬规则，到底靠什么操作来维持？下一篇文章，我们将进入 B 树最精彩的操作部分：插入时的节点分裂（split）、删除时的借键与合并（borrow & merge），以及数据库真正使用的 B+ 树——为什么 B+ 树要把数据全部赶到叶子、给叶子串上链表，让范围查询像读日志一样流畅。

《树系列第 14 篇：B 树操作与 B+ 树》——敬请期待。