7.4 B 树和 B+ 树·习题
复习入口
7.4 B 树和 B+ 树 · 7.4.1 B 树的定义 · 7.4.1.1 B 树的查找 · 7.4.1.2 B 树的高度 · 7.4.1.3 B 树的插入 · 7.4.1.4 B 树的删除 · 7.4.2 B+ 树的基本概念
本节共27题:选择题24题,综合应用题3题。每题答案紧接题目折叠显示。
文字转录进度:27/27题。已转录题目的题干、选项和解析可编辑;示意图按需保留。
单项选择题
单项选择题 01
原书题目P315 · 解析P317 · 目视转录
下图所示是一棵( )。
[12 25]
/ | \
[05 10] [15 19 22] [26 28]
A. 4 阶 B 树
B. 3 阶 B 树
C. 4 阶 B+ 树
D. 无法确定
查看答案与解析
答案:D。
关键字数比子树数少 1,先排除 B+ 树。4 阶 B 树根至少 2 棵子树(至少 1 个关键字),其他非叶结点至少 2 棵子树(至少 1 个关键字),至多 4 棵子树(至多 3 个关键字)。5 阶、6 阶可作类似分析。图示同时满足 4、5、6 阶 B 树的要求,因此不能确定是哪一阶。
单项选择题 02
原书题目P315 · 解析P317 · 目视转录
下列关于 m 阶 B 树的说法中,错误的是( )。
A. 根结点至多有 m 棵子树
B. 所有叶结点都在同一层次上
C. 非叶结点至少有 m/2(m 为偶数)或 (m+1)/2(m 为奇数)棵子树
D. 根结点中的数据是有序的
查看答案与解析
答案:C。
除根之外的非叶结点至少有 ⌈m/2⌉ 棵子树。根最多 m 棵子树,若根不是叶结点,则至少 2 棵子树。
单项选择题 03
原书题目P315 · 解析P317 · 目视转录
下列关于高度为 3 的 3 阶 B 树的说法中,正确的是( )。
Ⅰ.每个结点至少有两棵非空子树。
Ⅱ.树中每个结点至多有 2 个关键字。
Ⅲ.树中最多能存储 26 个关键字。
Ⅳ.插入一个元素引起 B 树结点分裂后,树的高度为 4。
A. Ⅰ、Ⅱ
B. Ⅱ、Ⅲ
C. Ⅲ、Ⅳ
D. Ⅰ、Ⅱ、Ⅳ
查看答案与解析
答案:B。
每个非根内部结点至少有 ⌈m/2⌉ 棵子树,本题根非叶,也至少有两棵子树。每个结点至多 m−1=2 个关键字,Ⅱ正确。高度 h 的 m 阶 B 树,关键字数至多为 ,代入 m=3、h=3,最多 26 个,Ⅲ正确。
插入引起分裂后,只要从根到插入位置的路径上至少有一个结点未满,树就不会增长。只有分裂传递到根并使根也分裂时,树高才增加 1,Ⅳ错误。例如根 [30]、孩子 [20] 和 [50 52],插入 60 后根变 [30 52]、孩子为 [20]、[50]、[60],高度不增;若根 [30 52]、孩子 [20]、[50]、[60 68],插入 70 则分裂最终传到根,高度增加。
转录核对:原书解析把“非根内部结点、非叶根”的性质归为“Ⅰ正确”,但题干Ⅰ写的是“每个结点”“非空子树”,与所给答案 B(Ⅱ、Ⅲ)不一致。此处保留题干与答案,并明确该表述差异。
单项选择题 04
原书题目P315 · 解析P318 · 目视转录
在 m 阶 B 树中做插入操作前,若一个结点的关键字数等于( ),则插入后必须分裂为两个结点;做删除操作前,若一个结点的关键字数等于( ),则删除后可能需要与其左兄弟或右兄弟合并。
A. m,⌈m/2⌉−2
B. m−1,⌈m/2⌉−1
C. m+1,⌈m/2⌉
D. m/2,⌈m/2⌉+1
查看答案与解析
答案:B。
结点关键字最多 m−1 个,超过此数应分裂;非根结点关键字至少 ⌈m/2⌉−1 个,低于此数可能需与其他结点合并。若改成 B+ 树,可思考相应区别。
单项选择题 05
原书题目P315 · 解析P318 · 目视转录
具有 n 个关键字的 m 阶 B 树,应有( )个叶结点。
A. n+1
B. n−1
C. mn
D. nm/2
查看答案与解析
答案:A。
这里叶结点对应查找失败的情况,n 个关键字的查找集合共有 n+1 种失败可能。
单项选择题 06
原书题目P315 · 解析P318 · 目视转录
高度为 5 的 3 阶 B 树至少有( )个结点,至多有( )个结点。
A. 32
B. 31
C. 120
D. 121
查看答案与解析
答案:B、D。
根至少 2 棵子树,其他非终端结点至少 ⌈m/2⌉ 棵。3 阶 B 树结点最少时类似满二叉树,高度 5 至少 个结点。最多 m 棵子树,结点最多时类似满三叉树,结点数 。注意此处求结点数而非关键字数。
单项选择题 07
原书题目P315 · 解析P318 · 目视转录
含有 n 个非叶结点的 m 阶 B 树中至少包含( )个关键字。
A. n(m+1)
B. n
C. n(⌈m/2⌉−1)
D. (n−1)(⌈m/2⌉−1)+1
查看答案与解析
答案:D。
除根外,每个非叶结点至少 ⌈m/2⌉−1 个关键字,根至少 1 个,所以最少为 (n−1)(⌈m/2⌉−1)+1。B 树和 B+ 树的定义、性质非常重要,需要熟练掌握。
单项选择题 08
原书题目P315 · 解析P318 · 目视转录
一棵 5 阶 B 树共有 53 个关键字,则最大高度为( ),最小高度为( )。
A. 2
B. 3
C. 4
D. 5
查看答案与解析
答案:C、B。
由最大高度公式 ,得 ,最大高度为 4。最小高度满足 ,故最小高度为 3。
单项选择题 09
原书题目P315 · 解析P318 · 目视转录
一棵 3 阶 B 树共有 2047 个关键字,则最大高度为( ),最小高度为( )。
A. 11
B. 10
C. 8
D. 7
查看答案与解析
答案:A、D。
最小高度 ,最大高度 。代入得 H≤log₂(2048/2)+1=11,h≥log₃2048≈6.9,最小取 7。有些辅导书把最底层不含关键字的叶结点也计入高度,会比本题答案多 1。
单项选择题 10
原书题目P315 · 解析P319 · 目视转录
在 7 阶 B 树中搜索第 2016 个关键字,若根结点已读入内存,则最多需启动( )次 I/O。
A. 4
B. 5
C. 6
D. 7
查看答案与解析
答案:B。
考虑关键字最少时第 2016 个关键字所在最大深度。根至少 1 个关键字,第二层至少 2 个结点、各 3 个关键字,第三层至少 2×4 个结点、各 3 个关键字,第 h 层至少 个结点。前 h 层关键字总数为 。
h=5 时 n=511;h=6 时 n=2047。第 2016 个关键字最坏在第 6 层,根已在内存,需 5 次 I/O。
单项选择题 11
原书题目P315 · 解析P319 · 目视转录
在高度 h 的 B 树中插入新关键字。假设插入过程中读入的结点一直在内存,根高度为 1,初始未读入内存。下列叙述错误的是( )。(“新结点”指新产生的结点,如一次分裂才产生一个新结点。)
A. 若插入导致树高变为 h+1,则一定导致根结点分裂
B. 若插入导致旧结点分裂,则树高一定变为 h+1
C. 本次插入产生的新结点个数最多为 h+1
D. 本次插入产生的读写磁盘次数最多为 3h+1
查看答案与解析
答案:B。
最坏情况下,每层均分裂。终端插入结点分裂为两个,需要 2 次写磁盘;分裂逐层上传,每层均需 2 次写,最后根分裂形成新根还需 1 次写,总写次数 2h+1。新结点数为 h+1,查找插入位置需 h 次读,读写总数为 3h+1,C、D 正确。
树高增加一定是从最底层分裂传到根并使根分裂,A 正确;若分裂未传到根,高度不变,B 错误。
单项选择题 12
原书题目P316 · 解析P319 · 目视转录
下列关于 B 树和 B+ 树的叙述中,错误的是( )。
A. 两者都能有效支持顺序查找
B. 两者都能有效支持随机查找
C. 两者都是平衡的多叉树
D. 两者都可以用于文件索引结构
查看答案与解析
答案:A。
差异主要包括:① 结点关键字与子树个数;② B+ 树非叶结点仅作索引;③ B 树结点关键字不与其他结点重复;④ B+ 树支持顺序、随机查找,B 树仅支持随机查找。
B+ 树叶结点包含全部关键字信息,按关键字从小到大顺序链接,可以顺序查找,B 树不支持。两者均可作文件索引,但 B+ 树磁盘读写代价更低,更适合数据库及文件索引。
单项选择题 13
原书题目P316 · 解析P319 · 目视转录
下列关于 B 树和 B+ 树查找操作的叙述中,错误的是( )。
A. B 树查找成功时,不一定需要查找到最后一层的内部结点
B. B 树查找失败时,一定需要查找到叶结点
C. B+ 树查找成功时,不一定需要查找到叶结点
D. B+ 树查找成功时,每次查找长度都相等
查看答案与解析
答案:C。
B 树中若目标在内部结点,查找即结束,不必进入叶结点;失败时,叶结点是所有路径终点,A、B 正确。B+ 树仅叶结点包含信息,非叶结点仅作索引,成功必然到相应叶结点,路径长度均相等,C 错、D 对。
单项选择题 14
原书题目P316 · 解析P319 · 目视转录
【2009 统考真题】下列叙述中,不符合 m 阶 B 树定义要求的是( )。
A. 根结点至多有 m 棵子树
B. 所有叶结点都在同一层上
C. 各结点内关键字均升序或降序排列
D. 叶结点之间通过指针链接
查看答案与解析
答案:D。
B 树不要求叶结点之间用指针链接,D 描述的是 B+ 树。
单项选择题 15
原书题目P316 · 解析P319 · 目视转录
【2012 统考真题】已知 3 阶 B 树如下。删除关键字 78 得到新 B 树,其最右叶结点中的关键字是( )。
[45]
/ \
[17 35] [55 65]
/ | \ / | \
[10] [21] [37] [47] [60 62] [78]
A. 60
B. 60,62
C. 62,65
D. 65
查看答案与解析
答案:D。
78 所在结点删除前只有 1=⌈3/2⌉−1 个关键字,左兄弟有 2=⌈3/2⌉ 个,可以“兄弟够借”。把左兄弟最大关键字 62 上移至双亲,把双亲中大于该上移关键字的 65 下移至原 78 所在结点,重新平衡。右侧子树根由 [55 65] 变 [55 62],孩子为 [47]、[60]、[65]。
单项选择题 16
原书题目P316 · 解析P320 · 目视转录
【2013 统考真题】在高度为 2 的 5 阶 B 树中,所含关键字个数至少是( )。
A. 5
B. 7
C. 8
D. 14
查看答案与解析
答案:A。
根分支至少 2、关键字至少 1;其他非叶结点分支至少 ⌈m/2⌉=3、关键字至少 2,因此最少为 1+2×2=5(不含关键字的叶结点不计入高度)。
注意:某个具体 B 树图形未必能确定阶数。5 阶 B 树不要求存在关键字数达到 4 的结点;非根结点关键字数可在 2~4,均为 2 也满足要求。
单项选择题 17
原书题目P316 · 解析P320 · 目视转录
【2014 统考真题】在有 15 个关键字的 4 阶 B 树中,含关键字的结点个数最多是( )。
A. 5
B. 6
C. 10
D. 15
查看答案与解析
答案:D。
关键字总数不变,要结点最多就要每个结点关键字最少。4 阶 B 树根至少 1 个,非根至少 ⌈4/2⌉−1=1 个,因此每个结点只放 1 个关键字,可组成 15 个结点、4 层的树,终端结点全在第四层,符合定义。
单项选择题 18
原书题目P316 · 解析P320 · 目视转录
【2016 统考真题】B+ 树不同于 B 树的特点之一是( )。
A. 能支持顺序查找
B. 结点中含有关键字
C. 根结点至少有两个分支
D. 所有叶结点都在同一层上
查看答案与解析
答案:A。
B+ 树叶结点包含全部关键字并顺序链接,可支持顺序查找;B 树只支持多路查找。
单项选择题 19
原书题目P316 · 解析P320 · 目视转录
【2017 统考真题】下列应用中,适合使用 B+ 树的是( )。
A. 编译器中的词法分析
B. 关系数据库系统中的索引
C. 网络中的路由表快速查找
D. 操作系统的磁盘空闲块管理
查看答案与解析
答案:B。
B+ 树是应文件系统所需产生的 B 树变形,磁盘读写代价更低,查询效率更稳定,更适于文件及数据库索引。编译器词法分析使用有穷自动机和语法树;路由表快速查找主要依靠高速缓存、路由表压缩及快速查找算法;系统一般用空闲空间链表管理磁盘空闲块。
单项选择题 20
原书题目P316 · 解析P320 · 目视转录
【2018 统考真题】高度为 5 的 3 阶 B 树含关键字个数至少是( )。
A. 15
B. 31
C. 62
D. 242
查看答案与解析
答案:B。
非根非叶结点至少 ⌈m/2⌉−1 个关键字,m=3 时至少 1 个,根也至少 1 个。最少时所有非叶结点有两个孩子,树形与高度 5 的满二叉树相同,关键字至少 31 个。
单项选择题 21
原书题目P316 · 解析P320 · 目视转录
【2020 统考真题】依次将 5,6,9,13,8,2,12,15 插入初始为空的 4 阶 B 树,根结点包含的关键字是( )。
A. 8
B. 6,9
C. 8,13
D. 9,12
查看答案与解析
答案:B。
4 阶 B 树任意非叶结点至多 3 个关键字。插入 5、6、9 后为 [5 6 9];插入 13 溢出,分裂为根 [6]、孩子 [5] 与 [9 13]。插入 8、2 后根 [6]、孩子 [2 5]、[8 9 13];插入 12,右孩子溢出并上移 9,根变 [6 9],孩子 [2 5]、[8]、[12 13];插入 15 后最后孩子为 [12 13 15],根仍 [6 9]。
单项选择题 22
原书题目P316 · 解析P320 · 目视转录
【2021 统考真题】高度为 3 的 3 阶 B 树,根为第 1 层。若第 2 层有 4 个关键字,则结点总数最多是( )。
A. 11
B. 10
C. 9
D. 8
查看答案与解析
答案:A。
每个结点至多 2 个关键字、3 棵子树,至少 1 个关键字。要使结点数最多,第二层 4 个关键字应包含在 3 个结点中,分别为 2、1、1 个关键字;对应第三层结点数为 3+2+2=7,总结点数 1+3+7=11。
单项选择题 23
原书题目P317 · 解析P321 · 目视转录
【2022 统考真题】在下面 5 阶 B 树 T 中,删除关键字 260 后进行必要调整,得到 T₁。下列不可能是 T₁ 根结点中关键字序列的是( )。
根为 [60 90 260 350],从左至右的孩子为 [30 50]、[70 80 85]、[100 110]、[280 300]、[400 500]。
A. 60,90,280
B. 60,90,350
C. 60,85,110,350
D. 60,90,110,350
查看答案与解析
答案:D。
5 阶 B 树除根外非叶结点关键字数应满足 2≤k≤4。删除不在终端结点的关键字,可用前驱或后继替代,再在相应结点删除。
情况①:把前驱 110 放入 260 处,删除 110 后 [100] 不满足定义。从左兄弟借 85,将 85 放入根,根中 90 移入 [100] 成 [90 100],根为 [60 85 110 350]。
情况②:把后继 280 放入 260 处,结点 [300] 不满足定义,左右兄弟都不够借。[300] 可与左兄弟 [100 110] 及关键字 280 合并为 [100 110 280 300],根变 [60 90 350]。
情况③:在情况②中,[300] 也可与右兄弟 [400 500] 及 350 合并为 [300 350 400 500],根变 [60 90 280]。所以只有 D 不可能。
快速解法:若根为 [60 90 110 350],90 与 110 之间只有 100 一个数据,不符合非根结点至少 2 个关键字的要求。
单项选择题 24
原书题目P317 · 解析P321 · 目视转录
【2023 统考真题】下列关于非空 B 树的叙述中,正确的是( )。
Ⅰ.插入操作可能增加树的高度。
Ⅱ.删除操作一定会导致叶结点变化。
Ⅲ.查找某关键字总是要查找到叶结点。
Ⅳ.插入的新关键字最终位于叶结点中。
A. 仅Ⅰ
B. 仅Ⅰ、Ⅱ
C. 仅Ⅲ、Ⅳ
D. 仅Ⅰ、Ⅱ、Ⅳ
查看答案与解析
答案:B。
插入可能引起叶结点分裂,向上传至根,树高增加 1,Ⅰ正确。删除叶结点关键字会使叶结点变化;若删除非叶结点关键字,要先与其前驱或后继交换,最终在叶结点删除,也使叶结点变化,Ⅱ正确。在非叶结点查到关键字即可停止,Ⅲ错误。新关键字初始插在最底层叶结点,但可能因分裂被转移至父结点,Ⅳ错误。
注意:此统考题把最底层终端结点称为叶结点,与多数教材将不含关键字的失败结点称为叶结点的口径不同。
综合应用题
综合应用题 01
原书题目P317 · 解析P321 · 目视转录
给定关键字 {20,30,50,52,60,68,70},给出创建一棵 3 阶 B 树的过程。
查看答案与解析
m=3,除根外非叶结点关键字数为 1~2。以下以 [关键字](孩子1;孩子2;…) 表示树。
| 插入后 | B树 |
|---|---|
| 20 | [20] |
| 30 | [20 30] |
| 50 | [30]([20];[50]) |
| 52 | [30]([20];[50 52]) |
| 60 | [30 52]([20];[50];[60]) |
| 68 | [30 52]([20];[50];[60 68]) |
| 70 | [52]([30]([20];[50]);[68]([60];[70])) |
插入 20、30 不超限。插入 50 后 [20 30 50] 溢出,中间关键字 30 升为根。插入 52 不分裂,插入 60 后 [50 52 60] 分裂,52 上移,父结点未溢出。插入 68 不分裂;插入 70 后 [60 68 70] 分裂,68 上移使 [30 52 68] 又溢出,继续分裂,52 升为新根。最终:
[52]
/ \
[30] [68]
/ \ / \
[20][50] [60][70]
综合应用题 02
原书题目P317 · 解析P322 · 目视转录
对如下 3 阶 B 树,依次执行:① 插入 90;② 插入 25;③ 插入 45;④ 删除 60;⑤ 删除 80。画出各步结果。
[50]
/ \
[30] [80]
/ \ / \
[8 20][35 40][60][100]
查看答案与解析
用 [关键字](各孩子,以分号隔开) 表示树。
- 插入 90 到 [100] 中,变 [90 100],未超过 2 个关键字,不分裂。结果:
[50]([30]([8 20];[35 40]);[80]([60];[90 100]))。 - 插入 25 到 [8 20],溢出后中间元素 20 上移,父结点成 [20 30],不继续分裂。结果:
[50]([20 30]([8];[25];[35 40]);[80]([60];[90 100]))。 - 插入 45 到 [35 40],40 上移至父结点 [20 30],引起父结点分裂,中间元素 30 上移到根 [50]。结果:
[30 50]([20]([8];[25]);[40]([35];[45]);[80]([60];[90 100]))。 - 删除 60 后,该结点为空,向右兄弟借,90 上移、80 下移。结果:
[30 50]([20]([8];[25]);[40]([35];[45]);[90]([80];[100]))。 - 删除 80 后,与父关键字 90、兄弟 [100] 合并为 [90 100],父结点空,需要继续调整。再将根中 50 与 [40] 合并为 [40 50],以 [90 100] 为其右孩子。最终:
[30]
/ \
[20] [40 50]
/ \ / | \
[8] [25][35][45][90 100]
这一调整过程包含多次调整。B 树插入、删除,特别是分裂和合并,是本节重点难点,需要熟练掌握。
综合应用题 03
原书题目P317 · 解析P323 · 目视转录
利用 B 树作文件索引,假设磁盘页块大小 4000B(实际应为 2 的次幂,此处为计算方便),指示磁盘地址的指针需 5B。现有 20000000 个记录,每条 200B,其中关键字 5B。问索引 B 树的阶数应为多少?假定文件数据部分未按关键字有序排列,索引部分需占用多少磁盘页块?
查看答案与解析
索引结点应适应操作系统一次读写的物理记录大小,不超过且接近一个磁盘页块。设阶数 m,结点最多存 m−1 个 5B 关键字及对应 5B 记录地址、m 个 5B 子树指针、1 个记录实际关键字数的 2B 整数,则
得 m≤267,取 267 阶。
一个索引结点最多 m−1=266 个索引项,最少 ⌈m/2⌉−1=133 个。每页块可放 4000/200=20 条记录,全部记录分布在 20000000/20=1000000 个页块中。按原书的估算方法,最多需要 1000000/133≈7519 个页块作为 B 树索引,最少需要 1000000/266≈3760 个页块。
注意 B 树与 B+ 树不同:B 树中全部数据记录的索引项分布于各层次结点,B+ 树的全部数据记录索引项都在叶结点。