迈向外存存储：深入理解 B 树与 B+ 树
在了解了平衡二叉树因为高度过高导致的外存 I/O 瓶颈后，我们终于迎来了解决该瓶颈的终极武器——B 树（B-Tree）及其演化变体B+ 树。
B 树通过允许节点拥有多个分叉，将树的形态调整得“矮胖”，从而完美匹配了现代存储介质的物理特性。
1. B 树的设计哲学
B 树之所以能解决外存读写瓶颈，其核心思想是：“按页对齐”与“高扇出”。
- 节点大小与磁盘页对齐： 操作系统与磁盘交互的最小单位是“页”（通常为 4KB）。B 树会将一个节点的大小设计为 1 个或多个物理页的大小。这样，读取一个节点的数据，只需要一次磁盘 I/O 就可以完整加载。
- 高扇出（Fan-out）： 既然读取一个节点需要一次磁盘 I/O，那我们在这个节点内塞入尽可能多的有序键和子节点指针。 假设一个节点能装下 100 个键和 101 个指针，它的分叉数（扇出）就是 101。通过这种设计，树的高度会极快地降低。
2. B 树的性质与核心定义
一个 m 阶（Order）的 B 树（即每个节点最多有 m 个子节点）需要满足以下性质：
- 键与子节点数量规则：
- 除根节点外，每个非叶子节点至少有
⌈m/2⌉个子节点（确保空间利用率不低于 50%）。 - 根节点若不是叶子节点，则至少有两个子节点。
- 拥有
k个子节点的节点恰好包含k-1个键（Key，即用于排序和检索的索引字段值，如用户 ID），且键按升序排列：K_1 < K_2 < ... < K_k-1。通俗理解：键在节点内部扮演的是“分界线（围栏）”的角色。如果有
k个分支（子节点），就刚好需要k-1个边界键来划分出这些分支的范围。例如有 3 个分支，则需要 2 个键来划分出 3 个区间：小于键1、键1与键2之间、大于键2。
- 除根节点外，每个非叶子节点至少有
- 子树键值区间：
- 指针与键交替排列：
P_0, K_1, P_1, K_2, ..., K_n, P_n。 - 指针
P_i所指向的子树中，所有的键值都在区间(K_i, K_i+1)之内。
- 指针与键交替排列：
- 完美平衡：
- 所有叶子节点都处于完全相同的深度（高度差为 0）。B 树通过向上分裂来长高，因而能保证绝对平衡。
结构图示 (以 3 阶 B 树为例)
[ 15 | 30 ]
/ | \
/ | \
[ 5 | 10 ] [ 20 | 25 ] [ 35 | 40 ]
3. B 树的关键操作
1) 查找 (Search)
- 从根节点开始，读取当前节点（触发一次磁盘 I/O）。
- 在当前节点的键数组中查找目标值
X（通过二分查找）。 - 如果找到，返回数据；如果未找到，根据大小关系定位到区间对应的子节点指针
P_i。 - 沿着该指针递归向下读取子节点，直到找到或者到达叶子节点。
🔍 查找模拟示例
我们要在如下 3 阶 B 树中查找键 25：
[ 15 | 30 ] <-- 1. 从根节点开始，15 < 25 < 30，走向中间子树
/ | \
[ 5 | 10 ] [ 20 | 25 ] [ 35 | 40 ] <-- 2. 读入节点，找到 25，成功返回
2) 插入 (Insert)
新数据永远插入到叶子节点中：
- 查找并定位到对应的叶子节点。
- 将新键按顺序插入其中。
- 检查溢出：如果插入后该节点的键数达到了限制（大于
m-1）：- 分裂 (Split)：以中间的键（第
⌈m/2⌉个键）为界，将节点拆分为左右两个子节点。 - 将中间键“提拔”到父节点中，并使它成为左右两个新子节点的分界。
- 如果父节点也因此溢出，则继续向上分裂。如果根节点分裂，则树高增加 1。
- 分裂 (Split)：以中间的键（第
📥 插入与分裂（级联分裂）示例
假设我们在上面的 3 阶 B 树（每个节点最多存 2 个键）中插入新值 22：
第一步：定位并插入叶子节点
22 应该插入到 [ 20 | 25 ] 节点中，插入后该节点变为 [ 20 | 22 | 25 ]。
此时节点键数为 3，超过上限 2，触发分裂：
[ 20 | 22 | 25 ] ==> 以中间值 22 为界分裂，22 被提拔到父节点
第二步：中间键上提至父节点
父节点原为 [ 15 | 30 ]，接收 22 后变为 [ 15 | 22 | 30 ]。
此时父节点的键数也变为了 3，同样超限，继续向上分裂：
[ 15 | 22 | 30 ] ==> 以中间值 22 为界分裂，22 成为新的根节点
插入完成后的最终结构： 由于根节点分裂，树的高度增加了 1 层：
[ 22 ]
/ \
[ 15 ] [ 30 ]
/ \ / \
[ 5 | 10 ] [ 20 ] [ 25 ] [ 35 | 40 ]
3) 删除 (Delete)
删除操作相对复杂：
- 如果要删除的键在内部非叶子节点，先将其与它的前驱（左子树的最大值）或后继（右子树的最小值）交换，将其转换为对叶子节点的删除。
- 在叶子节点中删除。
- 检查下溢 (Underflow)：如果删除后，节点键数低于最低限制
⌈m/2⌉ - 1：- 借键 (Rotate)：如果左/右兄弟节点有多余的键，通过父节点进行一次“旋转”，借一个键过来。
- 合并 (Merge)：如果兄弟节点也没有多余的键，则将当前节点、父节点中的分界键、兄弟节点合并为一个新节点。父节点因为拿出了一个键，也需要递归检查是否发生下溢。
📤 删除与调整（借键旋转）示例
我们在上面新生成的树中删除键 20：
第一步：直接在叶子节点中删除
删除后，该叶子节点变为空 [ ]。对于 3 阶 B 树，非根节点至少需要有 1 个键，当前节点键数为 0，发生下溢。
第二步：借键旋转调整
- 检查右兄弟
[ 25 ]：仅有 1 个键，无法出借。 - 检查左兄弟
[ 5 | 10 ]：拥有 2 个键，可以向其借键。 - 旋转调整：
- 将父节点的分界键
15移下来，填入发生下溢的节点，使其变为[ 15 ]。 - 将左兄弟中最大的键
10提拔到父节点，替换原来的15。
- 将父节点的分界键
删除调整后的最终结构：
[ 22 ]
/ \
[ 10 ] [ 30 ]
/ \ / \
[ 5 ] [ 15 ] [ 25 ] [ 35 | 40 ]
4. 从 B 树到 B+ 树的进化
虽然 B 树已经极大地降低了树的高度，但在数据库（如 MySQL 的 InnoDB 存储引擎）和现代文件系统（如 NTFS, ext4）中，人们对其进行了进一步改良，设计出了 B+ 树。
B 树：非叶子节点既存索引，也存行数据
[ 15 (Data) ]
/ \
[ 10 (Data) ] [ 20 (Data) ]
B+ 树：只有叶子节点存实际行数据，非叶子节点仅存索引键
[ 15 ] <-- 仅索引，不存行数据
/ \
[ 10(Data) ] <-> [ 15(Data) | 20(Data) ] <-- 叶子节点双向链表相连
B+ 树的改进规则：
- 数据全在叶子节点：非叶子节点（内部节点）只存储索引键和指针，不再存储具体的行数据。所有的数据物理记录只保存在叶子节点中。
- 叶子节点链表化：所有的叶子节点之间，通过双向链表横向连通。
- 非叶子节点与叶子节点键重合：非叶子节点中的键也会以最大值或最小值的形式出现在叶子节点中。
5. 为什么数据库更偏爱 B+ 树？
相比 B 树，B+ 树在面对数据库的复杂查询时具有压倒性的技术优势。我们通过一个**“导出学号 1000 到 1200 的学生花名册”**的具体实战场景，来对比二者的差距：
场景设定：
- 总数据量：100 万名学生。
- 行数据大小：学号 8 字节 (键 Key) + 姓名/成绩等详细数据 1KB (数据本体) = 共计约 1KB。
- 磁盘页大小：数据库默认的 16KB。
- 查询目标：执行
SELECT * FROM Student WHERE 学号 BETWEEN 1000 AND 1200;提取这 200 个学生的完整行数据。
1) 单节点容纳的键更多，树更矮 (对应精确查询)
- 在 B 树中：因为节点中同时存有键和 1KB 的行数据，一个 16KB 的节点最多只能装下 15 个 学生数据。
- 100 万数据，树的高度大约是：5 层（
log_15(1,000,000) ≈ 5）。 - 精确查找某一个学号，最坏需要进行 5 次磁盘 I/O（读盘 5 次）。
- 100 万数据，树的高度大约是：5 层（
- 在 B+ 树中：非叶子节点只存索引键（学号）和子节点指针，不存行数据，仅需 16 字节。一个 16KB 的节点可以容纳多达 1000 个 键！
- 100 万数据，树的高度只需要：3 层（
log_1000(1,000,000) ≈ 2层非叶子节点 + 1 层叶子节点）。 - 精确查找某一个学号，仅需 3 次磁盘 I/O。
- 100 万数据，树的高度只需要：3 层（
2) 极其强悍的区间查询性能 (对应范围查询)
在范围查询中，B 树与 B+ 树的查找路线有着本质的差别（我们用大写字母 A、B、C 代表物理节点，用数字代表具体数据与键）：
① B 树的查询过程：频繁的层级折返 (随机 I/O)
在 B 树中，行数据存放在各个层级的节点中：
节点 A: [ 1100 (数据) ] <-- 根节点
/ \
节点 B: [ 1000 (数据) ] 节点 C: [ 1200 (数据) ]
/ \ / \
节点 D: [ 999.. ] 节点 E: [ 1001.. ] 节点 F: [ 1101.. ] 节点 G: [ 1201.. ] <-- 叶子层
逻辑释义：由于树的排序逻辑是“左子树小、右子树大”，学号
1000的左子树（节点 D）只存放小于 1000 的数据；其右子树（节点 E）才存放1001 ~ 1099之间的数据。
B 树查找 1000 到 1200 行数据的路线：
- 读入节点 B：从中提取出学号
1000的学生行数据。 - 向下进入右子树节点 E：从中提取出学号
1001 ~ 1099之间所有学生的行数据。 - 退回（向上）到节点 B，再退回（向上）到根节点节点 A：从中提取出学号
1100的学生行数据。 - 向下越过节点 C 进入其左子树节点 F：从中提取出学号
1101 ~ 1199之间所有学生的行数据。 - 退回（向上）到节点 C：从中提取出学号
1200的学生行数据。
痛点：程序必须在 节点 B ➔ 节点 E ➔ 节点 B ➔ 节点 A ➔ 节点 F ➔ 节点 C 之间反复跨层级折返。每一次“跨层读节点”在磁盘上都是一次随机 I/O，磁头需要在盘面上来回移动寻道，效率极其低下。
② B+ 树的查询过程：直线的横向扫射 (顺序 I/O)
在 B+ 树中，上层节点仅用于分界，所有学生行数据全部沉淀在最底部的叶子节点（D、E、F）中：
节点 A: [ 1100 (仅索引) ]
/ \
节点 B: [ 1000 (仅索引) ] 节点 C: [ 1200 (仅索引) ]
/ \ / \
节点 D: [ 1000..数据 ] <=============> 节点 E: [ 1100..数据 ] <=============> 节点 F: [ 1200..数据 ]
B+ 树查找 1000 到 1200 行数据的路线：
- 定位起点：读取节点 A、节点 B，做大小比对后，直接锁定底部的起点——节点 D。
- 读取节点 D：从中提取出 1000 后的学生行数据。
- 横向跨步：不再向上退回任何上层节点，直接顺着底部的双向链表横向走到相邻的节点 E，读取里面的学生行数据。
- 横向跨步：继续顺着链表走到相邻的节点 F，读取里面的学生行数据。
优势：我们只做了一次向下查找。之后所有的拿取全部通过底部的链表进行扁平横向移动。
💡 物理本质（顺序 I/O vs 随机 I/O）： 这里的优势本质上并不是因为读取的物理磁盘页（Page）变少了。因为要拿到这 200 个学生的数据，不管用什么树，都必须把存放这 200 行数据的物理页面读入内存，搬运的总数据量是相似的。
其核心性能差距在于 B+ 树实现的是极速的“顺序 I/O”，而 B 树却退化为了极慢的“随机 I/O”：
- B+ 树的顺序 I/O：相邻的叶子节点在物理磁盘上通常是连续存放的。磁头只要定位到起点，就可以顺着磁道一气呵成地将相邻的磁盘页连续读出，磁头不需要在不同磁道间进行物理移动（无需反复寻道）。
- B 树的随机 I/O：因为数据分散在各个层级的节点里，磁头为了跟着中序遍历的顺序拿数据，必须在不同的磁盘物理磁道上来回折返、旋转。时间全部浪费在了磁头物理寻道和盘片旋转等待上（磁盘寻道一般需要 5-10ms 左右，而顺序读取只需几微秒）。
3) 查询性能更稳定
在 B 树中，有的键在根节点（1次 I/O 即可拿到），有的在叶子节点（3次 I/O 拿到），查询时间存在波动。而 B+ 树的数据全部存储在叶子节点中，任何查找都必须走到叶子节点，因此每一次查询的 I/O 次数都是完全相同且稳定的。
6. 总结
- 二叉搜索树 (BST)：实现了
O(log n)查找，但面临退化为链表的危机。 - 平衡二叉树 (AVL / 红黑树)：通过旋转/染色保持了高度平衡，在内存中表现完美；但面对海量外存存储时，因为树高和随机 I/O 瓶颈败下阵来。
- B 树：引入了矮胖的多路结构，使单节点与磁盘页对齐，大幅减少了磁盘 I/O 读写次数。
- B+ 树：将行数据彻底移至叶子节点，并通过双向链表横向连接，提供了恐怖的区间范围查询性能和极高的扇出，成为了现代关系型数据库索引底座的最终选择。