知识卡片

普通读书笔记卡 · 3633.a.8.b.1

下降前拆满节点避免回溯

理解等级:高级

B 树插入在从根向叶下降时,遇到满孩子就先拆分,确保递归进入的孩子不满。

这样父节点有空间接收提升的中位键,插入只需单次向下扫描;若先走到底再拆,可能沿路径向上连锁分裂。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第18章 B树 · 查看原书依据

      To avoid having to go back up the tree, just split every full node you encounter as you go down the tree. In this way, whenever you need to split a full node, you are assured that its parent is not full.

    参考来源

    - 位置:《算法导论(第4版)》第18章《B树》(OEBPS/chapter018.xhtml,文本字符[15000,20000))。 - 结论依据:原文对比回溯分裂与下降途中预拆满节点,并给出单向扫描理由。 - 原始内容:To avoid having to go back up the tree, just split every full node you encounter as you go down the tree. In this way, whenever you need to split a full node, you are assured that its parent is not full.