针对场景：

博客网站论坛的帖子回复、服务器日志记录

数据量大，每条记录无法做到有序排列记录

解决方法：

索引---把关键字和它对应的记录相关联的过程

索引分类：线性索引、树形索引、多级索引

线性索引：将索引项集合组织为线性结构---索引表

线性索引包括：稠密索引、分块索引、倒排索引

稠密索引

结构：

索引项---对应---记录

索引项是有序的、记录数据表可以是无序的。

                         稠密 索引记录的结构图

查找方式：

索引项使用折半/二分法、插值查找、斐波那契查找

记录数据表--顺序查找

缺点：

数据集很大，则索引项很大，对内存有限的计算机，反复访问磁盘使得查找性能降低

生活示例：

小本子记录各物品的放置位置

分块索引

结构：

对数据集分为若干块，使得块满足：

块内无序：快内的记录不要求有序

块间有序--要求第二块所有记录的关键字均大于第一块记录的关键字

索引项---对应--每块

索引项的的结构包括3项：最大关键码、块内记录的个数、指向块首数据元素的指针

                         分块索引记录的结构图

查找方式：

块间--使用折半/二分法、插值查找、斐波那契查找

块内--使用顺序查找

应用示例：

图书馆书本的查找

普遍应用于数据库表查找

倒排索引

结构

次关键码--对应--记录号表

记录号表存储具有相同次关键字的所有记录的记录号

实际应用：依据属性（字段、次关键码）值查找记录

索引表：属性值和属性值的各记录地址

示例：索引表（单词表）

特点：

查找记录快，在生成索引表后，查找时不用读取记录

实际应用：

搜索引擎等