day9 B树

何为B树？B树是一种平衡的多路搜索树，多用于文件系统，数据库的实现

下面上几张B树图：

3阶 4阶 5阶

从B树图中可以看出一些特点：1个节点可以存储超过2个元素，可以拥有超过2个子节点，每个节点的所有紫薯高度一致

m阶B树的性质()

假设一个节点存储的元素个数为x

如果该节点是根节点：,如果是非根节点，如果有子节点，子节点个数y=x + 1；那根节点的子节点个数,非根节点的的个数：

B树VS二叉搜索树

二叉搜索树 3阶B树

可以发现B树和二叉搜索树，在逻辑上是等价的，可以这样理解3阶B树是由二叉搜索树2～n代合并组成的，于是由下面这样一些性质：

2代合并的超级节点，最多拥有4个子节点(至少是4阶B树)，3代合并的超级节点，最多拥有8个子节点(至少是8阶B树)，n代合并的超级节点，最多拥有个子节点（至少是阶B树），m阶B树，最多需要代合并

B树搜索

1.现在节点内部从小到大开始搜索元素

2.如果命中，搜索结束

3.如果未命中，再去对应的子节点中搜索元素，重复步骤1

B树添加

新添加的元素必定是添加到叶子节点的（从上面往下比，然后一直到最后）

示例图

假如现在插入55

插入55

但是这里你会发现，如果所有叶子节点都达到饱和的情况下，或者要添加的那个叶子节点达到饱和的时候，就会出现一个问题节点上溢

添加-上溢的解决（假设5阶）

从前面可以知道一个性质，就是如果B树发生上益那么上溢节点的元素个数必然等于m，上溢的解决方式如下：

假设上溢节点最中间的元素位置为k，将k位置的元素向上与父节点合并，然后将[0,k-1]和[k+1,m-1]位置的元素分类成2个子节点，这2个子节点的元素个数，必然都不会低于最低限制（ceil(m/2)-1),如果一次分类完毕后，有可能导致父节点上溢，依然按照上面说的方式解决，一层一层往上处理，最极端的情况，就是有可能一直分裂到根节点；给个展示图：

上溢处理图

再示范多一个添加过程图：

B树添加

B树删除

删除分叶子节点删除和非叶子节点删除，如果需要删除的元素在叶子节点，那么直接删除就可以了例如下面图：

删除叶子节点

如果删除的是非叶子节点，那么就要先找到前驱或后继元素，覆盖所需删除元素的值，再把前驱或后继元素删除，如下图：

删除非叶子节点

从图中可以得出结论：非叶子节点的前驱或后继元素，必定在叶子节点中，真正删除的元素都是发生在叶子节点中；

但是删除节点有可能会导致下溢情况的出现，例如下面这种情形：

下溢

假设上面这个图是一棵5阶B树，那么如果删掉元素22之后，元素个数可能就会低于最低限制(),这个时候我们就要解决下溢的问题了

删除-下溢的解决

下溢节点的元素数量必然等于ceil(m/2)-2，如果这个时候下溢节点临近的兄弟节点，有至少ceil(m/2)个元素，可以向其借一个元素，如下图：

下溢1

但是如果下溢节点临近的兄弟节点，只有ceil(m/2)-1个元素呢？这个时候我们需要从父节点中挪取元素下来跟左右子节点进行合并，合并后的节点元素个数等于ceil(m/2)+ceil(m/2)-2,不超过m-1,但是这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播，示例图：

下溢2

举一个例子说明展示实际情况：

删除例子

B树大概就学习到这里先吧，后续如果我还能学到新的东西的时候再补充吧