B-树的插入
⚫ B-树是从空树起,逐个插入关键码而生成的。
⚫ 在B-树,每个非失误结点的关键码个数都在[ m/2 -1, m-1]
之间。
⚫ 插入在某个叶结点开始。如果在关键码插入后结点中的关键
码个数超出了上界 m-1,则结点需要“分裂”,否则可以直
接插入。
⚫ 实现结点“分裂”的原则是:
⚫ 设结点 A 中已经有 m-1 个关键码,当再插入一个关键码后
结点中的状态为( m, A
0
, K
1
, A
1
, K
2
, A
2
, ……, K
m
, A
m
)
其中 K
i
< K
i+1
, 1 i < m