如何选择树状图和列表（图解什么是B-树）

原文地址：

https://mp.weixin.qq.com/s?__biz=MzA5MjMxNTY3NA==&mid=2247484039&idx=1&sn=e72c6a7697275b19cdad89431eea8924&chksm=906e4bf2a719c2e49f8568da38fc25281b54a47581d23c2d1695ee08b0b8ef0c26dd08e8c542&scene=21#wechat_redirect

1.二叉搜索树

在说B树之前，我们需要先了解一下二叉搜索树

二叉搜索树，顾名思义，是用来搜索的有序树

它具有以下特点：

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

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

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

下边这个就是一棵二叉搜索树

1.1 二叉搜索树的查找

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

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

如果比结点关键字大，就进入右儿子

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

搜索数字8的过程如上图

比起循环遍历的查找方法

二叉查找可以将时间缩小到一半

1.2 二叉搜索树的插入

二叉搜索树的插入，从根结点开始，进行比较

如果相等，则不进行插入操作

如果大于当前节点，则与右孩子进行比较

如果小于当前节点，则与左孩子进行比较

最终将新元素加入到搜索停止的地方

插入数字11的过程如上图

1.3 二叉搜索树的删除

删除操作和查找操作差不多

找到之后就把当前节点删除

然后比较删除节点的左孩子替代当前位置

删除数字11的过程如上图

1.4 存在问题

二叉搜索树的插入过程不会改变已有节点的位置

这样在我们依次插入1,2,3,4,5,6,7的时候，会出现下面这种情况

当是这种结构的时候，它就是线性结构了

查找效率就又恢复到全部遍历了

为了解决这种问题，平衡二叉树（AVL树），又叫自平衡二叉树就出现了

2. 什么是B树

B树，即B-tree树，B是Balanced首字母，平衡的意思

因为B树的原英文名称为B-tree

很多人喜欢把B-tree译作B-树，然后读作B减树

其实，这么是不对的

容易让人会以为B树和B-树是两种树

特此声明：B-树就是指的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）节点为例，它有三个子节点，分别是

（001,002）、005、007

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

3、这是一个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）

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

所以将根节点的右孩子，拆分成了两个

至此，调整完成，完全符合B-的特性了

3.4 B-树删除操作

删除节点16

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

首先还是要先找到目标值，即16这个结点

然后将其删除，此时15节点的子孩子只有一个

不符合特性3了

将16的父节点元素较大值15往下放

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

此时根节点只有一个元素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

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的特点

比如，对于3阶B*树，当元素个数大于1的时候

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

6. 小结

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

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

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

B 树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B 树总是到叶子结点才命中；

B*树：在B 树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

依据自己的特性，这几种搜索树在文件系统或数据库的索引建立中，有着非常广泛的应用

,