针对场景：
博客网站论坛的帖子回复、服务器日志记录
数据量大，每条记录无法做到有序排列记录
解决方法：
索引---把关键字和它对应的记录相关联的过程
索引分类：线性索引、树形索引、多级索引
线性索引：将索引项集合组织为线性结构---索引表
线性索引包括：稠密索引、分块索引、倒排索引
稠密索引
结构：
索引项---对应---记录
索引项是有序的、记录数据表可以是无序的。
稠密 索引记录的结构图
查找方式：
索引项使用折半/二分法、插值查找、斐波那契查找
记录数据表--顺序查找
缺点：
数据集很大，则索引项很大，对内存有限的计算机，反复访问磁盘使得查找性能降低
生活示例：
小本子记录各物品的放置位置
分块索引
结构：
对数据集分为若干块，使得块满足：
块内无序：快内的记录不要求有序
块间有序--要求第二块所有记录的关键字均大于第一块记录的关键字
索引项---对应--每块
索引项的的结构包括3项：最大关键码、块内记录的个数、指向块首数据元素的指针
分块索引记录的结构图
查找方式：
块间--使用折半/二分法、插值查找、斐波那契查找
块内--使用顺序查找
应用示例：
图书馆书本的查找
普遍应用于数据库表查找
倒排索引
结构
次关键码--对应--记录号表
记录号表存储具有相同次关键字的所有记录的记录号
实际应用：依据属性（字段、次关键码）值查找记录
索引表：属性值和属性值的各记录地址
示例：索引表（单词表）
特点：
查找记录快，在生成索引表后，查找时不用读取记录
实际应用：
搜索引擎等
