知识卡片
B树查找先定位节点内区间
B 树查找先在当前节点找到第一个不小于目标的键;相等就返回节点与槽位,不等且是叶子就失败,否则读入对应孩子继续。
搜索只走根到叶的一条路径,节点内比较与块访问应分别计成本。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.