B树及其基本操作（查找、插入、删除）

B树及其基本操作（查找、插入、删除）

文章目录

• • B树的基本概念
  • B树的高度
  • B树的查找
  • B树的插入
  • B树的删除
  • • 删除的关键字不在终端结点（最低层非叶结点）
    • 删除的关键字在终端结点（最低层非叶结点）

B树的基本概念

B树，又称为多路平衡查找树。

一棵m阶B树是一棵平衡的 m m m叉查找树，它或者是空树，或者是满足以下性质的树：

1、 每个结点最多有 m m m棵子树（即至多含 m − 1 m-1 m−1个关键字），并具有如下结构： n , P 0 , K 1 , P 1 , K 2 , P 2 , . . . , K n , P n n, P_0, K_1, P_1, K_2, P_2, ... , K_n, P_n n, P0​, K1​, P1​, K2​, P2​, ... , Kn​, Pn​
其中， n n n是结点内关键码的实际个数， P i （ 0 ≤ i ≤ n ＜ m ） P_i（0≤i≤n＜m） Pi​（0≤i≤n＜m）是指向子树的指针， K i （ 1 ≤ i ≤ n ＜ m ） K_i（1≤i≤n＜m） Ki​（1≤i≤n＜m）是关键码，且 K i < K i + 1 （ 1 ≤ i ＜ n ） K_i<K_{i+1}（1≤i＜n） Ki​<Ki+1​（1≤i＜n）
2、 根结点至少有两个子女；除根结点以外的所有结点至少有 ⌈ m / 2 ⌉ lceil m/2 rceil ⌈m/2⌉个子女
3、 在子树 P i P_i Pi​中的所有关键码都小于 K i + 1 K_{i+1} Ki+1​，且大于 K i K_i Ki​；在子树 P n P_n Pn​中的所有关键码都大于 K n K_n Kn​
4、 所有失败结点都位于同一层，它们都是查找失败时查找指针到达的结点。所有失败结点都是空结点，指向它们的指针都为空。

一个简单的3阶B树示例：

B树是所有结点的平衡因子均等于0的多路查找树，上图所示的底层方形结点表示叶结点，在这些结点中没有存储任何信息。

B树的高度

若设 m m m 阶B树的高度为 h h h（B树的高度不包括失败结点，即最后一层的叶结点），最大结点个数为 n n n，则根据 m m m 叉树的性质，有
n ≤ ∑ i = 1 h m h − 1 = 1 m − 1 ( m h − 1 ) n≤sum_{i=1}^h m^{h-1}=frac{1}{m-1}(m^h-1) n≤i=1∑h​mh−1=m−11​(mh−1)
因为B树中每个结点中最多有 m − 1 m-1 m−1 个关键码，故在一棵高度为 h h h 的 m m m 阶B树种关键码的个数 N ≤ m h − 1 N≤m^h-1 N≤mh−1，因此有 h ≥ l o g m ( N + 1 ) h≥log_m(N+1) h≥logm​(N+1)

若让每个结点种的关键字个数达到最少，则容纳同样多关键字的B树的高度达到最大。
根据B树的定义：第一层至少有1个结点；第二层至少有2个结点；由于除了根结点外的每个非终端结点至少有 ⌈ m / 2 ⌉ lceil m/2 rceil ⌈m/2⌉棵子树，
则第三层至少含有 2 ⌈ m / 2 ⌉ 2lceil m/2 rceil 2⌈m/2⌉……，第 h + 1 h+1 h+1层至少有 2 ( ⌈ m / 2 ⌉ ) h − 1 2(lceil m/2 rceil)^{h-1} 2(⌈m/2⌉)h−1个结点，而第 h + 1 h+1 h+1层是不含任何信息的叶结点;
那么对于关键字个数为 n n n 的B树，叶结点即查找不成功的结点为 n + 1 n+1 n+1，故 n + 1 ≥ 2 ( ⌈ m / 2 ⌉ ) h − 1 n+1≥2(lceil m/2 rceil)^{h-1} n+1≥2(⌈m/2⌉)h−1，即 h ≤ l o g ⌈ m / 2 ⌉ ( ( n + 1 ) / 2 + 1 ) h≤log_{lceil m/2 rceil}((n+1)/2+1) h≤log⌈m/2⌉​((n+1)/2+1)

B树的查找

在B树上进行查找与二叉查找树很相似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所作的多路分支决定。

B树的查找包含两个基本操作：
① 在B树中找结点；
② 在结点内找关键字。
 在B树上找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应的指针信息到所指的子树中去查找。查找到叶结点时（对应指针为空指针），则说明树中没有对应的关键字，查找失败。

下图给出一个查找过程：

由于B树常存储在磁盘上，因此前一个查找操作是在磁盘上进行的，而后一个查找操作是在内存中进行的，所以B树中的大部分操作所需的磁盘存取次数与B树的高度成正比。

B树的插入

与二叉查找树的插入操作相比，B树的插入操作要复杂的多。
在二叉查找树中，仅需要查找到需插入的终端结点的位置。但是，在B树中找到插入位置后，并不能简单地将其添加到终端结点中，因为此时可能会导致整棵树不再满足B树定义中地要求。

将关键字key插入到B树的过程如下：
<1> 定位。利用B树查找算法，找出插入该关键字的最低层中的某个非叶结点。
<2> 插入。在B树中，每个非失败结点的关键字的个数都在区间 [ ⌈ m / 2 ⌉ − 1 , m − 1 ] [lceil m/2 rceil-1, m-1] [⌈m/2⌉−1, m−1]内。
 插入后的结点关键字个数小于 m m m，可以直接插入；
 插入后检查被插入结点内关键字的个数，当插入后的结点关键字个数大于 m − 1 m-1 m−1时，必须对结点进行分裂。

分裂的方法：
取一个新结点，在插入 k e y key key后的原始结点，从中间位置将其关键字分为两部分：

• 左部分包含的关键字放在原始结点中；
• 右部分包含的关键字放在新结点中；
• 中间位置（ ⌈ m / 2 ⌉ lceil m/2 rceil ⌈m/2⌉）的结点插入原结点的父结点。

若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B树高度增加1。

下面给出一个示例来理解上述这种分裂操作：

B树的删除

B树的删除操作与插入操作类似，不过要稍微复杂一些，即要使得删除后的结点中的关键字个数 ≥ ⌈ m / 2 ⌉ − 1 ≥lceil m/2 rceil-1 ≥⌈m/2⌉−1，因此涉及到结点的合并问题。

删除的关键字不在终端结点（最低层非叶结点）

当删除的关键字k不在终端结点（最低层非叶结点）中时，有以下几种情况：
<1> 若小于 k k k的子树中关键字个数 ＞ ⌈ m / 2 ⌉ − 1 ＞lceil m/2 rceil-1 ＞⌈m/2⌉−1，则找出 k k k的前驱值 k ′ k' k′，并用 k ′ k' k′来取代 k k k，再递归地删除 k k k即可。

<2> 若大于 k k k的子树中关键字个数 ＞ ⌈ m / 2 ⌉ − 1 ＞lceil m/2 rceil-1 ＞⌈m/2⌉−1，则找出 k k k的后继值 k ′ k' k′，并用 k ′ k' k′来取代 k k k，再递归地删除 k k k即可。

<3> 若前后两个子树中的关键字个数均为 ⌈ m / 2 ⌉ − 1 lceil m/2 rceil-1 ⌈m/2⌉−1，则直接将两个子结点合并，直接删除 k k k即可。

删除的关键字在终端结点（最低层非叶结点）

当被删除的关键字在终端结点（最低层非叶结点）中时，有以下几种情况：
<1> 直接删除关键字。若被删除关键字所在结点的关键字个数 > ⌈ m / 2 ⌉ − 1 >lceil m/2 rceil-1 >⌈m/2⌉−1，表明删除该关键字后仍满足B树的定义，则直接删去该关键字。

<2> 兄弟够借。若被删除关键字所在结点删除前的关键字个数 = ⌈ m / 2 ⌉ − 1 =lceil m/2 rceil-1 =⌈m/2⌉−1，且与此结点相邻的右（左）兄弟结点的关键字个数 ≥ ⌈ m / 2 ⌉ − 1 ≥lceil m/2 rceil-1 ≥⌈m/2⌉−1，则需要调整该结点、右（左）兄弟结点以及其双亲结点（父子换位法），以达到新的平衡。

• 执行操作：将借来的关键码上移到被删结点的双亲结点中，将双亲结点中相应的关键码下移

<3> 兄弟不够借。若被删除关键字所在结点删除前的关键字个数 = ⌈ m / 2 ⌉ − 1 =lceil m/2 rceil-1 =⌈m/2⌉−1，且此时与该结点相邻的右（左）兄弟结点的关键字个数 = ⌈ m / 2 ⌉ − 1 =lceil m/2 rceil-1 =⌈m/2⌉−1，则将关键字删除后与右（左）兄弟结点及双亲结点中的关键字进行合并。

• 执行操作：被删结点与兄弟结点合并成一个结点；并将双亲中它们所夹的关键码下移