B树，B-树和B+树的区别

我不是女神ヾ 2024-02-19 16:46 51阅读 0赞

**B树**

即二叉搜索树：

1.所有非叶子结点至多拥有两个儿子（Left和Right）；

2.所有结点存储一个关键字；

3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

如：

![1.JPG][]

B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；

否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入

右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；

如果B树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树

的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变B树结构

（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；

如：

![2.JPG][]

但B树在经过多次插入与删除后，有可能导致不同的结构：

![31.JPG][]

右边也是一个B树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的

树结构索引；所以，使用B树还要考虑尽可能让B树保持左图的结构，和避免右图的结构，也就

是所谓的“平衡”问题；

实际使用的B树都是在原B树的基础上加上平衡算法，即“平衡二叉树”；如何保持B树

结点分布均匀的平衡算法是平衡二叉树的关键；平衡算法是一种在B树中插入和删除结点的

策略；

**B-树**

\-树其实就是我们平时所说的B树，除了B-树外，还有另外一种叫B+树，我们这里先介绍什么是B-树：  
B-树是一种**平衡的多路查找树**，它在文件系统中很有用（原因之前已经介绍了）。B-树的结构有如下的特点：  
\*\*一棵度为m的B-树称为m阶B-树。一个结点有k个孩子时，必有k-1个关键字才能将子树中所有关键字划分  
为k个子集。B-树中所有结点的孩子结点最大值称为B-树的阶，通常用m表示。从查找效率考虑，一般要求  
m≥3。一棵m阶的B-树或者是一棵空树，或者是满足下列要求的m叉树：\*\*

*  树中的每个结点至多有m颗子树。
 *  若根结点不是叶子结点，则至少有两颗子树。
 *  除根结点外，所有非终端结点至少有\[ m/2 \] ( 向上取整 )颗子树。
 *  所有的非终端结点中包括如下信息的数据

（n,A0,[K1][],A1,K2,A2,….,Kn,An）  
其中：Ki（i=1,2,…,n）为关键码，且Ki < K(i+1)，

Ai 为指向子树根结点的指针(i=0,1,…,n)，且指针A([i-1][]) 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An 所指子树中所有结点的关键码均大于Kn.  
![这里写图片描述][SouthEast]  
n 为关键码的个数。

*  所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

### 3、B-树的基本操作–查找介绍 ###

我们先给出如下的一个4阶的B-树结构。  
![这里写图片描述][SouthEast 1]

如上图所示，这是我们的一个4阶的B-树，现在假设我们需要查找45这个数是否在B-树中。

1.  从根节点出发，发现根节点a有1个关键字为35，其中45>35，往右子树走，进入节点c
2.  发现结点c有2个关键字，其中其中43<45<78,所以进入结点g。
3.  发现结点g有3个关键字，其中3<45<47,所以继续往下走，发现进入了结束符结点：F，所以45不在B-树中

OK，我们从上述的查找的过程可以得出，在B-树的查找过程为：

1.  在B- 树中查找结点
2.  在结点中查找关键字。

由于B- 树通常存储在磁盘上， 则前一查找操作是在磁盘上进行的， 而后一查找操作是在内存中进行的， 即  
在磁盘上找到指针p 所指结点后， 先将结点中的信息读入内存， 然后再利用顺序查找或折半查找查询等于K  
的关键字。显然， 在磁盘上进行一次查找比在内存中进行一次查找的时间消耗多得多.  
因此， 在磁盘上进行查找的次数、即待查找关键字所在结点在B- 树上的层次树， 是决定B树查找效率的首要  
因素，对于有n个关键字的m阶B-树，从根结点到关键字所在结点的路径上路过的结点数不超过：  
![这里写图片描述][SouthEast 2]

### 4、B-树的插入 ###

其实B-树的插入是很简单的，它主要是分为如下的两个步骤：

1.  `1. 使用之前介绍的查找算法查找出关键字的插入位置，如果我们在B-树中查找到了关键字，则直接返回。否则它一定会失败在某个最底层的终端结点上。`
2.  `2.然后，我就需要判断那个终端结点上的关键字数量是否满足：n<=m-1,如果满足的话，就直接在该终端结点上添加一个关键字，否则我们就需要产生结点的“分裂”。`
3.  `分裂的方法是：生成一新结点。把原结点上的关键字和k（需要插入的值）按升序排序后，从中间位置把关键字（不包括中间位置的关键字）分成两部分。左部分所含关键字放在旧结点中，右部分所含关键字放在新结点中，中间位置的关键字连同新结点的存储位置插入到父结点中。如果父结点的关键字个数也超过（m-1），则要再分裂，再往上插。直至这个过程传到根结点为止。`

*  1
 *  2
 *  3
 *  4

下面我们来举例说明，首先假设这个B-树的阶为：3。树的初始化时如下：  
![这里写图片描述][SouthEast 3]

首先，我需要插入一个关键字：30，可以得到如下的结果：  
![这里写图片描述][SouthEast 4]

再插入26，得到如下的结果：

![这里写图片描述][SouthEast 5]

OK，此时如图所示，在插入的那个终端结点中，它的关键字数已经超过了m-1=2，所以我们需要对结点进分裂，所以我们先对关键字排序，得到：26 30 37 ，所以它的左部分为（不包括中间值）：26，中间值为：30，右部为：37，左部放在原来的结点，右部放入新的结点，而中间值则插入到父结点，并且父结点会产生一个新的指针，指向新的结点的位置，如下图所示：  
![这里写图片描述][SouthEast 6]

OK，然后我们继续插入新的关键字：85，得到如下图结果：  
![这里写图片描述][SouthEast 7]

正如图所示，我需要对刚才插入的那个结点进行“分裂”操作，操作方式和之前的一样，得到的结果如下：  
![这里写图片描述][SouthEast 8]

哦，当我们分裂完后，突然发现之前的那个结点的父亲结点的度为4了，说明它的关键字数超过了m-1，所以需要对其父结点进行“分裂”操作，得到如下的结果：  
![这里写图片描述][SouthEast 9]

好，我们继续插入一个新的关键字：7，得到如下结果：  
![这里写图片描述][SouthEast 10]

同样，需要对新的结点进行分裂操作，得到如下的结果：  
![这里写图片描述][SouthEast 11]  
到了这里，我就需要继续对我们的父亲结点进行分裂操作，因为它的关键字数超过了：m-1.  
![这里写图片描述][SouthEast 12]

哦，终于遇到这种情况了，我们的根结点出现了关键子数量超过m-1的情况了，这个时候我们需要对父亲结点进行分列操作，但是根结点没父亲啊，所以我们需要重新创建根结点了。  
![这里写图片描述][SouthEast 13]

好了，到了这里我们也知道怎么进行B-树的插入操作。

### 5、B-树的删除操作 ###

B-树的删除操作同样是分为两个步骤：

1.  利用前述的B-树的查找算法找出该关键字所在的结点。然后根据 k（需要删除的关键字）所在结点是否为叶子结点有不同的处理方法。如果没有找到，则直接返回。
2.  若该结点为非叶结点，且被删关键字为该结点中第i个关键字key\[i\]，则可从指针son\[i\]所指的子树中找出最小关键字Y，代替key\[i\]的位置，然后在叶结点中删去Y。

如果是叶子结点的话，需要分为下面三种情况进行删除。

*  如果被删关键字所在结点的原关键字个数n>=\[m/2\] ( 上取整），说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单，只需删除对应的关键字：k和指针：A 即可。
 *  如果被删关键字所在结点的关键字个数n等于( 上取整）\[ m/2 \]-1，说明删去该关键字后该结点将不满足B-树的定义，需要调整。

**调整过程为：如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于( 上取整）\[m/2\]-1。则可将右兄弟(或左兄弟)结点中最小关键字(或最大的关键字)上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。**

*  被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于（上取整）\[m/2\]-1。假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Ai所指，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一起，合并到 Ai所指兄弟结点中(若没有右兄弟，则合并至左兄弟结点中)。

下面，我们给出删除叶子结点的三种情况：  
第一种：关键字的数不小于（上取整）\[m/2\]，如下图删除关键字：12  
![这里写图片描述][SouthEast 3]  
删除12后的结果如下，只是简单的删除关键字12和其对应的指针。  
![这里写图片描述][SouthEast 14]

第二种：关键字个数n等于( 上取整）\[ m/2 \]-1，而且该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于( 上取整）\[m/2\]-1。  
![这里写图片描述][SouthEast 15]

如上图，所示，我们需要删除50这个关键字，所以我们需要把50的右兄弟中最小的关键字：61上移到其父结点，然后替换小于61的关键字53的位置，53则放至50的结点中。然后，我们可以得到如下的结果：  
![这里写图片描述][SouthEast 16]

第三种：关键字个数n等于( 上取整）\[ m/2 \]-1，而且被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于（上取整）\[m/2\]-1

![这里写图片描述][SouthEast 17]

如上图所示，我们需要删除53，那么我们就要把53所在的结点其他关键字（这里没有其他关键字了）和父亲结点的61这个关键字一起合并到70这个关键字所占的结点。得到如下所示的结果：  
![这里写图片描述][SouthEast 18]

Ok，我已经分别对上述的四种删除的情况都做了举例，大家如果还有什么不清楚的，可以看看代码，估计就可以明白了

；

**B+树**

B+树是B-树的变体，也是一种多路搜索树：

1.其定义基本与B-树同，除了：

2.非叶子结点的子树指针与关键字个数相同；

3.非叶子结点的子树指针P\[i\]，指向关键字值属于\[K\[i\], K\[i+1\])的子树

（B-树是开区间）；

5.为所有叶子结点增加一个链指针；

6.所有关键字都在叶子结点出现；

如：（M=3）

![5.JPG][]

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在

非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的特性：

1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好

是有序的；

2.不可能在非叶子结点命中；

3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储

（关键字）数据的数据层；

4.更适合文件索引系统；

**B\*树**

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

![6.JPG][]

B\*树定义了非叶子结点关键字个数至少为(2/3)\*M，即块的最低使用率为2/3

（代替B+树的1/2）；

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据

复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父

结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

B\*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分

数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字

（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之

间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B\*树分配新结点的概率比B+树要低，空间使用率更高；

**小结**

B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于

走右结点；

B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键

字范围的子结点；

所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点

中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

B\*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率

从1/2提高到2/3；

[1.JPG]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/a678a3f4a3f7483e823c42422b1efa0e.png
[2.JPG]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/0927acafa06b4f8da94e833475e08eda.png
[31.JPG]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/c3fab1dd05de45f7aa6ef7bdd2290b69.png
[K1]: https://www.baidu.com/s?wd=K1&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[i-1]: https://www.baidu.com/s?wd=i-1&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[SouthEast]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/4556ff3412bd4c1085b647aafe7dbe56.png
[SouthEast 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/caea0ee6aeac4f479027d19ee4f9ac47.png
[SouthEast 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/5f4cab525eeb40bb8556a019e1ddbe31.png
[SouthEast 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/3cd035ecde0c4af5900403a8f2a947e6.png
[SouthEast 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/962cd5819adc45399a3399e5e944b241.png
[SouthEast 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/87b67e0e7b3848058878c812ff86f424.png
[SouthEast 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/03e7f91c13f444b6a10f85caf1cb2e3e.png
[SouthEast 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/c72d580b46f54a7fb7cd7305cf04f0c7.png
[SouthEast 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/39ad00e7467b4049b8dafd7829f2cbaf.png
[SouthEast 9]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/ba65e5a5cd9c428dbafe2e79d82c8c91.png
[SouthEast 10]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/ea893a2e94174b13b0972479ae0d513a.png
[SouthEast 11]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/cbfc08ef408e4301b6a7d86c4e958477.png
[SouthEast 12]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/76ced33e819e4f99af49dae1a4f2a31b.png
[SouthEast 13]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/037d35deba6d424f86da4691073138e2.png
[SouthEast 14]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/a5500ef16b85405da82e71409a26b6b2.png
[SouthEast 15]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/4da36c08cc0a49d493905ce7122094bf.png
[SouthEast 16]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/78a3b6c3943c476c9c17ec5a48d1d3e9.png
[SouthEast 17]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/9488db08f2a34ca082a26207d2859040.png
[SouthEast 18]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/5a492de458794f57aa3404d65c8040d0.png
[5.JPG]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/573386989ddd48679ab225dc88aede7a.png
[6.JPG]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/a389b5cbbe8240149d102737fe353157.png