← 返回起始笔记位置

知识卡片

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

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 .