索引查找
转自：http://www.cnblogs.com/GumpYan/p/5754661.html
4.索引查找
关于索引，我们很容易地联想到数据库中的索引，建立了索引，可以大大提高数据库的查询速度。
索引查找又称为分块查找，是一种介于顺序查找和二分查找之间的一种查找方法。
分块查找的基本思想是：
首先查找索引表，可用二分查找或顺序查找（因为块间是有序的，可以用二分查找），
然后根据块首指针找到相应的块，并在确定的块中进行顺序查找。
满足两个条件：
（1）块内无序，每一块内的记录不要求有序。
（2）块间有序，如第二块记录的所有关键字要大于第一块，第三块的要大于第二块
分块查找的时间复杂度为O(√n)。
在实现索引查找算法前需要弄清楚以下三个术语。
（1）主表。即要查找的对象。
（2）索引项。一般我们会将主表分成几个子表，每个子表建立一个索引，这个索引就叫索引项。
（3）索引表。即索引项的集合。
同时，索引项包括以下三点。
（1）最大关键码，就是存储的每一块中的最大关键字（那一块中数字最大的那个）
（2）块长，就是每一块的元素个数
（3）块首指针，就是每一块第一个元素的指针