7.4.1.3 B 树的插入
原书定位
印刷页P312起,对应PDF第324页。下文为目视整理的知识提要;完整内容见原书对照。
先定位到终端实际结点,在结点内按序插入。若关键字数增为 ,按约定中间位置分裂,将中间关键字提升到父结点,两侧成为两个结点并分配孩子指针。
父结点也可能溢出,沿路径向上继续;仅根分裂并新建根时树高增加 1。插入次序及分裂时中间元素的取法会影响结果,手算需沿用题目或教材约定。

B 树分裂与中间关键字上移,原书P313。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P312起,对应PDF第324页。下文为目视整理的知识提要;完整内容见原书对照。
先定位到终端实际结点,在结点内按序插入。若关键字数增为 ,按约定中间位置分裂,将中间关键字提升到父结点,两侧成为两个结点并分配孩子指针。
父结点也可能溢出,沿路径向上继续;仅根分裂并新建根时树高增加 1。插入次序及分裂时中间元素的取法会影响结果,手算需沿用题目或教材约定。

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

