数据结构(54) B树、B+树

目录

1、B树

1.1、B树的定义

1.2、B树的高度（磁盘存取次数）

1.2.1、最小高度

1.2.2、最大高度

1.3、B树的查找

1.4、B树的插入

1.5、B树的删除

2、B+树

2.1、B+树的基本概念

2.2、B+树与B树的差异

2.3、B+树的查找、插入和删除

---

1、B树

1.1、B树的定义

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树：

1）树中每个结点至多有m棵子树，即至多含有m-1个关键字。

2）若根节点不是终端结点，则至少有两棵子树。

3）除根节点外的所有非叶结点至少有棵子树，即至少含有个关键字。（***博主认为是为了减少不必要的层高，提高效率和资源利用率***）

4）所有非叶结点的结构如下：

Ki(i = 1,2,...,n)代表关键字且满足K1<K2<...<Kn;

Pi(i = 0,1,...,n)代表指向子树根节点的指针。

例如：P0所指的子树中的所有结点的关键字均需小于K1，而P1所指子树中所有结点的关键字均大于K1。

5）所有的叶结点都出现在同一层次上，并且不带任何信息（可以视为外部结点或类似于二分查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。

B树是所有结点的平衡因子均为0的多路平衡查找树。

1）结点的孩子个数等于该结点中关键字个数加1.

2）如果根节点没有关键字就没有子树，此时B树为空；如果根节点有关键字，则其子树必然大于等于两棵，因为子树个数等于关键字个数加1。

3）除根节点外的所有非终端结点至少有棵子树（2个关键字），至多有5棵子树（4个关键字）。

4）结点中关键字从左到右递增有序，关键字两侧均有指向子树的指针，左边指针所指子树的所有关键字均小于该关键字，右边指针所指子树的所有关键字均大于该关键字。或者看成下层结点关键字总是落在上层关键字所划分的区间内。

5）所有叶结点均在第4层，代表查找失败的位置。

1.2、B树的高度（磁盘存取次数）

B树中大部分操作所需的磁盘存取次数与B树的高度成正比。下面来分析B树在不同情况下的高度。

B树的高度本博文中假设不包括最后的不带任何信息的叶节点所处的那一层。

若n>=1，则对任意一棵包含n个关键字、高度为h、阶数为m的B树：

1.2.1、最小高度

因为B树中每个结点最多有m棵子树，m-1个关键字，所以在一棵高度为h的m阶B数中关键字的个数应满足

因此有

1.2.2、最大高度

若让每个结点中的关键字个数达到最少，则容纳同样多关键字的B树的高度达到最大。由B树的定义可知：第一层至少有1个结点；第二层至少有2个结点；除根结点外的每个非终端结点至少有棵子树，则第三层至少包含个结点......第h+1层至少有个结点，注意到第h+1层是不包含任何信息的叶节点。对于关键字个数为n的B树，叶节点即查找不成功的结点为n+1，由此有，即

例如，假设一棵3阶B数共有8个关键字，则其高度范围为2≤h≤3.17。

1.3、B树的查找

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

B树的查找包括两个基本操作：①在B树上找结点；②在结点内找关键字。由于B树常存储在磁盘上，因此前一个查找操作是在磁盘上进行的，而后一个查找操作是在内存中进行的，即在找到目标结点后，先将结点信息读入内存，然后再结点内采用二分查找或折半查找。

在B树上查找到某个结点后，先在有序表中进行查找，若找到则查找成功。否则按照对应的指针信息到所指的子树中去查找

1.4、B树的插入

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

1）定位。利用前叙的B树查找算法，找出插入该关键字的最低层中某个非叶结点（在B树中查找key时，会找到表示查找失败的叶节点，这样就确定了最底层非叶结点的插入位置。注意：插入位置一定是最底层中的某个非叶结点）。

2）插入。在B树中，每个非失败结点的关键字个数都在区间内。插入后的结点关键字个数小于m，可以直接插入；插入后检查被插入结点内关键字的个数，当插入后的结点关键字个数大于m-1时，必须对结点进行分裂。

分裂的方法：取一个新结点，在插入key后的原结点，从中间位置将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放在新结点中，中间位置的结点插入原结点的父结点。若此时导致父结点的关键字个数也超过上限，则继续进行这种分裂操作，直至这个过程传到根节点为止，进而导致B树的高度增1。

对于m=3的B树，所有结点中最多有m-1=2个关键字，若某结点中已有两个关键字，则结点已满。如上图所示，插入一个关键字60后，结点内的关键字个数超过了m-1，结点此时必须进行分裂。

1.5、B树的删除

B树中的删除操作与插入操作类似，但要稍微复杂一些，即要使得删除后的结点中的关键字个数≥，因此涉及结点的“合并”问题。

当被删关键字k不在终端结点（最底层非叶结点）中时，可以用k的前驱（或后继）k'来替代k，然后在相应的结点中删除k'，关键字k'必定落在某个终端结点中，则转换成了被删关键字在终端结点中的情形。

在上图所示的4阶B树中，删除关键字80，用其前驱78替代，然后在终端结点中删除78，因此只需讨论删除终端结点中关键字的情形。

当被删关键字在终端结点（最低层非叶结点）中时，有下列三种情况：

1）直接删除关键字。若被删除关键字所在结点的关键字个数≥，表名删除该关键字后仍满足B树的定义，则直接删去该关键字

2）兄弟够借

若被删除关键字在你所在结点删除前的关键字个数为，且与此结点相连的右（或左）兄弟结点的关键字个数≥，则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法），以达到新的平衡。在下图（a）中删除4阶B数的关键字65，右兄弟关键字个数≥=2，将71取代原来65的位置，将74调整到71的位置

3）兄弟不够借。若被删除关键字所在结点删除前的关键字个数为，且此时与该结点相邻的左、右兄弟结点的关键字个数均为，则将关键字删除后与左（或）右兄弟结进行合并。在上图（b）中删除B树中的关键字5，它及其右兄弟结点的关键字个数=，故在5删除后将60合并到65结点中。

在合并过程中，双亲结点中的关键字个数会减1.若其双亲结点是根节点且关键字个数减少至0（根节点关键字个数为1时，有2棵子树），则直接将根节点删除，合并后的新结点成为根；若双亲结点不是根节点，且关键字个数减少到，且又要与它自己的兄弟结点进行调整和合并操作，并重复上述步骤，直至符合B树的要求为止。

2、B+树

2.1、B+树的基本概念

B+树是应数据库所需而出现的一种B树的变形树。

一棵m阶的B+树需满足下列条件：

1）每个分支结点最多有m棵子树（孩子结点）

2）非叶根节点至少有两棵子树，其他每个分支结点至少有棵子树。

3）结点的子树个数与关键字个数相等。

4）所有叶结点包含全部关键字及指向对应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序互联链接起来。

5）所有分支结点（可视为索引的索引）中仅仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向子结点的指针。

2.2、B+树与B树的差异

m阶B+树与m阶B树的主要差异如下：

1）在B+树中，具有n个关键字的节点只含有n棵子树，即每个关键字对应一颗子树；而在B树中，具有n个关键字的结点含有n+1棵子树。

2）在B+树中，每个结点（非根内部结点）的关键字个数n的范围是（根节点：1≤n≤m）；

      在B树中，每个结点（非根内部结点）的关键字个数n的范围是m-1（根节点：1≤n≤m-1）。

3）在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

4）在B+树中，叶结点包含全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

上图所示为一棵B+树。通常在B+树中有两个头指针：一个指向根节点，另一个指向关键字最小的叶节点。因此，可以对B+树进行两种查找：一种是从最小关键字开始的顺序查找。另一种是从根节点开始的多路查找。

2.3、B+树的查找、插入和删除

B+树的查找、插入和删除和B树的基本类似。只是在查找过程中，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，直到找到叶结点上的该关键字为止。所以在B+树中查找时，无论查找成功与否，每次查找都是一条从根节点到叶结点的路径。