线性索引查找
索引:就是把一个关键字与它对应的i记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。
索引按照结构可以分为：线性索引、树形索引和多级索引。
线性索引是将索引项集合组织为线性结构，也称为索引表。包括稠密索引、分块索引、倒排索引。
1. 稠密索引
一个完美的引子：
我母亲年纪大了，记忆力不好，经常在家里找不到东西，于是她想了一个办法。她用一个小本子记录了家里所有小东西放置的位置，比如户口本放在右手床头柜下面抽屉中，针线放在电视柜中间的抽屉中，钞票放在衣柜……总之，她老人家把这些小物品的放置位置都记录在了小本子上，并且每隔一段时间还按照本子整理一遍家中的物品，用完都放回原处，这样她就几乎再没有找不到东西。从这件事情就可以看出，家中的物品尽管是无序的，但是如果有一个小本子记录，寻找起来也是非常容易的，而这小本子就是索引。
稠密索引是指在线性表中，将数据集中的每个记录对应一个索引项。
对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列。通过对索引项的查找，就可以找到丢应的结果地址，但是如果数据集非常大，比如说上亿，那也就意味着索引同样的数据规模，可能就需要反复查询内存和硬盘，性能可能反而下降了。
2. 分块索引
引子：图书馆如何藏书
分块有序需要满足两个条件：块内无序（有序更好，代价比较大）、块间有序
对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。
最大关键码、块长和块首指针很容易理解。
平均查找长度ASL 为 在索引表中的平均查找长度 + 在记录（数据集）中的平均查找长度。
假设 有m块，每块*有t条记录，显然n = m * t。
故而 ASL = (m+1)/2 + (t+1)/2 = (n/t + t)/2 + 1. 上式的最小值，即n/t = t，n = t^2，则最小的ASL = n^(1/2) + 1;
课件，分块索引的效率比顺序查找o(n) 高了很多，总的来说，分块索引在兼顾了对细分块不需要有序的情况下，大大增加了整体查找的速度，所以普遍被用于数据库查找等技术的应用当中。
3. 倒排索引
引子：搜索引擎如何进行搜索，能够在非常快的速度之下显示搜索的最优匹配内容。
索引项的结构是次关键字码和记录号表，其中记录号表存储具有相同关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字），这样的索引方法就是倒排索引。
倒排索引源于实际应用中需要根据属性（或字段、次关键码）的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性来确定记录的位置，因而称为倒排索引。
倒排索引的优点显然是查找记录非常快，基本等于生成索引表后，查找时都不用去读取记录，即可以得到结果。但是它的缺点是这个记录号不定长，可多可少。
ps. 现实中的搜索技术要复杂得多，涉及到太多内容。