Lecture 27：B 树

B 树不是二叉树，而是面向外存的多路平衡查找树。一个结点装多个关键字和多个子指针，以较少的磁盘块访问跨越大量关键字；B+ 树则把全部记录放在叶结点，并把叶结点串起来以支持高效范围查询。

27.1 m 阶 B 树

27.1.1 结构定义

定义：#m阶B树

描述：一棵 $m$ 阶 B 树是多路平衡查找树。一个结点至多有 $m$ 棵子树，关键字按升序排列；所有表示查找失败的外部空指针位于同一层，因此所有实际终端结点也位于同一层。

• 教材补充：本节采用标准 B 树约定 $m\ge 3$；若取 $m=1$ 或 $m=2$，最少分支约束以及以 $\lceil m/2\rceil$ 为底的高度公式会退化，不属于下文公式的适用范围。

设某非叶结点有 $k$ 个关键字：

$$ (P_0,K_1,P_1,K_2,\ldots,K_k,P_k) $$

则它有 $k+1$ 个子树，且满足：

$$ \begin{aligned} &\forall x\in T_0,\quad x<K_1,\ &\forall x\in T_i,\quad K_i<x<K_{i+1}\quad(1\le i<k),\ &\forall x\in T_k,\quad K_k<x. \end{aligned} $$

其中 $P_i$ 是指向子树 $T_i$ 的指针。不能直接写成“$P_0<K_1<P_1$”，因为指针本身不是关键字；真正参与大小关系的是它所指子树中的全部关键字。

阶数约束：

• “$m$ 阶”表示最多 $m$ 个孩子，因此最多只有 $m-1$ 个关键字；这是 B 树最常见的计数错误。
• 除根外的最少孩子数为 $\lceil m/2\rceil$，不是 $m/2$ 的简单小数截断。
• 408 教材常把不带信息的空指针位置称为“叶结点”，把最底层实际关键字结点称为“终端结点”；有些资料则直接把终端结点称作叶结点。答题时先看题目术语，但两种口径描述的是同一结构。
• 外部叶结点同层保证从根下降到失败位置的路径等长，B 树不会退化成单支链。

蓝色结点是保存关键字的实际结点，紫色方块是概念上的失败结点/空指针位置。不能把紫色方块误认为存储记录的 B 树结点。

27.1.2 高度范围

令 $n$ 为 B 树中的关键字总数，$h$ 为实际关键字结点的层数（根为第 $1$ 层，不计最下方外部空指针），并令：

$$ t=\left\lceil\frac m2\right\rceil $$

• 当每个结点都尽量装满时，高度最小。前 $h$ 层最多包含：

$$ (m-1)(1+m+\cdots+m^{h-1})=m^h-1 $$

故 $n\le m^h-1$，得到：

$$ h\ge\left\lceil\log_m(n+1)\right\rceil $$

• 当结点都尽量少装时，高度最大。若 $h\ge2$，根至少有 $1$ 个关键字和 $2$ 个孩子，其余非根结点至少有 $t-1$ 个关键字，因此：

$$ n\ge 1+2(t-1)(1+t+\cdots+t^{h-2})=2t^{h-1}-1 $$

从而：

$$ h\le\left\lfloor\log_t\frac{n+1}{2}\right\rfloor+1 $$

综合可写为：

$$ \left\lceil\log_m(n+1)\right\rceil \le h\le \left\lfloor\log_{\lceil m/2\rceil}\frac{n+1}{2}\right\rfloor+1 $$

WARNING · 高度口径 若题目把外部失败结点也计入层数，上述上下界整体再加 $1$；计算前必须先确认题目是否把空指针层算作树高。

27.1.3 查找

过程：

1. 在当前结点内从小到大（或用结点内二分）比较关键字。
2. 若等于某个 $K_i$，查找成功。
3. 若 $K_i<key<K_{i+1}$，转入中间指针 $P_i$；小于最小键走 $P_0$，大于最大键走 $P_k$。
4. 在实际终端结点仍未找到目标时，沿相应空指针到达外部失败位置，查找失败；不要把存关键字的终端结点与不存信息的外部叶结点混为一谈。

查找 $9$ 时，先在根结点用 $22$ 判断走左子树，再在 $5,11$ 间选择中间子树，最后在终端结点 $6,8,9$ 中命中。

• 外存模型中，一般把读取一个结点当作一次磁盘 I/O。B 树分支多、高度低，故 I/O 次数远少于同规模二叉树。
• 结点内比较次数并非 I/O 次数；题目问“比较关键字次数”与问“磁盘访问次数”时，统计口径不同。
• B 树成功查找可能在内部结点提前结束，所以不同成功查找的结点访问层数不一定相同；只有失败查找都会下降到同一外部叶层。B+ 树才要求成功查找最终到达叶结点。
• 若结点内采用二分查找，单结点比较为 $O(\log m)$、结点访问为 $O(h)$，总 CPU 比较量为 $O(h\log m)=O(\log n)$；外存分析通常更关注至多 $h$ 次结点读取。

---

27.2 B 树的插入与删除

27.2.1 插入与分裂

插入原则：

1. 像查找一样向下定位，新关键字总是先插入终端（叶）结点。
2. 若插入后该结点至多有 $m-1$ 个关键字，结束。
3. 若出现 $m$ 个关键字，结点上溢：取中间关键字上移到父结点，两侧关键字分别组成两个子结点。
4. 父结点也可能上溢，按相同规则继续向上分裂；根分裂时产生新根，树高加 $1$。

对一个含 $m$ 个关键字的溢出结点，按 1 开始计数，上移第 $\lceil m/2\rceil$ 个关键字。分裂后左右结点均满足关键字数下限。

• 例如 5 阶 B 树原结点最多有 4 个关键字；插入第 5 个后，上移第 3 个，左右各保留 2 个。
• 上移的关键字不再留在两个子结点中；把它复制到父结点但不移出子结点是 B+ 树索引概念，不能直接套在 B 树插入上。
• 若分裂发生在非终端结点，还须按关键字区间把原来的孩子指针分配给分裂后的左右结点；不能只拆分关键字数组。

27.2.2 删除、借位与合并

删除原则：

• 若待删关键字在非终端结点，用其直接前驱或直接后继替换，然后转化为删除终端结点关键字。
• 删除后若结点关键字数仍不少于 $\lceil m/2\rceil-1$，结束。
• 若低于下限，优先向相邻兄弟结点借一个关键字：父结点中的分隔关键字下移，本兄弟的一个关键字上移到父结点，保持范围关系。
• 若相邻兄弟也处于下限，便与兄弟及父结点中间的分隔关键字合并；父结点可能因此继续下溢，向上递归处理。
• 根结点删除后若没有关键字且仍有唯一孩子，可让该孩子成为新根，树高减 $1$。

易错点：

• “借”不是只把兄弟一个关键字横向搬过来，必须经过父结点的分隔关键字，否则子树范围会错位。
• 合并时要把父结点的分隔关键字一起放入合并结点。
• 借位或合并若发生在非终端结点，还必须同步转移相应的孩子指针，保持每个子树的关键字范围以及“$k$ 个关键字对应 $k+1$ 个孩子”的关系。
• 非终端结点删除不会直接丢掉整个结点，先用前驱/后继替换才可保持有序关系。

---

27.3 B+ 树

27.3.1 结构特点

定义：#B+树

描述：B+ 树同样是多路平衡查找树，但全部关键字及对应记录地址都存于叶结点；非叶结点只保存用于导航的索引关键字和孩子指针，所有叶结点通过指针按关键字顺序连接。

• 每个分支结点最多有 $m$ 个孩子；非叶根结点至少有两个孩子，其他分支结点至少有 $\lceil m/2\rceil$ 个孩子。
• 非叶结点关键字仅起索引作用，不存放该关键字对应记录地址；因此一个磁盘块能容纳更多索引项，树通常更矮。
• 叶结点保存全部关键字和记录指针，且相邻叶结点相互链接。
• 课件采用“分支结点关键字是相应子树最大关键字”的表述。部分教材使用子树最小关键字作分隔符；做题应按题干的分隔符约定判断走向，结构思想相同。

按本讲“每个孩子对应一个最大关键字索引项”的约定，分支结点中关键字数等于孩子数：非叶根通常有 $2\sim m$ 个孩子/索引键，其他分支结点有 $\lceil m/2\rceil\sim m$ 个孩子/索引键。若整棵树只有一个叶根，根的最少记录数按题目给定的根特例处理；不同教材对 B+ 树阶数和叶结点最少记录数的定义可能不同，不能脱离题干硬套区间。

27.3.2 B 树与 B+ 树对比

为什么 B+ 树适合范围查询：

1. 先从根查到范围左端点所在叶结点。
2. 在该叶结点内定位第一个满足下界的关键字。
3. 沿叶结点链表向右扫描，直到超过上界。

这样不必反复回到上层索引结点，顺序 I/O 友好。

图中先沿多路索引定位到包含 $9$ 的叶结点，再利用叶链顺序访问；叶结点下方的“记录”才是对应的数据记录地址，非叶结点只负责导航。

题型：#B树阶数与结点范围

第一部分：解题方法

1. 先把“$m$ 阶”翻译成“最多 $m$ 个孩子、最多 $m-1$ 个关键字”。
2. 对非根结点写出最少孩子 $\lceil m/2\rceil$，再减一得到最少关键字。
3. 插入题先定位叶结点，再检查上溢、分裂和关键字上移；删除题先转换到叶结点，再检查下溢、借位和合并。
4. B/B+ 对比题优先抓住“记录在哪”和“叶结点是否连链”两个本质区别。

27.4 易错点总检

• “$m$ 阶”是最多 $m$ 个孩子，不是每个结点固定有 $m$ 个孩子。
• B 树结点的 $k$ 个关键字对应 $k+1$ 个孩子；按本讲约定，B+ 树分支结点的 $k$ 个索引关键字对应 $k$ 个孩子。
• B 树内部结点可命中记录，成功查找深度不固定；B+ 树内部命中索引键仍要继续下降到叶结点。
• B 树插入时中间关键字上移并离开原结点；B+ 树内部索引键可与叶结点关键字重复。
• B 树删除借位必须经过父分隔键，合并必须带上父分隔键；只在兄弟间横向搬键会破坏值域。
• 外部失败叶结点与实际终端结点的名称容易混淆，计算高度时尤其要先统一层数口径。

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：树形查找 · 下一篇：散列查找
• 关联专题：查找代码

27.5 本节复盘

• B 树的多路、同层叶结点特性用较低树高换取少量 I/O。
• $m$ 阶最多 $m$ 个孩子、$m-1$ 个关键字；非根结点下限由 $\lceil m/2\rceil$ 决定。
• 插入靠分裂上移，删除靠前驱/后继转换、借位和合并维持下限。
• B+ 树将记录集中在叶结点并链接叶子，特别适合数据库索引和范围查询。