索引查找：

　　索引查找（index search）又称分级查找。

　　比如在查字典的时候，首先在部首表中查到对应检字表中的页码，再在检字表中根据字的笔画数查到对应正文中的页码，最后在此页码中找到待查的汉字。其中，整个字典就是索引查找的对象，字典正文称为主表，部首表、检字表都是为方便查找主表而建立的索引，所以被称为索引表。

　　检字表以主表作为查找对象，所以称检字表为一级索引，称部首表为二级索引，即对一级索引的索引。

　　在计算机中，索引查找是在集合或线性表的索引存储结构的基础上进行的。索引存储的基本思想是：首先把主表按照一定的关系划分成若干个子表，为每个子表建立一个索引项，由所有的这些索引项构成主表的一个索引表，然后，可以采用顺序或者链接的方式来存储索引表和每个子表。

　　索引表中的每个索引项通常包含三个域（至少包含前两个域）：一是索引值域（index），用来存储标识对应子表的索引值，相当于记录的关键字；二是子表的开始位置域（start），用来存储对应子表的第一个元素的存储位置；三是子表长度域（length），用来存储对应子表的元素个数。

　　在索引存储中，若索引表中的每个索引项对应多条记录，则称为稀疏索引；若每个索引项唯一对应一条记录，则称为稠密索引。

　　索引查找是在索引表和主表上进行的查找。

　　首先根据给定的索引值K1，在索引表上查找出索引值等于K1的索引项，以确定对应子表在主表中的开始位置和长度，然后再根据给定的关键字K2，在对应的子表中查找出关键字等于K2的元素。

　　索引查找的比较次数等于算法中查找索引表的比较次数和查找相应子表的比较次数之和。（下面的讨论只考虑包含一级索引的情况）。

　　假定索引表长度为m，相应子表长度为s，则索引查找的平均查找长度为：

　　ASL =(1+m)/2+ (1+s)/2 = 1+ (m + s)/2

　　因为所有子表的长度之和等于主表长度n，所以若每个子表长度相同，即s=n/m，则平均查找长度为ASL =1+ (m + n/m)/2 。

　　由数学知识，当m=n/m时，平均长度最小，即 ASL= 1+n^½。

　　可见，索引查找的速度快于顺序查找，但低于二分查找。在主表被分为n^½ 个子表的前提下，其时间复杂度为O(n^½) 。

　　分块查找（blocking search）属于索引查找。它要求主表中每个子表（子表又称为块）之间是有序的（递增或递减）。

　　比如递增，即前块中的最大关键字必须小于后块中的最小关键字。但每个块中的元素排列次序可以是任意的。

　　它还要求索引表中的每个索引项的索引值域用来存储对应块中的最大关键字。

　　索引表是有序的，主表中的关键字域和索引表中的索引值域具有相同的数据类型，即为关键字所属的类型。

　　由于索引表是有序的，所以在索引表上既可采用顺序查找，又可采用二分查找，而每个块中的记录排列是任意的，所以在块内只能采用顺序查找。