返回主题:存储常用数据结构

知识卡片

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

节点大小决定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.