B树的基本概念及性质

1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）。

一棵m阶B树或为空树,或为满足下列特性的m叉树：

1.若根结点不是终端节点，则至少有两棵子树，最多有m棵子树。
2.除根结点外的所有非叶结点至少有⌈m/2⌉棵子树，最多有m棵子树。
3.所有的叶结点都出现在同一层次上，并且不带信息（可视为失败结点）。
4.所有非叶结点的结构如下：

a)、Pi-1所指子树中所有结点的关键字均小于Ki
b)、Pi所指子树中所有结点的关键字均大于Ki

B树的基本操作

B树的查找

B树的查找算法如下:

①、在B树中找结点（磁盘上进行），当查找到叶结点时，查找失败。
②、在结点内的多关键字有序表中查找关键字（内存中进行）:

a)、先在有序表中进行查找，若找到则查找成功。
b)、否则，根据找到的指针信息到所指的子树，执行①。

对于含有n个关键字的B树的查找，磁盘I/O次数也就是树的高度h（不包含叶结点）满足h <= log⌈m/2⌉((n+1)/2)+1

B树的插入

B树的插入过程如下:

1)、查找:利用B树的查找算法，找出插入该关键字的最底层中某个非叶结点。

2)、插入:当插入后的结点关键字个数小于m，则可以直接插入；如果等于m，则必须对结点进行分裂。

一棵3阶B树的分裂过程及方法如图所示:

若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作。若最终使得根结点分裂，B树的高度增1。

B树的删除

为使删除后的结点中的关键字个数 >= ⌈m/2⌉-1,将涉及结点的“合并”问题。
（1）当被删除的关键字k在非叶结点中时:
①、如果小于（大于）k的子树中关键字个数 > ⌈m/2⌉-1,则找出k的前驱(后继)值k’,并且用k’来取代k,再递归地按此方法删除k’。
②、如果前后两个子树中关键字个数均为⌈m/2⌉-1，则将两个子结点合并，直接删除k。如图3-1所示为某4阶B树的一部分。

（2）当被删除的关键字k在叶结点中时：
①、若该结点的关键字个数 > ⌈m/2⌉-1,则直接删除该关键字。
②、若该结点的关键字个数 = ⌈m/2⌉-1，且与此结点相邻的左（右）兄弟结点的关键字个数 >= ⌈m/2⌉，需要调整该结点、左（右）兄弟结点以及其双亲结点（父子换位法），以达到新的平衡，如下图所示。

③、若该结点关键字个数 = ⌈m/2⌉-1，且与该结点相邻的左（右）兄弟结点的关键字个数 = ⌈m/2⌉-1，则将该关键字删除后与左（右）兄弟结点及双亲结点中的关键字进行合并，如下图所示。

在合并的过程中，若此时导致其父结点的关键字个数也不满足B树的定义，则继续进行这种合并操作。
若最终使得根结点被合并，B树高度减1。
 

课后习题

【2018年真题】高度为5的3阶B树含有的关键字个数至少是（）
A.15    B. 31    C. 62    D. 242

参考答案：B

【2014年真题】在一棵具有 15 个关键字的 4 阶 B 树中，含关键字的结点个数最多是（）
A．5 
B．6 
C．10 
D．15

参考答案：D
答案解析：关键字数量不变，要求结点数量最多，那么即每个结点中含关键字的数量最少。根 据 4 阶 B 树的定义，根结点最少含 1 个关键字，非根结点中最少含é4/2ù-1=1 个关键字，所 以每个结点中，关键字数量最少都为 1 个，即每个结点都有 2 个分支，类似与排序二叉树， 而 15 个结点正好可以构造一个 4 层的 4 阶 B 树，使得叶子结点全在第四层，符合 B 树定义，因此选 D。 

【2013年真题】在一株高度为 2 的 5 阶 B 树中，所含关键字的个数最少是（）
A.5             B. 7         C. 8         D. 14

参考答案：A
答案解析：一棵高度为 2 的 5 阶 B 树，根结点只有到达 5 个关键字的时候才能产生分裂，成为高度为 2 的 B 树。 

【2012年真题】已知一棵 3 阶 B-树，如下图所示。删除关键字 78 得到一棵新 B-树，其最右叶结点中的关键字是（）。 
A．60 
B．60, 62 
C．62, 65 
D．65 

参考答案：D
答案解析：考查 B-树的删除操作。 
对于上图所示的 3 阶 B-树，被删关键字 78 所在结点在删除前的关键字个数=1=é3/2ù-1，且其左兄弟结点的关键字个数=2≥é3/2ù，属于“兄弟够借”的情况，则需把该结点的左兄弟结点中最大的关键字上移到双亲结点中，同时把双亲结点中大于上移关键字的关键字下移到要删除关键字的结点中，这样就达到了新的平衡，如下图所示。 

【2009年真题】下列叙述中，不符合 m 阶 B 树定义要求的是（）。 
A．根节点最多有 m 棵子树 
B．所有叶结点都在同一层上 
C．各结点内关键字均升序或降序排列 
D．叶结点之间通过指针链接

参考答案：D
答案解析：考查 m 阶 B-树的定义。 
A、B 和 C 都是 B-树的特点，而选项 D 则是 B+树的特点。注意区别 B-树和 B+树各自的特点。