知识卡片
节点大小决定B树分支度
B树节点通常按磁盘块取大小。
设 B 树最小度为 t,则一个内部节点最多约有 2t 个孩子。增大 t 会降低树高和 I/O 次数;但若节点内线性扫描,含 n 个键的树其 CPU 时间界为 O(t log_t n),而读取更大块的时间也可能随 t 增加。
因而“分支度并非越大越好”是同时计入CPU和设备代价后的模型权衡推论。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第18章 B树 · 查看原书依据
Large B-trees stored on disk drives often have branching factors between 50 and 2000, depending on the size of a key relative to the size of a block. A large branching factor dramatically reduces both the height of the tree and the number of disk accesses required to find any key.
参考来源
- 位置:《算法导论(第4版)》第18章《B树》(OEBPS/chapter018.xhtml,文本字符[5000,10000))。
- 结论依据:原文以键/块相对大小解释分支度和I/O;第18章搜索分析另给节点内线性扫描O(t)、总CPU O(t log_t n),习题18.2-7给块读取时间a+bt。末句为合并这些条件的权衡推论。
- 补充原文(同章文本字符[15000,20000)):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 ).
- 原始内容:Large B-trees stored on disk drives often have branching factors between 50 and 2000, depending on the size of a key relative to the size of a block. A large branching factor dramatically reduces both the height of the tree and the number of disk accesses required to find any key.