图解B+树的插入与删除

B+树的定义

上一篇我们介绍了B树, B+树与B树最大的不同是, B+树所有的关键字都存储在叶子节点, 中间节点仅作为索引.
关于B+树的定义以及解释要比B树多很多, 可能这也是因为B+树在实际使用中要比B树广泛很多. 我这里直接参考了nullzx对B+树的定义以及视图, 我主要修改我的B树的代码实现, 希望有用.

各种资料上B+树的定义各有不同, 一种定义方式是关键字个数和孩子结点个数相同. 这里我们采取维基百科上所定义的方式, 即关键字个数比孩子结点个数小1, 这种方式是和B树基本等价的. 上图就是一颗阶数为4的B+树.

除此之外B+树还有以下的要求.

1. B+树包含2种类型的结点：内部结点(也称索引结点)和叶子结点. 根结点本身即可以是内部结点, 也可以是叶子结点. 根结点的关键字个数最少可以只有1个.
2. B+树与B树最大的不同是内部结点不保存数据, 只用于索引, 所有数据(或者说记录)都保存在叶子结点中.
3. \(m\) 阶B+树表示了内部结点最多有 \(m-1\) 个关键字(或者说内部结点最多有 \(m\) 个子树), 阶数 \(m\) 同时限制了叶子结点最多存储 \(m-1\) 个记录.
4. 内部结点中的key都按照从小到大的顺序排列, 对于内部结点中的一个key, 左树中的所有key都小于它, 右子树中的key都大于等于它. 叶子结点中的记录也按照key的大小排列.
5. 每个叶子结点都存有相邻叶子结点的指针, 叶子结点本身依关键字的大小自小而大顺序链接.

B+ 树的插入操作

B+树的插入操作

1. 若为空树, 创建一个叶子结点, 然后将记录插入其中, 此时这个叶子结点也是根结点, 插入操作结束.

2. 针对叶子类型结点：根据key值找到叶子结点, 向这个叶子结点插入记录. 插入后, 若当前结点key的个数小于等于 \(m-1\), 则插入结束. 否则将这个叶子结点分裂成左右两个叶子结点, 左叶子结点包含前 \(\frac{m}{2}\) 个记录, 右结点包含剩下的记录, 将第 \(\frac{m}{2}+1\) 个记录的key进位到父结点中(父结点一定是索引类型结点), 进位到父结点的key左孩子指针向左结点,右孩子指针向右结点. 将当前结点的指针指向父结点, 然后执行第3步.

3. 针对索引类型结点：如果叶子节点发生分裂, 会在索引节点中插入关键字. 若当前索引结点key的个数小于等于 \(m-1\), 则插入结束. 否则, 将这个索引类型结点分裂成两个索引结点, 左索引结点包含前 $ \frac{m-1}{2}个key$, 右结点包含 \(m-\frac{m-1}{2}个key\), 将第 \(\frac{m}{2}\)个key进位到父结点中, 进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点. 将当前结点的指针指向父结点, 然后重复第3步.

下面是一颗5阶B树的插入过程, 5阶B数的结点最少2个key, 最多4个key.

是不是