B+树的原理

前言

B树的引入主要是由于 当 把数据储存到磁盘上，由于访问磁盘的IO时间是限制速度的主要原因，大 $O$O 模型不在适用，这个时候减少磁盘 $IO$IO 次数是主要要考虑的，我们希望把次数减少到一个非常小的常数。
将 AVL 树改造成有多个分支的，那么树的高度就小了，访问 的 $IO$IO 次数也会减少，这是个不错的选择，通常 一颗$M$M 阶的完全二叉树的高度大约为 $log{_M}^N$logM​N。

性质

• 数据到存储在叶子节点上
• 非叶子节点储存 $M-1$M−1 个关键字，用来指示搜索的方向，例如，第 $i$i 个关键字是 25，那比25 大的数字就在i+1方向的节点，25 是 i+1 个节点最小的数字；
• 除根节点外，非叶子节点的儿子数在 $ceil(M/2)$ceil(M/2) 和 $M$M之间;
• 根节点的儿子数在 $2$2 和$M$M之间。
• 所有叶子在相同深度上具有 $ceil(L/2)$ceil(L/2) 和 $L$L 之间个数的数据项。本例 L设为5
• 所有节点都有序排列

如下图就是一个 5 阶 B+树

insert 操作

插入先看项是否存在，然后执行相关操作，有好几种情况

1. 插入 57

从根节点开始找，这是第一次 IO,57 位于 44和66之间，所以 在第二个子树，访问第二个子树，这是第二次 IO,继续找 54后边的叶子，里边有 54，56，58，59 四个数字，没有超过个，直接插入就行了，结果为

2 插入55

我们发现，应该插入到第 3个键55对应的下一个叶子，即第4个叶子，但这个叶子再加1个，已经6个项了，超过了 5个，所以我们把他们分裂成两个叶子，父节点增减一个键，就是下边的

3 插入 40

插入 40 的时候，我们想按照上边插入 55的思路分裂叶子，但发现 叶子节点也是满的，不着急，继续向上分裂，最终父节点进行了分裂。

• 如果一直向上分裂，根节点分裂成两个节点，树的高度就会增加1，新的根节点就会有两个孩子节点，这就是根节点特殊的地方，可以有2个字节点，而其他节点不可以。
  

4 插入 29

发现对应的叶子满了，但右边的兄弟叶子没有满，可以把多余的给兄弟节点，使用叶子趋于饱满。

未完明天继续。。。。。