B+树简介

B+树是B-树的变体，也是一棵多路搜索树

B+树中，所有记录节点都是按照键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接

B+树的插入必须保证插入后叶子节点中的记录依然有序，同时需要考虑插入到B+树的三种情况

情况一：Leaf Page没满，Index page没满

此时可以直接将记录插入到叶子节点

情况二：Leaf Page满，Index page没满

此时需要拆分Leaf Page，将中间的节点放入到Index page中，小于中间节点的记录放在左边，大于或等于中间节点的记录放在右边

情况三：Leaf Page满，Index page满

此时需要拆分Leaf Page，小于中间节点的记录放左边，大于或等于中间节点的记录放右边，拆分Index Page，小于中间节点的记录放左边，大于中间节点的记录方右边，中间节点放入上一层Index page

因为B+树结构主要用于磁盘，页的拆分意味着磁盘的操作，应该尽可能的减少页的拆分操作，所以B+树也同样提供了平衡二叉树的旋转操作，当Leaf Page满，但是其兄弟节点没有满的情况下，此时B+树不会急于去做拆分页的操作，而是将记录移到页的兄弟节点上，通常情况下，左兄弟会被首先检查用来用来做旋转操作

B+树插入都是在叶子节点进行的，就是插入前，需要先找到要插入的叶子节点
如果被插入关键字的叶子节点，当前含有的关键字数量是小于阶数m，则直接插入
如果插入关键字后，叶子节点当前含有的关键字数目等于阶数m，该节点开始分裂为两个新的节点，一个节点包含⌊m/2⌋ 个关键字，另外一个关键字包含⌈m/2⌉个关键值。（⌊m/2⌋表示向下取整，⌈m/2⌉表示向上取整，如⌈3/2⌉=2）
分裂后，需要将第⌈m/2⌉的关键字上移到父节点。如果这时候父节点中包含的关键字个数小于m，则插入操作完成
分裂后，需要将⌈m/2⌉的关键字上移到父节点。如果父节点中包含的关键字个数等于m，则继续分裂父节点

B+树使用填充因子(最小值是50%)来控制树的删除变化，且同样需要保证删除后叶子节点中的记录依然有序，也需要考虑三种情况

情况一：叶子节点不小于填充因子，中间节点不小于填充因子

此时可以直接将记录从叶子节点删除，如果该节点还是Index Page的节点，用该节点的右节点代替

情况二：叶子节点小于填充因子，中间节点不小于填充因子

此时需要合并叶子节点和它的兄弟节点，同时更新Index page

情况三：叶子节点小于填充因子，中间节点小于填充因子

此时需要合并叶子节点和它的兄弟节点，更新Index page，合并Index page和它的兄弟节点

找到包含关键值的节点，如果关键字个数大于⌈m/2⌉-1，直接删除即可
找到包含关键值的节点，如果关键字个数大于⌈m/2⌉-1，并且关键值是当前节点的最大（小）值，并且该关键值存在父子节点中，那么删除该关键字，同时需要相应调整父节点的值
找到包含关键值的节点，如果删除该关键字后，关键字个数小于⌈m/2⌉，并且其兄弟节点有多余的关键字，则从其兄弟节点借用关键字
找到包含关键值的节点，如果删除该关键字后，关键字个数小于⌈m/2⌉，并且其兄弟节点没有多余的关键字，则与兄弟节点合并