- 索引：就是把一个关键字与它对应的记录相关联的过程。
- 索引按照结构可以分为线性索引、树形索引和多级索引。
- 线性索引：就是将索引项集合组织为线性结构，也称为索引表。
1 稠密索引
稠密索引：在线性索引中，将数据集中的每个记录对应一个索引项，索引项按照关键码有序排列。
但数据量大时，可能由于内存有限，需要反复访问磁盘，降低性能。
2 分块索引（分块查找）
分块索引：对数据集进行分块，使其块间有序，块内无序。对每一块建立一个索引项。
分块索引的索引项结构分三个数据项:
- 最大关键码：每一块中的最大关键字
- 块长：便于循环时使用
- 块首指针：便于开始遍历
在分块索引表中查找，就是分两步进行:
- 在分块索引表中查找要查关键字所在的块。
- 根据块首指针找到相应的块，并在块中顺序查找关键码。
增加了整体查找的速度，普遍被用于数据库表查找等技术的应用当中。
3 倒排索引
倒排索引：不是由记录来确定属性值，而是由属性值来确定记录的位置。
索引项包括一个属性值和具有该属性值的各记录的地址。