1、什么是索引？
拿到一本书，想直接跳到感兴趣的章节，而不是从头看到尾，这时需要看书的目录，上面列出章节和对应的页码，这里的目录可以看成是书的索引，如果没有索引，要查找书中某块内容需要从头翻到尾，从数据库的搜索的角度叫全表扫描，很明显效率很低，索引可以帮助我们提高检索数据的效率。
更经典的是字典，一般字典都特别厚，通常使用字典时就是想找某个字、词所在解析的内容的那一页，如果没有索引目录，查找内容要耗费的精力更多，通常字典的索引目录也很厚，但跟直接搜内容相比，效率还是大大提升了。
还有图书馆的例子，图书馆藏书很多，一般会给藏书编个号，查找书籍时，先在电脑上通过书名关键字查到对应的书编号，再根据编号从书架上找书。通常每个书架上都会标明本书架的书是从编号xxx~yyy，并且相邻书架的编号一般是顺序排放的，借阅人一般先根据书编号定位到书所在的书架，再从对应书架上查找。在这个例子中，书可看成是数据，书存放位置是数据存储顺序，书的编码可看成索引，数据按照索引指定的顺序排列，这种索引叫聚集索引。
PS. 关于索引概念的理解，安利下 数据库索引是什么？新华字典来帮你。
索引的类型
- 顺序索引。基于值的顺序排序。
- 散列索引。基于将值平均分布到若干散列桶中，一个值所属的散列桶是由一个函数决定的，该甘薯称为散列函数。
搜索码
用于在文件中查找记录的属性或属性集称为搜索码，如果一个文件上有多个索引，那么它就有多个搜索码。
数据表中的数据存储在文件中，如果查询条件的一个或多个属性刚好是建立了索引的搜索码，那么就会先从索引文件中找到要搜索的数据的位置，再直接从文件中相应的位置查找到数据。
2、顺序索引
聚集索引（主索引）：如果包含记录的文件按照某个搜索码指定的顺序排序，那么该搜索码对应的索引称为聚集索引。（字典和图书馆的例子）
非聚集索引（辅助索引）：搜索码指定的顺序与文件中记录的物理顺序不同的索引称为非聚集索引。
（1）稠密索引和稀疏索引
索引项或索引记录由一个<u>搜索码值</u>和指向具有该搜索码值的一条或者多条记录的<u>指针</u>构成，指向记录的指针包括磁盘块的标识和标识磁盘块内记录的块内偏移量。
可以使用的顺序索引有两类：
-
稠密索引
- 如果是聚集索引，文件中的每个搜索码值都有一个索引项，索引项包括搜索码值以及指向具有该搜索码值的第一条数据记录的指针。具有相同搜索码值的其余记录顺序地存储在第一条数据记录之后。
- 如果是非聚集索引，索引必须存储指向所有具有相同搜索码值的记录的指针列表。
- 稀疏索引
在稀疏索引中，只为搜索码的某些值建立索引项，并且要求关系按搜索码排序的顺序存储，即索引必须是聚集索引。（类似二分查找的思想）
每个索引项包括一个搜索码值和指向具有该搜索码值的第一条数据记录的指针。为了定位一条记录，需要先找到其最大搜索码值小于等于所查找记录的搜索码值的索引项，然后从该索引项指向的记录开始，沿着文件中的指针查找，直到找到所需记录为止。
【检索示例】查找教师 ID 为33456 的教师信息，从稀疏索引信息可知，该记录在搜索码值为 32343 的索引指向的记录后，于是从 ID 为 32343 的记录开始向后查找，第二条就是要查找的信息。
（2）多级索引
如果索引文件比较小，可以完全加载在内存中使用，但是对存储海量数据的表来说，其索引文件同样很大，达到 GB 级别，完全加载到内存中使用是不现实的，必须存储在磁盘中，等到使用时再取要用到的块加载到内存中，如果通过索引检索数据的过程中，读取索引文件块需要多次磁盘 IO，数据库查询的性能会受到影响，为了解决这个问题，可以使用多级索引。
假设一个 4KB 的块（磁盘中一个扇区的大小）可以容纳 100 条索引项，对于一张存储了 100 万数据的表，一个索引需要占用 10000 个这样的块，即 40 M，索引以顺序文件的方式存储在磁盘上。因为索引比较大，不能放在内存中，需要的时候，必须从磁盘块中取索引块，于是搜索一个索引项需要多次读取磁盘块。
根据搜索码从百万数据中检索数据，首先要找到搜索码的值对应的索引信息存在哪个磁盘块中，由于索引文件也是在磁盘中连续存储，所以在 10000 个块中找到对应的块，用二分法，需要 14 次读取块的操作（即将块加载到内存中 [ 耗时较长 ] + 读取块中的索引信息判断是否要找的索引 [ 非常快可以忽略不计 ]），假设每次读块耗时 10ms，则定位到索引所在的块需要 140ms，1s 最多只能进行 7 次索引搜索。
而多层索引，实际上就是对索引的索引，我们叫它为外层索引，而最原始最内层的指向数据库文件数据记录的索引叫内层索引。
（3）辅助索引
辅助索引必须是稠密索引，因为辅助索引不是聚集索引，所以辅助索引必须存储指向所有满足搜索码值记录的指针。
如上面的教师数据表，主索引是 ID，是一个聚集索引，现在为方便筛选查询工资为某个值或某个区间的记录，需要对工资列建立辅助索引，很明显，工资跟 ID 号的顺序排列是没关系的，所以这个辅助索引就不是聚集索引。
为方便快速检索，可以用一个附加的间接指针层来实现辅助索引，指针并不直接指向文件，而是指向一个包含文件指针的桶。
【缺点】使用辅助索引按辅助码的顺序对表进行顺序扫描时，由于每条记录都可能需要从磁盘中读入一个新的块，因此性能一般。
顺序索引的缺点：
随着文件的增大，索引查找性能和数据顺序扫描性能都会下降，虽然这种性能下降可以通过对文件进行重新组织来弥补，但是我们不希望频繁地进行重组。
