数据库中索引的分类

本文中可能存在汉译与现行流行词语不相符，均已注明英文原词。

名词解释：

index：索引，有时候特指一条特定的索引。

index entry/index record：索引项/索引记录，索引中一条特定的索引单元。

search key：搜索码，指在数据库的表中，用来建立索引的列。

record：数据库表中的一条（一行）数据。

索引简介

索引是为了优化大规模数据库的查找而在数据库内部维护的一种数据结构。

索引的最小单元是index entry，包含若干search key和具有该search key的数据地址（物理区块+偏移量）。

可以分为顺序索引和散列索引。

顺序索引又可以分为稠密索引、稀疏索引；聚簇索引、非聚簇索引。

散列索引。

此外还有诸如唯一索引（未完成）等名词

稠密索引(dense index)与稀疏索引(sparse index)

稠密索引：

• 从index角度看，dense index 的所有指针覆盖了所有数据。
• 从record角度看，任意一条record都有一个索引项。

稀疏索引

• 从index角度看，sparse index 的所有指针不能覆盖所有数据。即不能通过一个sparse index找到表中所有数据。
• 从record角度看，存在record无法对应到sparse index中的任一index entry。

稠密索引

稀疏索引

图源[2]。

聚簇索引(clustering index)与非聚簇索引(nonclustering index)

聚簇索引（主索引）

clustering index, 有时也作clustered index。也有人翻译成：聚集索引、聚合索引等，其实都是一样的。

[2]中对聚簇索引的定义是：

*a clustering index is an index whose search key also defines the sequential order of the file. *

这句定义非常简单，聚簇索引的实质就是索引本身index entry的和表中具有相应search key的record的顺序一致。

聚簇索引

对于可能存在的多个具有相同search key的record，index entry只需要保存第一个出现的该search key值的位置，由于顺序排列，其余相同具有该search key值的record都紧随其后地排列在第一条之后。

注意到书中紧随定义之后的一段话。

Clustering indices are also called primary indices; The term primary index ay appear to denote an index on a primary key but such indices can in fact be built on any search key .the search key of a clustering index is often the primary key, although that is not necessary so.

这里要注意辨别聚簇索引的另一个别名（主索引）与主键的关系：习惯上主键上建立主索引，但这不是必须的。

到这里看过其它介绍的读者可能会产生疑惑，因为很多网上资料写聚簇索引都是用层次结构（类似树）来表示的。

本质上，聚簇索引的定义就是index entry和具有相应search key的record的顺序一致，很简洁。至于为什么网上那么多资料都解释得如此复杂，就要提到一个概念——多级索引（Mutilevel indeices）

多级索引

如[聚簇索引]图中所示，索引中index entry的数目几乎和表中数据条数属于同量级（几乎相等），对于大规模数据库，索引的体量可能会很大，因此在查询中很难全部读取到主存中，难免出现频繁IO操作（关于主存和磁盘IO的读取速度对性能的讨论可以参考[1]）。

即使主存空闲容量>index大小，当index体量足够大时，计算机主存本身也需要为其它工作服务，不能大部分都被数据库查询啃食。

因此，需要对[聚簇索引]图中笨重的类线性表index结构做出调整（对数据结构进行优化），因此就出现了[多级索引]图这样的结构，这个就更像网上大多数人传递的“聚簇索引”版本了。

多级索引

多级索引的具体实现取决于不同的引擎。MyISAM和InnoDB使用B+树来实现，详见[2]。

非聚簇索引（辅助索引）

nonclustering index, 也称secondary index（辅助索引）。其它译法类似聚簇索引，也有非聚集索引、非聚合索引等。

非聚簇索引的一种变体

同样参考[2]中的定义：

Indices whose search key specifies an order different from the sequential order of the file are called nonclustering indices, or secondary indices.

非聚簇索引就是index entry和数据库中具有相应search key的record的排列顺序不同。

常见问题

• 非聚簇索引必须是dense index。（由于index entry与record顺序不同，sparse index很难保证能够找到表中的全部记录）
• 非聚簇索引的dense index的每一个index entry必须保存search key对应所有record的list（由于顺序不同，无法采取只保存第一个然后往后继续读取的方式）

常见面试问题

聚簇索引和非聚簇索引的区别

为什么使用B+树而不是红黑树、查找树？

参考资料

[1]. MySQL索引背后的数据结构及算法原理

[2]. Database System Concepts(6th Edition)