2.B-树的插入（1）利用前述的查找过程找到关键字k的插入结点p（注意m阶B-树的插入结点一定是某个叶子结点）：（2）判断结点p是否还有空位置，即其关键字个数n是否满足n<Max(Max=m-1) :①若n<Max成立，说明结点p有空位置，直接把关键字k有序插入到结点p中（插入关键字k后结点p的所有关键字仍有序）。6/28
2. B-树的插入 （1）利用前述的查找过程找到关键字k的插入结点p（注意m阶B-树的插 入结点一定是某个叶子结点）。 （2）判断结点p是否还有空位置，即其关键字个数n是否满足n<Max （Max=m-1）： ① 若n<Max成立，说明结点p有空位置，直接把关键字k有序插入到结 点p中（插入关键字k后结点p的所有关键字仍有序）。 6/28
若n=Max，说明结点p没有空位置，需要把结点p分裂成两个。分裂R.Rks+1k1ks-1R..中间关键字如果此时双亲结点的关键字个数也超过Max，则要再分裂，再往上插，直至这个过程传递到根结点为止。如果根结点也需要分裂，则整个m阶B-树增高一层。7/28
② 若n=Max，说明结点p没有空位置，需要把结点p分裂成两个。 p k1 . ks . kn . 中间关键字 k1 . ks-1 . ks . ks+1 . kn 分裂 如果此时双亲结点的关键字个数也超过Max，则要再分裂，再往 上插，直至这个过程传递到根结点为止。如果根结点也需要分裂，则 整个m阶B-树增高一层。 7/28
【例9.16】关键字序列为（1，2，6，7，11，4，8，13，10，5，17,9，16，20，3，12，14，18，19，15），创建一棵5阶B-树。解：这里m=5，结点中最大关键字个数Max=m-1=4。112.672,6,78/28
【例9.16】关键字序列为（1，2，6，7，11，4，8，13，10，5，17， 9，16，20，3，12，14，18，19，15），创建一棵5阶B-树。 解：这里m=5，结点中最大关键字个数Max=m-1=4。 1 1 2,6,7 1 2 6 7 8/28
112671117.111 24,8,1312478 11 136.101011.13124124787810111319/28
11 1 2 6 7 11 1 2 7 11 6 4,8,13 1 2 4 7 8 11 13 6 10 1 2 4 7 8 10 11 13 6 1 2 4 6 10 7 8 11 13 9/28
6.105,17,9,161245891113161776.10207891245111316172010166院11.137.8917 20124510/28
5,17,9,16 1 2 4 5 6 10 7 8 9 11 13 16 17 20 1 2 4 5 6 10 7 8 9 11 13 16 17 20 1 2 4 5 6 10 16 7 8 9 11 13 17 20 10/28