本文共 486 字，大约阅读时间需要 1 分钟。

转自：

4.索引查找　　

　　关于索引，我们很容易地联想到数据库中的索引，建立了索引，可以大大提高数据库的查询速度。

　　索引查找又称为分块查找，是一种介于顺序查找和二分查找之间的一种查找方法。

　　分块查找的基本思想是：

　　首先查找索引表，可用二分查找或顺序查找（因为块间是有序的，可以用二分查找），

　　然后根据块首指针找到相应的块，并在确定的块中进行顺序查找。

　　满足两个条件：

　　（1）块内无序，每一块内的记录不要求有序。

　　（2）块间有序，如第二块记录的所有关键字要大于第一块，第三块的要大于第二块

　　分块查找的时间复杂度为O(√n)。

　　在实现索引查找算法前需要弄清楚以下三个术语。

　　（1）主表。即要查找的对象。

　　（2）索引项。一般我们会将主表分成几个子表，每个子表建立一个索引，这个索引就叫索引项。

　　（3）索引表。即索引项的集合。

　　同时，索引项包括以下三点。

　　（1）最大关键码，就是存储的每一块中的最大关键字（那一块中数字最大的那个）

　　（2）块长，就是每一块的元素个数

　　（3）块首指针，就是每一块第一个元素的指针

转载地址：http://ulgsi.baihongyu.com/