2. B 树的高度（磁盘存取次数）
## 2. B 树的高度（磁盘存取次数）
由上一节可知，B树中大多数操作所需的磁盘存取次数与树的高度成正比。
下面分析B树在不同情况下的高度范围。需要特别说明的是：B树的高度不包括最底层外部叶结点所处的那一层（部分教材将该层计入高度，定义略有不同）。
设 $n\geqslant 1$ ，对于任意一棵包含 $n$ 个关键字、高度为 $h$ 、阶数为 $m$ 的B树：
1）最小高度情形：当每个结点的关键字数达到最大值时，B树的高度最小。因每个结点最多有 $m$ 棵子树（最多含 $m - 1$ 个关键字），故高度为 $h$ 的B树最多可容纳的关键字数为 $n \leqslant (m - 1)(1 + m + m^2 + \dots + m^{h - 1}) = m^h - 1$ ，因此有 $h \geqslant \log_m(n + 1)$ 。
2）最大高度情形：当每个结点的关键字数达到最小值时，B树的高度最大。第1层（根）至少有1个结点；第2层至少有2个结点；除根结点外，每个非叶结点至少有 $\lceil m / 2\rceil$ 棵子树，因此第3层至少有 $2\lceil m / 2\rceil$ 个结点……，第 $h + 1$ 层至少有 $2(\lceil m / 2\rceil)^{h - 1}$ 个结点。注意到第 $h + 1$ 层为不存储数据的外部叶结点。对于包含 $n$ 个关键字的B树，其外部叶结点数量恒为 $n + 1$ ，由此有 $n + 1\geqslant 2(\lceil m / 2\rceil)^{h - 1}$ ，即 $h\leqslant \log_{\lceil m / 2\rceil}((n + 1) / 2) + 1$ 。
例如，假设一棵3阶B树共有8个关键字，则其高度范围为 $2\leqslant h\leqslant 3.17$ 。由于高度 $h$ 必为整数，故实际高度范围为 $2\leqslant h\leqslant 3$ 。
## 3. B 树的插入
**考点出处** 通过插入操作构造一棵初始为空的B树（2020）
与二叉排序树的插入操作相比，B树的插入要复杂得多。在B树中找到插入位置后，不能简单地将关键字添加到终端结点中，因为这可能导致结点违反B树的定义约束。
将关键字 key 插入 B 树的过程如下：
1）定位。利用B树查找算法，沿着路径向下查找，最终指向一个外部叶结点（表示查找失败），但实际的插入位置一定是该叶结点的父结点，即最底层终端结点。
2）插入与分裂。每个非根结点的关键字个数必须维持在区间 $\lceil m / 2 \rceil - 1, m - 1 \rceil$ 内。若该结点在插入 key 后关键字总数不超过 $m - 1$ ，则可直接插入；若插入后关键字总数超过 $m - 1$ （达到 $m$ 个），则必须对该结点进行分裂。
分裂方法：创建一个新结点，并将插入key后的原结点中的关键字从中间位置（第 $\lceil m / 2\rceil$ 个关键字）处分成左右两部分：左半部分的关键字保留在原结点中；右半部分的关键字移至新结点中；中间的关键字（注意，是关键字而非结点）被提升并插入原结点的父结点。若父结点因接收该关键字而超出上限（关键字数大于 $m - 1$ ），则对父结点递归执行分裂操作。这一过程可能向上传播，直至根结点。若根结点也被分裂，则B树高度增1。
对于 $m = 3$ 的B树，每个结点最多包含 $m - 1 = 2$ 个关键字。当某个结点已有两个关键字时[见
<!-- page: 319 -->
第7章 查找
307
图7.29(a)]，则已满。此时，插入60后，结点包含3个关键字［见图7.29(b)］，超过上限。分裂后，中间关键字52被提升至父结点，原结点与新结点各保留1个关键字［见图7.29(c)］。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.29 结点的“分裂”示意 ## 4. B树的删除 B树的删除比插入操作更复杂，因为删除后需保证每个结点的关键字数不少于下限（$\lceil m/2 \rceil - 1$），否则需通过“借位”或“合并”来恢复平衡。 **修改语言** B树的删除操作的实例（2012、2022） 当被删关键字 $k$ 不在终端结点中时，可以用 $k$ 的前驱（或后继）$k'$ 替代，即 $k$ 左侧子树中“最右下”的元素（或右侧子树中“最左下”的元素），然后在相应的结点中删除 $k'$。关键字 $k'$ 必定落在某个终端结点中，从而转化为删除终端结点中关键字的情形。例如，在图7.30的4阶B树中，删除关键字80，用其前驱78替代，然后在终端结点中删除78。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.30 B树中删除非终端结点关键字的取代 因此只需讨论被删关键字在终端结点中的情形，有下列三种情况： 1）直接删除关键字。若被删关键字所在结点删除前的关键字个数 $\geqslant \lceil m / 2 \rceil$，则删除该关键字后仍满足B树定义，可以直接删除该关键字。 2）兄弟够借。若被删关键字所在结点删除前的关键字个数 $= \lceil m / 2 \rceil - 1$，且与该结点相邻的右（或左）兄弟结点的关键字个数 $\geqslant \lceil m / 2 \rceil$，则需要调整该结点、右（或左）兄弟结点及其父结点（父子换位法），以达到新的平衡。例如，在图7.31(a)中删除4阶B树的关键字65，右兄弟关键字个数 $\geqslant \lceil m / 2 \rceil = 2$，将父结点中的关键字71下移到当前结点替代65，再将右兄弟中的最小关键字74上移到父结点原71的位置。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 兄弟够借
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 兄弟不够借
图7.31 4阶B树中删除终端结点关键字的示意图
<!-- page: 320 -->
2027年数据结构考研复习指导
3）兄弟不够借。若被删关键字所在结点删除前的关键字个数为 $\lceil m/2 \rceil - 1$，且其左右兄弟结点的关键字个数也均为 $\lceil m/2 \rceil - 1$，则删除该关键字后，需将该结点、其中一个兄弟结点以及父结点中分隔它们的关键字合并为一个新结点。例如，在图7.31(b)中删除4阶B树的关键字5，该结点与其右兄弟的关键字个数均为 $\lceil m/2 \rceil - 1 = 1$，因此在删除5后，将父结点中的关键字60与左右两个子结点（分别为空和含65）合并为一个新结点。
**考点关注** 非空B树的查找、插入、删除操作的特点（2023）
在合并过程中，父结点中的关键字个数会减1。若其父结点是根结点且关键字个数减少至0（根结点关键字个数为1时，有2棵子树），则直接将根结点删除，合并后的新结点成为根；若父结点不是根结点，且关键字个数减少到 $\lceil m/2 \rceil - 2$，则需对其执行借位或合并操作，并可能向上递归，直至整棵树重新满足B树性质。
## 7.4.2 B+树的基本概念
**考点关注** B+树的应用场合（2017）
B+树是为满足数据库系统高效检索需求而设计的一种B树变体。
一棵 $m$ 阶 B+树应满足下列条件。
1）每个分支结点最多有 $m$ 棵子树。
2）非叶根结点至少有2棵子树；其余每个分支结点至少有 $\lceil m/2 \rceil$ 棵子树。
3）每个分支结点的关键字个数等于其子树个数。
4）所有关键字及其对应的记录指针均存储在叶结点中；叶结点内的关键字按升序排列，且相邻叶结点通过指针按关键字顺序链接，从而支持高效的顺序查找。
5）所有分支结点（可视为索引的索引）仅包含用于引导查找的关键字（通常为其对应子结点中关键字的最大值）以及指向各子结点的指针。
**考点关注** B树和B+树的差异的分析（2016）
$m$ 阶 $\mathbf{B}+$ 树与 $m$ 阶 B 树的主要差异如下。
1）子树数量关系不同：在 $\mathrm{B}+$ 树中，具有 $n$ 个关键字的结点恰好含有 $n$ 棵子树，即每个关键字对应一棵子树；而在 B 树中，具有 $n$ 个关键字的结点含有 $n+1$ 棵子树。
2）关键字数量范围不同：在 $\mathrm{B}+$ 树中，每个非根内部结点的关键字个数 $n$ 满足 $\lceil m/2 \rceil \leqslant n \leqslant m$（非叶根结点满足 $2 \leqslant n \leqslant m$）；而在 B 树中，每个非根内部结点的关键字个数 $n$ 满足 $\lceil m/2 \rceil - 1 \leqslant n \leqslant m - 1$（根结点满足 $1 \leqslant n \leqslant m - 1$）。
3）关键字存储位置不同：在 $\mathrm{B}+$ 树中，所有关键字均存储在叶结点中，非叶结点中的关键字是其对应子树中关键字的副本（通常为最大值），因此会重复出现在叶结点中；而在 B 树中，关键字仅出现一次，终端结点与其他结点的关键字互不重复。
4）结点功能不同：在 $\mathrm{B}+$ 树中，叶结点包含完整的数据信息，所有非叶结点仅起索引作用，其索引项只包含对应子树的最大关键字和指向该子树的指针。由于非叶结点结构更紧凑，一个磁盘块可容纳更多关键字，从而可减少磁盘I/O次数，提升查询效率。
5）支持顺序查找：B+树通常设置一个头指针，指向关键字最小的叶结点，并将所有叶结点通过指针按关键字顺序链接成一个线性链表，便于范围查询和顺序遍历。
图7.32所示为一棵4阶B+树。可以看出，分支结点中的关键字是其子树中最大关键字的副本。通常在B+树中有两个头指针：一个指向根结点，另一个指向关键字最小的叶结点。因此，B+树支持两种查找方式：一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。
<!-- page: 321 -->
第7章 查找
309
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.32 B+树结构示意图 B+树的查找、插入和删除操作与B树基本类似。区别在于：在查找过程中，即使在非叶结点中遇到与给定关键字相等的值，也不会终止查找，而是继续向下，直到到达对应的叶结点为止。因此，无论查找成功与否，每次查找都对应一条从根结点到某个叶结点的路径。 ## 7.4.3 本节试题精选 ### 一、单项选择题 01. 右图所示是一棵（）。 A. 4阶B树 B. 3阶B树 C. 4阶B+树 D. 无法确定
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
02. 下列关于 $m$ 阶B树的说法中，错误的是（）。
A. 根结点至多有 $m$ 棵子树
B. 所有叶结点都在同一层次上
C. 非叶结点至少有 $m/2$（$m$ 为偶数）或 $(m+1)/2$（$m$ 为奇数）棵子树
D. 根结点中的数据是有序的
03. 下列关于高度为3的3阶B树的说法中，正确的是（）。
I. 每个内部结点至少有两棵非空子树
II. 树中每个结点至多有2个关键字
III. 树中最多能存储26个关键字
IV. 插入一个元素引起B树结点分裂后，树的高度变为4
A. I、II
B. I、II、III
C. III、IV
D. I、II、IV
04. 在一棵 $m$ 阶 B 树中做插入操作前，若一个结点中的关键字个数等于（），则插入操作后必须分裂成两个结点；在一棵 $m$ 阶 B 树中做删除操作前，若一个结点中的关键字个数等于（），则删除操作后可能需要同它的左兄弟或右兄弟结点合并成一个结点。
A. $m, \lceil m/2 \rceil - 2$
B. $m - 1, \lceil m/2 \rceil - 1$
C. $m + 1, \lceil m / 2 \rceil$
D. $m / 2, \lceil m / 2 \rceil + 1$
05. 具有 $n$ 个关键字的 $m$ 阶 B 树，应有（ ）个叶结点。
A. $n + 1$
B. $n - 1$
C. $mn$
D. $nm/2$
06. 高度为5的3阶B树至少有（ ）个结点，至多有（ ）个结点。
A. 32
B. 31
C. 120
D. 121
07. 含有 $n$ 个非叶结点的 $m$ 阶 B 树中至少包含（ ）个关键字。
A. $n(m + 1)$
B. $n$
C. $n(\lceil m / 2 \rceil - 1)$
D. $(n - 1)(\lceil m / 2 \rceil - 1) + 1$
08. 已知一棵5阶B树中共有53个关键字，则树的最大高度为（），最小高度为（）。
A. 2
B. 3
C. 4
D. 5
<!-- page: 322 -->
2027年数据结构考研复习指导
09. 已知一棵3阶B树中共有2047个关键字，则树的最大高度为（），最小高度为（）。
A. 11
B. 10
C. 8
D. 7
10. 在7阶B树中，按从上往下，从左往右的顺序搜索第2016个关键字，若根结点已读入内存，则最多需启动（）次I/O。
A. 4
B. 5
C. 6
D. 7
11. 在一棵高度为 $h$ 的B树中插入一个新关键字，假设在插入过程中读入的结点一直在内存中，根结点的高度为1，且初始时未读入内存，则下列叙述中错误的是（）。（注意，本题中的新结点是指新产生的结点，如一次分裂才产生一个新结点。）
A. 若插入操作导致树的高度变为 $h + 1$ ，则本次插入一定导致了根结点的分裂
B. 若插入操作导致旧结点的分裂，则树的高度一定会变为 $h + 1$
C. 由于本次插入操作而产生的新结点的个数最多为 $h + 1$
D. 由于本次插入操作而产生的读/写磁盘的次数最多为 $3h + 1$
12. 下列关于B树和 $\mathrm{B + }$ 树的叙述中，错误的是（）。
A. B 树和 $\mathrm{B + }$ 树都能有效地支持顺序查找
B. B 树和 $\mathrm{B + }$ 树都能有效地支持随机查找
C. B 树和 $\mathrm{B + }$ 树都是平衡的多又树
D. B 树和 $\mathrm{B + }$ 树都可以用于文件索引结构
13. 下列关于B树和 $\mathrm{B + }$ 树的查找操作的叙述中，错误的是（）。
A. B 树查找成功时，不一定需要查找到最后一层的内部结点
B. B 树查找失败时，一定需要查找到叶结点
C. $\mathrm{B + }$ 树查找成功时，不一定需要查找到叶结点
D. $\mathrm{B + }$ 树查找成功时，每次查找的长度都相等
14.【2009统考真题】下列叙述中，不符合 $m$ 阶B树定义要求的是（）。
A. 根结点至多有 $m$ 棵子树
B. 所有叶结点都在同一层上
C. 各结点内关键字均升序或降序排列
D. 叶结点之间通过指针链接
15.【2012统考真题】已知一棵3阶B树，如右图所示。删除关键字78得到一棵新B树，其最右叶结点中的关键字是（）。
A. 60
B. 60, 62
C. 62, 65
D. 65
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
16. 【2013统考真题】在一棵高度为2的5阶B树中，所含关键字的个数至少是（）。
A. 5
B. 7
C. 8
D. 14
17.【2014统考真题】在一棵有15个关键字的4阶B树中，含关键字的结点个数最多是（）。
A. 5
B. 6
C. 10
D. 15
18. 【2016统考真题】 $\mathrm{B + }$ 树不同于B树的特点之一是（）。
A. 能支持顺序查找
B. 结点中含有关键字
C. 根结点至少有两个分支
D. 所有叶结点都在同一层上
19. 【2017统考真题】下列应用中，适合使用 $\mathrm{B + }$ 树的是（）。
A. 编译器中的词法分析
B. 关系数据库系统中的索引
C. 网络中的路由表快速查找
D. 操作系统的磁盘空闲块管理
20. 【2018统考真题】高度为5的3阶B树含有的关键字个数至少是（）。
<!-- page: 323 -->
第7章 查找
311
A. 15
B. 31
C. 62
D. 242
21. 【2020 统考真题】依次将关键字 5, 6, 9, 13, 8, 2, 12, 15 插入初始为空的 4 阶 B 树后，根结点中包含的关键字是（ ）。
A. 8
B. 6, 9
C. 8, 13
D. 9, 12
22. 【2021 统考真题】在一棵高度为 3 的 3 阶 B 树中，根为第 1 层，若第 2 层中有 4 个关键字，则该树的结点数最多是（ ）。
A. 11
B. 10
C. 9
D. 8
23. 【2022 统考真题】在下图所示的 5 阶 B 树 $T$ 中，删除关键字 260 之后需要进行必要的调整，得到新的 B 树 $T_{1}$。下列选项中，不可能是 $T_{1}$ 根结点中关键字序列的是（ ）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
A. 60, 90, 280
B. 60, 90, 350
C. 60, 85, 110, 350
D. 60, 90, 110, 350
24. 【2023 统考真题】下列关于非空 B 树的叙述中，正确的是（ ）。
I. 插入操作可能增加树的高度
II. 删除操作一定会导致叶结点的变化
III. 查找某关键字总是要查找到叶结点
IV. 插入的新关键字最终位于叶结点中
A. 仅 I
B. 仅 I、II
C. 仅 III、IV
D. 仅 I、II、IV
25. 【2025 统考真题】给定 7 个不同的关键字，能构造的不同 4 阶 B 树的个数最多是（ ）。
A. 7
B. 8
C. 9
D. 10
## 二、综合应用题
01. 给定一组关键字 $\{20, 30, 50, 52, 60, 68, 70\}$，给出创建一棵 3 阶 B 树的过程。
02. 对如右图所示的 3 阶 B 树，依次执行下列操作，画出各步操作的结果。
1）插入 90
2）插入 25
3）插入 45
4）删除 60
5）删除 80
03. 利用 B 树做文件索引时，若假设磁盘页块的大小是 4000B（实际应是 2 的次幂，此处是为了计算方便），指示磁盘地址的指针需要 5B。现有 20000000 个记录构成的文件，每个记录为 200B，其中包括关键字 5B。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
认同在这个采用 B 树作索引的文件中，B 树的阶数应为多少？假定文件数据部分未按关键字有序排列，则索引部分需要占用多少磁盘页块？
## 7.4.4 答案与解析
## 一、单项选择题
01. D
关键字数目比子树数目少 1，首先可排除 $\mathrm{B} +$ 树。对于 4 阶 B 树，根结点至少有 2 棵子树（关键字数至少为 1），其他非叶结点至少有 $\lceil n / 2 \rceil = 2$ 棵子树（关键字数至少为 1）、至多有 4 棵子树（关键字数至多为 3）。5 阶 B 树和 6 阶 B 树的分析也类似。题目所示的 B 树，同时满足 4 阶 B 树、5 阶 B 树和 6 阶 B 树的要求，因此不能确定是哪种类型的 B 树。
<!-- page: 324 -->
2027年数据结构考研复习指导
02. C
除根结点外的所有非叶结点至少有 $\lceil m / 2\rceil$ 様子树。对于根结点，最多有 $m$ 様子树，若其不是叶结点，则至少有2様子树。
03. B
每个非根的内部结点必须至少有 $\lceil m / 2\rceil$ 様子树，而本题中的根结点不是叶结点，也至少要有两様子树，说法I正确。每个结点至多有 $m - 1 = 2$ 个关键字，说法II正确。在高度为 $h$ 的 $m$ 阶B树中，关键字个数至多为 $(m - 1)(1 + m + m^2 +\dots +m^{h - 1}) = m^h -1$ ，代入 $m = 3$ ， $h = 3$ ，即树中最多能存储26个关键字，说法III正确。对于说法IV，插入一个元素引起B树结点分裂后，只要从根结点到该元素插入位置的路径上至少有一个结点未满，B树就不会长高，如图1所示；只有当结点的分裂传到根结点，并使根结点也分裂时，才会导致树高增1，如图2所示，说法IV错误。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图1 结点分裂不导致树高增1（3阶B树）
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图2 结点分裂导致树高增1（3阶B树）
04. B
因为B树每个结点内的关键字个数最多为 $m - 1$ ，所以当关键字个数大于 $m - 1$ 时，则应该分裂。每个结点内的关键字个数至少为 $\lceil m / 2\rceil -1$ 个，所以当关键字个数少于 $\lceil m / 2\rceil -1$ 时，则可能与其他结点合并（除非只有根结点）。若将本题题干改为 $\mathrm{B + }$ 树，请读者思考上述问题的解答。
05. A
B 树的叶结点对应查找失败的情况，对有 $n$ 个关键字的查找集合进行查找，失败的可能性有 $n + 1$ 种。
06. B、D
由 $m$ 阶 B 树的性质可知，根结点至少有 2 様子树；根结点外的所有非终端结点至少有 $\lceil m / 2\rceil$ 様子树，结点数最少时，3 阶 B 树形状至少类似于一様满二叉树，即高度为 5 的 B 树至少有 $2^{5} - 1 = 31$ 个结点。因为每个结点最多有 $m$ 様子树，所以当结点数最多时，3 阶 B 树形状类似于满三叉树，结点数为 $(3^{5} - 1) / 2 = 121$ （注意，这里求的是结点数而非关键字数，若求的是关键字数，则还应把每个结点中关键字数的上下界确定出来）。
07. D
除根结点外， $m$ 阶 B 树中的每个非叶结点至少有 $\lceil m / 2\rceil -1$ 个关键字，根结点至少有一个关键字，所以总共包含的关键字最少个数 $= (n - 1)(\lceil m / 2\rceil -1) + 1$ 。