知识卡片

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

B树查找先定位节点内区间

理解等级:中级

B 树查找先在当前节点找到第一个不小于目标的键;相等就返回节点与槽位,不等且是叶子就失败,否则读入对应孩子继续。

搜索只走根到叶的一条路径,节点内比较与块访问应分别计成本。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第18章 B树 · 查看原书依据

      Using a linear-search procedure, lines 1–3 of B-TREE-SEARCH find the smallest index i such that k ≤ x.keyi, or else they set i to x.n + 1.

    参考来源

    - 位置:《算法导论(第4版)》第18章《B树》(OEBPS/chapter018.xhtml,文本字符[15000,20000))。 - 结论依据:原文逐步说明节点内定位、成功和失败出口以及对子节点的单路径递归。 - 原始内容:Using a linear-search procedure, lines 1–3 of B-T REE -S EARCH find the smallest index i such that k ≤ x . key i , or else they set i to x . n + 1.