查找算法 关于索引

大话数据结构中介绍了三个索引 稠密索引 分块索引 倒排索引

1.稠密索引

稠密索引指的是在线性索引中，将数据集中的每一个记录都对应一个索引项。对于索引项来说一定是有序的排列，索引项的有序意味着可以使用顺序查找算法，比如说前面学过的二分查找，发布纳妾查找（将一组数补齐成fn然后分fn-1和fn-2，然后对应的还能继续分），插入查找（适用于分布平均），这三种查找算法的思想应该都是类似的降低查找规模，额呵呵 说多了回到稠密索引。。这就是稠密索引的优点可以根据对应有序的索引项来查找对应的记录，但是同时也意味着索引需要相同的数据集长度规模

2.分块索引

分块有序就是把数据集合的记录分成了若干份，并且这些块满足两个条件

• 1 快内无序，即每一快内的记录不要求有序。（有序更好，但是要付出大量的时间和空间代价）
• 2 快间有序，譬如要求第二个块的所有记录均要大于第一个块所有记录的关键字。。快间有序能够提高查找效率，这个分块索引表中的每一行记录对应着最大关键码，快长 还有指针指向块 那么就可以根据这个分块索引表查找

3.倒排索引

倒排索引的概念很简单：就是将文件中的单词作为关键字，然后建立单词与文件的映射关系。当然，也可以添加文件中单词出现的频数等信息，倒排索引是搜索引擎中的一个基本概念，几乎所有的搜索引擎都会使用到倒排索引。