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−1)(1+m+⋯+mh−1)=mh−1(m-1)(1+m+\cdots+m^{h-1})=m^h-1,代入 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 至少 25−1=312^5-1=31 个结点。最多 m 棵子树,结点最多时类似满三叉树,结点数 (35−1)/2=121(3^5-1)/2=121。注意此处求结点数而非关键字数。

单项选择题 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。

由最大高度公式 H≤log⁡⌈m/2⌉[(n+1)/2]+1H\le\log_{\lceil m/2\rceil}[(n+1)/2]+1,得 H≤log⁡3(54/2)+1=4H\le\log_3(54/2)+1=4,最大高度为 4。最小高度满足 h≥log⁡m(n+1)=log⁡554≈2.48h\ge\log_m(n+1)=\log_554\approx2.48,故最小高度为 3。

单项选择题 09

原书题目P315 · 解析P318 · 目视转录

一棵 3 阶 B 树共有 2047 个关键字,则最大高度为( ),最小高度为( )。

A. 11

B. 10

C. 8

D. 7

查看答案与解析

答案:A、D。

最小高度 h≥log⁡m(n+1)h\ge\log_m(n+1),最大高度 H≤log⁡⌈m/2⌉[(n+1)/2]+1H\le\log_{\lceil m/2\rceil}[(n+1)/2]+1。代入得 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 层至少 2×4h−22\times4^{h-2} 个结点。前 h 层关键字总数为 1+2×3(1+4+⋯+4h−2)=1+2(4h−1−1)1+2\times3(1+4+\cdots+4^{h-2})=1+2(4^{h-1}-1)。

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]
查看答案与解析

用 [关键字](各孩子,以分号隔开) 表示树。

  1. 插入 90 到 [100] 中,变 [90 100],未超过 2 个关键字,不分裂。结果:[50]([30]([8 20];[35 40]);[80]([60];[90 100]))。
  2. 插入 25 到 [8 20],溢出后中间元素 20 上移,父结点成 [20 30],不继续分裂。结果:[50]([20 30]([8];[25];[35 40]);[80]([60];[90 100]))。
  3. 插入 45 到 [35 40],40 上移至父结点 [20 30],引起父结点分裂,中间元素 30 上移到根 [50]。结果:[30 50]([20]([8];[25]);[40]([35];[45]);[80]([60];[90 100]))。
  4. 删除 60 后,该结点为空,向右兄弟借,90 上移、80 下移。结果:[30 50]([20]([8];[25]);[40]([35];[45]);[90]([80];[100]))。
  5. 删除 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 整数,则

(2(m−1)+m)×5+2≤4000,(2(m-1)+m)\times5+2\le4000,

得 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+ 树的全部数据记录索引项都在叶结点。