7.4.1.1 B 树的查找
原书定位
印刷页P311起,对应PDF第323页。下文为目视整理的知识提要;完整内容见原书对照。
每到一个实际结点,先在结点内顺序或折半查关键字;相等成功,否则选对应区间指针继续,遇空外部结点失败。成功可以发生在任一实际层。
代价分为结点内的内存比较与跨结点的磁盘访问。若根和部分上层已缓存,实际 I/O 次数须扣除缓存命中的访问;不能直接把所有关键字比较次数当磁盘次数。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P311起,对应PDF第323页。下文为目视整理的知识提要;完整内容见原书对照。
每到一个实际结点,先在结点内顺序或折半查关键字;相等成功,否则选对应区间指针继续,遇空外部结点失败。成功可以发生在任一实际层。
代价分为结点内的内存比较与跨结点的磁盘访问。若根和部分上层已缓存,实际 I/O 次数须扣除缓存命中的访问;不能直接把所有关键字比较次数当磁盘次数。

