知识卡片

普通读书笔记卡 · 3633.a.3.a

B树查找区分IO与CPU

理解等级:高级

设 B 树含 n 个键、最小度为 t、高度为 h=O(log_t n)。以节点内线性扫描实现搜索时,查找沿单条根叶路径访问 O(h) 个磁盘块;每节点至多约 2t 个键,因此每层比较 O(t) 次,CPU 总成本为 O(t log_t n)。

减少 I/O 的宽节点未必减少 CPU 比较,须按瓶颈权衡。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      The B-TREE-SEARCH procedure therefore accesses O(h) = O(logt n) disk blocks, where h is the height of the B-tree and n is the number of keys in the B-tree. Since x.n < 2t, the while loop of lines 2–3 takes O(t) time within each node, and the total CPU time is O(th) = O(t logtn).

    参考来源

    - 位置:《算法导论(第4版)》第18章《B树》(OEBPS/chapter018.xhtml,文本字符[15000,20000))。 - 结论依据:原文分别给出块访问与节点内线性扫描的复杂度。 - 原始内容:The B-T REE -S EARCH procedure therefore accesses O ( h ) = O (log t n ) disk blocks, where h is the height of the B-tree and n is the number of keys in the B-tree. Since x . n < 2 t , the while loop of lines 2–3 takes O ( t ) time within each node, and the total CPU time is O ( th ) = O ( t log t n ).