树系列第 14 篇：B 树操作与 B+ 树——数据库索引的秘密

欢迎来到“树系列”第 14 篇。第 13 篇我们回答了一个问题：为什么内存里近乎完美的红黑树，一到磁盘上就成了灾难？答案的核心是“访问成本模型”变了——内存里一次指针跳转只要 100 纳秒，磁盘上一次随机 IO 却要 0.1～10 毫秒，两者相差五六个数量级；磁盘还按块读写、偏爱顺序访问。于是 B 树登场：一个节点多存几个键、多带几个孩子，把层数从 log₂n 压到 logₘn，再让节点大小对齐磁盘页，使一次 IO 恰好带回一个完整的节点。第 13 篇把 B 树“为什么长这样”讲清楚了，但只讲了静态的样子：一棵已经建好的 B 树，长什么样、怎么查找。本篇要补上动态的部分：B 树是怎么长大的？插入时节点满了怎么办？删除时节点空了怎么办？ 更重要的是，我们要回答一个第 13 篇结尾留下的悬念——真正统治数据库索引的并不是经典 B 树，而是它的表亲 B+ 树。为什么数据库要把数据全部赶到叶子节点，为什么还要给叶子串一条链表？本篇会把这些秘密全部拆开。

如果说第 13 篇是“理念篇”，这篇就是“操作篇”和“实战篇”。我们不再只欣赏 B 树的美，而是亲手“操作”它：把一个键插进去，看着叶子节点撑破、中间键上提、父亲再撑破、上提到根；再把一个键删掉，看着节点变空、向左邻借、向右邻借，实在借不到就两兄弟合并。这些操作听起来像一套繁琐的礼仪，但只要你抓住两条核心原则，一切都顺理成章。第一条原则叫维持约束：B 树不是“想长什么样就长什么样”的树，它被阶数 m 严格约束着——每个节点最多 m 个孩子、至少 ⌈m/2⌉ 个孩子（根例外），所有叶子必须同层。第二条原则叫局部修复：任何插入删除，都只影响从叶子到根的一条路径，我们在这条路径上做分裂、借键或合并，就能把被破坏的约束补回来。这两条原则，加上“键是有序的”这一天然事实，就是整篇操作部分的全部骨架。

读完本篇，你应该能回答三组问题。第一组：B 树插入时，为什么是“先插叶子、满了就分裂”，分裂时为什么偏偏把中间键上提而不是最大键或最小键？根分裂为什么会让树长高一层？第二组：B 树删除时，什么情况下需要借键，什么情况下需要合并，借键和合并各自的触发条件是什么？第三组：B+ 树和 B 树到底差在哪几个点上——数据是不是只在叶子？叶子之间有没有链表？内部节点为什么“只存键不存数据”？这三组问题搞懂了，你再看 MySQL 的 InnoDB、PostgreSQL 的默认索引、NTFS 和 ext4 文件系统，会发现它们的选择全都说得通，不再需要死记结论。

0 本篇路线图

本篇的结构是“先操作，再升级”。第 1 节快速回顾第 13 篇的成果：B 树的阶数、键数范围、叶子同层这三条定义性约束，以及“节点对齐磁盘页”的工程设定；这一节也是全篇的记号基础，后面所有的分裂、合并图都要用到它。第 2 节讲 B 树的查找：这是所有操作的第一步，节点内用二分、节点间往下走，并用一张图完整走一遍查找路径，最后分析复杂度——层数决定 IO 次数，节点内比较只在内存里发生。第 3 节是重头戏之一：B 树插入。先讲“先插叶子”的基本流程，再讲溢出分裂的规则，接着看分裂如何沿路径向上传播，最后用 m=3（即 2-3 树）和序列 [1,2,3,4,5,6,7] 做一次完整的逐步走查，把每一步的树形都画出来。第 4 节讲 B 树删除，这是全篇最容易绕晕的部分，所以我们只做综述级处理：下溢的判断、借键的两种情况、合并的完整过程，配关键图例，不穷举所有边界。第 5 节切换话题，问一个关键问题：经典 B 树已经很好了，B+ 树到底优化了什么？答案有三个——范围查询、磁盘局部性、内部节点只存索引带来的更大扇出。第 6 节给出 B+ 树的完整结构：内部节点与叶子的分工、叶子的数据指针与兄弟链表，然后分别走一遍单点查找和范围查询，最后对比 B+ 树插入分裂与 B 树插入分裂的细微差别：叶子分裂“复制上提”，内部节点分裂“移动上提”，一字之差背后是搜索路径的语义差异。第 7 节讲工程现实：MySQL InnoDB、PostgreSQL、SQLite、MongoDB、NTFS、ext4 为什么都选 B+ 树家族，并解释聚簇索引与二级索引的区别。第 8 节把红黑树、跳表、B 树、B+ 树放在一张对比表里，看清“内存场景 vs 磁盘场景”的选型逻辑。第 9 节是可动手体验的 iframe。最后是速查表、自测题和下一篇预告。

路线图分成两半：第 1～4 节是“操作”（把 B 树玩熟），第 5～8 节是“升级”（从 B 树走到 B+ 树并落回工程）。前半段的每一次分裂、借键，都是后半段理解 B+ 树设计的前提。

这张路线图也暗示了阅读策略：如果第 3、4 节的分裂合并还没形成画面，不要急着跳到 B+ 树——后面所有“复制上提”“移动上提”的差异，都建立在先看懂 B 树操作的基础上。

1 回顾：B 树的定义

在动手操作之前，先把第 13 篇的核心结论压缩成一张“身份卡”。B 树是一棵多路平衡查找树：它不再是二叉树，每个节点可以拥有多个键和多个孩子；它也不是“大致平衡”，而是有一条近乎苛刻的硬规则——所有叶子必须位于同一层。这两点加在一起，构成了 B 树区别于红黑树、AVL 树最鲜明的外形。

1.1 阶数 m：孩子数的上限

B 树的定义离不开一个参数——阶数 m。一棵 m 阶 B 树满足：每个节点最多有 m 个孩子；非叶节点至少要有 ⌈m/2⌉ 个孩子；根节点比较特殊，它至少有 2 个孩子（如果树里不止一个节点的话）。孩子数定了，键数也就跟着定了：一个有 k 个孩子的节点，恰好存 k−1 个键，这些键把值域切成 k 个区间，每个孩子对应一个区间。因此 m 阶 B 树的键数范围是：非根节点最少 ⌈m/2⌉−1 个键，最多 m−1 个键；根节点最少 1 个键。

“阶数”这个词在教材里有两种用法，初学者经常踩坑。有的教材说“m 阶 B 树最多 m 个孩子”，键数上限 m−1，这是最常见、也是我们本篇采用的约定；另一种教材把阶数定义为“节点最多存多少个键”，那么孩子上限就变成 m+1。两种约定描述的是同一棵树，只是参数偏移了一位。读任何资料之前，先确认它用的是哪种约定，否则你会在“为什么是 ⌈m/2⌉ 而不是 ⌈(m+1)/2⌉”这种记号问题上浪费大量时间。本篇统一采用“m = 最大孩子数”的约定。

拿最小的非平凡例子来看：m=3 的 B 树，每个节点最多 3 个孩子、2 个键，非根节点至少 2 个孩子、1 个键。这正是著名的 2-3 树——每个节点要么有 2 个孩子（1 个键），要么有 3 个孩子（2 个键）。m=4 则得到 2-3-4 树：节点可以拥有 2、3 或 4 个孩子，对应 1、2、3 个键。红黑树那篇我们提到过，红黑树和 2-3-4 树在结构上是同构的：红黑树的一个“黑节点 + 若干红孩子”，对应 2-3-4 树里的一个多键节点。现在你拥有了 B 树的视角，回头再看红黑树，会多一层“原来如此”的感觉。

1.2 键的排布：有序且分隔

第二个定义性特征是键的有序排布。B 树的每个节点内部，键按升序排列；假设一个节点存了 d 个键 k₁ < k₂ < … < k_d，那么它有 d+1 个孩子 c₀、c₁、…、c_d，每个孩子是一棵子树，子树中的所有键严格落在对应的区间里：c₀ 中的键都小于 k₁，c₁ 中的键都在 k₁ 和 k₂ 之间，依此类推，c_d 中的键都大于 k_d。这正是二叉搜索树“左小右大”的推广：二叉搜索树用 1 个键切出 2 个区间，B 树用 d 个键切出 d+1 个区间。

这张图的关键是“区间”而不是“孩子”：分裂时上提中间键，本质上是在维护“每个孩子仍然对应一个连续区间”；合并时拉下父键，则是把两个相邻区间重新连成一段。整篇操作部分都在反复使用这个不变式。

这张图是理解 B 树一切操作的基础。分裂时为什么选中间键？因为只有中间键才能同时充当左半区间的右边界和右半区间的左边界，上提之后两棵子树依然满足“子树键全在对应区间”的约束。合并时为什么把父节点的某个键拉下来？因为两棵兄弟子树之间本来就隔着父节点里的这个分隔键，合并时它必须被“吞”进新节点，区间才能连续。可以说，B 树的每个操作都在维护一个不变式：键是分隔符，孩子是区间。

1.3 叶子同层：绝对平衡

第三个定义性特征是所有叶子在同一层。B 树没有“树高不平衡”的概念：从根到任意一个叶子的路径长度完全相同。这个性质从构造过程就保证了——树只会通过“根分裂”这一种方式长高，而根分裂会让全树所有叶子同时下移一层；树的变矮也只发生在“根合并”时，所有叶子同时上移一层。不存在“这棵子树比那棵子树高一层”的可能。

为什么这个看似霸道的规则如此重要？因为磁盘上树高就是 IO 次数。如果允许叶子散落在不同层，那么“最坏情况下要走多少层”就无法保证，也就无法给延迟一个确定的上界；而数据库和文件系统恰恰最讨厌“不稳定的最坏情况”——它们宁可每次都稳定地走 4 层，也不愿意平均 3 层、偶尔 10 层。红黑树允许最长路径是最短路径的两倍，这种“近似平衡”在内存里足够好；但到了磁盘上，两倍的差距意味着最坏情况会多出一倍的 IO，工程上不可接受。B 树用“叶子同层”把最坏情况直接焊死：插入删除之后，树要么还是这么高，要么整体长高/变矮一层，绝不出现局部的不平衡。

1.4 工程设定：节点对齐磁盘页

最后回顾一个工程性设定：B 树的节点大小通常对齐磁盘页或数据库页。InnoDB 的默认页是 16KB，PostgreSQL 是 8KB；文件系统块常见 4KB。一个节点恰好放在一个页里，一次磁盘 IO 读入整个节点，然后在内存里完成节点内部的比较。节点大、键多、扇出高，树就矮；但节点也不是越大越好，页太大意味着单次 IO 传输更多、缓冲池能缓存的页更少、分裂合并时的写放大更大。工程上要在“树高”和“页开销”之间找平衡，这个权衡在第 5 节讲 B+ 树动机时还会再出现。

回顾完毕。现在记号齐了：m 阶、键数范围、叶子同层、页对齐。接下来我们从最简单的操作开始——查找。

2 B 树查找：节点内二分，节点间向下

查找是 B 树所有操作的基础：插入要先找到该插进哪个叶子，删除要先找到该删哪个键，范围查询要先找到起点。好消息是，B 树的查找逻辑和二叉搜索树几乎同构，只是“一层比较一个键”变成了“一层比较多个键”。理解了查找，你就理解了 B 树为什么能如此自然地把“多路”和“有序”融合在一起。

2.1 查找算法的完整流程

给定一棵 m 阶 B 树和一个目标键 key，查找从根节点开始，反复执行下面的过程：

第一步，在当前节点内部找 key。节点里的键是有序数组，所以可以用二分查找：如果找到某个键等于 key，查找成功，直接返回；如果没找到，二分查找会告诉我们 key 应该落在哪个相邻区间——更准确地说，会给出第一个大于 key 的键的位置。

第二步，如果当前节点是叶子，说明树里没有这个键，查找失败。为什么可以立刻断言失败？因为 B 树的键都存放在所有节点里（经典 B 树中，内部节点和叶子都存键），而查找路径已经排除了所有可能包含 key 的区间，走到叶子还没找到，就证明整棵树都不存在该键。

第三步，如果当前节点是内部节点，根据二分得到的位置，选取对应的孩子指针，把当前节点切换为孩子，回到第一步。这里的关键是“选哪个孩子”：key 小于节点第一个键，走最左孩子；key 大于节点最后一个键，走最右孩子；key 夹在 kᵢ 和 kᵢ₊₁ 之间，走第 i 个孩子（从 0 开始编号）。

整个过程可以用一句话概括：在节点内部用二分确定方向，在节点之间沿着指针向下走。节点内部的比较再多次，都发生在内存里，和一次磁盘 IO 相比可以忽略；节点之间的每一下探，才是一次真正的磁盘 IO。所以 B 树查找的 IO 次数由树高决定，而比较总次数由“树高 × 节点内比较”决定。

2.2 配图走一遍：找 43

空谈流程不如亲手走一遍。假设有一棵 m=5 的 B 树，根节点存着键 20、40、60、80，下面挂着五棵子树。现在我们要查找 key = 43。查找过程是这样的：

第一次访问根节点：根里有 20、40、60、80 四个键。用二分比较，43 大于 20、大于 40，但小于 60，所以 43 应该落在 40 和 60 之间的区间，走第二个孩子（对应区间 (40, 60)）。这一步在根节点内做了两三次比较，然后下探一层。

第二次访问第二个孩子：这个节点存着 42、45、47 三个键。43 大于 42、小于 45，所以走 42 和 45 之间的孩子。注意，这里的“孩子”可能又是一棵子树。

第三次访问第三层的某个叶子：这个叶子节点存着 43、44 两个键（在经典 B 树中，叶子也存真实键）。二分比较，正好找到 43，查找成功。整趟查找访问了 3 个节点，也就是 3 次磁盘 IO；节点内部的比较加起来大约 6～8 次，全部在内存中完成。

注意“节点内比较”和“节点间 IO”是分开记账的：前者的次数再多也只消耗内存，后者的次数严格等于树高。数据库优化器给查询估成本时，算的正是后者。

如果把这条路径和二叉搜索树对比，你会看到本质一致、细节不同：二叉搜索树每层只比较 1 次、然后二选一走一边；B 树每层比较 log₂d 次（d 是节点内键数）、然后从 d+1 条路里选一条。层数上，B 树矮得多；比较次数上，B 树每层多一点。但在磁盘场景里，这个交换极其划算——因为比较是免费的，IO 是昂贵的。

2.3 复杂度：层数决定 IO，节点内比较决定 CPU

把上面的过程翻译成复杂度，需要两个视角。第一个视角是 IO 复杂度：一次查找访问的节点数等于树高 h。对于 n 个键、m 阶 B 树，树高大约在 logₘn 到 log_{⌈m/2⌉}(n/2) 之间，取决于节点利用率。用第 13 篇的账：m=100 时十亿条数据只要 4～5 层；即便节点利用率只有一半，也只要 6 层左右。也就是说，一次单点查找的磁盘 IO 次数是一个个位数，这是 B 树最核心的性能承诺。

第二个视角是 CPU 复杂度：每个节点内部用二分查找，节点最多 m−1 个键，所以节点内比较次数是 O(log₂m)；总共 h 层，总比较次数是 O(h·log₂m)。代入 h ≈ logₘn，得到 O(log₂n)——和二叉搜索树同阶。这说明 B 树没有在算法复杂度上“作弊”，它把同样的 O(log n) 比较次数分摊到了每个节点的内存比较里，同时用多路把 IO 次数压到了 O(logₘn)。在磁盘上，O(logₘn) 的 IO 是主矛盾，O(log₂n) 的比较是无关紧要的背景噪声；在纯内存里，这两项的相对权重反过来，这也正是第 8 节对比表要展开的选型逻辑。

还有两个细节值得提。第一个是“根节点驻留”：数据库缓冲池几乎总是把根节点和上层节点长期留在内存里，所以真实查询的磁盘 IO 常常比树高还要少 1～2 次，只有“冷路径”才需要把每一层的页从磁盘读进来。第二个是“二分 vs 线性”：节点内的键数组如果很小（比如只有几个键），线性扫描甚至比二分更快，因为分支预测和顺序访问在微架构上更友好；只有当节点键数较多（比如上百个）时，二分才稳定胜出。工程实现里两种都有，但复杂度分析上我们统一按二分来算。

2.4 查找的变体：前缀查找、范围查找、上下界

B 树查找不只有“精确命中”一种形态。数据库里大量查询是 WHERE name LIKE 'A%' 或者 WHERE age BETWEEN 20 AND 30，它们需要的是三种变体：

第一种是下限查找（lower_bound）：找到第一个大于等于 key 的键。它和精确查找几乎一样，只是在“没找到”时不返回失败，而是返回当前区间里最接近 key 的键。范围查询和“找前驱后继”都建立在它之上。第二种是上限查找（upper_bound）：找到第一个大于 key 的键，用于确定范围终点。第三种是前缀扫描：先做一次下限查找定位到第一个匹配前缀的键，然后沿着节点内的有序数组和树的中序遍历顺序逐个读下去，直到遇到不匹配的键为止。经典 B 树做前缀扫描要借助中序遍历——从叶子往上、再往右子树走，路径比较绕；这正是第 6 节 B+ 树用“叶子链表”解决的问题。等我们讲完插入分裂，再回头对比两种树在范围查询上的差距，你会对 B+ 树的设计动机有更深的体感。

3 B 树插入：先插叶子，满了就分裂

查找解决了“怎么读”，插入则要解决“怎么写”。B 树的插入比红黑树直观得多：它不做旋转，只做两种动作——插入键和分裂节点。你甚至可以把 B 树的插入理解成“自底向上的满则裂”：先把新键放进某个叶子，叶子满了就劈成两半，把中间键上交给父亲；父亲也可能因此满，于是继续劈、继续上交，直到某个祖先没有满，或者一路劈到根。

3.1 插入流程三步走

标准插入算法可以压缩成三步：

第一步，查找定位。用第 2 节的查找过程，从根一路走到应该包含新键的叶子节点。注意查找是“失败式定位”：新键几乎总是不在树里（重复键的处理见后文），我们要找的是“它应该落在哪个叶子”。

第二步，插入叶子。把新键按大小插入叶子节点的有序数组。如果插入后叶子键数仍不超过 m−1，一切正常，插入结束。这是最常见的情况，不需要任何额外动作。

第三步，处理溢出。如果插入后叶子键数达到 m（超过了上限 m−1），叶子“溢出”了，需要分裂：把 m 个键按序分成左、中、右三部分，中间键上提到父节点，左半部分留在原节点，右半部分放进一个新节点。如果父节点因此溢出，就递归地重复分裂，直到某个祖先不满为止；如果根节点也溢出，就创建一个新根，树整体长高一层。

这个流程里最需要理解的是第三步的细节：分裂时为什么上提“中间键”而不是任意键。回到 1.2 节的“键是分隔符”观点：分裂的本质，是把一个装不下的节点拆成两个都能合法存在的节点。左半部分需要一个新的“右边界”，右半部分需要一个新的“左边界”，而父节点需要一个新的分隔键来区分这两个区间。中间键是唯一同时满足三个条件的键——它大于左半的所有键、小于右半的所有键、且原本就属于这个节点，不需要从别处搬运。如果上提最大键，左节点会空出一个位置但右节点没有左边界；如果上提最小键，对称地不成立。所以“中间键上提”不是习惯，而是约束推导出的必然。

注意这里“2 上提”和“左 1 / 右 3,4”的顺序：分裂后的两半仍然有序，且被父节点里的 2 正确分隔。如果上提的是 1 或 4，左右两半就会缺一个边界，整棵树的区间结构立刻被破坏。

3.2 分裂如何一路向上传播

分裂的麻烦之处在于它可能“传染”。叶子分裂后，父节点多了一个键（上提上来的中间键）和一个孩子（新节点），如果父节点原本就满了，它也会溢出，需要再次分裂；分裂出的中间键继续上提给祖父……这个过程沿着插入路径一路向上，直到遇到一个没满的祖先，或者到达根。

为什么不会“横向传染”？因为分裂只影响当前节点、它的父节点和新创建的兄弟节点，其他子树毫发无损。这保证了插入的代价是 O(h) 次节点操作，而不是 O(n)。对磁盘来说，这意味着一次插入最多写 O(h) 个页，通常只有 1～2 个页会真的落盘，其余大多还能在缓冲池里完成。

这条路径之所以是“一条直线”而非整棵树：每次分裂只影响当前节点、父节点和新兄弟，其他子树完全不动。因此一次插入的代价是 O(h) 次节点操作，而不是 O(n)——对磁盘来说就是 O(h) 次页写入。

一个容易混淆的点：分裂时新节点总是插在“右边”。因为上提的中间键是从左到右第 ⌈m/2⌉ 个（约定用上中位数或下中位数，两本教材各有所爱），右半部分的键都大于中间键，所以新节点必然是父节点里对应区间的右侧兄弟。这个“向右分裂”的细节，在后面 B+ 树的叶子链上会变得非常重要——叶子链表是有方向的，新叶子总是挂在旧叶子的右边。

3.3 根分裂：树唯一的长高方式

如果分裂一路传到根，根节点也满了，会发生什么？答案是：创建一个全新的根，把旧根从中间劈开，中间键放进新根，左半和右半分别成为新根的两个孩子。这是 B 树唯一允许的“长高”方式，也是“所有叶子同层”这一不变式唯一的维护手段。

想象一棵只有一层的 B 树：根节点本身也是叶子，存着键 1、2、3（m=3 时上限 2 个键？这里我们先按 m=4 举例：上限 3 个键）。插入 4 后根节点有 4 个键，溢出。分裂后，中间键 2 上提到新根，原节点保留 1，新节点装 3、4，树从“根=叶子”的一层变成“新根 + 两个叶子”的两层。有趣的是，树长高时，所有原有叶子并没有变，但它们全体都向下移了一层。这正是“叶子同层”被自动维持的原因：树高只会在根这里整体变化，绝不可能出现局部高一层。

根分裂是“唯一的长高方式”这句话值得细品：它意味着树的高度永远不会局部增加，只会在根这里整体 +1。于是“所有叶子同层”不是事后检查出来的性质，而是由构造过程自动保证的。

根分裂还有一个工程上的好处：它让插入操作永远不需要回溯到根以上。所有维护动作都沿着“叶子→祖先→根”的单向路径完成，写完最后一个节点就结束了。对比红黑树的插入修复（可能从插入点一路修复到根，但每层只做常数次旋转/变色），B 树的分裂在结构上更“大开大合”，但每步的决策逻辑更简单，这也是为什么数据库内核更喜欢 B 树家族而不是红黑树家族。

3.4 完整走查：m=3 插入 [1, 2, 3, 4, 5, 6, 7]

理论说够了，来一场实战。我们取 m=3，即每个节点最多 3 个孩子、2 个键，非根节点至少 1 个键。这就是 2-3 树。要插入的序列是 1、2、3、4、5、6、7，全部按升序到达——这是对 B 树最不友好的输入（二叉搜索树遇到它早就退化成链表了），我们正好看看 B 树如何靠分裂保持平衡。

第 1 步：插入 1。 树为空，创建一个根节点，里面只放 1。此时根节点也是叶子。

第 2 步：插入 2。 2 大于 1，放进同一个根节点。根节点变成 [1, 2]，键数 2，正好达到 m−1=2 的上限，但还没溢出，合法。

第 3 步：插入 3。 3 比 1、2 都大，放进根节点后变成 [1, 2, 3]，键数 3 超过了上限 2，溢出。分裂：中间键选 2（第 ⌈3/2⌉=2 个），左半 [1]、右半 [3]，中间键 2 上提到新根。树从一层变成两层：

第 4 步：插入 4。 从根开始找：4 大于 2，走向右孩子 [3]。叶子 [3] 插入 4 变成 [3, 4]，没溢出，结束。树的高度依然是 2，但右叶子已经有了 2 个键。

第 5 步：插入 5。 5 大于 2，走向右叶子 [3, 4]，插入后变成 [3, 4, 5]，溢出。分裂：中间键 4 上提给父节点 [2]，左半 [3] 留下，右半 [5] 成为新叶子。父节点 [2] 收到 4 后变成 [2, 4]，没溢出。完成：

第 6 步：插入 6。 从根 [2, 4] 出发：6 大于 4，走最右孩子 [5]。插入后 [5, 6]，没溢出。树保持原样：

第 7 步：插入 7。 7 大于 4，走最右叶子 [5, 6]，插入后变成 [5, 6, 7]，溢出。分裂：中间键 6 上提给父节点 [2, 4]，左半 [5] 留下，右半 [7] 成为新叶子。父节点 [2, 4] 收到 6 后变成 [2, 4, 6]，再次溢出。继续分裂：中间键 4 上提，左半 [2]、右半 [6]，中间键 4 放进新根。原根被劈成两个孩子，树从两层长高到三层：

走查结束。回头看这七步，有几个值得记住的观察。第一，尽管输入是完全升序的，最终树依然是一棵完美的平衡树：所有叶子都在同一层，树高只有 3。第二，分裂一共发生了三次（第 3、5、7 步），其中只有最后一次是“根分裂”，树高从 2 变 3；前面两次都只是局部调整。第三，节点利用率并不总是满的：最终 [2] 只有 1 个键，[6] 也只有 1 个键，这是分裂的必然代价——把满节点劈成两半后，每个半节点都只有约一半的键，而中间键被上提了。这解释了为什么 B 树允许节点“半满”，也解释了为什么长期随机插入删除后，节点平均利用率大约在 70% 左右。

3.5 插入的边界情况与工程细节

几个值得单独说明的细节。重复键：经典 B 树通常要求键唯一，数据库主键索引天然唯一；如果允许重复，常见做法是让重复键都进右子树，或者给键附加一个唯一性后缀。预分裂：从上到下插入时，如果发现路径上的节点已经满了，可以提前把它分裂，这样到底层时不会再向上回溯；这种“单趟插入”实现更复杂，但能减少写锁持有的时间，很多数据库的 B 树变体就是这么做的。缓冲池与写放大：分裂会创建新页、修改父页，脏页最终要刷回磁盘；一次插入可能写 2～3 个页，这和红黑树“一次插入只改常数个节点”的磁盘开销是同一量级，但 B 树的页更大，所以每次写入的字节数更多。并发控制：数据库里插入通常要锁住“叶子到根”路径上的节点（悲观锁），或者用 latch coupling 的方式逐层加锁、逐层释放，避免死锁和撕裂写。

到这里，插入已经完整覆盖：先插叶子、溢出分裂、中间键上提、传播到根、根分裂长高。接下来是删除——B 树操作里公认最绕的部分。

4 B 树删除：下溢、借键与合并

删除之所以难，是因为插入的“满则裂”有个对称问题：删多了会“空则补”。插入溢出是因为键太多，删除下溢是因为键太少。非根节点的键数下限是 ⌈m/2⌉−1，一旦低于这个数，节点就“下溢”了，必须想办法把它补回合法状态。补的办法有两种：向兄弟借，或者和兄弟合并。这一节我们按“先借后并、并时借父”的顺序讲清楚，并用关键图例把三种情况展示出来。完整的删除算法有九种以上的情况分支（叶子/内部、左兄弟/右兄弟、有键可借/无键可借、根节点特殊处理），面试和工程里都不需要背全，抓住“维持键数范围 + 维持叶子同层”这两条不变式，任何情况都能推导出来。

4.1 删除的三个阶段

标准删除算法分三个阶段。第一阶段，定位并删除键。先查找目标键。如果目标键在叶子节点里，直接删掉，然后检查是否下溢。如果目标键在内部节点里，情况复杂一点：我们可以用它的“前驱”或“后继”来替换它。前驱是左子树里最大的键，后继是右子树里最小的键；无论选哪个，它一定位于叶子节点。于是“删内部节点的键”就转化为“删叶子节点的键”：先把前驱/后继的值拷贝到内部节点覆盖目标键，然后去叶子里删除那个前驱/后继。这个“用叶子键替换”的技巧和二叉搜索树删除时“用中序后继替换”是同一个思想，只是 B 树必须保证替换键来自叶子，才能把问题统一到“只删叶子”上。

第二阶段，检查并修复下溢。删除叶子键后，如果叶子键数仍 ≥ ⌈m/2⌉−1，合法，结束；否则进入修复流程。修复时先看相邻兄弟：如果左兄弟或右兄弟有“多余的键”（键数大于下限），就借一个键过来；如果两个兄弟都刚好在下限，就合并。注意，借键和合并都发生在叶子这一层，但都会牵动父节点——因为键是分隔符，兄弟之间隔着父节点里的一个键，借和并都必须把这个父键纳入计算。

第三阶段，处理连锁反应。合并会让父节点少一个键、少一个孩子；如果父节点因此下溢，修复就要向上继续：父节点向它的兄弟借键或与兄弟合并，如此递归。最极端的情况是根节点也下溢：如果根只剩 0 个键，就让它的唯一孩子成为新根，树整体变矮一层——这是“根分裂长高”的逆操作，也是 B 树唯一允许的变矮方式。删除的递归深度最多是树高 h，所以一次删除的 IO 代价同样是 O(h)。

4.2 借键：向兄弟“转交”而非“搬移”

借键是整个删除里最需要小心理解的动作，因为借的不是兄弟的键，而是父节点的键。为什么？看一个例子：m=3，父节点存着键 5，左孩子存 [2, 3]，右孩子存 [7]。现在左孩子删掉一个键变成 [2]，下溢（下限是 1，[2] 恰好 1 个键？这里换一个数字让下溢更明显：父节点 [5]，左孩子 [2]，右孩子 [7, 8]，左孩子删掉 2 后变空，下溢）。左孩子需要至少 1 个键，右兄弟 [7, 8] 有 2 个键、富余 1 个。标准的“左借右”动作是：把父节点的键 5 移到左孩子，把右兄弟最小的键 7 移到父节点。最终左孩子 [5]、右兄弟 [8]、父节点 [7]。

为什么不能直接把右兄弟的 7 搬给左孩子？因为那样左孩子变成 [7]、右兄弟 [8]，两个孩子的区间就乱了：父节点 5 依然落在左孩子区间的左边？我们推演一下：如果直接把 7 搬过去，父键 5 还在父节点，左孩子 [7] 与父键 5 之间的大小关系就违反了“左孩子所有键 < 父键 5”的约束。所以借键必须“旋转”式地转交：父键下降补位，兄弟键上升补父位。这样三个位置上的有序性全部保持：父键 5 大于左孩子原来的键、小于右兄弟原来的键，用它补进左孩子正好合适；兄弟最小键 7 大于 5、小于兄弟其余键，升上去当新的分隔键也正好合适。借键的本质是一次三节点之间的旋转，类似 AVL 树旋转的“搬家”，只是搬的是键而不是整棵子树。

注意借键前后，三个节点的键总数没变，只是重新分配：左孩子从 1 个键变 2 个，右孩子从 2 个变 1 个，父节点仍 1 个键。只要兄弟有富余，下溢就能就地修复，不需要动更上层。

当内部节点下溢时，借键更复杂一些：除了键，还要“借孩子”。内部节点下溢意味着孩子数太少，向兄弟借键的同时，兄弟最靠近的子树指针也要跟着转交过来，因为“键数减一、孩子数减一”是同步的。这个细节在综述里不展开，你只需要记住：对内部节点，借的不只是键，还有与键相邻的子树；对叶子节点，则只借键。

4.3 合并：两兄弟加一个父键，合成一个新节点

当两个相邻兄弟都恰好处于下限（或其中一方已经没有富余键）时，借无可借，只能合并。合并的规则是：把左兄弟的全部键、父节点里夹在中间的那个分隔键、右兄弟的全部键，拼成一个节点。为什么要把父键也拉下来？因为两个兄弟之间的值域本来就是连续的，中间只隔着父节点里这个分隔键；合并后这个分隔键失去了“分隔”的意义，必须一起并进去，否则值域会缺一块。

合并总是产生一个满节点：因为合并发生在两个兄弟都刚好在下限时，“左键数 + 1 + 右键数”恰好等于上限 m−1。这解释了为什么 B 树删除后不会频繁再次分裂——合并出来的节点为将来预留了空间。

合并的后果是父节点少了一个键、少了一个孩子。如果父节点因此下溢，就要递归处理：父节点向它的兄弟借键，或者与它的兄弟合并。这个过程可能一直向上传播，和插入分裂向上传播完全对称。如果根节点最后只剩下一个孩子，就把这个孩子提升为新根，树变矮一层。合并后新节点的键数是“左兄弟键数 + 1 + 右兄弟键数”，在双方都刚好下限时，这个数正好等于上限 m−1，所以合并出来的节点是满的——也就是说，合并总是产生一个满节点，这为将来可能的再分裂留下了空间。

4.4 删除的直觉总结

把插入和删除放在一起看，会发现一套漂亮的对称性。插入时节点“满”了，用分裂处理：一分为二，中间键上交。删除时节点“空”了，优先借键（三个节点旋转），借不到就合并（两个节点加一个父键拼成一个）。分裂让父节点多一个键，合并让父节点少一个键，两者的传播方向都是从叶子向上，都会在最坏情况下到达根，一个让树长高、一个让树变矮。对称的另一面是细节：分裂只需要“拆”，不依赖兄弟的富余程度；合并和借键需要先检查兄弟。所以实现上插入永远比删除简单，面试也总是先考插入、再考删除。

还有两个常被问到的点。第一，删除内部节点的键为什么必须用叶子键替换：因为替换之后，真正被删掉的是叶子里的键，后续的借键/合并都只发生在叶子层，问题被统一了。如果直接删内部键并强行拉孩子上来，会破坏“键数 = 孩子数 − 1”的约束。第二，删除可以“预合并”：从上到下查找时，如果发现即将进入的孩子只有下限个键，就提前从兄弟借键或与兄弟合并，保证目标键一定存在于一个“有富余”的叶子中，从而做到单趟删除、无需回溯。这与插入的“预分裂”是同一类工程优化，本质都是把“自底向上的修复”提前成“自顶向下的预防”。

4.5 配图走查一次删除：先借键，再合并

纸上谈兵不如完整走一遍。我们继续用 m=3（2-3 树），从一棵现成的树开始。树的形状是：根 [4, 8]，三个孩子分别是 [2]、[6]、[10]；[2] 带叶子 [1, 3]；[6] 带叶子 [5] 和 [7, 9]；[10] 带叶子 [11]。所有叶子都在第三层，合法。

场景一：借键。 删除键 5。找到叶子 [5]，删掉后它变成空节点，键数 0，低于下限 1，下溢。看它右边的兄弟 [7, 9]，有 2 个键，富余 1 个，可以借。执行“三节点旋转”：父节点 [6] 的键 6 下放到左叶子，右兄弟的最小键 7 上提到父节点。最终左叶子变成 [6]，右叶子变成 [9]，父节点 [6] 变成 [7]（节点编号随键变化），根 [4, 8] 不动。整棵树的键数范围全部恢复合法。

这张图把“借键”的三个移动方向一次看清：被删的 5 离开树，父键 6 往下走，兄弟最小键 7 往上走。三个键接力轮转，但每个节点的区间约束没有一刻被破坏。

注意借键前后，键 5 从树里消失，键 6 从内部节点降到叶子，键 7 从叶子升到内部节点——三个键都换了位置，但有序性丝毫无损。这就是删除里最需要眼力的动作：借键不是兄弟之间直接搬，而是父键与兄弟键的接力轮转。

场景二：连锁合并。 换一棵树：根 [4, 8]，孩子 [2]、[6]、[10]；[2] 带叶子 [1] 和 [3]；[6] 带叶子 [5] 和 [7]；[10] 带叶子 [9] 和 [11]。这次删除键 1。叶子 [1] 删空后下溢；它的右兄弟 [3] 只有 1 个键，正好在下限，借无可借，只能合并。把父节点 [2] 的键 2、右兄弟 [3] 一起并入左叶子，得到新叶子 [2, 3]；父节点 [2] 因此少了一个键、一个孩子，变成 0 个键、1 个孩子——内部节点下溢了。

继续向上修：节点 [2] 的右兄弟 [6] 也只有 1 个键、2 个孩子，无法借键，于是再次合并：父节点 [4, 8] 的键 4、节点 [2] 的孩子、节点 [6] 的全部内容拼成新节点 [4, 6]，它带着三个叶子 [2, 3]、[5]、[7]。根 [4, 8] 因此少了一个键、一个孩子，变成 [8] 和两个孩子，仍然合法。最终树：根 [8]，左孩子 [4, 6] 带三个叶子，右孩子 [10] 带两个叶子。树高不变，但中间层从三个节点变成了两个。

这个例子展示了删除最“贵”的情况：一次删除引发两轮合并，每轮都让父节点少一个键。但轮数有上限（最多等于树高），而且整个过程仍然只沿一条路径进行——这正是 B 树删除保持 O(logₘn) 的保证。

这次走查展示了删除最让人头疼的地方：一次删除可能引发多轮合并，每轮合并都会让父节点少一个键，直到父节点不再下溢为止。但请放心，轮数有上限——最多等于树高。而且和插入一样，删除也有一条“对称的底线”：如果合并一路打到根，根只剩一个孩子时，这个孩子上位成为新根，树变矮一层；绝不会出现“根变成空节点”的非法状态。

到这里，经典 B 树的三个操作——查找、插入、删除——已经全部讲完。现在请停下来想一想：如果 B 树已经这么完美，为什么数据库还要折腾出一个 B+ 树？下一节，我们从数据库的真实查询开始，找 B 树的三个“美中不足”。

5 B+ 树的动机：三个美中不足

第 13 篇和第 14 篇前半部分都在为 B 树辩护：矮、平衡、页对齐、支持动态维护。但 B 树不是没有缺点。数据库工程师在使用经典 B 树做索引时，会遇到三个具体的问题，而 B+ 树的每一项设计——数据只在叶子、叶子串链表、内部节点只存键——都精准地对应其中一个问题。

5.1 问题一：范围查询要“上上下下”

数据库查询远不止单点查找。SELECT * FROM orders WHERE price BETWEEN 100 AND 1000、ORDER BY time DESC LIMIT 10、GROUP BY 的分组聚合，全都需要按顺序扫描一段连续的键。经典 B 树里，数据分散在所有层：根和内部节点里也存着真实键。要做范围查询，你得先找到区间的起点，然后按“中序遍历”的顺序前进：先处理节点内的键，再到右子树里找最小的键，访问完右子树又可能回到父节点……这个“上上下下”的过程非常频繁。在内存里这没什么，但在磁盘上，每换一个方向都可能触发一次随机 IO，范围查询的性能会非常难看。

数据库真正想要的是：找到起点之后，一路向右，顺序读，像读数组一样流畅。B 树做不到，因为叶子之间没有“横向”的联系；B+ 树做到了，它给所有叶子穿了一条链表。这就是 B+ 树的第一个动机：范围查询的顺序化。

5.2 问题二：内部节点存数据，白白浪费“扇出”

第二个问题更隐蔽，但可能是 B+ 树存在的最根本原因。回顾第 13 篇的层数账：树高取决于每个节点能装多少个孩子指针（扇出），扇出越大树越矮。而扇出由节点大小除以“每个孩子指针占的字节”决定；如果节点里同时还要存真实数据，孩子指针就得和一大坨数据抢空间。

想象一个 16KB 的数据库页：如果做经典 B 树，内部节点除了键，还要存指向表里真实记录的指针（甚至在某些实现里直接存记录）。一条记录可能几百字节，一个页装不下多少个；可如果内部节点只存“键 + 孩子指针”，键通常只有几字节到几十字节，孩子指针 8 字节，一个页轻松装下几百上千个键指针对。扇出从几十涨到几百上千，树高直接降一层甚至两层。 数据库的账很现实：十亿条记录，扇出 100 需要 5 层，扇出 1000 只要 3 层——每少一层，就少一次磁盘 IO，也就是少一个数量级的延迟隐患。

于是 B+ 树做了一个分工：内部节点只当“路标”，存键和孩子指针，不存数据；所有真实数据（或指向数据的指针）全部下沉到叶子节点。内部节点因此可以装下远超 B 树的键数，树更矮，IO 更少。这是 B+ 树的第二个动机：牺牲内部节点的“数据功能”，换取更大的扇出。

5.3 问题三：磁盘局部性

第三个问题是磁盘局部性。经典 B 树的键分散在各层：一个范围查询读到的键，一会儿在叶子，一会儿在内部节点，对应的磁盘页位置各不相同，无法预读，缓存也无法高效组织。B+ 树把所有数据集中在叶子层，叶子页在物理磁盘上按序排列的可能性大大提高；配合数据库的“按页预读”和“叶子页顺序分配”，范围扫描可以接近顺序 IO 的速度。再加上叶子链表的存在，即使叶子页在物理上不连续，扫描逻辑上也是连续的，操作系统和存储控制器可以更好地做预取。这是 B+ 树的第三个动机：把“逻辑顺序”尽量变成“物理顺序”。

5.4 动机小结：三个问题一张图

这三个问题其实是同一个思路的三个侧面：经典 B 树把“指路的键”和“真实的数据”混在同一个节点里，导致范围查询要上下折返、内节点挤占扇出、数据散落各层。B+ 树的方案是彻底分层：内节点只负责指路，叶子专门装数据。

值得注意的是，B+ 树并不是对 B 树的“否定”，而是一次专业化改造：B 树把“索引”和“数据”混在一个结构里，B+ 树则明确分成“索引层（内节点）”和“数据层（叶子）”。这种分层带来的收益在数据库场景里压倒性地大，以至于现代关系型数据库几乎全部采用 B+ 树家族。下一节我们把 B+ 树的结构彻底拆开。

6 B+ 树结构：索引层与数据层

B+ 树的基本参数和 B 树完全一样：m 阶、每个节点最多 m 个孩子、非根节点至少 ⌈m/2⌉ 个孩子、所有叶子同层。区别只有两个，但这两个区别决定了它的一切行为：第一，内部节点只存键，不存数据，键的个数等于孩子指针的个数减一；第二，所有数据（或者指向数据的指针）都存放在叶子节点里，叶子节点之间用单向或双向链表串起来。换句话说，B+ 树是一棵“只有叶子会结果的树”，内部节点全部是路标。

6.1 内节点 vs 叶子：一张总览图

先看一张完整的 B+ 树结构图。根节点存键 40、80；中间层节点存键 20、60；叶子节点存 [10, 20]、[30, 40]、[50, 60]、[70, 80]、[90]，每个叶子还带着指向真实记录的指针（图中用 R₁、R₂ 等表示），并且叶子之间由链表箭头串联。注意一个细节：叶子里的键和内部节点里的键会重复出现——比如 20 既在中间节点里，也在叶子 [10, 20] 里。这不是浪费，而是 B+ 树的必然设计：内部节点的键只是“路标”，真正的数据（记录指针）在叶子；路标和叶子数据重合是允许的，因为它们的职责不同。

这张图值得盯住两个细节：一是叶子链表的方向，它让“范围扫描”变成纯粹的向右平推；二是内节点的“空”最右路标，它表示大于 80 的键都归右边这棵子树。理解这两点，后面的查找和范围查询图就只是它的具体走法。

为了把“内节点只存索引”的收益讲透，这里做一个具体估算。假设数据库页 16KB，键是 8 字节的整数，孩子指针 8 字节。一个经典 B 树内部节点如果还要挂 100 字节的记录指针数组，一页只能装 160 个左右键；而 B+ 树内部节点只需要 8 字节键 + 8 字节指针，一页能装约 1000 个键。扇出从 160 涨到 1000，十亿条数据对应的树高从约 5 层降到 3 层。两层 IO 的差距，就是 B+ 树在数据库里称王的最硬核理由。

6.2 B+ 树查找：走到叶子才算数

B+ 树的单点查找和 B 树几乎一样，只有最后一个差别：B 树可能在内部节点命中就直接返回；B+ 树必须一路走到叶子。因为内部节点里没有数据，即使内部节点的某个键等于目标键，也不能返回——那只是一个路标，真正对应的记录在叶子层。所以 B+ 树的查找路径是“根 → 中间层 → 叶子”，叶子是唯一能返回结果的地方。

这个“必须走到叶子”看似多走了一层，实际几乎不增加 IO：树高本来就包含叶子层，B 树命中内部节点时省掉的只是“剩下的层数”，而这类命中在数据量极大时占比很低（内部节点键数只占总键数的一小部分）。更重要的是，“必须到叶子”换来的是范围查询的极致简单：所有数据都在同一层，找到起点后向右平推即可。

走一遍例子：查找键 43。根节点 [40, 80]：43 在 40 和 80 之间，走中间子树；中间节点 [60]：43 小于 60，走左孩子；叶子 [30, 40, 43, 45]：二分找到 43，通过叶子里的数据指针取出记录。三次节点访问，三次磁盘 IO，其中根和中间层大概率常驻缓冲池，真正落盘的往往只有最后一次。

与经典 B 树的差别就在这里：即使根节点里有键 40 或 80，B+ 树也不会“命中即返回”，因为那些键只是路标。这一条规则让所有查询都统一到“走到叶子”，从而让叶子链表的扫描成为唯一的数据出口。

6.3 范围查询：叶子链走一遍

范围查询是 B+ 树最闪耀的场景。执行 WHERE key BETWEEN 33 AND 78，算法分两步：

第一步，找起点。从根开始按查找规则走到包含 33 的叶子（找不到 33 就找第一个大于 33 的键）。这一步的代价和单点查找一样，最多 h 次 IO。

第二步，沿叶子链表向右扫。从起点叶子开始，按节点内顺序依次输出 33 之后的所有键；当前叶子读完了，就通过叶子链表的 next 指针走到下一个叶子，继续输出，直到遇到第一个大于 78 的键为止。整个过程只有一次向下找起点，其余全部是横向顺序移动，没有任何“向上回溯”。如果叶子页在磁盘上恰好连续，这些横向移动还能被存储层预读成顺序 IO。

对比经典 B 树：范围查询每访问完一个节点都要判断“下一步该回父节点还是钻右子树”，方向不断变化；B+ 树则把扫描变成单方向的直线。数据库优化器偏爱直线，因为直线的 IO 模式可以预取，而之字形会打乱预读器。

把这段扫描和经典 B 树的范围查询对比：B 树每访问完一个节点，要么向上回父节点、要么向下钻右子树，方向不断变化；B+ 树则是一条单方向的直线。数据库优化器非常喜欢“直线”，因为直线的 IO 模式可预测、可预取、可批量读取；而“之字形”的 IO 模式会打乱预读器的工作。这也是为什么同样是 B 树家族，B+ 树几乎垄断了“范围查询为主”的关系型数据库索引，而经典 B 树往往只出现在“等值查询为主”或内存场景里。

6.4 B+ 树插入：叶子分裂“复制上提”

B+ 树的插入流程和 B 树一样是“先插叶子、满了分裂、中间键上提、可能传播到根”，但有一个关键差异：叶子分裂时，中间键要复制一份上提，而不是“移动”上提。

为什么？因为 B+ 树的数据全在叶子，叶子里的每个键都代表一条真实数据，删掉任何一个都会丢失数据；而内部节点需要这个键作为路标。所以叶子分裂时，中间键必须“既留在叶子里，又出现在父节点里”——叶子保留它（数据不丢），父节点获得一个副本（路标建立）。这跟经典 B 树“中间键从节点里拿走、上交给父节点”完全不同。

“复制”与“移动”的区别，就是“数据”与“路标”的区别：叶子里的 30 是一条真实记录，删了会丢数据；父节点里的 30 只是指路牌，丢了也不影响正确性，但路标必须存在。所以同一个键在两处各留一份。

6.5 B+ 树插入：内节点分裂“移动上提”

当分裂传播到内部节点时，行为又变回“移动上提”。内部节点不存数据，它的键只是路标；如果路标键在上提时被复制一份留在原节点，就会出现重复路标：父节点和子节点都有同一个分隔键，查找时会产生歧义——同一个键到底该走哪棵子树？因此内部节点分裂必须把中间键从节点中移走、上交给父节点，原节点和兄弟节点各保留一半。

于是 B+ 树形成一条精确的规则：叶子分裂复制上提，内部节点分裂移动上提。一字之差，源于“叶子键是数据、内节点键是路标”的本质分工。这个规则也解释了为什么 B+ 树的叶子键可以有重复（路标与数据重合），而内部节点的键必须互不相同。

如果内部节点的键在分裂后还留在原处，父节点和孩子就会出现同一个“分隔键”，查找时无法判断该走哪棵子树。所以内部节点分裂必须“移动”：键从旧节点拿走、交到父节点，两侧各保留一半。

6.6 B+ 树删除：与插入的镜像

B+ 树的删除遵循与插入对称的规则：删叶子里的键，下溢时先借兄弟（从兄弟借键时同样要经过父节点“旋转”，而且因为叶子间有链表，借键后链表顺序依然保持），借不到就合并。由于数据只在叶子，B+ 树删除永远发生在叶子层；内部节点的键只会在“合并导致父节点下溢”时被拉下来删除。还有一个 B+ 树特有的细节：删除叶子里的键后，内部节点里对应的路标要不要同步删掉？ 答案是不用。路标允许“指向一个区间”，即使该键本身已被删除，路标仍然正确地把查找引向正确的子树；真正影响正确性的只有叶子数据。这个“路标可以过期”的性质让 B+ 树的删除比经典 B 树更宽松，也进一步简化了实现。

6.7 两级结构的工程收益盘点

把 6.1～6.6 的内容收拢一下，B+ 树相对 B 树的工程收益有四项。第一，扇出更大、树更矮：内节点只存键，一页装下更多键，IO 次数更少。第二，范围查询天然有序：数据全在叶子且叶子有链表，扫描无回溯。第三，局部性与预读更好：数据集中在叶子层，物理上更容易连续存放。第四，缓存效率更高：内节点小、稳定、几乎总是命中缓冲池，真正读盘的主要是叶子页；索引层与数据层可以分别做缓存策略。这四项收益在“数据量巨大、读写混合、以范围查询和排序为家常便饭”的关系型数据库里，每一项都价值连城。

7 为什么 B+ 树是数据库与文件系统的主流

理论部分到此结束，接下来看真实世界。MySQL、PostgreSQL、SQLite、MongoDB 的默认索引，Windows 的 NTFS、Linux 的 ext4、Apple 的 APFS，甚至许多 NoSQL 引擎，都建立在 B 树家族之上——其中绝大多数是 B+ 树或它的近亲变体。这不是巧合，而是同一个成本模型反复推演出的同一个答案。这一节我们挑几个最著名的例子，看看 B+ 树在真实工程里长什么样，再解释聚簇索引和二级索引这两个数据库高频概念。

7.1 MySQL InnoDB：主键索引就是表本身

MySQL 默认存储引擎 InnoDB 使用 B+ 树组织数据，而且用得非常彻底：主键索引的叶子节点直接存放整行记录，也就是说，InnoDB 的表就是一棵以主键为键的 B+ 树。这种“索引即数据”的组织方式被称为聚簇索引（clustered index）。当你要 SELECT * FROM users WHERE id = 100 时，InnoDB 从 B+ 树根节点一路走到叶子，叶子页里就是完整的那一行，不需要再回表。

聚簇索引带来两个直接后果。第一，插入顺序影响物理布局：如果主键是自增的，新行总是插在 B+ 树的最右叶子，顺序写、页利用率高、页分裂少；如果主键是 UUID 之类的随机值，新行会散落在各处，频繁触发叶子分裂和页重排，写放大明显。这也是为什么 MySQL 社区反复建议“用自增主键、别用随机 UUID 当主键”——本质上是让 B+ 树的写入模式符合磁盘的顺序偏好。第二，二级索引必须回表：非主键索引（比如 KEY(name)）也是一棵 B+ 树，但它的叶子存的是主键值，而不是整行数据。按 name 查到主键后，还要再进主键索引的 B+ 树查一次，才能拿到完整行，这个过程叫回表。如果查询只需要 name 和主键，回表可以省掉，这就是“覆盖索引”优化。

7.2 PostgreSQL：堆表 + 二级索引

PostgreSQL 的默认索引也是 B+ 树，但组织方式和 InnoDB 不同：PostgreSQL 的表数据存放在堆（heap）里，行的物理位置用行标识符（ctid，即“页号 + 槽位号”）表示；B+ 树索引的叶子存的是“键 + 指向堆中行的 ctid”。也就是说，PostgreSQL 用的是非聚簇索引：索引和表数据是两套结构，查索引拿到 ctid 后，还需要按 ctid 去堆里取行——无论主键还是二级索引，都要“回表”一次。

两种方案孰优孰劣是个经典论战。聚簇索引（InnoDB）的优势是主键查询少一次间接跳转、数据按主键物理有序，适合“主键范围查询多”的场景；劣势是二级索引较大（存了主键副本）、主键变更要移动整行、插入随机主键时页分裂多。非聚簇堆表（PostgreSQL）的优势是行可以独立移动（比如 UPDATE 改行后 ctid 变了，索引重建成本低）、二级索引更小；劣势是每次索引查询都要多一次堆访问。有意思的是，两者底层都是 B+ 树，架构选择的分歧并不在“用不用 B+ 树”，而在“数据放哪里”——B+ 树提供了统一的索引骨架，聚簇与否只是叶子节点里放“完整行”还是“行指针”的差别。理解了这一点，很多数据库面试题（“聚簇索引为什么主键查询快”“什么是回表”）就都变成了 B+ 树叶子内容的延伸。

这张图把“聚簇”和“非聚簇”翻译成一句大白话：叶子放整行，就是聚簇；叶子放行指针，就是非聚簇。回表之所以存在，正是因为数据不在你手里这棵 B+ 树的叶子里，而在另一处。

7.3 SQLite、MongoDB 与 NoSQL

SQLite 的默认表结构（ROWID 表）本质上也是 B+ 树：表本身是一棵以 rowid 为键的 B+ 树，叶子存整行；WITHOUT ROWID 表则把主键直接作为 B+ 树的键。MongoDB 的默认索引同样使用 B 树家族（WiredTiger 存储引擎内部是 B+ 树变体），支持单字段、复合索引和范围查询。连以写优化著称的 RocksDB、LevelDB，虽然在内存里用跳表、落盘用 LSM 树（Log-Structured Merge Tree），但它们的内存表 MemTable 刷盘后形成的 SSTable 内部也是有序结构，很多实现会用到 B+ 树的思想。可以说，“有序 + 可动态更新 + 按块存储”这三个条件凑齐的地方，B+ 树家族就会自然出现。

为什么 NoSQL 也逃不过 B+ 树？因为 NoSQL 只是不强制 SQL 和事务，不代表不需要“按键快速定位”和“按范围扫描”——而这两件事，哈希表做不到（无顺序）、有序数组做不到（更新慢）、跳表在磁盘上局部性差，最后剩下的最优解还是 B+ 树。唯一真正避开 B+ 树的场景是“写入吞吐优先、读可以慢一点”的日志型系统：LSM 树把随机写变成顺序写，用后台合并换取读性能，牺牲了一部分读放大。但即便在 LSM 世界里，查询最终也要落到“有序结构”上，很多 LSM 实现会用 B+ 树做 Level 内部的索引。数据结构选型的底层逻辑，永远是在“读写比、顺序性、块访问”这几个维度上算账。

7.4 文件系统：NTFS、ext4 的目录索引

文件系统同样离不开 B+ 树家族。NTFS 的目录使用 B+ 树索引文件名：当目录条目少时，索引直接放在目录文件的常驻区；条目多起来，就分裂成 B+ 树，内部节点存文件名（用于排序和二分），叶子节点存文件引用（MFT 条目号），叶子之间也用链表串联，便于按文件名顺序枚举目录。ext4 的目录索引 htree 虽然是一棵哈希树（把文件名哈希后组织成类似 B 树的索引），但它借鉴了 B 树“大节点、多路、页对齐”的骨架；ext4 的 extent 树（管理文件数据块映射）则更接近 B 树。至于 Btrfs、ZFS，它们的元数据也大量使用 B 树变体。文件系统选 B+ 树的原因和数据库完全一致：目录可能包含上百万个文件，文件名要有序以便 ls 排序和通配符查找，条目要能增删，而底层磁盘按块访问——每一条都指向 B+ 树。

这张图想说明的是“B+ 树不是数据库的私产”：凡是需要按顺序查找、频繁增删、底层又是按块访问的地方，最终都会收敛到 B+ 树或它的近亲。理解这三个条件，比记住具体系统名单重要得多。

7.5 聚簇索引 vs 二级索引：B+ 树视角的速成课

既然提到了聚簇索引，这里用 B+ 树的语言把两组概念彻底对齐，方便以后看数据库文档。

聚簇索引：叶子节点存整行（或主键附近的全部列）。一张表只能有一个聚簇索引（通常就是主键），因为行数据只能按一种物理顺序存放。它的 B+ 树“键 = 主键，值 = 行”。主键范围查询极快：找到起点，沿叶子链表扫就是按主键顺序扫全表。

二级索引：叶子节点存“索引键 + 主键值”（InnoDB）或“索引键 + ctid”（PostgreSQL）。一张表可以有多个二级索引，每棵 B+ 树的键都不同。二级索引覆盖的列不完整时，需要“回表”：先在这棵 B+ 树里查到主键/ctid，再去主键 B+ 树或堆里取行。如果查询需要的所有列都在二级索引的叶子里，就无需回表，这叫覆盖索引。

这两个概念一旦映射到 B+ 树，就再也不用背了：叶子放什么，决定了它是什么索引；回表，就是从一棵 B+ 树的叶子跳去另一棵 B+ 树的叶子。

7.6 扩展阅读：B* 树、B-link 树与填充因子

B 树家族不止“B 树”和“B+ 树”两位成员，工程上还有几个重要变体，这里各用一段话介绍，免得你在资料里碰到它们时发懵。

B 树**是经典 B 树的优化变体：普通 B 树在节点满了就分裂，B 树则要求节点至少装满三分之二，并且在分裂前先尝试把键“摊”给兄弟节点；只有当兄弟也满了才分裂，分裂时还允许从兄弟借一个键过来，一次分裂产生两个三分之二满的节点。代价是实现更复杂，收益是节点平均利用率从约 70% 提升到约 85%，树更矮、磁盘占用更少。数据库索引很少直接用 B* 树，但它代表了“延迟分裂、提高利用率”这一类优化思想。

B-link 树是为并发设计的 B+ 树变体：它给每个节点增加一个“向右的链接指针”（link），插入分裂时先完成兄弟链的链接，再更新父节点。这样并发查找即使走到一个“父指针还没更新”的旧节点，也可以顺着 link 找到正确的兄弟，不需要持有父节点的锁。数据库和文件系统里广泛采用这种“锁耦合 + 水平链接”的思路，避免写者长时间阻塞读者。你之前可能听过“数据库索引支持无锁读”这类说法，背后的结构常常就是 B-link 树的思想。

填充因子（fill factor）与延迟合并：创建索引时数据库允许指定填充因子，例如 80%，即叶子页只填 80% 就申请新页——这为将来的插入预留了空间，减少分裂频率；代价是树略微变高。删除侧的工程实现往往也不会立刻合并“刚下溢”的节点，而是允许节点暂时低于下限，等批量删除或页利用率掉到某个阈值（例如低于 50%）再合并。理由很实际：一次借键或合并要修改多个页、可能触发级联操作，与其为单个删除大动干戈，不如积累一段时间再统一整理。理解这些变体的共同点，比记住每个名字重要：它们都在“树高、利用率、写放大、并发度”四个目标之间做取舍，而取舍的骨架永远是 B+ 树那套有序多路结构。

7.7 回到问题：为什么数据库不直接“全内存”

既然 B+ 树的一切努力都是为了省磁盘 IO，有人会问：现在内存越来越大、价格越来越低，为什么不干脆把整个索引放进内存，回到红黑树或跳表？答案分两层。第一层，数据量增速与内存成本：单表几十亿行、索引数百 GB 在今天并不罕见，全内存的代价是千万级人民币级别的服务器，而磁盘方案只需要零头；绝大多数业务愿意用毫秒级的延迟换取数量级的成本下降。第二层，可靠性要求：数据库必须把数据持久化到磁盘，崩溃后要能恢复；索引即使常驻内存，最终也要以某种磁盘结构存在，否则每次重启都要重建。既然磁盘结构躲不掉，不如就让磁盘结构本身高效——这就是 B+ 树至今不可替代的底层逻辑。当然，内存数据库（如 Redis 的某些模式、SAP HANA）确实会全内存并选用跳表、哈希表或数组，但那是另一个成本模型下的另一道题，恰好印证了第 8 节的结论：结构没有绝对优劣，只有匹配不匹配。

8 与红黑树、跳表对比：内存与磁盘的选型

第 13 篇我们对比过红黑树与 B 树，第 14 篇把 B+ 树也放进同一张桌子，再请上跳表，做一次完整的四者对比。对比的核心维度只有三个：适用存储介质、IO 次数、实现与并发。请记住一个前提：没有“最好”的结构，只有“最匹配成本模型”的结构。

维度	红黑树	跳表	B 树	B+ 树
典型场景	内存（TreeMap、std::map）	内存（Redis ZSET、并发友好）	内存/磁盘折中、等值查询	磁盘（数据库、文件系统）
树高/层数	log₂n	期望 O(log n)	logₘn	logₘn，内节点更瘦
单点查找	O(log n) 内存跳转	O(log n) 指针跳跃	O(logₘn) 次 IO	O(logₘn) 次 IO
范围查询	中序遍历，需要上下回溯	找到起点后沿底层链表走	中序遍历，上上下下	叶子链表顺序扫，最优
插入删除	旋转 + 变色，局部修复	随机层数，概率平衡	分裂/借键/合并	分裂/借键/合并，规则更清晰
磁盘局部性	差（节点小、随机分布）	差（链表节点分散）	中（节点对齐页，但数据在各层）	优（数据集中叶子、可顺序分配）
缓存友好	中（小节点）	差（随机指针）	良	优（内节点小、常驻）
实现复杂度	高（红黑树五性质）	低（随机化）	中	中

这张图把选型清单压缩成两句话：内存里指针便宜，结构和实现简单更重要；磁盘上一次 IO 很贵，树矮、扫描顺序、页对齐才是第一优先级。B 树夹在中间，B+ 树则是磁盘场景的完全体。

这张表里有三个值得划重点的结论。第一，红黑树和跳表是内存选手：它们赢在“实现简单、局部更新、无需考虑页”，输在“节点/指针分散、层数多、无法对齐磁盘块”。第二，B+ 树是磁盘选手：它的一切设计都在为“少一次 IO、让扫描变顺序”服务，为此甚至接受“所有查询都必须走到叶子”的额外一层。第三，B 树夹在中间：它的存在感更多是历史与教学意义——许多教材与早期数据库用经典 B 树，今天的通用数据库几乎都进化到了 B+ 树。真正该问的不是“B 树好还是 B+ 树好”，而是“我的数据放在内存还是磁盘？我的查询是等值多还是范围多？”答案会自己浮出来。

8.1 选型清单：什么场景选什么结构

把前面的对比翻译成一张可执行的选型清单，遇到实际问题时按顺序问自己四个问题。

第一个问题：数据主要住在哪里？ 主要住内存，就从红黑树、跳表、哈希表里选；主要住磁盘，就从 B+ 树、LSM 树里选。中间状态（部分热点在内存）则看缓存命中率，命中率高时内存结构的缺点被掩盖，但磁盘结构依然更稳。

第二个问题：查询形态是什么？ 纯等值查询，哈希表最快；等值 + 范围混合，选 B+ 树或跳表；只有范围查询且数据基本静态，有序数组 + 二分反而最省。数据库为什么默认 B+ 树？因为 SQL 查询的形态无法预先承诺，B+ 树是“全形态通吃”的保守最优。

第三个问题：写入模式如何？ 随机写多、且能接受读放大，考虑 LSM 树（RocksDB、LevelDB）；顺序写多、读延迟敏感，B+ 树更合适；写入量极小，红黑树/跳表也够用。

第四个问题：是否需要持久化与崩溃恢复？ 需要，就绕不开磁盘友好的结构；不需要，内存结构可以尽情发挥。四个问题问完，你会发现大多数“某某结构更好”的争论，其实只是提问者默认了不同的前置条件——把前置条件摆到桌面上，答案往往没有争议。

9 动手体验：搜索算法可视化实验室

分裂、上提、借键、合并这些操作，光看文字和静态图很容易“眼睛会了、手不会”。这个系列配套了一个交互式可视化实验室，你可以在浏览器里直接操作：选择 B 树/B+ 树、设定阶数 m、逐步插入或删除键，观察节点如何分裂、中间键如何上提、叶子链表如何拼接。强烈建议用它把第 3 节的 [1,2,3,4,5,6,7] 序列亲手插一遍，再反向把键逐个删掉，亲眼看看“根分裂长高”和“根合并变矮”的镜像过程。你还可以对比相同插入序列下 B 树与 B+ 树的分裂行为，体会“复制上提”与“移动上提”在可视化里的一字之差。

进实验室前，给你三个练习目标。目标一：把阶数设为 3，依次插入 1～7，数一数发生了多少次叶子分裂、多少次根分裂，和第 3 节的走查核对。目标二：插入 8～15，观察分裂如何“一路向上”，以及哪些层保持不动。目标三：切换到 B+ 树，插入同样的序列，特别注意叶子分裂时中间键的“复制上提”，然后执行一次范围查询，看扫描是否完全沿着叶子链表进行。三个目标做完，本篇的每一张图都会在你脑子里动起来。

10 常见误解与实现细节

10.1 “B+ 树把数据全放叶子，所以叶子很小”

恰恰相反：B+ 树的叶子往往是整棵树里最大的节点，因为它们装着真实数据或数据指针；小的是内部节点——只装键和指针。一张 16KB 的叶子页可能只放得下几十条记录，而同尺寸的内部节点页能装上千个键。这也解释了为什么数据库的 B+ 树“上面很宽、下面很实”：上层路标多，下层数据满。

10.2 “B+ 树的键会重复，所以浪费空间”

表面看，20 这个键既出现在内部节点又出现在叶子，确实多存了一份。但内部节点的键加起来只占总键数的约 1/(m−1)，在 m 上百的工程里连百分之一都不到；而它换来的收益——更大的扇出、更矮的树、无需回表定位——远大于这点开销。用“百分之一的存储，换一次磁盘 IO”，这笔账数据库算得很清楚。

10.3 “B+ 树查询一定要走到叶子，所以比 B 树慢”

这只在理论上成立（B 树命中内部节点可以提前返回），工程上几乎不成立。第一，B+ 树更矮，总节点访问数通常更少；第二，内部节点几乎都命中缓冲池，真正读盘的主要是叶子；第三，B 树命中内部节点的概率约等于“内部节点键数/总键数”，数据量越大这个概率越低，十亿条数据时可能只有几个百分点。B+ 树多走的路，几乎全部走在缓存里。

10.4 实现细节：页内布局与并发

工程实现里，B+ 树的内节点通常按“键数组 + 孩子指针数组”的扁平布局放在页里，键有序、指针穿插；叶子节点则在数据区前放一个“槽目录”，支持页内二分。分裂时新页从缓冲池申请，页号写入父节点的孩子指针数组；合并时回收页并更新兄弟链表。并发方面，现代数据库采用 latch coupling（加锁下探、离开即释放）来允许并发查询与单写者，或者用写时复制（Btrfs 等文件系统）规避原地修改。这些细节在不同引擎里花样繁多，但骨架永远是本篇讲的这套：有序、多路、页对齐、叶子链。

10.5 “分裂越多越好，因为树会保持平衡”

不是。分裂是“恢复合法状态”的代价，不是收益：每次分裂都要创建新页、修改父页、写回磁盘，产生写放大。工程上恰恰会想办法减少分裂：设置填充因子预留空间、让叶子按主键顺序追加写入、批量导入时按排序后的数据构建 B+ 树而不是逐条插入。B 树保证的是“分裂后树依然平衡”，而不是“分裂本身免费”。判断一个插入策略好不好，要看它触发的分裂次数，而不只是看最终树形。

10.6 “叶子链表用单向就够了，为什么很多实现用双向”

单向链表足够支撑“从小到大的范围扫描”，这是 B+ 树的核心需求。但工程实现常常加一条反向指针，原因有三个：第一，ORDER BY ... DESC（从大到小排序）需要从最大键开始向左扫，反向链表让倒序扫描同样无回溯；第二，删除节点或调整页布局时，需要从右邻居回看，双向链让相邻页维护更简单；第三，数据库的“页预取”在双向扫描时可以双向预读，避免只朝一个方向优化。所以“B+ 树叶子用链表”这句话在面试里可以说单向，在真实实现里默认双向——两者并不矛盾，只是成本模型的细化。

11 B 树 / B+ 树对比速查表

全篇收尾前，把最重要的对比浓缩成一张速查表，方便日后查阅。左边是经典 B 树，右边是 B+ 树；差别只有四处，其余完全相同。

对比项	B 树	B+ 树
数据存放	内部节点和叶子都存键（数据）	只有叶子存数据，内部节点只存键（路标）
叶子链表	无，范围查询靠中序遍历	有，叶子间单向/双向链表
单点查找	内部节点命中可提前返回	必须走到叶子才能拿数据
范围查询	上上下下，方向多变	找到起点后沿链表平推，最优
叶子分裂	中间键移动上提	中间键复制上提（数据不丢）
内部节点分裂	中间键移动上提	中间键移动上提
扇出	被数据占用空间拉低	只存键，扇出大、树矮
磁盘局部性	数据分散各层	数据集中叶子，可顺序分配、预读
典型使用	教材、内存引擎、部分文件系统	MySQL / PostgreSQL / SQLite / NTFS 等
维护不变式	键数范围、叶子同层	键数范围、叶子同层、叶子链不断

记忆口诀：B 树“键在路中，数据随行”；B+ 树“路标只指路，果实全在叶，叶子一条链”。 两棵树共享同一个骨架——多路、有序、平衡、页对齐；差别全在“数据放哪、叶子怎么连”这两个问题上。

12 自测题

如果七道题你全部答对，那么分裂、上提、借键、合并这些动作对你来说已经不是术语，而是可以推演的过程。如果有一两道卡住了，建议回到对应小节再看一遍图，然后用第 9 节的实验室亲手操作一次——动手验证过一遍，比重新读三遍文字都管用。

13 下一篇预告

本篇把 B 树从“静态结构”讲到了“动态操作”，又把 B+ 树从动机讲到结构，最后落到数据库和文件系统的工程选型。B 树家族的传奇到此告一段落，但“有序 + 可动态更新”的探索并没有结束。下一篇我们转向一个老朋友——跳表：它没有树形结构，却用“多层链表 + 抛硬币”实现了期望 O(log n) 的查找；它在内存里和红黑树正面竞争，Redis 的有序集合为它站台；它还被 LSM 树用作内存表，撑起了写优化的半壁江山。我们会把跳表的插入、删除、查找逐层拆开，对比它与红黑树、B+ 树的适用边界，并回答那个经典问题：为什么 Redis 不用红黑树，而选了跳表？

《树系列第 15 篇：跳表》——敬请期待。