分块查找

二分查找表使分块有序的线性表和索引表（抽取各块中的最大关键字及其起始位置构成索引表

）组成，由于表是分块有序的，所以索引表是一个递增有序表，因此采用顺序或二分查找索引表，以确定待查结点在哪一块，由于块内无序，只能用顺序查找。

设表共n个结点，分b块，s=n/b

(分块查找索引表)平均查找长度=Log2（n/s+1）+s/2

(顺序查找索引表)平均查找长度=(S2+2S+n)/(2S)

注：分块查找的优点是在表中插入或删除一个记录时，只要找到该记录所属块，就在该块中进行插入或删除运算（因块内无序，所以不需要大量移动记录）。它主要代价是增加一个辅助数组的存储控件和将初始表分块排序的运算。

它的性能介于顺序查找和二分查找之间。