知识卡片
多分支搜索树减少访问层数
数据库可能同时需要按键查找、按序访问和动态变更,搜索树的组织方式可支持这些需求。本章以B树为例说明较大分支因子使每层容纳更多范围,设计目标之一是减少访问记录时的磁盘I/O。
这里只给用途和设计方向,尚未定义节点布局、分裂/合并或精确I/O界。不能由“分支多”直接断言任何配置都是最优,后续要结合块大小和维护规则理解。
168较大分支因子可减少需穿过的层数,对慢辅助存储的I/O更重要;不是无条件保证内存中最快,仍需节点搜索与维护成本。
169 B树/B+/B*共同背景是平衡、多分支与按辅助存储块组织节点,以降低路径层数和I/O;本段未给三者具体分裂/合并差异,不虚构实现或当作同一种树。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 多分支搜索树减少访问层数
- · 问与答
- · 相关主题
原书出处 · 3 处
- · 查看原书依据
磁盘I/O的开销将降低到最小。 表达式处理(本章会讲到) 这个任务是编译器和手持式计算器经常做的。一种处理算数表达式的自然方法是通过表达式树,这是一种将表达式的操作数和操作符按照层次结构组织起来的一棵二叉树。 人工智能 人工智能可以用来帮助解决许多历来对计算机来说很难解决的问题。比如国际象棋这种逻辑
- · 查看原书依据
辅助存储空间(比如闪存)内执行查找操作时,分支因子较大的树在性能上会有明显的区别。在这种情况下,一般会采用某种类型的B树(见本章结尾部分的相关主题)。 问:在一棵二叉搜索树中,某结点x的后继结点是指x之后的下一个最大结点。例如,在一棵二叉搜索树中包含键值24、39、41、55、87、92,于是41的
- · 查看原书依据
块大小保持一致。所有类型的B树都是平衡的,且一般都有较大的分支因子。这使得树的高度较小,于是为了得到某条记录必须遍历的层级数减少了,从而减少了I/O操作带来的开销。
参考来源
- 位置:《算法精解:C语言描述》第9章《第9章 树》(spine1286;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1253.html;u144-ch09-003)。
- 结论依据:144数据库系统应用段完整实读,保留B树较大分支因子与磁盘访问关系,不虚构数据页字段或实现参数。
- 原始内容:磁盘I/O的开销将降低到最小。 表达式处理(本章会讲到) 这个任务是编译器和手持式计算器经常做的。一种处理算数表达式的自然方法是通过表达式树,这是一种将表达式的操作数和操作符按照层次结构组织起来的一棵二叉树。 人工智能 人工智能可以用来帮助解决许多历来对计算机来说很难解决的问题。比如国际象棋这种逻辑
- 位置:《算法精解:C语言描述》第9章《问与答》(spine1306;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1273.html;u168-ch09-003)。
- 结论依据:168较大分支因子可减少需穿过的层数,对慢辅助存储的I/O更重要;不是无条件保证内存中最快,仍需节点搜索与维护成本。
- 原始内容:辅助存储空间(比如闪存)内执行查找操作时,分支因子较大的树在性能上会有明显的区别。在这种情况下,一般会采用某种类型的B树(见本章结尾部分的相关主题)。 问:在一棵二叉搜索树中,某结点x的后继结点是指x之后的下一个最大结点。例如,在一棵二叉搜索树中包含键值24、39、41、55、87、92,于是41的
- 位置:《算法精解:C语言描述》第9章《相关主题》(spine1307;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1274.html;u169-ch09-003)。
- 结论依据:169 B树/B+/B*共同背景是平衡、多分支与按辅助存储块组织节点,以降低路径层数和I/O;本段未给三者具体分裂/合并差异,不虚构实现或当作同一种树。
- 原始内容:块大小保持一致。所有类型的B树都是平衡的,且一般都有较大的分支因子。这使得树的高度较小,于是为了得到某条记录必须遍历的层级数减少了,从而减少了I/O操作带来的开销。