B树与B+树的区别?

原创
2021/02/24 19:40
阅读数 263

1.B树简介

B树是一种多路平衡搜索树。它由二叉树变换而来的。定义如下:
1.1每个节点最多有m-1个关键字
1.2根节点最少有1个关键字
1.3非根节点至少有m/2个关键字
1.4每个节点的关键字都是按照从小到大的顺序排列,每个关键字的左子树中的关键字都小于它,而右子树中所有关键字都大于它。
1.5所有的叶子节点都处于同一层,或者说根节点到每个叶子节点的长度都相同
1.6每个节点存储有索引与数据。
因此,根节点的关键字数量范围:1<=k<=m-1;非根节点关键字数量范围m/2<=k<=m-1。
注意:描述一颗B树时必须要指明它的阶数(m),阶数表示一个节点最多有多少个孩子节点。

2.B树插入数据过程

假设5阶B树,则节点最多有4个key,最少有2个key。现要插入6、10、4、14、5、11、15、3、12等数据。
2.1 插入6、10、4、14到根节点,则根节点中数据是4、6、10、14。
2.2 插入5时出现裂变,根节点变成6,左子树节点变成4、5,右子树节点变成10、14。
2.3 接着插入11、15、3三个数据,逐个与根节点比较,比较过程如下:
2.3.1 11与6比较,大于6,则插入6的右子节点,得到数据10、11、14
2.3.2 15与6比较,大于6,则插入6的右子节点,得到数据10、11、14、15
2.3.3 3与6比较,小于6,则插入6的左子节点,得到数据3、4、5
2.3.4 12与6比较,大于6,则插入6的右子节点,得到数据10、11、12、14、15,注意此时又需要裂变了。此时的数据结构如下

根:6
左:3、4、5
右:10、11、12、14、15(需裂变)

很明显,取中间的数据12到根节点,重新得到的平衡树如下

根:6、12
左:3、4、5
中:10、11
右:14、15

裂变的本质是:尽可能使这个树矮,因为矮意味着磁盘I/O次数少。

3.B树删除数据过程

首先查找B树中是否存在需要删除的元素,如果存在,则删除该元素,之后判断该元素是否存在左右孩子节点,如果有,则上移孩子节点中相近元素(左孩子最右边节点或者右孩子最左边节点)到父节点中;如果没有,则直接删除。
假设如上B树中需要删除14、12节点,步骤如下:
3.1 删除14节点,不会对树的平衡有任何影响,所以直接删除了;但是如果接着再删除15节点,就影响树的平衡了,需要重新裂变了。
3.2 删除12节点,12节点左子树有10、11,右子树有15。如果我们将15移上去,得到如下树:

根:6、15
左:3、4、5
右:10、11

我们发现这种树不可能,需要重新裂变;那么我们选择将11移上去,得到如下树:

根:6、11
左:3、4、5
中:10
右:15

我们发现这种树是平衡的,满足要求。

4.B树搜索数据过程

假设我们要搜索节点10,步骤如下:
4.1 10与根节点比较,不等于6,则再跟11比较,发现小于11,那么就会与11的左子树中第一个节点比较,刚好是10,则查询到了。2级查询到数据,则需要操作2次磁盘I/O。从这里我们也可以知道,树越矮,则磁盘操作越少,速度越快。

5.B+树简介

B+树是B树的变种。它与B树的关系如下:
相同点:

1>根节点至少有一个元素
2>非根节点元素范围:m/2<=k<=m-1

不同点:

1>B+树有两种类型节点:内部节点(也称索引节点)与叶子节点。内部节点只存储索引,不存储数据;叶子节点存储数据。
2>每个叶子节点都存有相邻叶子节点的指针,叶子节点本身依关键字有小到大顺序链接。

6.B+树插入数据过程

B+树插入数据与B树插入过程基本相同,不同的是:遇到裂变时,中间key变成根节点,同时中间key要成为右子树的第一个key。
假设5阶B+树,向B+树插入5、8、10、15、16、17、18数据过程如下:
6.1 插入5、8、10、15到根节点,则根节点中索引是5、8、10、15,注意索引中有值。
6.2 再插入16索引,则需要裂变,取索引10作为根节点,10同时要作为右子树第一个索引,得到的数据如下:

根:10
左:5、8
右:10、15、16

6.3 再插入17,不会裂变,插入18时,得到的数据如下:

根:10
左:5、8
右:10、15、16、17、18

此时需要裂变,取中间节点到根节点,得到如下数据:

根:10、16
左:5、8
中:10、15
右:16、17、18

自此结束。
注意:B树与B+树最显著的区别是B+的节点存放索引+数据,B+树内部节点存放索引,叶子节点存储数据。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部