平衡二叉树、B树、B+树，B*树的区别与联系

﹏ヽ暗。殇╰゛Y 2022-01-26 14:21 246阅读 0赞

### 平衡二叉树 ###

**定义：基于二分法**的策略**提高数据的查找速度**的一种二叉树数据结构；

**特点：平衡二叉树是采用二分法**思想把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度；平衡二叉树的数据结构组装过程遵循以下规则：

（1）**非叶子节点**只能允许**最多两个子节点**存在。

（2）每一个非叶子节点数据分布规则为**左边的子节点小当前节点的值**，**右边的子节点大于当前节点的值**(这里值是基于自己的算法规则而定的，比如hash值)；

![image-20190529103352585][]

平衡树的层级结构：因为平衡二叉树**查询复杂度**和**树的层级（h高度）成反比，h值越小查询越快，为了保证树的左右两端数据大致平衡以降低二叉树的查询难度**一般会采用一种算法机制实现**节点数据结构的平**衡，实现了这种算法的有比如**AVL**、**Treap**、**红黑树**等，使用平衡二叉树能保证数据的**左右两边的节点层级相差不会大于1**，这样可以避免树形结构由于删除增加变成线性链表进而影响查询效率。保证数据平衡的情况下查找数据的速度近于二分法查找。

**总结平衡二叉树特点：**

1.  非叶子节点最多拥有两个子节点；
2.  非叶子节值大于左边子节点、小于右边子节点；
3.  树的左右两边的层级数相差不会大于1;
4.  没有值相等重复的节点;

### B树 ###

定义：B树和平衡二叉树稍有不同的是B树属于**多叉树**又名**平衡多路查找树**（查找路径不只两个），**数据库索引**技术里大量使用者B树和B+树的数据结构（**今天数据库课上刚学到的**）。

**规则：**

1.  **排序方式**：所有节点关键字是按**递增次序**排列，并遵循**左小右大**原则；
2.  **子节点数**：非叶节点的**子节点数>1**，且\*\*<=M （M>=2）\*\*，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；
3.  **关键字数**：枝节点的**关键字数量**大于等于`ceil(m/2)-1`个且小于等于`M-1`个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
4.  所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

示意图如下图所示，这里假设字母的排序规则为A>B>C…：

![image-20190529105433812][]

如上图我要从上图中找到E，查找流程如下

1.  获取根节点的关键字进行比较，当前根节点关键字为M，E<M，所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；
2.  拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；
3.  拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；

### B+树 ###

\*\*概念：\*\*B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；

![屏幕快照 2019-05-30 12.32.16][2019-05-30 12.32.16]

如上图所示，我们看看B+树遵循的规则：

1.  B+跟B树不同之处在于B+树的**非叶子**节点不保存关键字记录的指针，只进行数据索引，即有k个子树的中间节点包含有k个元素，而B树中是k-1个元素，这样使得B+树每个**非叶子**节点所能保存的关键字大大增加；
2.  B+树**叶子**节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到，所以**每次数据查询的次数都一样**；
3.  B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针（如图中红色虚线框中所示）。
4.  所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素(如图中黑色和红色标出的数字)
5.  非叶子节点的子节点数=关键字数，另一种规则是非叶节点的关键字数=子节点数-1，虽然这两种规则数据排列结构不一样，但其原理还是一样的**Mysql 的B+树是用第一种方式实现**;

可能有的读者对上面的第1点不太理解，从图上看B树和B+树的节点中都是数字啊，有什么不一样，为什么说B+树的非叶子节点不保存关键字记录的指针？这里引入一个\*\*"卫星数据"**的概念来给大家解释，所谓卫星数据，指的是**索引元素所指向的数据记录\*\*，也就是我们这里说的\*\*“关键字记录的指针”\*\*，比如数据库中的某一行。在B树中，无论中间节点还是叶子节点都带有卫星数据，而B+树只有叶子节点才带有卫星数据，我们来给一张对比图：

**B树：**

![image-20190530125100140][]

**B+树：**

![image-20190530124400140][]

从上面两幅图就可以就看出，B树的每一个节点都有一个\*\*“关键字记录的指针”\*\*（即图中的data部分），而B+树只有叶子节点才有。

**特点：**

1、B+**树的层级更少**：相较于B树B+每个**非叶子**节点存储的关键字数更多，树的层级更少所以查询数据更快；

2、B+**树查询速度更稳定**：B+所有关键字数据地址都存在**叶子**节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;

3、B+**树天然具备排序功能：B+树所有的叶子**节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。

4、B+**树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子**节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

**B树**相对于**B+树**的优点是，如果经常访问的数据离根节点很近，而**B树**的**非叶子**节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比**B+树**快。

### B\*树 ###

![image-20190530130200063][]

规则：B\*树是B+树的变种，相对于B+树他们的不同之处如下：

1.  首先是关键字个数限制问题，B+树初始化的关键字初始化个数是ceil(m/2)，b\*树的初始化个数为 c e i l ( 2 3 m ) ceil(\\frac\{2\}\{3\}m) ceil(32m)
2.  B\*树中**非根**和**非叶子结点**增加**指向兄弟的指针**，如上图的红色箭头所示。
3.  B+树节点满时就会分裂，而B\*树节点满时会**检查兄弟节点是否满**（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则**从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来**；

特点：

在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B\*树的分解次数变得更少；

### 总结 ###

**1、相同思想和策略**

从平衡二叉树、B树、B+树、B\*树总体来看它们的贯彻的思想是相同的，都是采用二分法和数据平衡策略来提升查找数据的速度；

**2、不同的方式的磁盘空间利用**

不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变，每一次演变都是为了让节点的空间更合理的运用起来，从而使树的层级减少达到快速查找数据的目的；

[image-20190529103352585]: /images/20220126/3d987799f4df4ec9908ba086fe82759c.png
[image-20190529105433812]: /images/20220126/f43c6e4a164b4b44bae82f5dbd278e56.png
[2019-05-30 12.32.16]: /images/20220126/5d1237d5d37c4d0da706fddc0977e818.png
[image-20190530125100140]: /images/20220126/445d292d968c471d9d2b96e16195f91f.png
[image-20190530124400140]: /images/20220126/08086acf6a604cb98e3b7796ce4b8b89.png
[image-20190530130200063]: /images/20220126/55b7cbcb6c9b435bbf1a35befb3a39c8.png