知识卡片
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 比较,须按瓶颈权衡。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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 ).