知识卡片
B树多键分割查找范围
B 树内部节点存 n 个有序键时有 n+1 个孩子。
节点键把键空间划成 n+1 段,每个孩子负责一段;查找先在节点内定位区间,再沿对应孩子下降,所以一次节点访问能完成多路分支选择。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第18章 B树 · 查看原书依据
If an internal B-tree node x contains x.n keys, then x has x.n + 1 children. The keys in node x serve as dividing points separating the range of keys handled by x into x.n + 1 subranges, each handled by one child of x. A search for a key in a B-tree makes an (x.n + 1)-way decision based on comparisons with the x.n keys stored at node x.
参考来源
- 位置:《算法导论(第4版)》第18章《B树》(OEBPS/chapter018.xhtml,文本字符[0,5000))。
- 结论依据:原文给出节点键数、孩子数和按键分隔子范围的关系。
- 原始内容:If an internal B-tree node x contains x . n keys, then x has x . n + 1 children. The keys in node x serve as dividing points separating the range of keys handled by x into x . n + 1 subranges, each handled by one child of x . A search for a key in a B-tree makes an ( x . n + 1)-way decision based on comparisons with the x . n keys stored at node x .