索引的基础结构
稠密索引、稀疏索引、主索引(聚集索引)、辅助索引（非聚集索引）
主索引（聚集索引）
能够确定记录在数据文件中的位置，索引的顺序与物理顺序相对应，通常在主键上建立索引。
特点：
辅助索引（非聚集索引）
不能确定记录在数据文件中的位置，与物理顺序不匹配，通常在其他属性上建立附注索引。
特点：
稠密索引
为每一个元组创建一个对应的索引项，索引文件的顺序与元组顺序一致。例如在顺序文件上构建稠密索引，索引内仅包含每一个元组的主键记录和指向记录本身的指针。
顺序文件是对关系中的元组按照主键进行排序而生成的文件。
特点：
稀疏索引
为每一个存储块建立一个索引项，建立稠密索引是必须排好序的记录。例如在顺序文件上构建稀疏索引，索引内包含每个数据块中第一个记录对应的值和指向记录本身的指针。
特点：
多级索引
索引的索引，为了压缩很大的索引文件。
特点：
B树
索引的常用数据结构，可以减少定位记录时所经历的中间过程，从而加快存取速度
数据结构
B树是广义化的二叉搜索树，只是每个节点不仅仅只有两个子数。是一颗平衡树。
B树的应用
由于其叶子节点的指针，可以指向任一数据记录，所以B树可以用到任何的索引结构中。如：
B树的查找
B树的其他操作
插入、删除等，在此不再赘述。
散列表
数据结构
哈希链表
应用
已知一个散列函数，查找键利用该散列函数可以计算出一个介于0到B-1的整数。（B是桶的数目）桶数组是一个序号从0到B-1的数组，其中包含了B个链表的头（每个数组元素是一个存储块，为了便于理解认为数组中存的是该块的指针链的头指针）。通过散列函数，将每个记录分别放到对应的桶中，如果桶溢出，可以加一个溢出块链。
操作
插入、删除等不再赘述
比较B树和散列表
- 散列表方法适用于查找给定值的查询
- B树适用于范围查询
