五、分块检索

分块检索又称为索引检索，性能介于顺序检索和二分检索之间。它把线性表分成若干块，在每一块中结点的存放是任意的，但是块与块之间必须保持关键码值递增（或者递减）的顺序。把（每块中最大的关键码值，块的起始位置）这样的二元组构成一个索引表。由于表是分块有序的，所以索引表是一个递增（递减）有序表。检索时，首先用待检索的关键码在索引中查找，确定如果满足条件的结点存在时它应在哪一块中，在索引中检索的方法既可以采用二分法、也可以采用顺序检索；然后再到相应的块中顺序检索，便可以得到检索的结果。
    分块检索的主要代价是增加一个辅助索引数组的存储空间和将初始线性表分块排序的运算。另外当大量的插入删除运算使块中结点数分布很不均匀时，检索速度将会下降。
    分块检索的优点是：在线性表中插入或删除一个结点时，只要找到该结点应属于的块，然后在块内进行插入和删除运算。由于块内结点的存放是任意的，所以插入或删除比较容易，不需要移动大量的结点。插入可以在块尾进行；如果待删除的记录不是块中最后一个记录时，可以将本块内最后一个记录移入被删除记录的位置。