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

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

一 概述

1
2
1.B+树插入关键字注意事项
2.B+树插入关键字图示

二 B+树插入关键字注意事项

1
2
3
4
在 B+树中插入关键字时，需要注意以下几点：
1.插入的操作全部都在叶子结点上进行，且不能破坏关键字自小而大的顺序；
2.由于 B+树中各结点中存储的关键字的个数有明确的范围，
做插入操作可能会出现结点中关键字个数超过阶数的情况，此时需要将该结点进行“分裂”；

三 B+树插入关键字图示

B+树中做插入关键字的操作，有以下 3 种情况：

一、情况1

1
2
若被插入关键字所在的结点，其含有关键字数目小于阶数 M，则直接插入结束；
例如，在图 1 中插入关键字 13，其结果如图 2 所示：

二、情况2

1
2
3
4
若被插入关键字所在的结点，其含有关键字数目等于阶数 M，则需要将该结点分裂为两个结点，
一个结点包含⌊ M/2⌋ ，另一个结点包含⌈ M/2⌉ 。
同时，将⌈ M/2⌉ 的关键字上移至其双亲结点。假设其双亲结点中包含的关键字个数小于 M，则插入操作完成。
例如，在图 1 的基础上插入关键字 95，其插入后的 B+树如图 3 所示：

三、情况3

1
2
在第 2 情况中，如果上移操作导致其双亲结点中关键字个数大于 M，则应继续分裂其双亲结点。
例如，在图 1 的 B+树中插入关键字 40，则插入后的 B+树如图 4 所示：

四 注意

1
2
3
4
如果插入的关键字比当前结点中的最大值还大，破坏了 B+树中从根结点到当前结点的所有索引值，
此时需要及时修正后，再做其他操作。
例如，在图 1 的 B+树种插入关键字 100，由于其值比 97 还大，
插入之后，从根结点到该结点经过的所有结点中的所有值都要由 97 改为 100。改完之后再做分裂操作。

五 参考

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