7.2.3 分块查找
原书定位
印刷页P273起,对应PDF第285页。下文为目视整理的知识提要;完整内容见原书对照。
数据划成若干块,块内可无序,块间有序;索引表存各块最大关键字与起始地址。先查索引确定目标块,再顺序查块内记录。
总 ASL 为索引查找与块内查找两部分之和。若 , 块、每块 条,索引和块内都顺序查,等概率成功时:
此模型在 时较小;若索引用折半查找,代价模型和最佳块长要重新分析。

分块查找索引表示,原书P274。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P273起,对应PDF第285页。下文为目视整理的知识提要;完整内容见原书对照。
数据划成若干块,块内可无序,块间有序;索引表存各块最大关键字与起始地址。先查索引确定目标块,再顺序查块内记录。
总 ASL 为索引查找与块内查找两部分之和。若 , 块、每块 条,索引和块内都顺序查,等概率成功时:
此模型在 时较小;若索引用折半查找,代价模型和最佳块长要重新分析。

分块查找索引表示,原书P274。

