7.4.1.3 B 树的插入

教材导航 · 第7章

原书定位

印刷页P312起,对应PDF第324页。下文为目视整理的知识提要;完整内容见原书对照。

先定位到终端实际结点,在结点内按序插入。若关键字数增为 mm,按约定中间位置分裂,将中间关键字提升到父结点,两侧成为两个结点并分配孩子指针。

父结点也可能溢出,沿路径向上继续;仅根分裂并新建根时树高增加 1。插入次序及分裂时中间元素的取法会影响结果,手算需沿用题目或教材约定。

B 树分裂与中间关键字上移

B 树分裂与中间关键字上移,原书P313。

对应练习

7.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P312,PDF第324页

原书对照,原书P313,PDF第325页