B树和B+树

本文只总结删除。

核心思想为，优先处理下层次的结构，处理好后，下层次不再改变；把错误往上传递。

——————————————————

B树：

1、第一次被删除的一定是叶子节点的某个元素

2、（暂定删除节点元素为X）如果删除后，本节点的元素数少于等于（1/2总元素数向上取整后-1），则3或4；否则直接结束

3、如果兄弟节点也没有富裕元素，则兄弟和本节点和parent中连接两节点的元素合并。注意parent中被合并的元素层次会下降。【如果此时参考点为叶子节点，则这时候相当于删除了parent的一个元素。现在把参考点设为parent，回到步骤2】【如果现在参考点不是叶子节点，则同样要把上一层节点中的一个元素下降到这里，和自己与兄弟合并。参考点再次向上挪一层。回到步骤2】

4、如果兄弟有富裕（大于 1/2总元素数向上取整后-1），则向parent借一个元素P，然后取一个兄弟的元素Q取代原来P的位置。【如果现在参考点为叶子节点，则可以结束。】【此时如果参考点不是叶子节点，要把兄弟的Q的一棵子树，给到被合并的元素X所在的那一个节点上】

————————————————

B+树

比价树的删除要easy一些。

1、首先删除的肯定是处于叶子节点。

2、这时候如果这个节点元素数不是很少，则直接结束。如果元素少于标准，则3或4

3、如果兄弟富裕，从兄弟借一个。具体操作为把父节点的一个关键字用兄弟两端的某个元素代替，然后把兄弟的一个元素移过来。

4、如果兄弟不富裕，则和兄弟合并，删除父节点的一个元素。

===》现在把参考点设为父节点。

此时父节点少了一个元素；且除了叶子节点，b+树与b树无异。

则现在直接把执行流跳转到b树的第2条。