数据结构与算法——第9章-查找表-B+树中删除关键字(9.10.3)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 概述

1
2
3
1.B+树中删除关键字情况
2.B+树中删除关键字步骤
3.总结

二 B+树中删除关键字情况

在 B+树中删除关键字时，有以下几种情况：

一、情况1

1
2
找到存储有该关键字所在的结点时，由于该结点中关键字个数大于⌈ M/2⌉ ，做删除操作不会破坏 B+树，则可以直接删除。
例如，在图 1 所示的 B+树中删除关键字 91，删除后的 B+树如图 5 所示：

二、情况2

1
2
当删除某结点中最大或者最小的关键字，就会涉及到更改其双亲结点一直到根结点中所有索引值的更改。
例如，在图 1 的 B+树中删除关键字 97，删除后的 B+树如图 6 所示：

三、情况3

1
2
3
4
5
当删除该关键字，导致当前结点中关键字个数小于⌈ M/2⌉ ，
若其兄弟结点中含有多余的关键字，可以从兄弟结点中借关键字完成删除操作。

例如，在图 1 的 B+树中删除关键字 51，由于其兄弟结点中含有 3 个关键字，
所以可以选择借一个关键字，同时修改双亲结点中的索引值，删除之后的 B+树如图 7 所示：

四、情况4

1
2
第 3 种情况中，如果其兄弟结点没有多余的关键字，则需要同其兄弟结点进行合并。
例如，在图 7 的 B+树种删除关键字 59，删除后的 B+树为:

五、情况5

1
2
3
当进行合并时，可能会产生因合并使其双亲结点破坏 B+树的结构，需要依照以上规律处理其双亲结点。
例如，在图 6 的 B+树中删除关键字 63，当删除后该结点中只剩关键字 72，且其兄弟结点中只有 2 个关键字，
无法实现借的操作，只能进行合并。但是合并后，合并后的效果图如图 9 所示：

六、结果

1
2
如图 9 所示，其双亲结点中只有一个关键字，而其兄弟结点中有 3 个关键字，
所以可以通过借的操作，来满足 B+树的性质，最终的 B+树如图 10所示：

三 B+树中删除关键字步骤

1
2
3
4
5
总之，在 B+树中做删除关键字的操作，采取如下的步骤：
1. 删除该关键字，如果不破坏 B+树本身的性质，直接完成操作；
2. 如果删除操作导致其该结点中最大（或最小）值改变，则应相应改动其父结点中的索引值；
3. 在删除关键字后，如果导致其结点中关键字个数不足，
有两种方法：一种是向兄弟结点去借，另外一种是同兄弟结点合并。（注意这两种方式有时需要更改其父结点中的索引值。）

四 总结

1
2
本节介绍了有关 B+树的查找、插入和删除操作，
由于其更多的是用于文件索引系统，所以没有介绍具体地代码实现，只需要了解实现过程即可。

五 参考

  • C语言中文网—B+树及基本操作