|
|
|
|
|
|
|
|
|
|
|
索引顺序查找又称分块查找，是对顺序查找方法的一种改进。
|
|
|
|
在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的，即后一块中所有记录的关键字均大于前一个块中最大的关键字。此外，还建立了一个“索引表”，索引表按关键字有序，如下图所示。
|
|
|
|
|
|
|
|
因此，查找过程分为两步：第一步在索引表中确定待查记录所在的块；第二步在块内顺序查找。
|
|
|
|
由于分块查找实际上是两次查找的过程，因此整个分块查找的平均查找长度应该是两次查找的平均查找长度（块内查找与索引查找）之和，所以分块查找的平均查找长度为ASLbs=Lb+Lw，其中Lb为查找索引表的平均查找长度，Lw为块内查找时的平均查找长度。
|
|
|
进行分块查找时可将长度为n的表均匀地分成b块，每块含有s个记录，即 。在等概率的情况下，块内查找的概率为 ，每块的查找概率为 ，若用顺序查找方法确定元素所在的块，则分块查找的平均查找长度为：
|
|
|
|
|
可见，其平均查找长度在这种条件下不仅与表长n有关，而且和每一块中的记录数s有关。可以证明，当s取 时，ASLbs取最小值 ，这时的查找效率较顺序查找要好得多，但远不及折半查找。
|
|
|
