B树详解

由于数据结构的东西涉及到许多的图片啊，流程啊什么的。所以会参考许多网上存在的资料加以总结，我会将参考链接放在文章后面。

B树

B树基本概念

网上的许多资料在讲述数据结构之前都会讲相关的一些符合、说明以及特性什么的都交代清除。在阅读网上资料的时候我发现许多知识点说的都非常的官方，简单来说就是贼难看懂。所以我在记录的时候会将那些难懂的官方内容用通俗的话解释一下，方便我自己的理解。

首先来说，为什么我们要引入B树呢？有二叉树不是很好吗？

存在即合理。所以还是有存在的理由的。B树的时间复杂度与二叉树一样，均为O(logN)。然而Ｂ树出现是因为磁盘ＩＯ。ＩＯ操作的效率很低，那么，当在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只能逐一加载磁盘页，每个磁盘页对应树的节点。造成大量磁盘ＩＯ操作（最坏情况下为树的高度）。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。
　　所以，我们为了减少磁盘ＩＯ的次数，就你必须降低树的深度，将“瘦高”的树变得“矮胖”。

PS：这里我找到了一个讲述很好的二叉树与B树的比较链接。大家可以阅读以下。

http://m.elecfans.com/article/662237.html

比如下面的图片：

二叉树 B树

二叉树以2为最大基准向下延伸，而B树则没有标准，所以它可以变得矮矮胖胖的。

B 树又叫平衡多路查找树。一棵m阶的B 树 (m叉树)的特性如下：

• B树中所有节点的孩子节点数中的最大值称为B树的阶，记为M（重点）

• 树中的每个节点至多有M棵子树 ---即：如果定了M，则这个B树中任何节点的子节点数量都不能超过M

• 若根节点不是终端节点，则至少有两棵子树

• 除根节点和叶节点外，所有点至少有m/2棵子树（上溢）

• 所有的叶子结点都位于同一层。（比如上面的图片中我没有了11 13 15，那么我12就没有存在的意义了，就需要调整整个树的布局）

下面是我在百科中找到的性质：

image.png

B树的查找操作

查找操作的理解不难。我直接用几张图来阐述一下。

在B树上进行查找和二叉树的查找很相似，二叉树是每个节点上有一个关键子和两个分支。B树上每个节点有K个关键字和K+1个分支。二叉树的查找只考虑向左还是向右走，而B树中需要由多个分支决定。

B树的查找分两步，首先查找节点，由于B树通常是在磁盘上存储的所以这步需要进行磁盘IO操作。第二步是查找关键字，当找到某个节点后将该节点读入内存中然后通过顺序或者折半查找来查找关键字。若没有找到关键字，则需要判断大小来找到合适的分支继续查找。

如下有一个3阶的B树，观察查找元素21的过程：

image.png

第一次磁盘IO：

image.png

第二次磁盘IO：

image.png

这里有一次内存比对：分别跟3与12比对。

第三次磁盘IO:

这里有一次内存比对，分别跟14与21比对

PS：此处参考：http://m.elecfans.com/article/662237.html

由于B树相对于二叉树来说矮胖了许多，所以它所涉及的IO操作也相对少了许多。不过根据我们上面的分析，其在查找数据的时候并没有减少比较次数。但是我们知道，我们在比较数据的时候是在内存中进行的，所以相对来说时间上会更加迅速，几乎可以忽略。

而相同数量的key在B树中生成的节点要远远少于二叉树中的节点，相差的节点数量就等同于磁盘IO的次数。这样到达一定数量后，性能的差异就显现出来了。

这里先放下一个问题，既然我的介数M是自行设定的。那么我们的M如果很小那么会变成类似于二叉树，那么当M很大的时候呢？

我认为当M很大会导致比较次数过多，在当前磁盘空间能容纳的范围下也有可能导致比较次数过多而导致效率降低的情况。

B树的插入

对高度为ｋ的m阶B树，新结点一般是插在叶子层。通过检索可以确定关键码应插入的结点位置。然后分两种情况讨论：
　　1、 若该结点中关键码个数小于m-1，则直接插入即可。
　　2、 若该结点中关键码个数等于m-1，则将引起结点的分裂。以中间关键码为界将结点一分为二，产生一个新结点，并把中间关键码插入到父结点(ｋ-1层)中
　　重复上述工作，最坏情况一直分裂到根结点，建立一个新的根结点，整个B树增加一层。

例如：在下面的B树中插入key：4

image.png

第一步：检索key插入的节点位置如上图所示，在3,5之间；

第二步：判断节点中的关键码个数：
　　节点3，5已经是两元素节点，无法再增加（已经 = 3-1）。父亲节点 2， 6 也是两元素节点，也无法再增加。根节点9是单元素节点，可以升级为两元素节点。；

第三步：结点分裂：
　　拆分节点3，5与节点2，6，让根节点9升级为两元素节点4，9。节点6独立为根节点的第二个孩子。

最终结果如下图：虽然插入比较麻烦，但是这也能确保Ｂ树是一个自平衡的树。

image.png

另一个例子：

image.png

当插入一个关键字60后,节点内的关键字个数超过出了m-1=2，此时必须进行节点分裂，分裂的过程如上图所示。

资源来源参考于：https://blog.csdn.net/z_ryan/article/details/79685072

B树的删除

B树的删除操作相对较为复杂，我看许多文档解释的都十分官方且难懂。所以我准备用更为简单的图来对删除操作的不同情况进行解释。希望大家看完后能够理解。

• 首先，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。

之后我们需要分一下四种情况来考虑。（下面的例子中以5阶B树为例，介绍B树的删除操作，5阶B树中，结点最多有4个key,最少有2个key）对于删除key的过程来说，对于叶结点和非叶结点其实差别在一个地方，那就是如果当前我们操作的是非叶结点，那么后继key（这里的后继key指最接近当前删除值，且大于当前删除值的值）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。

例如：

a）原始状态

image.png

b）在上述情况下接着删除27。从上图可知27位于非叶子结点中，所以用27的后继替换它。从图中可以看出，27的后继为28，我们用28替换27，然后在28（原27）的右孩子结点中删除28。删除后的结果如下图所示。

image.png

之后我们就把非叶结点的情况转换为了处理叶结点的情况。

此时我们就要分一下几种情况来考虑如何处理叶结点。

• ①该结点key个数>=Ceil(m/2)-1（上界，例如m=5，那么最后为2），结束删除操作，否则执行下一步。

• ②该结点key的个数<Ceil(m/2)-1，且兄弟结点key个数>Ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。

a）紧接上面的例子。

image.png

b）删除后发现，当前叶子结点的记录的个数小于2（<Ceil(m/2)-1），而它的兄弟结点中有3个记录（>Ceil(m/2)-1 当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，不论选哪一个都行，只是最后B树的形态会不一样而已），我们可以从兄弟结点中借取一个key。所以父结点中的28下移，兄弟结点中的26上移，删除结束。结果如下图所示。

image.png

• ③如果该结点key的个数<Ceil(m/2)-1，且兄弟结点key个数<=Ceil(m/2)-1，那么将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。

例如：

a）原图为

image.png

b）在上述情况下删除32。

image.png

当删除后，当前结点中只有一个key（个数<Ceil(m/2)-1），而兄弟结点中也仅有2个key（<=Ceil(m/2)-1）。所以只能让父结点中的30下移和这个两个孩子结点中的key合并，成为一个新的结点，当前结点的指针指向父结点。结果如下图所示。

image.png

由于我们移动了父结点中的数据，所以其key值减少，那么我们就要对当前父结点进行考虑。

下面看一个考虑父结点的例子。

a）原图

image.png

b）上述情况下，我们接着删除key为40的记录，删除后结果如下图所示。

image.png

同理，当前结点的记录数小于2（根据情况③），兄弟结点中没有多余key，所以父结点中的key下移，和兄弟（这里我们选择左兄弟，选择右兄弟也可以）结点合并，合并后的指向当前结点的指针就指向了父结点。

image.png

同理，对于当前结点而言只能继续合并了，最后结果如下所示。（根据情况③）

image.png

合并后结点当前结点满足条件，删除结束。

此处参考了部分：https://www.cnblogs.com/nullzx/p/8729425.html的内容。