（一小？校长手记）什么是B-树

3.什么是B树？

首先，B树是一种多路平衡搜索树。

简单来说日非是什么字，每个节点存储多个数据值。

每个节点还拥有两个以上的子节点

与平衡二叉树相比，可以大大降低树的高度

提高树检索效率

3.1 B树的特点

我们来详细介绍一下，m阶B树有以下特点：

1、定义任意非叶子节点最多有M个儿子； 且M>2；

2、根节点的孩子个数为[2,M]；

3、除根节点外的非叶子节点的儿子数为[M/2，M]；

4、每个节点至少存储M/2-1（向上取整），最多M-1个关键字； （至少2个关键词）

5、非叶子节点的关键字个数=子节点的指针个数-1；

6、非叶子节点的关键字：K[1]、K[2]、…、K[M-1]； 且 K[i] < K[i+1]；

7. 指向非叶子节点的指针：P[1], P[2], …, P[M]； 其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其他P[i]指向关键字所属的子树至 (K[i-1], K[i])；

8、所有叶子节点位于同一层；

你看起来是不是有点困惑？

例如，这是一个B树

对比上面的B树特性，我们来做一下解释

1、节点8左边的值全部小于8，右边的值全部大于8。

2、以(003,006)节点为例。 它有3个子节点，分别是

(001,002), 005, 007

其中（001,002）小于003，005大于003且小于006，007大于006

3. 这是一个三阶B树，每个节点最多有两个元素，每个节点最多有三个子节点。

好吧，这样是不是就更清楚了？

3.2 B树查询操作

查询值9的过程

从根节点开始，先与8进行比较

大于8，所以找到8的右子节点，即(0010,0012)节点

和10相比，小于10，所以找到这个节点最左边的孩子9

与9比较，等于要查找的值，返回

3.3 B树插入操作

插入值6的操作

首先，就像搜索一样，先比较

终于找到了合适的位置，就是节点(0013,0015)

将16插入该节点，则变为(0013,0015,0016)

由于元素个数k大于m-1（这是三阶B树，m-1=2）

为了符合B树的特性，会先更新父节点的元素个数。

向上传递元素时，传递的原则是中间值优先，所以传递的元素是15

但父节​​点也必须符合B-的特点

由于元素个数也超出了，所以向上层传递元素，传递的元素为12

最后到达根节点，变成(0008,0012)

此时根节点需要有3个孩子

所以根节点的右孩子被分成了两个

至此调整完成，完全满足B-的特点

3.4 B树删除操作

删除节点 16

删除操作相当于插入操作的逆操作。

首先我们需要找到目标值，即节点16

然后删除它。 此时，节点15只有一个子节点。

不符合特征3

将16中值15较大的父节点元素向下放置

同时将值12较大的15的父节点元素向下放置

此时根节点只有一个元素8，并且只能有两个子节点。

将 10 和 12 合并为 (0010,0012)

调整指针指向

至此调整完成，完全符合B树特性。

完全删除值16

4.什么是B+树？

B+树是B树的变种，是一种多路搜索树。

4.1 B+树的特点

它的基本定义和特点与B树相同，除了：

1、非叶子节点的子树指针与关键字个数相同

2、非叶子节点的子树指针P[i]指向键值属于[K[i],K[i+1]]的子树（B树是开区间）（下面动画示例）是遵循开区间生成的，当然满足条件，但显然不是最优结构）

3.为所有叶子节点添加链指针

4.所有关键字都出现在叶子节点中

再举个栗子大家就清楚了。

与B树相比，B+树的所有节点值都会出现在叶子节点中。

而且，所有叶子节点形成一个升序链表

4.2 B+树查询

查询值11

[外部链接图像传输失败。 源站可能有防盗链机制。 建议保存图片直接上传(img--60)()]

4.3 B+树的插入

插入值16

4.4 B+树的删除

删除值16

5.什么是B*树？

它是B+树的变体。 指向兄弟的指针被添加到B+树的非根节点和非叶节点。

B*树定义非叶子节点元素数量至少为(2/3)*M，即块的最小使用率为2/3（替代B+树的1/2）

B*的查询、插入、删除操作与B+树类似

正是遵循非叶子节点元素个数至少为(2/3)*M的特点

例如，对于三阶B*树，当元素个数大于1时

每个非叶子节点的元素数量，至少两个

六、总结

二叉搜索树：二叉树，每个节点只存储一个关键字，如果等于命中，如果较小，则走左节点，如果较大，则走右节点；

B（B-）树：多路搜索树，每个节点存储M/2到M个关键字，非叶子节点存储指向关键字范围的子节点；

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

B+树：在B树的基础上，在叶子节点上增加了一个链表指针。 所有关键字出现在叶子节点，非叶子节点作为叶子节点的索引； B+树总是命中叶节点。 ;

B*树：在B+树的基础上，对于非叶子节点还增加了链表指针，将节点的最小利用率从1/2提高到2/3；

根据自身的特点，这些搜索树在文件系统或数据库中建立索引方面有着非常广泛的应用。

7.思考

为什么MySQL的引擎最终选择B+树？