知识卡片
多路树以扇出减少块访问
二叉节点较小时,访问一条深路径可能需要很多块读取。B树类结构在节点内存放多个有序键与分支,使一次页读取获得更多路由信息,以更大扇出降低树高。
节点容量取决于页大小、键和链接大小及管理字段。空余容量会占空间,但也支持更新;性能还取决于缓存、键长度与负载,不是所有B树操作都必然胜过二叉树。图7-31只是分区示意,不给出完整分裂合并算法,也不规定每次必须按二的幂分区。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 7.13 数据库
原书出处 · 1 处
- 7.13 数据库 · 查看原书依据
B树的节点比二叉树节点有更多的分支(子节点)。分支数由磁盘块决定,如图7-31所示。 图7-31 B树 可以看到,内部节点是平衡的,因此搜索时间可预测。图7-31中有一些未使用的子链接占用空间。当子链接用完时,可以通过改变节点覆盖的范围轻松地重新平衡树。例如,
参考来源
- 位置:《计算机系统解密》7.13 数据库(来源项目book-sources,源文件:extracted/计算机系统解密/_epub-src/text/part0080.html)
- 结论依据:本项全部正文与图表实际读取,区分作者示例、推导与实现边界;纠错另有明确说明。
- 原始内容:B树的节点比二叉树节点有更多的分支(子节点)。分支数由磁盘块决定,如图7-31所示。 图7-31 B树 可以看到,内部节点是平衡的,因此搜索时间可预测。图7-31中有一些未使用的子链接占用空间。当子链接用完时,可以通过改变节点覆盖的范围轻松地重新平衡树。例如,