数据库索引的工作方式类似于书本目录索引。如果我们希望打开某本书中某个主题的页面，可以在书前的目录中查找主题所在的页码，找到他出现的页，从而避免将书从头翻到尾，因此索引能够更快地搜索信息。
例如这样一个查询：select * from table1 where id=10000。如果没有索引，必须遍历整个表，直到ID等于10000的这一行被找到为止；有了索引之后(必须是在ID这一列上建立的索引)，即可在索引中查找。由于索引是经过某种算法优化过的，因而查找次数要少的多。可见，索引是用来定位的。
两种基本的索引类型：

• 顺序索引：基于值的顺序排序
• 散列索引：基于将值平均分布到若干散列桶中。一个值所属的散列桶是由散列函数决定的

本篇主要讲解顺序索引。

对某种技术的评价基于以下这些元素：

• 访问类型：特定属性值的记录或在某个特定范围内的记录
• 访问时间：使用该技术找到所需记录的时间
• 插入时间：插入一行新数据项的时间，其中包括了找到插入这个新数据项的正确位置所需的时间，以及更新索引的时间
• 删除时间：删除一行数据项的时间，其中包括找到待删除项的时间，以及更新索引的时间
• 空间开销：索引结构额外占用的空间

搜索码（Serach key）：用于在文件中查找记录的属性称为搜索码

• 顺序索引
  • 聚集索引(clustering index)
  • 非聚集索引(nonclustering index)
  • 稠密索引(dense index)
  • 稀疏索引(sparse index)
  • 多级索引(multi level index)

顺序索引

顺序索引按顺序存储搜索码的值，并将每个搜索码与包含该搜索码的记录关联起来。被索引文件中的记录自身也可以按照某种顺序存储，正如图书馆的书按某些（多个）属性顺序存放一样。一个文件可以有多个索引，分别基于不同的搜索码。

顺序索引分为两类，单级索引（不怎么用）和多级索引（通常是B+树，大量使用）。

• 单级索引就是把所有的索引字段以及对应的文件位置按顺序一个个的排列出来，这种索引查找起来比较慢，因为是顺序存储的，可以使用二分查找法，但是总体来说效率不高，这种索引是最基础的索引。
  • 如果被索引的字段本身按照一定的顺序排序，那么这种索引叫做聚集索引。否则叫做非聚集索引。
  • 如果被索引的字段的每个值都有一个索引与其对应，那么这种索引叫做稠密索引，否则叫做稀疏索引。
• 多级索引实际上就是在单级索引之上再加索引（稀疏索引），也就是指向索引的索引，二级索引上面还可以再加三级索引，可以不停的加，加到最后最上层只剩下一个节点（根节点），就成了一个树状结构了。

聚集索引(clustering index)

包含记录的文件 按 某个搜索码指定的顺序排序，那么该搜索码对应的索引为聚集索引。聚集索引也称为主索引，对于数据库而言，其是可以存在多个索引的，而磁盘上的数据顺序只可能有一种，因而对于索引而言，一个表只可能有一个索引被定义为聚簇索引（默认是主键索引）。

但是：
主键不是聚集索引
通常，我们会在每个表中都建立一个ID列，以区分每条数据，并且这个ID列是自动增大的，步长一般为1。我们的这个办公自动化的实例中的列Gid就是如此。此时，如果我们将这个列设为主键，SQL SERVER会将此列默认为聚集索引。这样做有好处，就是可以让数据在数据库中按照ID进行物理排序，但笔者认为这样做意义不大。
显而易见，聚集索引的优势是很明显的，而每个表中只能有一个聚集索引的规则，这使得聚集索引变得更加珍贵。

从我们前面谈到的聚集索引的定义我们可以看出，使用聚集索引的最大好处就是能够根据查询要求，迅速缩小查询范围，避免全表扫描。在实际应用中，因为ID号是自动生成的，我们并不知道每条记录的ID号，所以我们很难在实践中用ID号来进行查询。这就使让ID号这个主键作为聚集索引成为一种资源浪费。其次，让每个ID号都不同的字段作为聚集索引也不符合"大数目的不同值情况下不应建立聚合索引"规则；当然，这种情况只是针对用户经常修改记录内容，特别是索引项的时候会负作用，但对于查询速度并没有影响。

特点：

1. 顺序与物理顺序相对应
2. 一个表只能有一个聚集索引
3. 通常在主键上建立
4. 要求必须唯一

非聚集索引(nonclustering index)

搜索码指定的顺序与文件中记录的物理顺序不同的索引称为 非聚集索引 或 二级索引（secondary index）。
与聚集索引不同，非聚集索引的逻辑顺序与磁盘上行的物理存储顺序不同。磁盘上的数据可以随意分布，而通过非聚集索引，可以在逻辑上为数据排序。如下图，叶节点没有包含具体的数据，而是包含了一个指向具体数据的指针。

特点：

1. 顺序与物理顺序无关、不匹配，仅能告诉我们记录当前的存放位置
2. 通常在其他键上建立
3. 不要求唯一

稠密索引(dense index)

如上图所示：在稠密索引中文件中的每个搜索码值都对应一个索引值。索引项包括索引值以及指向该搜索码值的第一条数据记录的指针。由于该索引符合聚集索引，因此记录根据相同的码值排序。

在稠密非聚集索引中，索引必须存储指向所有具有相同搜索码值的记录的指针列表。

特点：

1. 稠密索引的顺序与文件中元组的顺序必须一致，且一一对应
2. 每一个元组都有一个索引项。
3. 不用排序

稀疏索引(sparse index)

如上图所示：在稀疏索引中，只为索引码的某些值建立索引项。 换句话说，只有索引时聚集索引时才能使用稀疏索引。和稠密索引一样，每一个索引项包括索引值以及指向该搜索码值的第一条数据记录的指针。为了定位一条记录，我们找到其最大搜索码值小于或等于所查找记录的搜索码值的索引项，然后从该索引项指向的记录开始，沿着文件中指针查找，直到找到所需记录为止。例如一本字典，每页页眉都顺序地列出了该页中按字母序出现的第一个单词，字典中每页顶部的单词共同构成了字典页的稀疏索引。

特点：

1. 稀疏索引必须是排好序的键
2. 每一个数据块有一个索引项
3. 更节省索引空间

正如我们所看到的：稠密索引比稀疏索引更快地定位一条记录，而稀疏索引所占空间较小，插入和删除时所需的维护开销也越小。

多级索引(multi level index)

索引的索引，为了压缩很大的索引文件。

特点：

1. 多级索引只能是稀疏索引
2. 层级越多，空间越小，但是查询的效率会降低

参考文献：《数据库系统概念》:作者: （美）Abraham Silberschatz / （美）Henry F.Korth / （美）S.Sudarshan