数据结构之线性索引查找
数据结构之线性索引查找
在数据结构的查找中，有顺序查找（时间复杂度O（n））、有序查找中的三种优化查找：
- 折半查找，时间复杂度O（logn）；
- 插值查找，时间复杂度O（logn），针对均匀数据时比折半要优异；
- 斐波那契查找，时间复杂度O（logn），只需要加法计算；
上述查找针对海量数据时，耗时非常大，故有了索引查找。
线性索引包括：稠密索引、分块索引、倒排索引。
稠密索引
稠密索引即数据集中每一个记录都对应一个索引。如下图所示：
对于稠密索引来说，索引的关键字一定是按照有序排列的。
缺点：索引量与数据量是同样规模的，反复读取索引耗时大。
分块索引
即对数据集进行分块，每个块之间是有序的，对每个块建立索引项，从而减少索引的数量。
分块满足的两个条件：
- 块内无序；
- 块间有序；
如下图所示：
分块索引的平均查找长度：