B-树和B+树数据结构及B-树的创建和删除操作详细过程

众所周知，mysql的索引用的是B+树

那么到底啥是B+树呢？今天学习了一下

下面总结一下我今天学到的知识！

若有错误感谢纠正

首先

B-树念作B树（而不是B减树）

B+树念作B加树

1、B-树

1.1、B树概念

1. 每个结点最多有m个分支(子树) ;而最少分支数要看是否为根结点，如果是根结点且不是叶子结点则至少有2个分支，非根非叶结点至少有「m/2⌉ 个分支。
2. 有n (k<=n<=m) 个分支的结点有n-1个关键字，它们按递增顺序排列。k=2(根结点)或「m/2⌉ (非根结点)
3. 结点内各关键字互不相等。
4. 叶结点处于同一层;可以用空指针表示，是查找失败到达的位置。

阶数是人为规定的，下图为五阶B树。

节点结构体定义示意图：

p所指向的结点关键字小Key+1大于Keyi。

1.2、关键字的查找

从根节点开始，从左往右扫描关键字，如果找不到就沿着适当的分支到下一节点中去查找。因为节点的关键字很少，所以可以用顺序查找

1.3、关键字的插入（建树方法）

用以下关键字序列{1，2，6, 7，11，4，8, 13, 10，5，17，9, 16,20, 3, 12, 14, 18, 19， 15}创建一棵5阶B-树。

1. 五阶B树最多有四个关键字，所以插入前四个关键字

   

2. 然后插入11

   

   但是超过了四个关键字，所以进行节点拆分的操作

   节点拆分：把当前节点中的5/2向上取整的位置上的关键字提出来

   

   5/2向上取整为3

   3位置上的关键字是6

   把6提出来，并把它左边的关键字，右边的关键字分别装在两个新的节点中

   

   插入时，先查找再插入（如插入4的时候找到了2的右分支的位置）
3. 插入到如下情况时需要再次进行节点拆分，如下图所示

   

   将10提出来并入上层节点，如下图所示

   

4. 不断插入后，成如下图所示时需要再次才分

   

   将13提出来并入上一次节点

   

   发现还需要再次拆分，将10提出来进行拆分（进行一次插入进行了两次拆分操作，这就叫连锁反应）

   

1.4、关键字的删除

对于上面建好的B-树，给出删除关键字8、16、 15、 4的过程。

1. 删除8如下图所示

   

2. 删除16时，16所在节点非叶子结点，删除后可以用左分支节点的最大关键字或者右分支节点的最小关键字代替16，因为左分支节点只有两个关键字，已到达节点的最小数量2（最小分支数是5/2向上取整为3，最小关键字数就是3-1为2）所以用17取代16，删除后的数结构如下图所示

   

3. 删除15时因为15所在的节点关键字数目已经达到下限，所以想起兄弟节点借关键字。先让17下来，然后让右兄弟节点的关键字上去，效果如图所示。然后再删除15即可。

   

4. 删除4时，所有两边的兄弟节点都无法借关键字。于是不借关键字，直接删除4然后进行节点合并操作。

   删除4

   

   关键字5所在的节点与左边的节点或右边的节点进行合并，此处是与右边节点合并。将上层节点的6拉下来与左右分支节点形成一个新节点。

   

   但是此时发现关键字3所在的节点只有一个关键字，不符合B树要求，于是再次进行合并，将上层节点关键字10拉下来与左右节点合并，效果如下图所示。

   

2、B+树

B+树与B-树的不同

1. 在B+树中，具有n个关键字的结点含有n个分支;而在B-树中，具有n个关键字的结点含有n+1个分支。
2. 在B+树中，每个结点(除根结点以外)中的关键字个数n的取值范围为「m/2⌉ <=n<=m,根结点的取值范围为2<=n<=m;而在B-树中，它们]的取值范围分别是「m/2⌉-1<=n<=m-1和1<=n<=m-1。
3. 在B+树中叶子结点包含信息，并且包含了全部关键字，叶子结点引出的指针指向记录。
4. 在B+树上有一个指针指向关键字最小的叶子结点，所有叶子结点链接成一个线性链表，而B-树没有。B+树可以根据P指针进行顺序查找。

学习视频来源：

https://www.bilibili.com/video/BV1Aa4y1j7a4?t=1605