索引
一.索引的概念
索引：索引实际上是一组键值对，键是表中的某些属性，值是指向相应文件内容的指针
顺序索引：基于值的顺序排序。
散列索引：基于将值平均分布到若干桶中，一个值所属于哪个桶，是由一个散列函数决定的。（就是哈希表的思想）
搜索码：用于在文件中查找记录的属性或属性集。即索引的“键”
二.顺序索引
顺序索引按照排好的顺序存储搜索码的值，并将每个搜索码与包含该搜索码的记录关联起来。
被搜索文件本身也可以按一定顺序来排列。
聚集索引：搜索码排序和被搜索文件内容排序一致的索引，它定义了文件中内容的次序。
非聚集索引（辅助索引）：搜索码排序与文件内容不一致
1.稠密索引
对于文件中的每个搜索码值都有一个索引，即对表中的每一个元组都有索引。索引项包括搜索码值和一个指向具有该搜索码值的第一条数据记录的指针，其他拥有相同搜索码值的数据会顺序存储在第一条之后。
2.稀疏索引
在稀疏索引中，只为某些是搜索码建立索引值。只有当表中数据按搜索码依次排序存储的时候才能用稀疏索引。
3.多级索引
为了提高查找效率，我们可以使用多级索引。先来看一下索引的大小对查找效率的影响，如果一个索引非常大，它不能被存入主存，那么我们就需要去磁盘上读取一些索引项，这会大大降低效率。
所以我们引入了多级索引，我们在原始索引上构建一个稀疏的外层索引，这个过程可以多次重复。这样可以将磁盘io的次数降到最低。例：我们现在有两层索引，原始索引有100个块，每个块有100条数据，二级索引存储了指向这些块的指针，共100条，它在主存中。我们通过二分查找找到最大搜索码值小于等于要搜索的数据的搜索码的索引项，进而得到相应的块。将该块读入主存，再去遍历或二分搜索具体数据。这个过程只需要1次磁盘io。如果不用多级索引，直接在原始索引上二分，我们读log2 100 = 7次磁盘io。
4.索引的增删
插入
稠密索引：如果该搜索码未出现在索引中，就在索引中的适当位置插入带有该搜索码的索引项。否则，如果索引项存储的是所有指向具有相同搜索码的数据的指针，那么就在该索引项中添加一个新的指针；如果索引项存储的是具有相同搜索码的第一条记录的指针，就将待插入记录放到具有相同搜索码值的其他记录之后。
稀疏索引：如果它的值不在目前的块的范围内，那就新建一个块，它是新块中的第一个索引项。如果这条插入记录具有所在块的最小值，就更新指向块的索引项。否则不做改动。例：现在有稀疏索引 1、5、10，如果插入15，那么系统将新建一个块，它的第一个索引项是15；如果插入5，那么指向5-9块的索引项指针将被更新，指向这个新插入的索引项。其他情况，稀疏索引不动。
删除
稠密索引：如果要删除的记录是唯一记录，那就直接删。否则，如果索引项存储的是所有指向具有相同搜索码的数据的指针，那么就从索引项中删除指向待删除记录的指针。如果索引项存储的是具有相同搜索码的第一条记录的指针，如果待删除记录是具有该搜索码值的第一条记录，那就将索引项指向下一条记录。
稀疏索引：如果索引值不包含具有待删除记录搜索码值的索引项，索引不动。否则，如果待删除记录是具有该搜索码值的唯一记录，就用下一个搜索码值的索引记录来替换相应的索引记录，如果下一个搜索码值已经有了一个索引项，那就删除而不是替换该索引项。如果它不是唯一记录，那就用具有相同搜索码值的下一条记录更新索引项。
5.辅助索引
辅助索引必须是稠密的。每个索引项需要包含指向所有具有该索引项搜索码值的记录的指针。
6.B+树索引文件
顺序索引文件一般被组织成B+树，它随着数据量的增长，具有比较稳定的性能。
7.非唯一性搜索码
由于搜索码可以是表中的任意属性，所以它不一定是候选码。为了保证效率和避免一些负责的问题，大多数据库的B+树都实现只处理唯一搜索码。它们会自动添加记录ID或其他属性，使得非唯一搜索码变得唯一。
二、散列索引
散列是在主存中构建索引的常用技术。散列索引的组织结构等同于哈希表。