索引入门：顺序索引

之前我对索引的了解基本就是主索引和二级索引，此外还经常见到一些其他概念，如聚集索引和非聚集索引，稀疏索引和密集索引等，今天系统整理一下。

本文预计阅读时间 5 分钟。

索引的来源

我们用之前的表结构为例，一张表就对应一个文件。这里我们增加了一个 ID 列。这个表用来存储员工信息。在员工管理系统中通常需要将一个人的所有信息展示出来，这就需要在数据库中一次性查出某个人的所有属性。一般来说会通过人的ID来查，因为姓名会重复，而ID可以自增不重复，我们把 ID 作为一条记录的唯一标识，在关系型数据库中就可以设为表的主键。

在没有索引的情况下，当我查询一个 ID 的所有信息时，需要一个一个遍历，读取每行记录出来比对，当数据量大了之后就非常慢。于是与文件相关联的附加的结构（索引）横空出世。

简单来说，数据库中的索引和书的目录类似，记录了每一节的标题和页码。

以上边的数据为例，我们在左边列出了这些记录在磁盘上的位置，索引就记录每条记录在磁盘的位置：1->10，2->20，3->30 。可以看到，相比于原始数据，索引的空间占用小了很多。

我们这每一个 -> 就是一个索引项（index entry）或索引记录（index record）。

一般索引都是建立在某些字段上的，这些字段可以叫做搜索键（索引字段），只有在建立了索引字段上查询，才能用相应的索引结构加速查询。上边例子中的索引字段就是 ID。

当然也可以在多个字段上分别建立索引。比如在身高字段上也建立一个索引，这样根据身高查询也快了。每个建立索引的字段都可以叫做索引字段。

根据《数据库系统概念》的官方定义：

索引项由一个键值和指向具有该键值的一条或多条记录的指针构成。指向记录的指针包括磁盘块的标识和标识磁盘块内记录的块内偏移量。

索引的分类

第一种分类方法是我们常说的主索引（聚集索引）和二级索引（非聚集索引）。

这个分类方法和文件中记录的排序方式有关。如果文件中的记录按照某个索引字段的顺序在磁盘中排序存储，这个索引就叫做 主索引 或 聚集索引（Clustered Index）。而其他字段上的索引就叫做 二级索引 或 非聚集索引（NonClustered Index）。简单来说：主索引和磁盘顺序有关，二级索引无关。

关于聚集索引和非聚集索引还可以参考 SQL Server 的文档（https://docs.microsoft.com/en-us/sql/relational-databases/indexes/clustered-and-nonclustered-indexes-described?view=sql-server-2017）。

一个文件上最多有一个聚集索引，因为磁盘是一维的，只能按一个字段排序。

今天我们介绍的是顺序索引，即索引是根据某些字段值的顺序排序的，文件中的数据项也是顺序组织的。

稠密和稀疏

在顺序索引中，索引又分稠密索引和稀疏索引，稠密索引是每个记录都有一个索引项。而稀疏索引中只有部分记录对应索引项。

稠密索引好理解，就是上边例子中的，为每个人的ID和位置都记录一个索引项。

如果把书中的每一句话当做一个数据项，那么目录就是稀疏索引。我们找到一个章节的页码后，这个章节的内容都在这个章节和下一个章节之间。

也就是说稀疏索引必须是聚集索引，非聚集索引必须是稠密索引。这两句有点绕，可以先仔细想一想，这是为了支持快速查询的。想通了之后，可以编一句顺口溜：稀疏必有序，无序必稠密。

索引的评价指标

在没有索引之前，我们只需要更新数据文件就好了，在有了索引文件之后，我们还需要同时更新（增删改）索引文件。因此，索引是在写入速度、空间占用和查询性能三者的权衡。其中，写入速度和查询性能是最重要的两个方面。

评价一个索引的好坏可以从以下几个角度看：

访问类型：即支持的查询模式，如单点查询或范围查询，模糊查询或精确查询等。

访问时间：即查询一个特定数据项或一组数据项的时间。

插入时间：在索引结构中定位并插入一个新数据项的时间。

删除时间：在索引结构中定位并删除一个数据项的时间。

空间开销：索引结构额外占用的空间。

总结

索引可以用来加速查询，但需要精确的设计，设计的不好，不仅不会加速查询，还会拖慢写入速度。此外，索引的空间占用还影响了一个索引能否全部缓存在内存里。索引是写入速度、空间占用、查询性能三者的权衡。最后，再说一遍顺口溜：稀疏必有序，无序必稠密。