知识卡片

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

拆节点的IO次数为常数

理解等级:中级

在最小度为 t 的 B 树中,满节点含 2t−1 个键。拆分一个满孩子要在父节点挪出键与孩子指针的位置,把中位键提升到父节点,并写回旧孩子、新孩子和父节点。

一次拆分的 CPU 工作量是 Θ(t),磁盘块操作为 O(1);两种成本不能混为同一数量级。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      The CPU time used by B-TREE-SPLIT-CHILD is Θ(t), due to the for loops in lines 5–6 and 8–9. (The for loops in lines 11–12 and 14–15 also run for O(t) iterations.) The procedure performs O(1) disk operations.

    参考来源

    - 位置:《算法导论(第4版)》第18章《B树》(OEBPS/chapter018.xhtml,文本字符[20000,25000))。 - 结论依据:原文伪代码写回三个节点,紧随其后分别给出CPU与磁盘复杂度。 - 原始内容:The CPU time used by B-T REE -S PLIT -C HILD is Θ( t ), due to the for loops in lines 5–6 and 8–9. (The for loops in lines 11–12 and 14–15 also run for O ( t ) iterations.) The procedure performs O (1) disk operations.