SimpleDB Lab3 DELETE
Lab3 DELETE
20201118
主要实现B+树的删除操作。
B+树中删除关键字
在 B+树中删除关键字时，有以下几种情况：
1、 找到存储有该关键字所在的结点时，由于该结点中关键字个数大于⌈M/2⌉，做删除操作不会破坏 B+树，则可以直接删除。
例如，在图 1 所示的 B+树中删除关键字 91，删除后的 B+树如图 5 所示：
图 5 删除91的B+树
2、 当删除某结点中最大或者最小的关键字，就会涉及到更改其双亲结点一直到根结点中所有索引值的更改。
例如，在图 1的 B+树中删除关键字 97，删除后的 B+树如图 6 所示：
图 6 删除97后的B+树
3、 当删除该关键字，导致当前结点中关键字个数小于⌈M/2⌉，若其兄弟结点中含有多余的关键字，可以从兄弟结点中借关键字完成删除操作。
例如，在图 1 的 B+树中删除关键字 51，由于其兄弟结点中含有 3 个关键字，所以可以选择借一个关键字，同时修改双亲结点中的索引值，删除之后的 B+树如图 7 所示：
图 7 删除关键字51后的B+树
4、 第 3 种情况中，如果其兄弟结点没有多余的关键字，则需要同其兄弟结点进行合并。
例如，在图 7 的 B+树种删除关键字 59，删除后的 B+树为:
图 8 删除关键字59后的B+树
5、 当进行合并时，可能会产生因合并使其双亲结点破坏 B+树的结构，需要依照以上规律处理其双亲结点。
例如，在图 6 的 B+树中删除关键字 63，当删除后该结点中只剩关键字 72，且其兄弟结点中只有 2 个关键字，无法实现借的操作，只能进行合并。但是合并后，合并后的效果图如图 9 所示：
图 9 合并操作后的效果图
如图 9 所示，其双亲结点中只有一个关键字，而其兄弟结点中有 3 个关键字，所以可以通过借的操作，来满足 B+树的性质，最终的 B+树如图 10 所示：
图 10 删除63后的B+树
总之，在 B+树中做删除关键字的操作，采取如下的步骤：
- 删除该关键字，如果不破坏 B+树本身的性质，直接完成操作；
- 如果删除操作导致其该结点中最大（或最小）值改变，则应相应改动其父结点中的索引值；
- 在删除关键字后，如果导致其结点中关键字个数不足，有两种方法：一种是向兄弟结点去借，另外一种是同兄弟结点合并。（注意这两种方式有时需要更改其父结点中的索引值。
摘自：http://data.biancheng.net/view/61.html
周末再写0.0