7.4.1.1 B 树的查找

教材导航 · 第7章

原书定位

印刷页P311起,对应PDF第323页。下文为目视整理的知识提要;完整内容见原书对照。

每到一个实际结点,先在结点内顺序或折半查关键字;相等成功,否则选对应区间指针继续,遇空外部结点失败。成功可以发生在任一实际层。

代价分为结点内的内存比较与跨结点的磁盘访问。若根和部分上层已缓存,实际 I/O 次数须扣除缓存命中的访问;不能直接把所有关键字比较次数当磁盘次数。

对应练习

7.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P311,PDF第323页

原书对照,原书P312,PDF第324页