跳转至

408 高频考点精讲:B树(B-Tree)

模块归属:数据结构 · 树与二叉树 / 查找
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生


一、 考情档案

  • 近十年考查频次:6 次(2016~2025 年:2016#10、2018#8、2020#10、2022#8、2023#7、2025#8)
  • 历年总考查频次:10 次(含 2009#9、2012#9、2013#8、2014#9 等,历年命题频率极高)
  • 出题形式:单项选择题(包含极值数学推导、算法动态操作推演、基本性质辨析、合法拓扑计数)
  • 命题特点:
  • 考查频度极高且稳定:近十年考查 6 次,平均每 1~2 年必设一道选择题(分值 2 分)。
  • 考点考查纵深明显:由最初的定义参数记忆(如阶数与子树下限),逐步转向算法动态平衡全过程推演(插入分裂、删除借键与合并),并在 2025 年延伸至受约束的树拓扑形态组合计数。
  • 三大命题主线高度集中:
    • 容量及高度极值推导:阶数 \(m\)$ \text{、高度} $\(h\)$ \text{、关键字数} $\(N\) 之间的上下界代数推导;
    • 动态维护操作推演:终端结点插入引起的中位关键字上溢分裂、删除引起的直接前驱/后继替换、下溢兄弟借键及父子合并;
    • 结构差异辨析:B树(多路平衡查找树)与作为数据库/文件索引结构的 B+树的核心特征对比。
近十年考查年份分布:
2016   2017   2018   2019   2020   2021   2022   2023   2024   2025
 √      -      √      -      √      -      √      √      -      √
(#10)         (#8)          (#10)         (#8)   (#7)          (#8)

二、 具体考察内容

1. B树的严格数学定义及物理结构

(1) 基本概念

B树(B-Tree),即多路平衡查找树(Multiway Balanced Search Tree)。一棵 \(m\)$ \text{阶 B 树或为空树,或为满足如下性质的} $\(m\) 叉树: 1. 树中结点的子树上界:树中每个结点至多有 \(m\)$ \text{棵子树,即至多含有} $\(m - 1\) 个关键字。 2. 根结点的子树下界:若根结点不是终端结点,则至少有 2 棵子树,即至少含有 1 个关键字。 3. 非根分支结点的子树下界:除根结点外的所有非叶分支结点至少有 \(\lceil m/2 \rceil\)$ \text{棵子树,即至少含有} $\(\lceil m/2 \rceil - 1\) 个关键字。 4. 叶结点的绝对共层性:所有的叶结点都出现在同一层次上,并且不携带任何实际信息(叶结点代表查找失败的外部虚结点,指针为空)。

(2) 结点存储结构

在 B 树中,结点的逻辑结构形式统一表示为: $\((n, P_0, K_1, P_1, K_2, P_2, \dots, K_n, P_n)\)$ 其中各字段含义及数学约束如下: - \(n\):该结点当前实际包含的关键字个数。 - \(K_i\)(\(1 \le i \le n\)):结点的关键字,按严格单调递增排列: $\(K_1 < K_2 < \dots < K_n\)$ - \(P_i\)(\(0 \le i \le n\)):指向子树根结点的指针。满足严格的多路大小关系: - 指针 \(P_0\)$ \text{所指子树中所有结点的关键字均小于} $\(K_1\); - 指针 \(P_i\)(\(1 \le i \le n-1\)$ \text{)所指子树中所有结点的关键字均大于} $\(K_i\)$ \text{且小于} $\(K_{i+1}\); - 指针 \(P_n\)$ \text{所指子树中所有结点的关键字均大于} $\(K_n\)。

(3) 核心概念辨析:终端结点对比叶结点

在 408 考研及权威教材(严蔚敏版、Knuth 体系)中,必须严格区分两类底层结点: - 终端结点(Terminal Nodes / 最后一层分支结点):树中包含实际数据关键字的最底层物理结点,其子树指针均指向外部叶结点。 - 叶结点(Leaf Nodes / 外部结点 / 失败结点 External Nodes):位于终端结点之下的一层虚构结点,不包含任何关键字和有效数据,对应查找失败时的空指针 NULL。 - 命题审题陷阱:部分真题题干会将最底层的“终端结点”通俗称为“叶结点”(如 2023 年第 7 题)。遇到此类表述,需结合选项语境辨析其指的是“包含关键字的最底层非空结点”还是“不含数据的外部失败结点”。


2. 各类结点关键字与子树数目界限汇总

对于一棵 \(m\)$ \text{阶 B 树(} $\(m \ge 3\)),不同类型结点的参数上下界必须精准掌握:

结点类型 子树个数范围 关键字个数范围 备注说明
根结点(非叶/非终端结点) \([2, m]\) \([1, m - 1]\)$ \text{ 树高} $\(\ge 2\) 时,根结点至少 2 棵子树、1 个关键字
非根分支结点(内部内部结点) \([\lceil m/2 \rceil, m]\) \([\lceil m/2 \rceil - 1, m - 1]\) 下限取自阶数的一半向上取整减 1
终端结点(底层关键字结点) \([0, 0]\)$ \text{(指向外部指针为} $\([\lceil m/2 \rceil, m]\)) \([\lceil m/2 \rceil - 1, m - 1]\) 最底层的实际关键字载体
根结点(整棵树仅含 1 个结点) \([0, 0]\) \([1, m - 1]\)$ \text{ 此时树高} $\(h = 1\),根结点即终端结点

3. B树高度与关键字容量极值推导(严格数学证明)

约定:树高 \(h\)$ \text{定义为包含实际关键字的层数(根结点为第 1 层,终端结点为第} $\(h\)$ \text{层,外部失败结点为第} $\(h+1\)$ \text{层)。全树关键字总数为} $\(N\)。

(1) 基础定理:外部叶结点数与关键字总数恒等关系

定理:含有 \(N\)$ \text{个不同关键字的任意 B 树,其外部叶结点(失败结点)总数} $\(N_{\text{leaf}}\) 恒满足: $\(N_{\text{leaf}} = N + 1\)$ 证明: 任意 \(N\) 个有序排列的关键字: $\(K_1 < K_2 < \dots < K_N\)$ 在实数轴上构成了 \(N\)$ \text{个分割点,将整个值域空间} $\((-\infty, +\infty)\)$ \text{严格划分为} $\(N + 1\) 个互不相交的开区间: $\((-\infty, K_1), (K_1, K_2), \dots, (K_{N-1}, K_N), (K_N, +\infty)\)$ 在多路查找过程中,若目标关键字落入这 \(N + 1\)$ \text{个开区间中的任意一个,均对应一次查找失败,并最终落到对应的某一个外部叶结点指针。因此,查找失败的区间数与外部叶结点数严格一一对应,必有} $\(N_{\text{leaf}} = N + 1\)。证毕。

(2) 树高度 h 下界推导(关键字容量最大模型 / 最矮形态)

为使高度为 \(h\)$ \text{的} $\(m\)$ \text{阶 B 树容纳尽可能多的关键字,树必须达到完全饱和状态:全树每个结点的关键字数均达到上限} $\(m - 1\)$ \text{,拥有} $\(m\) 棵子树。 此时,全树为一棵满 \(m\) 叉树: - 第 1 层结点数:\(m^0 = 1\) - 第 2 层结点数:\(m^1 = m\) - 第 3 层结点数:\(m^2\) - ... - 第 \(h\)$ \text{层结点数:} $\(m^{h-1}\)

全树总结点数 \(M_{\max}\) 为: $\(M_{\max} = \sum_{i=1}^h m^{i-1} = \frac{m^h - 1}{m - 1}\)$ 因为每个结点恰含 \(m - 1\)$ \text{个关键字,所以高度为} $\(h\)$ \text{的} $\(m\)$ \text{阶 B 树所能容纳的最大关键字总数} $\(N_{\max}\) 为: $$N \le N_{\max} = (m

  • 1) \cdot M_{\max} = (m

  • 1) \cdot \frac{m^h

  • 1}{m

  • 1} = m^h

  • 1$$ 对不等式两端变形: $\(m^h \ge N + 1 \implies h \ge \log_m (N + 1)\)$ 由于高度 \(h\) 必须为正整数,故树高下界为: $\(h_{\min} = \lceil \log_m (N + 1) \rceil\)$

(3) 树高度 h 上界推导(关键字容量最小模型 / 最瘦长形态)

为使高度为 \(h\)$ \text{的} $\(m\) 阶 B 树含有的关键字总数最少,各结点的分支数和关键字数均必须取理论下限: - 根结点(第 1 层):仅含 1 个关键字,拥有 2 棵子树; - 第 2 层:恰好有 2 个结点; - 第 2 层至第 \(h\)$ \text{层的每个结点,均取子树下界} $\(\lceil m/2 \rceil\)$ \text{,关键字数均取下界} $\(\lceil m/2 \rceil - 1\); 各层的最少结点数依次为: - 第 1 层:\(1\) 个结点 - 第 2 层:\(2\) 个结点 - 第 3 层:\(2 \lceil m/2 \rceil\) 个结点 - 第 4 层:\(2 (\lceil m/2 \rceil)^2\) 个结点 - ... - 第 \(h\)$ \text{层(终端结点层):} $\(2 (\lceil m/2 \rceil)^{h-2}\) 个结点

由于第 \(h\)$ \text{层的每个结点拥有} $\(\lceil m/2 \rceil\)$ \text{棵指向外部失败叶结点的指针,因此第} $\(h+1\) 层(外部叶结点层)的叶结点总数满足: $\(N_{\text{leaf}} \ge 2 (\lceil m/2 \rceil)^{h-2} \cdot \lceil m/2 \rceil = 2 (\lceil m/2 \rceil)^{h-1}\)$ 代入基础定理 \(N_{\text{leaf}} = N + 1\): $\(N + 1 \ge 2 (\lceil m/2 \rceil)^{h-1}\)$ 两端同时除以 2 并取对数: $\(\frac{N + 1}{2} \ge (\lceil m/2 \rceil)^{h-1} \implies h - 1 \le \log_{\lceil m/2 \rceil} \left( \frac{N + 1}{2} \right)\)$ $\(h \le \log_{\lceil m/2 \rceil} \left( \frac{N + 1}{2} \right) + 1\)$ 由于高度 \(h\) 必须为正整数,故树高上界为: $\(h_{\max} = \lfloor \log_{\lceil m/2 \rceil} \left( \frac{N + 1}{2} \right) \rfloor + 1\)$

(4) 高度极值综合不等式

对于包含 \(N\)$ \text{个关键字的} $\(m\)$ \text{阶 B 树,其高度} $\(h\)(包含关键字层数)严格满足: $\(\lceil \log_m (N + 1) \rceil \le h \le \lfloor \log_{\lceil m/2 \rceil} \left( \frac{N + 1}{2} \right) \rfloor + 1\)$


4. B树的查找算法

B 树作为多路平衡查找树,其查找过程由两个基本操作交替进行: 1. 树上层间定位(访盘 I/O):从根结点开始,沿着指针逐层向下检索。由于 B 树常用于文件系统或大型数据库,结点规模通常与磁盘块(Page/Block)大小对齐,每次读取一个结点对应一次磁盘 I/O。 2. 结点内部查找(内存检索):将结点调入内存后,在有序数组 \((K_1, K_2, \dots, K_n)\)$ \text{中检索目标关键字} $\(Key\)(可使用顺序查找或折半查找): - 若 \(Key = K_i\):在当前结点中命中,查找成功,返回数据记录地址并终止; - 若 \(K_i < Key < K_{i+1}\)$ \text{:未命中,沿对应指针} $\(P_i\) 载入子树根结点,重复查找; - 若指针 \(P_i\)$ \text{为 NULL:说明已经抵达第} $\(h+1\) 层的外部失败叶结点,查找失败并终止。

复杂度分析: 树的高度 \(h = O(\log_m N)\)$ \text{,结点内部折半查找耗时} $\(O(\log_2 m)\)。全树查找的总时间复杂度为: $\(T(n) = O(\log_m N \cdot \log_2 m) = O\left( \frac{\log_2 N}{\log_2 m} \cdot \log_2 m \right) = O(\log_2 N)\)$ 虽然 CPU 比较次数与二叉平衡树同阶,但 B 树将树高降至 \(\log_m N\),大幅削减了极其耗时的磁盘 I/O 次数。


5. B树的插入算法与上溢分裂机制

(1) 基本插入原则

新关键字的插入必须且只能发生在最底层的终端结点中。严禁直接向内部非终端分支结点插入新关键字。

(2) 插入与上溢处理流程

  1. 定位插入结点:调用查找算法,确定新关键字应插入的目标终端结点。
  2. 按序放入关键字:将关键字按升序放入该终端结点的关键字序列中。
  3. 容量检测与上溢判断:
  4. 若插入后该结点关键字数 \(k \le m - 1\):符合容量限制,插入完成;
  5. 若插入后该结点关键字数 \(k = m\):超出容量上限,发生上溢(Overflow),必须执行结点分裂(Split)。

(3) 上溢分裂算法步骤

当结点关键字数达到 \(m\) 时,执行分裂: 1. 确定中位关键字:在已排序的 \(m\) 个关键字中,取位置为: $\(\text{MidIndex} = \lceil m / 2 \rceil\)$ 处的关键字 \(K_{\lceil m / 2 \rceil}\) 作为提升对象。 2. 分裂为左右两部分: - 左部分:索引 \(1 \sim \lceil m / 2 \rceil - 1\)$ \text{的关键字及对应指针保留在原结点中(共} $\(\lceil m / 2 \rceil - 1\) 个关键字); - 右部分:索引 \(\lceil m / 2 \rceil + 1 \sim m\)$ \text{的关键字及对应指针放入新分配的右兄弟结点中(共} $\(m - \lceil m / 2 \rceil\) 个关键字); 3. 中位关键字上移:将中位关键字 \(K_{\lceil m / 2 \rceil}\) 插入到原结点的双亲结点中,并将其右侧指针指向新分配的右兄弟结点。 4. 级联分裂与树高增长: - 双亲结点在接收提升的关键字后,其关键字数同样增加 1。若双亲结点的关键字数也达到 \(m\),则对双亲结点继续执行分裂; - 分裂过程可沿着父指针链路自底向上一路级联传播; - 若根结点发生分裂,由提升的中位关键字生成一个全新的单关键字根结点,左右指针分别指向分裂产生的两半。这是 B 树高度增长的唯一机制。


6. B树的删除算法四种情形

B 树删除算法的核心思想:将一切非终端结点的删除化归为最底层终端结点的删除,并通过借键或合并维护结点的下界约束。

(1) 非终端结点的删除化归

若待删除关键字 \(K\) 位于非终端结点中: - 必须在其左子树中选取直接前驱(左子树中最右下终端结点的最大关键字),或在其右子树中选取直接后继(右子树中最左下终端结点的最小关键字); - 用该直接前驱(或后继)的值覆盖被删关键字 \(K\); - 随后将问题转化为在对应的底层终端结点中删除该直接前驱(或后继)。

(2) 终端结点的删除及下溢维护

在终端结点中删除目标关键字后,若该结点剩余关键字数 \(k\) 满足: $\(k \ge \lceil m / 2 \rceil - 1\)$ 则结点合法,删除操作完成。若 \(k < \lceil m / 2 \rceil - 1\)(发生下溢 Underflow),根据相邻兄弟结点的关键字盈余状态,分为以下三种情形调整:

情形一:兄弟够借 —— 向左兄弟借键
  • 触发条件:当前结点的左相邻兄弟结点关键字富余,即其关键字数: $\(k_{\text{left}} \ge \lceil m / 2 \rceil\)$
  • 调整规则(父子兄三方联动旋转):
  • 将双亲结点中介于左兄弟与当前结点之间的分割关键字下移至当前结点的最左端;
  • 将左兄弟结点的最大关键字上移至双亲结点中,填补下移关键字的原位置;
  • 将左兄弟的最右侧子树指针转交给当前结点作为最左侧子树指针。 调整后,当前结点、左兄弟结点及双亲结点的关键字数均满足合法界限。
情形二:兄弟够借 —— 向右兄弟借键
  • 触发条件:左兄弟无富余但右相邻兄弟结点富余,即其关键字数: $\(k_{\text{right}} \ge \lceil m / 2 \rceil\)$
  • 调整规则(对称旋转):
  • 将双亲结点中介于当前结点与右兄弟之间的分割关键字下移至当前结点的最右端;
  • 将右兄弟结点的最小关键字上移至双亲结点;
  • 将右兄弟的最左侧子树指针转交给当前结点作为最右侧子树指针。
情形三:兄弟都不够借 —— 结点合并(Merge)
  • 触发条件:当前结点的左、右相邻兄弟结点的关键字数均已处于法定下限 \(\lceil m / 2 \rceil - 1\)。
  • 调整规则:
  • 将双亲结点中介于当前结点与兄弟结点之间的分割关键字下拉;
  • 将当前结点、下拉的双亲分割关键字、以及相邻兄弟结点的所有关键字三者合并为一个新结点;
  • 合并后的结点所包含的关键字总数为: $$(\lceil m / 2 \rceil

  • 2) + 1 + (\lceil m / 2 \rceil

  • 1) = 2 \lceil m / 2 \rceil

  • 2 \le m

  • 1$$ 容量严格不超过结点的容量上限,新结点合法。

  • 级联下溢与树高缩减:
  • 双亲结点因分割关键字被下拉,其关键字数减少 1;
  • 若双亲结点因此发生下溢,需自底向上递归重复上述调整;
  • 若下溢传播至根结点,且根结点原本仅有 1 个关键字,该关键字被下拉合并后,根结点变为空结点,原根结点被释放,合并后的新结点成为全新的根结点。这是 B 树高度降低的唯一机制。

7. B树和B+树核心特征对比

B+树是应大规模文件系统与数据库索引需求对 B 树进行的工程改良结构。两者具有五大核心差异:

比较维度 B 树(B-Tree) B+ 树(B+ Tree)
关键字与子树指针数量对应 每个结点包含 \(n\)$ \text{个关键字对应} $\(n + 1\)$ \text{棵子树 每个结点包含} $\(n\)$ \text{个关键字对应} $\(n\) 棵子树(部分标准定义)
关键字出现位置 各结点的关键字在全树范围内互不重复,各层均含有效数据 非叶结点的关键字仅作为索引,所有关键字必完整出现在叶结点中
数据记录指针分布 根结点、内部结点、终端结点均存放对应记录的物理存储地址 仅最底层的叶结点存放数据记录指针,非叶分支结点仅存储索引项
叶结点横向组织结构 各终端结点相互独立,不存在任何横向相连的指针 所有叶结点按关键字升序串联,构成一个双向循环链表
支持的检索方式 仅支持从根节点开始的多路分支点检索 既支持多路分支检索,又支持沿叶结点链表进行顺序查找与范围查找
分支结点容量与 I/O 效率 结点内需存储数据记录指针,单个磁盘块容纳的索引项少,树相对较高 分支结点不含数据指针,单个磁盘块可容纳更多索引项,树更矮胖,访盘 I/O 次数更少
非根分支结点关键字数范围 \([\lceil m/2 \rceil - 1, m - 1]\) \([\lceil m/2 \rceil, m]\)

三、 近十年真题精讲(2016~2025)


【真题 1】2025 年 408 第 8 题 · 4 阶 B 树拓扑形态计数

题目
给 7 个不同的关键字,能够构成不同 4 阶 B 树的个数为( )。
A. 7          B. 8          C. 9          D. 10

【解析】

  1. 分析 4 阶 B 树的结点容量约束:
  2. 阶数 \(m = 4\);
  3. 根结点关键字数 \(k_{\text{root}}\)$ \text{满足:} $\(1 \le k_{\text{root}} \le m - 1 = 3\);
  4. 非根结点的关键字数 \(k\)$ \text{满足:} $\(\lceil 4/2 \rceil - 1 = 1 \le k \le 3\);
  5. 每个结点的分支数为关键字数加 1。
  6. 给定 7 个不同的有序关键字,由于二叉/多路搜索树中各关键字的相对顺序严格唯一确定,因此不同 B 树的形态仅由树的高度以及关键字在各层结点的分配结构唯一确定。

  7. 按树高 \(h\) 分类讨论:

  8. 情形一:树高 \(h = 1\)
    整棵树仅含一个根结点,该结点必须容纳全部 7 个关键字。但 4 阶 B 树单个结点最多容纳 \(m - 1 = 3\)$ \text{个关键字,因此树高} $\(h = 1\) 的形态不存在(0 种)。
  9. 情形二:树高 \(h = 3\)(最瘦长极限形态)
    若树高为 3,根结点至少 1 个关键字(2 棵子树);第二层的 2 个结点各至少 1 个关键字(各 2 棵子树,共 4 棵子树到达第三层);第三层的 4 个终端结点各至少 1 个关键字。
    此时全树最少包含关键字数: $\(N_{\min} = 1 + (1 + 1) + (1 + 1 + 1 + 1) = 7\)$ 恰好等于 7。因此若树高为 3,每个结点必须且只能取关键字数下限 1(即退化为完全二叉树拓扑结构),每个结点的结构完全唯一固定,故树高 \(h = 3\) 的合法形态共有 1 种。
  10. 情形三:树高 \(h = 2\)
    整棵树由第 1 层根结点与第 2 层终端结点组成。根据根结点的关键字个数 \(k_{\text{root}} \in \{1, 2, 3\}\) 分别枚举:
    • 子情形 1:根结点包含 1 个关键字
      根结点拥有 2 个孩子结点,剩余 \(7 - 1 = 6\)$ \text{个关键字分配给第二层的 2 个终端结点。每个结点的容量上限为 3,下限为 1。分配方案} $\((k_1, k_2)\)$ \text{必须满足} $\(k_1 + k_2 = 6\)$ \text{且} $\(1 \le k_i \le 3\)。
      唯一的整数解为 \((3, 3)\),即左右孩子结点各分配 3 个关键字。此情形共有 1 种 结构。
    • 子情形 2:根结点包含 2 个关键字
      根结点拥有 3 个孩子结点,剩余 \(7 - 2 = 5\)$ \text{个关键字分配给第二层的 3 个终端结点。分配方案} $\((k_1, k_2, k_3)\)$ \text{满足} $\(k_1 + k_2 + k_3 = 5\)$ \text{且} $\(1 \le k_i \le 3\):
    • 组合类型 \(\{2, 2, 1\}\)$ \text{:排列数为} $\(\frac{3!}{2! \times 1!} = 3\)$ \text{种(即} $\((2, 2, 1), (2, 1, 2), (1, 2, 2)\));
    • 组合类型 \(\{3, 1, 1\}\)$ \text{:排列数为} $\(\frac{3!}{1! \times 2!} = 3\)$ \text{种(即} $\((3, 1, 1), (1, 3, 1), (1, 1, 3)\)); 合计:\(3 + 3 =\) 6 种 结构。
    • 子情形 3:根结点包含 3 个关键字
      根结点拥有 4 个孩子结点,剩余 \(7 - 3 = 4\)$ \text{个关键字分配给第二层的 4 个终端结点。分配方案} $\((k_1, k_2, k_3, k_4)\)$ \text{满足} $\(\sum k_i = 4\)$ \text{且} $\(1 \le k_i \le 3\)。
      由于每个结点至少含 1 个关键字,唯一的分配方案为 \((1, 1, 1, 1)\)。此情形共有 1 种 结构。
  11. 情形四:树高 \(h \ge 4\)
    若树高为 4,根据最小关键字公式,最少需要关键字数为 \(2 \times 2^{4-1} - 1 = 15\)$ \text{个,} $\(15 > 7\),不可能。

  12. 汇总统计不同合法拓扑总数: $$ \text{总数} = 1 (h=3) + 1 (\text{根}1\text{键}) + 6 (\text{根}2\text{键}) + 1 (\text{根}3\text{键}) = 9 \text{ 种} $$

正确答案:C


【真题 2】2023 年 408 第 7 题 · 非空 B 树操作性质辨析

题目
下列关于非空 B 树的叙述中,正确的是( )。
I. 插入操作可能增加树的高度
II. 删除操作一定会导致叶结点的变化
III. 查找某关键字一定是要查找到叶结点
IV. 插入的新关键字最终位于叶结点中
A. 仅 I          B. 仅 I, II          C. 仅 III, IV          D. 仅 I, II, IV

【解析】

  • 命题术语注意:本题题干中的“叶结点”指包含关键字的最底层非空分支结点(即终端结点)。
  • 命题逐项剖析:
  • I 正确:在最底层终端结点中插入关键字时,若引发上溢分裂,且分裂自底向上一路级联传播至根结点,会导致原根结点分裂产生一个新根结点,全树高度随之增加 1。
  • II 正确:在 B 树中,若被删关键字位于终端叶结点中,直接在叶结点中执行删除并维护平衡;若被删关键字位于内部非终端结点中,必须选取其直接前驱或直接后继覆盖该位置,随后转化为在最底层终端叶结点中删除该直接前驱或后继。因此,无论是何种删除操作,最终的物理删除执行点必落在最底层的叶结点上,一定会引起底层叶结点的关键字内容或指针结构发生变化。
  • III 错误:B 树是平衡多路查找树,每个非叶分支结点中均存储着有效关键字。若待查关键字恰好存放在非叶分支结点中(如根结点),一旦比对成功即提前返回,不需要也不应该继续查找到叶结点。
  • IV 错误:虽然新关键字最初始的插入动作均发生在最底层的叶结点中,但若插入导致该叶结点上溢分裂,其中位关键字会被向上提升至父结点或更高层的非叶分支结点中。若该中位关键字恰好是新插入的关键字,它最终将留存于非叶结点中,而非停留在叶结点中。
  • 综合判断:I、II 正确,III、IV 错误。

正确答案:B


【真题 3】2022 年 408 第 8 题 · 5 阶 B 树动态删除推演

题目
在 5 阶 B 树 \(T\)$ \text{中,删除关键字 260 之后需要进行必要的调整,得到新的 B 树} $\(T_1\)$ \text{。下列选项中,不可能是} $\(T_1\) 根结点中关键字序列的是( )。
A. 60, 90, 280
B. 60, 90, 350
C. 60, 85, 110, 350
D. 60, 90, 110, 350

【解析】

  1. 5 阶 B 树的合法参数边界:
  2. 阶数 \(m = 5\);
  3. 根结点关键字数 \(1 \le k \le 4\);
  4. 非根结点关键字数 \(\lceil 5/2 \rceil - 1 = 2 \le k \le 4\)。
  5. 结合题目原树结构与删除流程分析:
  6. 待删关键字 260 位于根结点中(原树根结点的关键字序列为 <60, 90, 260, 350>)。
  7. 根据非终端结点删除规则,删除 260 必须用其直接前驱(其左子树中的最大关键字)或直接后继(其右子树中的最小关键字)替换:
    • 若选取直接前驱 110 替换 260:根结点临时变为 <60, 90, 110, 350>。随后在左子树终端结点中删除 110,该终端结点剩余关键字数减少为 1,发生下溢(低于下限 2)。此时需向左兄弟借键或与兄弟合并。在向左兄弟借键的过程中,双亲中的分割关键字 90 下移至当前结点,左兄弟的最大关键字 85 上移至根结点填补 90 的空缺。此时根结点调整为 <60, 85, 110, 350>,与 C 项完全一致(C 项可能);
    • 若选取直接后继 280 替换 260:随后右子树终端结点发生下溢,若右兄弟不足以借键而发生双亲分割关键字下移合并,根结点中的关键字将被下拉一个,使得根结点关键字减少为 3 个,可能形成 <60, 90, 280> 或 <60, 90, 350>,与 A、B 项相符(A、B 项可能);
  8. 分析 D 项:
    D 选项中的关键字序列为 <60, 90, 110, 350>。若根结点为该序列,意味着 260 被直接替换为 110 后,左子树删除 110 所引发的下溢未做任何父子借键或合并调整便草草结束。而此时包含 110 的左子树结点必定处于非法下溢状态,违反了 5 阶 B 树非根结点关键字数不少于 2 的强制约束。因此 D 项绝不可能作为最终调整完毕的合法根结点状态。

正确答案:D


【真题 4】2020 年 408 第 10 题 · 4 阶 B 树依次插入动态推演

题目
依次将关键字 5, 6, 9, 13, 8, 2, 12, 15 插入初始为空的 4 阶 B 树后,根节点中包含的关键字是( )。
A. 8          B. 6, 9          C. 8, 13          D. 9, 12

【解析】

4 阶 B 树(\(m = 4\)$ \text{)每个结点最多容纳} $\(m - 1 = 3\)$ \text{个关键字。当结点内关键字达到 4 个时发生上溢,必须取第} $\(\lceil 4/2 \rceil = 2\) 个关键字提升到父结点执行分裂。

动态插入步骤逐步模拟: 1. 插入 5, 6, 9:
结点未满,放入根结点:[5, 6, 9]。 2. 插入 13:
结点变为 [5, 6, 9, 13],包含 4 个关键字,发生上溢。
取第 \(\lceil 4/2 \rceil = 2\) 个关键字(即 6)向上提升为新根结点: - 新根结点:[6] - 左子树:[5] - 右子树:[9, 13] 3. 插入 8:
8 比 6 大,进入右子树 [9, 13],按序排列为 [8, 9, 13],未超限。 4. 插入 2:
2 比 6 小,进入左子树 [5],按序排列为 [2, 5],未超限。 5. 插入 12:
12 比 6 大,进入右子树 [8, 9, 13],按序排列为 [8, 9, 12, 13],包含 4 个关键字,发生上溢。
在 [8, 9, 12, 13] 中取第 2 个关键字(即 9)向上提升至根结点: - 提升后的根结点:[6, 9] - 分裂产生的左孩子:[8] - 分裂产生的右孩子:[12, 13] 6. 插入 15:
15 比 9 大,进入最右孩子 [12, 13],按序排列为 [12, 13, 15],未超限。

最终树的形态为: - 根结点包含关键字:[6, 9] - 子树分布:[2, 5]、[8]、[12, 13, 15]。

正确答案:B


【真题 5】2018 年 408 第 8 题 · 3 阶 B 树关键字最少极值推导

题目
高度为 5 的 3 阶 B 树含有的关键字个数至少是( )。
A. 15          B. 31          C. 62          D. 242

【解析】

  1. 参数提取:
  2. 阶数 \(m = 3\);
  3. 高度 \(h = 5\);
  4. 目标:求全树含有的关键字总数 \(N\) 的最小值。
  5. 极小值约束模型构建:
  6. 根结点包含关键字数取最小值 1,拥有 2 棵子树;
  7. 除根以外的所有非叶分支结点,关键字数均取下限: $\(\lceil m/2 \rceil - 1 = \lceil 3/2 \rceil - 1 = 1\)$ 每个结点的子树分支数均取下限 \(\lceil m/2 \rceil = 2\);
  8. 第 5 层(终端结点层)的每个结点同样各含 1 个关键字。
  9. 推算各层结点数: 全树结构退化为满二叉树形态:
  10. 第 1 层(根结点):\(1\) 个结点
  11. 第 2 层:\(2\) 个结点
  12. 第 3 层:\(4\) 个结点
  13. 第 4 层:\(8\) 个结点
  14. 第 5 层:\(16\) 个结点
  15. 计算关键字总数: 全树总结点数: $$ \text{M = 1 + 2 + 4 + 8 + 16 = 31 \text{ 个}} $$ 由于整棵树中每一个结点均恰好只含有 1 个关键字,故全树包含的关键字总数至少为: $$ \text{N_{\min} = 31 \times 1 = 31 \text{ 个}} $$

(亦可直接套用叶结点恒等式法秒杀:第 5 层有 16 个结点,共引出 \(16 \times 2 = 32\)$ \text{个外部叶结点。由} $\(N_{\text{leaf}} = N + 1 \implies 32 = N + 1 \implies N = 31\)。)

正确答案:B


【真题 6】2016 年 408 第 10 题 · B+ 树与 B 树结构特征对比

题目
B+ 树不同于 B 树的特点之一是( )。
A. 能支持顺序查找
B. 结点中含有关键字
C. 根结点至少有两个分支
D. 所有叶结点都在同一层上

【解析】

  • A 项正确:B+ 树的所有叶结点包含了全部关键字及指向记录的物理指针,且各个叶结点通过双向指针相互链接构成一个有序链表,因此不仅支持多路随机查找,还支持直接沿底层链表进行快速的顺序查找与范围查找;而 B 树的各叶结点互不相通,不支持直接顺序遍历。
  • B 项错误:B 树和 B+ 树的各个结点中均包含关键字,此为共性,非不同点。
  • C 项错误:若树非空且高度大于 1,B 树与 B+ 树的根结点都至少拥有 2 个分支。
  • D 项错误:作为平衡多路查找树,B 树与 B+ 树的所有叶结点都必须严格处于同一层次上,保持绝对平衡。

正确答案:A


四、 核心解题套路与易错陷阱

1. 树高与关键字容量极值计算速解模型

面对涉及树高与容量的题目,考生需掌握两大极值模型:

(1) 最瘦长模型(高度最高 / 关键字最少)

  • 构造口诀:“根 1 键 2 叉,余下全取 \(\lceil m/2 \rceil\)”。
  • 速算推导: 直接计算外部叶结点总数: $\(N_{\text{leaf}} = 2 \times (\lceil m/2 \rceil)^{h-1}\)$ 利用基本定理 \(N_{\text{leaf}} = N + 1\) 瞬间求出关键字最少值: $\(N_{\min} = 2 (\lceil m/2 \rceil)^{h-1} - 1\)$

(2) 最矮胖模型(高度最低 / 关键字最多)

  • 构造口诀:“全树拉满满 \(m\) 叉”。
  • 速算推导: 总结点数为满 \(m\)$ \text{叉树求和} $\(\frac{m^h - 1}{m - 1}\)$ \text{,每个结点装满} $\(m-1\) 个关键字: $$N_{\max} = (m

  • 1) \cdot \frac{m^h

  • 1}{m

  • 1} = m^h

  • 1$$

(3) 审题易错陷阱

必须确认题目中给出的高度 \(h\) 是否包含外部失败叶结点: - 若高度 \(h\) 不包含外部叶结点(即关键字层数),套用上述公式; - 若题目明确声明高度 \(h'\)$ \text{包含叶结点(即叶结点为第} $\(h'\)$ \text{层),则关键字层数实际为} $\(h' - 1\)。


2. 动态插入分裂关键细节

  1. 落脚点陷阱:新关键字绝对不会直接插入到内部非终端结点中,第一步必落入最底层的终端结点。
  2. 中位提升位置算法化:
  3. 插入新关键字后结点达 \(m\) 个;
  4. 提升的关键字下标恒为 \(\lceil m / 2 \rceil\);
  5. 例如:
    • 对于 3 阶 B 树:达到 3 个关键字时分裂,提升第 \(\lceil 3/2 \rceil = 2\) 个关键字;
    • 对于 4 阶 B 树:达到 4 个关键字时分裂,提升第 \(\lceil 4/2 \rceil = 2\) 个关键字;
    • 对于 5 阶 B 树:达到 5 个关键字时分裂,提升第 \(\lceil 5/2 \rceil = 3\) 个关键字。
  6. 长高机制:整棵树高度增加的唯一途径是根结点分裂产生新的单关键字根结点。

3. 动态删除借键与合并易错陷阱

  1. 非终端结点的先代换后删除: 若删除非终端结点关键字,先用直接前驱(左子树最大键)或直接后继(右子树最小键)顶替,再将删除压力转嫁到底层终端结点。
  2. 严防“私相授受”借键错误: 终端结点下溢向兄弟借键时,绝不能把兄弟结点的关键字直接平移过来!必须执行父子兄三方联动:
  3. 双亲中的分割关键字下移给当前结点;
  4. 兄弟结点的边缘关键字上移顶替双亲中的分割关键字。
  5. 合并引起的树高缩减: 合并操作消耗一个双亲结点的分割关键字。当合并级联至根结点,且根结点原先仅有 1 个关键字时,根结点变空被释放,树高减少 1。

4. 拓扑形态组合计数解题框架(应对 2025 年新题型)

面对“给定 \(N\)$ \text{个关键字,求能构成的不同} $\(m\) 阶 B 树个数”的高难度题目,严格按如下三步分类讨论: 1. 按高度 \(h\) 分割求解域: 利用极值公式计算出允许的高度范围 \([h_{\min}, h_{\max}]\)。通常仅有 1~2 个高度合法。 2. 按根结点关键字数 \(k_{\text{root}}\) 分类: 根据 \(1 \le k_{\text{root}} \le m - 1\)$ \text{,确定根结点引出的子树棵数} $\(k_{\text{root}} + 1\)。 3. 剩余关键字整数拆分与排列: 将剩余的 $N

  • k_{\text{root}}$$ \text{个关键字分配给各子树结点,列出所有满足“每个结点关键字数介于} $$[\lceil m/2 \rceil

  • 1, m

  • 1]$”的正整数划分,并计算对应排列数。


五、 考点速记清单

  1. 核心参数界限:
  2. 根结点(非叶):子树 \([2, m]\)$ \text{,关键字} $\([1, m - 1]\)。
  3. 非根分支结点:子树 \([\lceil m/2 \rceil, m]\)$ \text{,关键字} $\([\lceil m/2 \rceil - 1, m - 1]\)。
  4. 终端结点:关键字 \([\lceil m/2 \rceil - 1, m - 1]\)。
  5. 两大极值公式:
  6. 最小关键字数(最瘦):\(N_{\min} = 2 (\lceil m/2 \rceil)^{h-1} - 1\)。
  7. 最大关键字数(最胖):\(N_{\max} = m^h - 1\)。
  8. 外部叶结点恒等式:\(N_{\text{leaf}} = N + 1\)。
  9. 动态操作速记口诀:
  10. 插入必定入底端,满 \(m\)$ \text{分裂提中间(} $\(\lceil m/2 \rceil\) 位上移)。
  11. 删分支化前与后,下溢兄弟富借走(父下兄上做联动)。
  12. 兄弟贫困三方合(两兄弟+父分割键),父借空时楼降一。
  13. B树与B+树甄别核心特征:
  14. 双向链表连、全在叶子存、支持范围查 \(\to\) B+ 树;
  15. 关键字全异、层层有数据、各叶互独立 \(\to\) B 树。