知识准备

在总结B树和B+树插入和删除的过程之前，首先要明确一下B树和B+树的几个性质：

• 对于B树和B+树的根节点都至少有一个根节点；
• 对于B树和B+树的非根节点元素，每个节点中的关键字的个数的范围为：（假设一个m阶的B/B+树）[m/2，m-1]。（闭区间）
• 对于每个节点中的关键字都按照升序进行排列。
• 对于B树，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
• 对于B树，所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

除此之外B+树还有如下性质：

• B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。

• B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。

• m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录。

• 内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。

• 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。

---

B树的插入和删除

在一下插入和删除的分析中，以一颗5阶的B树为例来进行分析：

插入

假设现在给定一组数据：39，22，97，41……等一系列数据，要将他们插入这棵5
阶的B树中。
首先，根据该B树为5阶，可知每个非根节点的关键字个数的范围为：[2,4]，即每个非根节点的关键字数必须大于等于二且小于等于4。这一系列数据的插入过程分析如下：

• 对于前4个数据，可以直接插入到根节点作为关键字，因为其数量不大于4。其中，每插入一个数据之后的关键字都按照升序进行排列。
• 当插入第五个数据时，因为直接插入到根节点关键字数量已经不符合范围要求，这时还是将这5个树升序排列，并从他们的“中位数”将这一串关键字分裂开，即分为一个根节点和两个非根节点。（如果最大关键字数量为奇数，当关键字数量超过变成偶数时，则选择中位数中的其中之一作为根节点分开即可）
• 对于之后插入的数据，根据数据的的大小判断应插入到哪一个叶节点中，并判断当前插入到的节点中的关键字数量是否超过范围。
• 如果超过范围，则按照第二步中“分裂”的方法，并将当前分裂出的父节点归结到根节点中。
• 继续按照上述方法插入，如果根节点的关键字个数也超过4时，这时继续“分裂”，也就产生了第一层非根节点。
• 之后的插入以此类推。

删除

仍然以一个5阶B树为例分析其删除节点的过程，假设给定一个要删除的结点：

• 若当前节点不存在，则找不到该节点，删除失败。
• 如果当前节点为叶节点，并且当前节点的关键字个数大于2（m/2），说明删除节点后的关键字个数仍符合范围要求，所以直接删除，删除节点结束。
• 如果删除后的关键字个数不符合范围要求，此时需要向兄弟节点“借”一个结点，如果兄弟节点删除后的个数符合要求，则将相邻的关键字“上移”为当前节点的父节点，对应的父节点下移与删除的结点中的关键字合并；
• 如果此时兄弟节点的关键字个数“不够借”，此时需要先删除这个关键字，然后将该节点中的剩下的关键字与兄弟节点中的关键字，以及将他们对应的父节点中的关键字“下移”，将这三者合并为一个结点即可。
• 如果删除的结点是非叶节点，则用后继key（这里的后继key均指后继记录的意思，即子节点中第一个大于该节点中key值的关键字）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。

---

B+树的插入和删除

插入

对于B+树的插入，和B树的插入过程基本相同，不同的就是，当遇到中间key要进行分裂时，中间的key同时要成为父节点的key和右子树的第一个key。
注意：
若当前key已经在父节点的key和子节点的key中重复出现过，则不再作为右节点的第一个key出现，如下图所示：

在上图中，关键字16就是这种情况。

删除

• 若待删除的key不存在，则删除失败，删除过程结束。
• 若key对应的结点删除之后key的数量仍满足范围，则删除结束。
• 若不满足，则采取向兄弟节点借的方式。若兄弟结点key有富余（大于Math.ceil(m-1)/2 – 1），向兄弟结点借一个记录，同时用借到的key替换父结（指当前结点和兄弟结点共同的父结点）点中的key，删除结束。否则执行下一步。
• 若兄弟结点中没有富余的key,则当前结点和兄弟结点合并成一个新的叶子结点，并删除父结点中的key（父结点中的这个key两边的孩子指针就变成了一个指针，正好指向这个新的叶子结点），将当前结点指向父结点（必为索引结点），执行第5步（第5步以后的操作和B树就完全一样了，主要是为了更新索引结点）。
• 之后的操作和B树完全相同。

（在理解两树的插入和删除时最好结合例子来亲身体会，不然会很难理解）

总结

对于B+树的删除，在删除的过程中其实会遇到很多种情况，但其实需要抓住字关键的一点，即每删除一个key都要观察当前节点剩下的关键字个数够不够key的数量的最小值，如果不够，就需要通过“借”来进行修改，并需要根据情况修改/替换/删除父节点的key值，置于进行哪种具体操作，需要视情况而定；如果不够兄弟节点的关键字不够借，则需要选择兄弟节点进行合并，并修改父节点的关键字。

---

ps：总结来自于博文：
B树和B+树的插入、删除图文详解