简介
索引相当于目录。通过索引，可以在大量数据库记录中快速检索到目标记录。
索引中也需要存储大量记录，这些记录可能存储在磁盘上，但是仍然需要支持高效率的新增、删除和检索。
索引可以解决哪些问题
要想根据关键字查询数据库记录，首先应将记录根据关键字排序，然后对有序线性表进行二分查找。
但是用户可能会根据多个关键字对数据库中的一条记录进行查询，比如用户表，可能根据用户名查询、身份证号查询等等。无法根据多个关键字对同一批记录进行排序。
索引如何解决上述问题
在数据库主文件之外，新建索引文件
索引文件由关键码值和指向具有该关键码值的数据库完整记录的指针组成
可以对索引文件的关键码进行排序后查找，然后根据关键码值对应的指针，即可找到数据库完整记录。
主码索引和辅码索引
数据库每条记录的唯一标识，称为主码（primary_key）。
对于记录中的其它属性，可能多条记录有相同的属性值，称为辅码（secondary key）。
辅码索引由辅码值和和具有该辅码值的多条记录的主码值组成。
根据辅码值找到主码值后，可以根据主码值直接检索整个数据库，找到完整记录；也可以根据主码值在主码索引找到指针，通过指针找到完整记录。
如果使用主码索引，则只有主码索引存储数据库完整记录位置，其它索引都只存储主码值或指向主码索引的指针。
实现索引的数据结构
散列表：只支持“找到关键码值为K的记录”的查找，不支持范围查找和按顺序访问。
按关键码排序的简单线性表：新增、删除操作的开销大。
树形索引
线性索引
线性索引由关键码值／指针对组成：
key：关键码值
value：指向数据库完整记录的指针
线性索引按关键码值排序，根据关键码值二分查找后找到指针，根据指针找到数据库完整记录。
支持随机访问。
问题：如果线性索引太大，无法存储在内存，就只能存储到磁盘，此时二分查找需要多次访问磁盘，开销太大。
二级线性索引
线性索引存储在多个磁盘块中
二级线性索引是一个数组，在内存中，存储线性索引每个磁盘块中第一个关键码值
比如线性索引占用4个磁盘块，则内存中的二级线性索引是一个长度为4的数组
由于线性索引关键码值是有序的，只需在内存的二级线性索引中，找到小于目标关键码值的最大值，即找到了线性索引所在的磁盘块，此时，将该磁盘块内容读取到内存，再在内存中二分查找内容找到目标关键码对应的指针，近而找到数据库完整记录。
解决了多次访问磁盘的问题。整个过程只需读取两次磁盘：一次将线性索引磁盘块内容读取到内存，一次根据指针在磁盘中读取数据库完整记录。
问题：1、新增、删除数据库记录时，都要更新线性索引，而线性数组新增、删除开销太大；2、如果多条记录有相同的关键码值，会在索引文件中占用多个存储空间，造成浪费。
二维数组
第一列存为有序数组，存储关键码值
每一行存储具有该关键码值记录的主码值
解决了新增、删除记录开销太大问题。在辅码值范围不变的情况下，新增、删除数据库记录，只需修改其中一行数据即可。
解决了重复关键码值浪费存储空间问题。
问题：1、新增一个辅码值时，由于第一列是有序的，可能会导致移动多行记录。2、二维数组的每一行都是固定长度，有些辅码值的记录可能很少（比如上图中第3行），导致存储空间浪费。
有序数组+链表
有序数组中存储关键码值
数组中每个关键码值关联一个链表，存储具有该关键码值记录的主码值
解决了新增、删除记录开销太大问题。新增、删除记录时，只需修改链表中的记录，而修改链表是很容易的。
解决了重复关键码值浪费存储空间问题。
问题：如果索引存储在内存中，没有问题。但是如果存储在磁盘中，则可能出现链表存储在多个磁盘块的情况。
有序数组+单个链表
主码表（链表）
key：主码值
value：指向链表中下一个跟主码值记录拥有相同关键码值记录的主码值指针
辅码表
key：关键码值（有序）
value：指向主码表中，第一个具有该关键码值记录的主码值指针。
通过辅码表指针在主码表中找到的所有记录
可见，虽然所有主码值都存储在一个链表中，但找到结果还是与多个链表是等价的。
而且在链表中新增、删除元素都很容易的。
解决了链表可能存储在多个磁盘块的问题。数组关联的是链表元素指针，而不是一整个链表，不管链表元素存储在哪，都可以通过指针找到。
但是对于有序数组的新增、删除操作，开销仍然很大。
ISAM
ISAM（Indexed Sequential Access Method）本质上是二级线性索引。
数据结构如图所示：
磁盘中的数据结构是多个柱面，每个柱面由柱面索引、数据库完整记录、溢出区组成。
- 数据库完整记录按主码值顺序存储在多个磁盘块中
- 柱面索引存储当前柱面中，存储记录的每个磁盘块的最小主码值。
- 新增记录时，新增在每个柱面的溢出区，如果溢出区满了，就存储到系统溢出区。
内存中有一个主码表，存储每个柱面索引中的最小值。
检索时，根据二级线性索引原理
1、在内存主码表检索到目标主码值所在的柱面，将磁盘柱面中的柱面索引读取到内存
2、在内存柱面索引中检索到目标主码值所在的磁盘块，将磁盘块读取到内存
3、在内存磁盘块内容中检索，根据目标主码值检索到数据库完整记录
4、如果没有找到记录，就检索溢出区
在情况好时（即不需要访问溢出区的时候），只需访问两次磁盘
但是在情况不好且溢出区很大甚至被填满时，检索速度就会越来越慢
这时候就需要重组数据库：将溢出区的数据按顺序整理到磁盘块
当插入或删除记录的情况很少或者没有时，线性索引是很有效的。在20世纪60年代，IBM使用这种数据结构存储数据库数据，当时这种数据库重组很普遍，一般在夜间完成。
树形索引
二叉查找树（BST，binary search tree），可以存储重复关键码值，可以高效的插入、删除和检索（平均情况下运行时间都是O(logn)）。
如果索引以BST结构存储在内存中，即使BST的平衡性很差，也不会对性能产生较大影响。
但是如果索引太大，无法存储在内存，只能存储到磁盘，这时就会遇到两个问题：
1、如何保持BST的平衡性
如果BST的平衡性很差，会导致叶结点的深度增加，查询次数增加，即相应的增加磁盘访问次数
2、如何在磁盘中安排结点，使得从根结点到任何叶结点的路径所经过的磁盘页最少。
即磁盘I/O最少
解决第一个问题，可以让BST保持完全二叉树形状。
解决第二个问题，可以让每个子树的根节点和所有叶结点都存储在同一个磁盘页中，每个磁盘页有三个结点的存储空间，如图所示
如果一个叶结点和它的父结点在同一个磁盘页中，如果父结点被读取到内存中，那么这个叶结点也会同时被读取到内存中，访问该结点时，就不需要再次访问磁盘，而是可以直接在内存中访问了。
问题：为了让BST始终保持完全二叉树形状和上述的磁盘存储结构，每次新增、删除时，都可能需要大量的重组操作。
