3动在查传表c I B 先查找插入的位置,必然在最低一层结点有序插入 但结点的插入可能会导致结点被撑破,需要分两种情况处理: 1)如果插入关键字后叶子结点中的关键字数量=m-1,则插入操 作完毕 (2)如果插入后,叶子结点中的关键字数量是m,则需要将叶子结点 分为2,成为2个听子,中间的关键字携带着新叶子结点的指针上 升到双亲结点中。这就转化为在双亲结点中插入一个关键字的问题3、动态查找表(cont’d) (1)B树(B-树) III. B树的插入：先查找插入的位置，必然在最低一层结点有序插入 ！但结点的插入可能会导致结点被撑破，需要分两种情况处理： (1)如果插入关键字后,叶子结点中的关键字数量<=m-1，则插入操 作完毕。 (2)如果插入后，叶子结点中的关键字数量是m，则需要将叶子结点 一分为2，成为2个叶子，中间的关键字携带着新叶子结点的指针上 升到双亲结点中。这就转化为在双亲结点中插入一个关键字的问题 了。 这个问题的处理仍需要按照(1)(2)两种情况处理，一直到增加关键字 的结点未满或者新生成根结点为止