本文主要介绍数据库中常用的索引结构。
索引分类
1. 顺序文件
顺序文件是对关系中的元组按主键进行排序而生成的文件（包含数据）。关系中的元组按照这个次序分布在多个数据块中。
2. 稠密索引
在记录有序数据块的基础上，将全部键（稠密）单独存放到单独的存储块：块中只存放记录的键以及指向记录本身的指针。
3. 稀疏索引
稀疏索引只为数据文件的每个存储块设一个键-指针对，比稠密索引节省了更多的存储空间，但查找给定值的记录需要更多时间。
4. 多级索引
当索引文件占据多个存储块，可以在索引上再建索引，这样可以使第一级索引的使用更为有效。
5. 辅助索引
辅助索引不决定数据文件中记录的存放位置，而仅指向记录的当前存放位置，这一位置可能是由建立在其他某一个字段上主索引确定的。
辅助索引一定是稠密索引。因为辅助索引不影响记录的辅助位置，不能够根据辅助索引定位不在索引中显式指明的任何记录的位置。
辅助索引有助于查找给定一个或多个字段值的记录。
6. 倒排索引
一个文档可被看成是关系Doc的元组；
关系Doc的每一个属性上都建有辅助索引；
将所有属性的索引合成一个，为倒排索引。
常用索引
1. B-树
B-树限定规则：
- 叶结点中的键是数据文件中键的拷贝，这些键以排好序的形式，从左到右分布在叶结点中；
- 根结点中至少有两个指针被使用；
- 叶结点中，最后一个指针指向它右边的下一个叶结点存储块；
- 在内层结点中，所有的n+1个指针都可以用来指向B-数中下一层的块；
- 所有被使用的键和指针通常都存放在数据块的开头位置，叶结点第（n+1）个指针是个例外，指向下一个叶结点；
B-数特性：
- B-树能自动地保持与数据文件大小相适应的索引层次；
- 对所使用的存储块空间进行管理，使每一个块充满程度在半满与全满之间；
2. 散列表
通过散列函数h散列到某个桶中的记录被放到该桶的存储块中，如果记录过多，可以给该桶加溢出块的链。
可扩展散列表：
- 为桶引入一个间接层，用一个指向块的指针数组来表示桶；
- 指针数组能增长，它的长度总是2的幂，因而数组每增长一次，桶的数目翻倍；
- 并非每个桶都有一个数据块；某一个桶中的所有记录可以放在一个块中，这些桶可以共享一个块；
- 散列函数h为每个键计算出一个K位二进制序列，K足够大；
3. 多维索引
利用传统索引执行范围查找：对记录按照单个索引分别进行查找；
3.1 多维索引的散列结构-网格文件：
在每个维度上 网格线 把空间分成条状；不同纬度上网格线数目可以不同；（同一/不同）维度上相邻网格线之间可有不同区间长度；
3.2 多维索引的树结构-多键索引：
每一层为单独一个属性，树根为第一个属性的索引，第二层为第二个属性的索引，以此类推。
3.3 多维索引的树结构-kd树：
kd树是一个二叉树，内部结点有一个相关联的属性a和一个值V，将集合分成两个部分；所有维的属性在层间交替出现，树的不同层上的属性是不同的。
3.4 多维索引的树结构-四叉树：
每一内部结点对应于二维空间中一个正方形区域，或k维空间的k维立方体；每个正方形的数量比块容量小，那么就是一个叶子结点。
3.5 多维索引的树结构-R树：
区域树表示由二维或更高维区域组成的数据（数据区），R-树的一个内部结点对应于某个内部区域。原则上，区域是可以任何形状的，R树结点的键位置上含有子区域，允许子区域有部分重叠。
4. 位图索引（Bitmap）
位图索引是一个长度为n的位向量的集合，每个位向量对应字段中可能出现的一个值。
压缩位图：采用分段长度编码来对位图索引进行压缩。