B 树 / B+ 树 · 定义与操作可视化

1B 树定义（m 阶）

平衡的 M 叉查找树：用分叉换树高，把磁盘访问压到很小的常数。

动机：通过增加分叉来降低树高。M 叉查找树的最佳高度约为 log_MN，分叉越多树越矮，从而把磁盘访问次数降到很小的常数。B 树本质上是一棵平衡的 M 叉查找树。

M 叉查找树最佳高度 ≈ log_MN

m 阶 B 树的定义

一棵 m 阶 B 树，要么为空，要么满足下面四条性质：

根结点：或是叶子，或至少有 2 个、至多有 m 个儿子。
除根与叶子外的结点：每个结点的儿子数 s 满足 ⌈m/2⌉ ≤ s ≤ m。
关键字数与子树数：有 s 个儿子的非叶结点恰含 n = s−1 个关键字，即子树数 = 关键字数 + 1；结点形如 (n, A₀, (K₁,R₁), A₁, …, (Kₙ,Rₙ), Aₙ)。
叶子：所有叶子都在同一层，且不带信息（视为查找失败结点，为空、指针为空）。

⌈m/2⌉ ≤ s ≤ m，n = s − 1，子树数 = 关键字数 + 1

结点的形态与各项含义

每个结点按如下结构组织，关键字在结点内有序排列：

(n, A₀, (K₁,R₁), A₁, (K₂,R₂), A₂, …, (Kₙ,Rₙ), Aₙ)

K₁ < K₂ < … < K_n（关键字有序）

符号	含义
`n`	本结点的关键字个数（n = 儿子数 − 1）
`Kⱼ`	第 j 个关键字，满足 K₁ < K₂ < … < K_n
`Rⱼ`	第 j 个关键字所对应记录的硬盘地址
`Aᵢ`	第 i 棵子树（指向硬盘块）的地址

四条性质速查表

性质	对象	约束
①	根结点	是叶子，或儿子数为 2 ~ m
②	除根与叶子外的结点	儿子数 s 满足 ⌈m/2⌉ ≤ s ≤ m
③	非叶结点	含 n = s − 1 个关键字；子树数 = 关键字数 + 1；形态 `(n, A₀, (K₁,R₁), …, Aₙ)`
④	所有叶子	同处一层；不带信息，为空的查找失败结点

关键结论：一个磁盘块作为一个 B 树结点。结点中 Aᵢ 是指向硬盘块的子树地址，Rⱼ 是关键字对应记录的硬盘地址；记住子树数 = 关键字数 + 1，所有叶子始终在同一层（B 树是平衡树）。

结点结构剖析

n=3 A₀ K₁R₁ A₁ K₂R₂ A₂ K₃R₃ A₃

n＝关键字个数 · A_i＝子树（硬盘块）地址 · K_j＝关键字（K₁<…<K_n） · R_j＝该关键字记录的硬盘地址。子树数 = 关键字数 + 1；一个磁盘块即一个结点。

2B 树查找

从根逐层下行，结点内按区间选子树指针；每下一层 = 一次磁盘 I/O。

查找的目标：从根结点出发，逐层下行直到命中关键字或确认失败。由于儿子众多、树高很低，整个过程只需很少的几次磁盘 I/O。

查找过程

从根结点开始，逐层向下行进。
在当前结点内部，将待查值与有序的关键字 K₁<K₂<…<K_n 比较，按其落入的区间选择对应的子树指针 A_i，沿该指针下行到下一层结点。
重复上述比较与下行，直到判定成败。

回顾结点的形态 (n, A₀, (K₁,R₁), A₁, …, (K_n,R_n), A_n)：每个关键字两侧各有一个子树指针，待查值落在哪个区间，就走哪一根 A_i。

成败判定

查找成功：在某结点内到达对应的关键字位置（待查值等于某个 K_j），即可由其 R_j 取得记录的硬盘地址。
查找失败：一路下行最终落到空的叶子结点 F（不带信息、指针为空的查找失败结点），此时确定待查值不存在。

注意：必须真正到达某关键字处（成功）或落到空叶结点 F（失败），才能判定成败，中途不能提前结束。

磁盘 I/O 与代价

一个磁盘块对应一个 B 树结点，因此每下行一层就对应一次磁盘 I/O（读入该层结点所在的磁盘块）。下行的层数最多就是树高，所以：

查找的磁盘 I/O 次数 ≈ 树高（M 叉查找树最佳高度 log_MN）

B 树通过增大分叉压低树高，从而把昂贵的磁盘访问次数降到很小的常数——这正是 B 树查找高效的根本原因。

3B 树插入与分裂

总在最底层插入；结点超员（达 m 个关键字）则居中关键字上移、一分为二。

插入位置：B 树的插入总是发生在最底层的非叶结点。先按查找过程逐层下行定位到目标结点，再把新关键字按序插入该结点中。

插入后是否需要分裂

若插入后结点的关键字数 ≤ m−1，结点未超员，直接结束。
若插入前该结点关键字数已 = m−1（插入后达到 m 个、超员），则必须分裂。

分裂过程

把超员结点一分为二，拆成前半与后半两个结点。
排序后居中的那个关键字上移到父结点，使父结点增加一个关键字、一棵子树（上移关键字两侧分别由前半、后半两个结点承接）。
若父结点因此也超员，则递归分裂，沿查找路径向上传播，必要时一直传到根。

插入复杂度 ≈ 2 × 树高

易错提醒（以 5 阶 B 树为例）

每个结点最多 m−1 = 4 个关键字；插入第 5 个关键字时才会分裂，而不是更早。
上移到父结点的是排序后居中的那个关键字，不是任意挑选的关键字。
目标结点未满（关键字数 < m−1）则不分裂，按序插入即可结束。

口诀：定位到最底层非叶结点 → 按序插入 → 未超员就结束；超员则裂为前后两半、居中关键字上移到父（父增一关键字、一子树），父若超员再向上递归。

4B 树删除（借 / 合并 / 树高−1）

删内部用替身覆盖；删底层后低于下限「先借后合并」，合并可向上传播至掏空根。

删除内部结点的关键字不能直接删，而是用替身覆盖后转化为删除最底层的替身：

用后继替身：取该关键字右子树的最左关键字覆盖之；
用前驱替身：取该关键字左子树的最右关键字覆盖之。

覆盖后，原问题就转化为删除最底层（非叶）结点中的替身关键字。

删除最底层关键字后的判定

在最底层删去关键字后，按结点当前的关键字数与下限比较：

若仍满足关键字数下限，则删除完成，结束；
若低于下限，按先借后合并处理。

借（向兄弟领养）

当左/右兄弟有富余（关键字数高于下限）时，经父结点中转完成借：

父的分隔关键字下移到本结点；
兄弟的端点关键字上移到父结点。

借之后本结点关键字数回到下限及以上，父结点关键字数不变，结束。

合并

当左、右兄弟都恰为下限、无可借时，进行合并：

父的分隔关键字下移并入合并后的结点；
本结点与该兄弟合为一个结点，父结点关键字数减一。

口诀：先借后合并。兄弟有富余就借（父的分隔关键字下移、兄弟端点关键字上移，经父中转），兄弟都到底就合并（父的分隔关键字下移并入、父关键字数减一）。

失衡的向上传播

合并会使父结点关键字数减一，父结点因此可能低于下限而失衡，于是在父结点这一层继续按"先借后合并"处理，失衡可能逐层向上传播。

最坏情况：若传播一直到达根，且根被掏空，则删去根，整棵树高度减一。

常规删除：简单删除 → 借 → 合并 → 替身+借

合并向上传播：根被掏空 → 整树高度 −1（最坏情况）

5m 阶数的选择

让一个磁盘块恰好装下一个结点，由块容量反推阶数 M。

B 树要靠磁盘块承载结点：一个磁盘块作为一个结点。因此结点能容纳多少内容，由磁盘块的物理容量决定，阶数 M正是据此倒推出来的——块越大、能放下的分支越多，树就越扁，磁盘 I/O 越少。

结点内的三类存储

设磁盘块容量为 max 字节，每个关键字占 key 字节。一个 M 阶结点最多有 M 个儿子、M−1 个关键字，结点内需要同时存放三类内容：

关键字：最多 M−1 个，每个 key 字节，共 (M−1)×key。
子树（分支）地址：指向下层结点（硬盘块）的指针 A_i，最多 M 个。
记录地址：每个关键字对应记录的硬盘地址 R_j，最多 M−1 个。

确定 M 的不等式

三类内容之和不能超过一个磁盘块的容量，由此得到约束：

(M−1)×key + M 个分支地址 + (M−1) 个记录地址 < max

把不等式中三项依次对应到上面三类存储：(M−1)×key 为关键字所占空间，M 个分支地址为子树指针所占空间，(M−1) 个记录地址为记录指针所占空间。求解该不等式即可确定满足条件的最大 M。

口诀：关键字 M−1 个、分支地址 M 个、记录地址 M−1 个，三者之和小于磁盘块容量 max，解出的最大 M 就是该 B 树的阶数。

关于符号：理论约束写成严格小于 < max（内容不能塞满到溢出磁盘块）；而在第 7 节具体求解时，常对取整后的整数解写成 ≤（如 36M−32 ≤ 8192）以求满足条件的最大整数 M。两式并不矛盾。

6B+ 树定义（M 阶）

数据全在叶子、叶子连成单链表：随机查找与顺序遍历兼得（索引顺序文件）。

B 树支持随机查找，但若要按序遍历全部记录则是灾难——必须做中序遍历，遍历代价高昂。B+ 树兼顾随机查找与顺序访问，本质上是一种索引顺序文件。

M 阶 B+ 树满足以下五条性质——核心思想是：数据记录全部下沉到叶子，非叶结点只作为查找的"路标"。

编号	性质
①	数据记录只存储于叶子；非叶结点至多含 `M−1` 个键，仅用于引导查找。其中第 i 个键 = 第 i+1 棵子树的最小值。
②	根结点或是叶子，或有 `2 ~ M` 个儿子。
③	除根外，非叶结点的儿子数为 `⌈M/2⌉ ~ M`（防止退化）。
④	所有叶子都在同一层；每个叶子含 `⌈L/2⌉ ~ L` 个数据项。
⑤	所有叶子连成一个单链表。

第 i 个键 = 第 i+1 棵子树的最小值　|　非叶结点键数 ≤ M−1　|　非叶结点（除根）儿子数 ∈ [⌈M/2⌉, M]　|　叶子数据项 ∈ [⌈L/2⌉, L]

查找

从根结点开始，按关键字落入的区间逐层下行，直到到达叶子。

由于数据地址只在叶子，查找必须到达叶子才能判定成败——这一点与 B 树"可停于任一层"不同。

7B+ 树 L 与 M 的选择

由块大小、键长、指针长、记录长反推 M 与每叶容量 L。

L 与 M 的选择由磁盘块容量决定：一个磁盘块作为一个结点，要让结点内的全部内容恰好放进一个块中，由此用不等式反解出 M 与 L。

非叶结点：确定 M

给定参数：磁盘块 8192 字节、键 32 字节、分支地址 4 字节。一个非叶结点至多含 M−1 个键（仅用于引导查找），并带 M 个分支地址。

(M − 1) × 32 + M × 4 = 36M − 32 ≤ 8192

解此不等式（36M ≤ 8224）即得 M = 228。

叶子：确定 L

数据记录只存储于叶子。若每条记录 256 字节，则一个磁盘块能容纳的记录数为：

8192 / 256 = 32

故 L = 32，即每个叶子含 16 ~ 32 条数据项（叶子的下限为 ⌈L/2⌉ = 16，上限为 L = 32）。

结点类型	容量约束	结果
非叶结点	`36M − 32 ≤ 8192`	M = 228
叶子	`8192 / 256 = 32`	L = 32，每叶 16 ~ 32 条

通常 L 远小于 M：一条完整记录（256 字节）远大于一个键（32 字节），故同一磁盘块在叶子中只能装下较少记录，而在非叶结点中可装下很多键。

8B+ 树插入与删除

叶满分裂、复制分隔键上移；叶不足则领养或合并，根只剩一子才变矮。

B+ 树插入与删除的核心在于维护两条不变量：每个叶子含 ⌈L/2⌉ ~ L 个数据项、所有叶子同层。任何插入都从叶子开始，任何删除引发的失衡都可能逐层向上过滤，因此调整始终沿查找路径传播。

本页演示参数为 M=4,L=4，所以除根外非叶结点的儿子数下限是 ⌈4/2⌉=2；可视化里出现 2 个孩子是合法状态。真正必须一直维护的是索引键不变量：每个非叶结点都应满足 keys[i] = min(children[i+1])，删除、领养、合并和内部调整后都要按右侧子树最小值刷新分隔键。

插入

插入时先定位到叶子（从根按区间下行直到对应叶子），再分情况处理：

叶子不满：直接把数据项插入该叶子，结束。
叶子满：把该叶子分裂为两个半满叶子，并更新父结点。
父结点满：父结点继续分裂，沿查找路径向上传播；最坏情况一直分裂到根。

正因为分裂可能一路传到根，根允许仅有两个孩子——这是合法状态。

删除

删除发生在叶子。当某叶子的元素数降到最小值以下（低于 ⌈L/2⌉）时，按"先借后合并"调整：

领养（借）：邻居（兄弟叶子）有富余时，从邻居处领养一个数据项补足本结点。
合并：邻居也恰为最少时，两者合并为一个叶子，父结点失去一个孩子。

合并使父结点孩子数减一，可能导致父结点也低于下限，于是失衡向上过滤直到根。

当过滤到根、使根只剩一个孩子时：删去根，让其唯一的孩子成为新根。这是唯一使 B+ 树变矮的情况。

操作	触发条件	处理方式	向上影响
插入	叶子不满	直接插入	无
插入	叶子满	分裂为两个半满叶并更新父	父满则继续分裂，最坏分裂到根
删除	邻居有富余	领养（借）邻居一项	就地解决，不向上传播
删除	邻居也最少	合并，父失去一个孩子	向上过滤；根只剩一子则删根、其子为新根（唯一变矮）

插入：叶分裂（复制最小值上移）→ 内部分裂 → 新建根（树高+1）

删除：领养（借）→ 合并 → 根只剩一子 → 树高 −1（B+ 唯一变矮情形）

9性能与 B 树 / B+ 树比较

深度 log_⌈M/2⌉(2N/L)，一般 3~4 层；叶链表使顺序遍历轻而易举。

性能分析的核心目标：估算 B+ 树的深度（即查找需要的磁盘读次数），并与 B 树对比两者在查找、插入、删除及顺序遍历上的差异。

B+ 树的深度估计

设共有 N 条记录。由于每个叶子至少装 ⌈L/2⌉ 个数据项，最坏情况下叶子尽量稀疏，最多会有 2N/L 个叶子。又因除根外每个非叶结点至少有 ⌈M/2⌉ 个儿子，从叶子层向上收敛的速度由 ⌈M/2⌉ 决定，于是树的深度为：

最坏叶子数 = 2N / L，深度 = log_⌈M/2⌉(2N / L)

在常见参数下（L 远小于 M，分叉很大），这个深度一般只有 3 ~ 4 层 即够。

磁盘访问代价

查找：至多约 5 次读磁盘。
插入 / 删除：在查找之上多一次写（写回被修改的结点）。
分裂 / 归并：至多再加 4 次写；此类操作罕见，可均摊忽略。

B 树 vs B+ 树

关键差别在于数据存放位置：B 树的关键字与地址可分布在任何结点，因此查找可停于任一层；B+ 树的全部数据都在叶子，因此查找必到叶子。

对比项	B 树	B+ 树
关键字与地址分布	可分布在任何结点	全部数据在叶子，非叶仅引导查找
查找终止位置	可停于任一层	必到叶子
查找时间	≤ 树高	一定 = 树高
插入 / 删除最差代价	树高的 2 倍	树高的 2 倍

查找时间口诀：B 树查找时间 ≤ 树高（可能早停），B+ 树查找时间 恒 = 树高（必到叶）；而两者的插入 / 删除最差代价都是树高的 2 倍。

B+ 树便于按序遍历

B+ 树的全部记录都按序排在叶子层，并由单链表串起，因而顺序访问极为方便：

用头指针指向首叶；
各叶的尾指针链向右邻叶，组成一个单链表；
顺着链一路向右，即可顺序遍历全部记录。

这正是 B+ 树相对 B 树的关键优势：随机查找用树结构，顺序遍历则沿叶子单链表直接扫描，无需中序遍历。