一、索引的分类及应用

目录

一、索引概述

作为一名应用系统开发人员，为什么要关注数据库内部的存储和检索呢？首先，你不太可能从头实现一套自己的存储引擎，往往需要从众多现有的存储引擎中选择一个适合自己应用的存储引擎。因此，为了针对你特定的工作负载而对数据库调优时，最好对存储引擎的底层机制有一个大概的理解。

索引背后的基本想法都是保留一些额外的元数据，这些元数据作为路标，帮助定位想要的数据从而进行快速检索。如果希望用集中不同的方式搜索相同的数据，在数据的不同部分，我们可能定义多种不同的索引。

但需要注意的是，索引是基于原始数据派生而来的额外数据结构。很多数据库允许单独添加和删除索引，而不影响数据库的内容，它只会影响查询性能。但维护额外的结构势必会引入开销，特别是在新数据写入时。由于每次写数据时，需要更新索引，因此任何类型的索引通常都会降低写的速度。

这里涉及存储系统中重要的权衡设计：适当的索引可以加速读取查询，但每个索引都会减慢写速度。为此，默认情况下，数据库通常不会对所有内容进行索引，它需要应用开发人员或数据库管理员，基于对应用程序典型查询模式的了解，来手动选择索引。目的是为应用程序提供最有利加速的同时，避免引入过多不必要的开销。

本文对索引进行简单的介绍，但并未覆盖所有的

二、索引与访问路径

关系型数据库的一大优势是，用户无需关心数据的访问方式。其访问路径是由DBMS的一个组件，即优化器来确定的。虽然不同的关系型系统的优化器各不相同，但它们都是在系统搜集的统计信息的基础上，尽可能以最高效的方式访问数据。显然优化器是SQL处理过程的可信。访问路径即为数据的访问方式，另一个经常被用来代指访问路径的术语是执行计划。

在SQL语句能够被真正执行前，优化器必须首先确定如何访问数据。这包括：应该使用哪一个索引，索引的访问方式如何，是否要使用辅助式随机读，等等。所有的这些细节都包含在访问路径中。

如下图，该访问路径定义了一次索引片段的顺序扫描，以及对每一个所需表页进行的一次同步读。

2.1 索引片及匹配列

如上图，索引的一个窄的片段会被顺序扫描，相应的表行将通过同步读从表中读取，除非该页已在缓冲池中。所以访问路径的成本大成都上取决于索引片的厚度，即谓词表达式确定的值域范围。索引片越厚，需要顺序扫描的索引页就越多，需要处理的索引记录也就越多，而最大开销还是来自于增加的对表的同步读操作。相应的，如果索引片比较窄，就会显著减少索引访问的那部分开销，但主要的成本节省还是在更少的对表的同步读取上。

索引片厚度的决定性因素是查询语句中的WHERE子句，当某一列是索引列，同时查询时该列的过滤方式可以用于定义索引片时，我们称这些数据列为匹配列。如果查询SQL中的WHERE子句有多个匹配列，那它们可以共同作用来定义一个更窄的索引片，这样不仅显著减少了索引的处理量，更为重要的是，减少了对表的同步读的次数。

2.2 索引过滤及过滤列

有时候，列可能既存在于WHERE子句中，也存在于索引中，但这个列却不能参与索引片的定义。即，不是所有的索引列都能够定义索引片的大小，不过这些列仍然能够减少回标进行同步读的次数，所以这些列仍然扮演着很重要的角色，我们称这些列为过滤列。

例如，在大部分RDBMS中，索引列顺序中，在范围过滤的谓词后面的索引列，不可参与索引片的定义，但是可以进行索引过滤。

2.3 过滤因子（选择性）

根据前面的匹配和过滤介绍，索引片大小最重要的度量就是需要扫描的索引记录数。对于匹配谓词命中的索引记录行数，可以通过谓词的过滤因子来进行预估。

过滤因子描述了谓词的选择性，即表中满足谓词条件的记录行数所占的比例，它主要依赖于列值的分布情况。当查询具有多个组合谓词时，由于业务数据的场景限定，组合谓词之间通常存在一定的关联性。因此，在进行代价评估时，通常需要将组合谓词作为一个整体来评估过滤因此，而不能仅仅基于零相关性进行评估。

优化器在评估可选访问路径的成本时，必须先评估过滤因子。过滤因子的准确性可以通过在写入数据的同时对数据特性进行统计或是采样统计来获取。

三、索引的存储方式分类

3.1 聚簇索引

聚簇索引(7)并不是一种单独的索引类型，而是一种数据存储方式。具体的细节依赖于其实现方式，但InnoDB的聚簇索引实际上在同一个结构中保存了BTree索引和数据行。当表有聚簇索引时，它的数据行实际上存放在索引的叶子页（leafpage）中。术语“聚簇”表示数据行和相邻的键值紧凑地存储在一起。因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引（不过，覆盖索引可以模拟多个聚簇索引的情况，本章后面将详细介绍）。

下图展示了聚簇索引中的记录是如何存放的。注意到，叶子页包含了行的全部数据，但是节点页只包含了索引列。在这个案例中，索引列包含的是整数值。

一些数据库服务器允许选择哪个索引作为聚簇索引，但直到本书写作之际，还没有任何一个MySQL内建的存储引擎支持这一点。InnoDB将通过主键聚集数据，这也就是说图53中的“被索引的列”就是主键列。

如果没有定义主键，InnoDB会选择一个唯一的非空索引代替。如果没有这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引。InnoDB只聚集在同一个页面中的记录。包含相邻键值的页面可能会相距甚远。

聚簇主键可能对性能有帮助，但也可能导致严重的性能问题。所以需要仔细地考虑聚簇索引，尤其是将表的存储引擎从InnoDB改成其他引擎的时候（反过来也一样）。

聚集的数据有一些重要的优点：

1. 可以把相关数据保存在一起。例如实现电子邮箱时，可以根据用户ID来聚集数据，这样只需要从磁盘读取少数的数据页就能获取某个用户的全部邮件。如果没有使用聚簇索引，则每封邮件都可能导致一次磁盘I/O。

2. 数据访问更快。聚簇索引将索引和数据保存在同一个BTree中，因此从聚簇索引中获取数据通常比在非聚簇索引中查找要快。使用覆盖索引扫描的查询可以直接使用页节点中的主键值。如果在设计表和查询时能充分利用上面的优点，那就能极大地提升性能。

同时，聚簇索引也有一些缺点：

1. 聚簇数据最大限度地提高了I/O密集型应用的性能，但如果数据全部都放在内存中，则访问的顺序就没那么重要了，聚簇索引也就没什么优势了。

2. 插入速度严重依赖于插入顺序。按照主键的顺序插入是加载数据到InnoDB表中速度最快的方式。但如果不是按照主键顺序加载数据，那么在加载完成后最好使用OPTIMIZETABLE命令重新组织一下表。

3. 更新聚簇索引列的代价很高，因为会强制InnoDB将每个被更新的行移动到新的位置。基于聚簇索引的表在插入新行，或者主键被更新导致需要移动行的时候，可能面临“页分裂（pagesplit）”的问题。当行的主键值要求必须将这一行插入到某个已满的页中时，存储引擎会将该页分裂成两个页面来容纳该行，这就是一次页分裂操作。页分裂会导致表占用更多的磁盘空间。

4. 聚簇索引可能导致全表扫描变慢，尤其是行比较稀疏，或者由于页分裂导致数据存储不连续的时候。

5. 二级索引（非聚簇索引）可能比想象的要更大，因为在二级索引的叶子节点包含了引用行的主键列。二级索引访问需要两次索引查找，而不是一次。（二级索引查到主键索引片，然后再来聚簇索引里查找一次）

InnoDB如果有主键，同时又有一个不包含主键的索引，那数据是怎么存储的？一个聚簇索引+一个二级索引（不聚簇），且二级索引中记录的是主键值。

如果表没有主键，甚至都没有唯一键索引的话，InnoDB内部会基于一个包含了ROW_ID值的列生成一个隐式的聚簇索引，行都会根据这个ROW_ID排序。ROW_ID是一个6个字节，即48位的单调递增字段。有新数据插入时，就会生成一个新的递增的ROW_ID。所以，根据ROW_ID排序的行，本质上是按照插入顺序排序。

InnoDB二级索引的叶子节点中存储的不是“行指针”，而是主键值，并以此作为指向行的“指针”。这样的策略减少了当出现行移动或者数据页分裂时二级索引的维护工作。使用主键值当作指针会让二级索引占用更多的空间，换来的好处是，InnoDB在移动行时无须更新二级索引中的这个“指针”。

3.2 非聚簇索引（二级索引）

非聚簇索引的数据和索引是分别存放的，其索引结构中的叶子节点仍然是索引节点，只不过有指向对应数据块的指针。

以MyISAM举例，MyISAM的数据分布非常简单，按照数据插入的顺序存储在磁盘上，如下图：

在行的旁边显示了行号，从0开始递增。因为行是定长的，所以MyISAM可以从表的开头跳过所需的字节找到需要的行（MyISAM并不总是使用图54中的“行号”，而是根据定长还是变长的行使用不同策略）。这种分布方式很容易创建索引。下面显示的一系列图，隐藏了页的物理细节，只显示索引中的“节点”，索引中的每个叶子节点包含“行号”。下图显示了表的主键。

那col2列上的索引又会如何呢？有什么特殊的吗？回答是否定的：它和其他索引没有什么区别。下图显示了col2列上的索引。

下图为聚簇索引和非聚簇索引的表分布对比

三、索引数据结构

3.1 哈希索引

哈希索引（hashindex）基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hashcode），哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。

因为索引自身只需存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引查找的速度非常快。然而，哈希索引也有它的限制：

1. 哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能的影响并不明显。哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序。

2. 哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如，在数据列（A,B）上建立哈希索引，如果查询只有数据列A，则无法使用该索引。

3. 哈希索引只支持等值比较查询，包括=、IN()、<=>（注意<>和<=>是不同的操作）。也不支持任何范围查询，例如WHEREprice>100。访问哈希索引的数据非常快，除非有很多哈希冲突（不同的索引列值却有相同的哈希值）。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。

4. 如果哈希冲突很多的话，一些索引维护操作的代价也会很高。例如，如果在某个选择性很低（哈希冲突很多）的列上建立哈希索引，那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应行的引用，冲突越多，代价越大。

因为这些限制，哈希索引只适用于某些特定的场合。而一旦适合哈希索引，则它带来的性能提升将非常显著。

3.2 B-Tree索引

当人们谈论索引的时候，如果没有特别指明类型，那多半说的是BTree索引，它使用BTree数据结构来存储数据。大多数MySQL引擎都支持这种索引。

BTree通常意味着所有的值都是按顺序存储的，并且每一个叶子页到根的距离相同。图51展示了BTree索引的抽象表示，大致反映了InnoDB索引是如何工作的。

BTree索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点（图示并未画出）开始进行搜索。根节点的槽中存放了指向子节点的指针，存储引擎根据这些指针向下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点，这些指针实际上定义了子节点页中值的上限和下限。最终存储引擎要么是找到对应的值，要么该记录不存在。

3.3 位图索引

位图索引由针对各个不同列值的位图（位向量）组成。在每一个为图中，表中的每一行对应一个位。若该行满足位图条件，则该位被置为1。

对于复杂且不可预测的组合谓词的大表查询，适合用位图索引。因为用位图索引进行与和或计算的速度非常快，即便表行数量达亿级也是如此。而若使用B树索引进行同样的操作则需要收集大量指针并进行排序。

另一方面，一个包含合适的列的B树索引能够避免标访问。这一点很重要，因为对一张打标进行随机I/O是非常慢的（约10ms）。而若使用位图索引，那么就必须访问表行，除非SELECT列表只包含COUNT。因此使用位图索引可能比使用一个合适的（宽）B数索引的总执行时间长的多。

位图索引应当在满足以下条件的情况下使用：

1. 可能的谓词组合数量太多了，以至于设计足够的B树索引是不可行的。

2. 单个谓词具有很高的过滤因子，但组合起来之后（WHERE子句）具有很低的过滤因子，或者SELECT列中只包含COUNT。

3. 更新操作是批量进行的（不存在锁征用）

3.4 LSM Tree

B+树的一些特性使其能够通过主键对记录进行高效插入、查找以及删除。但正因为B+树为了满足快速的查询响应而在数据结构上做的限制，写入数据时，对于一个有固定大小的页表来说，页表大小超过容量限制时就会产生问题。这时需要将该页表拆分成两个新的页表，同时更新原页表的父节点，并使其指向刚创建的两个新节点。现在的问题是，新建的两个页表在硬盘中并不一定是彼此相邻的。如果要进行一次从key1到key3的范围查询，则需要读取两个在磁盘上不连续甚至可能相隔很远的叶节点页表。这也是为什么我们在大部分基于B+树的设计中都能找到一组被称为OPTIMIZETABLE（优化表）命令的原因，B+树这种数据组织方式只是简单地按顺序把表重写，从而使表的范围查询变成了磁盘的多段连续读取。

LSM被设计来提供比传统的B+树或者ISAM更好的写操作吞吐量，通过消去随机的本地更新操作来达到这个目标。

那么为什么这是一个好的方法呢？这个问题的本质还是磁盘随机操作慢，顺序读写快的老问题。这二种操作存在巨大的差距，无论是磁盘还是SSD。

上图很好的说明了这一点，他们展现了一些反直觉的事实，顺序读写磁盘（不管是SATA还是SSD）快于随机读写主存，而且快至少三个数量级。这说明我们要避免随机读写，最好设计成顺序读写。

所以，让我们想想，如果我们对写操作的吞吐量敏感，我们最好怎么做？一个好的办法是简单的将数据添加到文件。这个策略经常被使用在日志或者堆文件，因为他们是完全顺序的，所以可以提供非常好的写操作性能，大约等于磁盘的理论速度，也就是200~300 MB/s。

LSM Tree的树节点可以分为两种，保存在内存中的称之为MemTable, 保存在磁盘上的称之为SSTable。

SSTable，及排序字符串表，其键值对的序列是按照键进行排序的，且每个键只在每个合并的段文件中出现一次（经过压缩）。与使用散列索引的日志段相比，SSTable有截个很大的优势：

1. 合并段简单高效（因为每个键只在每个合并的段文件中出现一次）

2. 由于文件的排序特性，在文件中找到一个特定的键不需要保存内存中所有键的索引。而是可以依靠键的排序特性，结合一部分的顺序查找进行快速定位。

比较B+树和LSM树的意义在于理解它们的相对优势和不足。在没有太多的修改时，B+树表现得很好，因为这些修改要求执行高代价的优化操作以保证查询能在有限时间内完成。在任意位置添加数据的规模越大、速度越快，这些页成为碎片的速度就越快。最后，用户写入的速度可能比优化后重写文件的处理速度更快。由于更新和删除以磁盘寻道的速率完成，这就强制用户就范于磁盘提供的较差的性能指标。LSM树以磁盘传输速率工作并能较好地扩展以处理大量的数据。它们使用日志文件和内存存储来将随机写转换成顺序写，因此也能保证稳定的数据插入速率。由于读和写独立，因此在这两种操作之间没有冲突。

四、高性能的索引策略

4.1 覆盖索引

通常大家都会根据查询的WHERE条件来创建合适的索引，不过这只是索引优化的一个方面。设计优秀的索引应该考虑到整个查询，而不单单是WHERE条件部分。索引确实是一种查找数据的高效方式，但是MySQL也可以使用索引来直接获取列的数据，这样就不再需要读取数据行。如果索引的叶子节点中已经包含要查询的数据，那么还有什么必要再回表查询呢?如果一个索引包含（或者说覆盖）所有需要查询的字段的值，我们就称之为“覆盖索引”。覆盖索引是非常有用的工具，能够极大地提高性能。考虑一下如果查询只需要扫描索引而无须回表，会带来多少好处：

1. 索引条目通常远小于数据行大小，所以如果只需要读取索引，那MySQL就会极大地减少数据访问量。这对缓存的负载非常重要，因为这种情况下响应时间大部分花费在数据拷贝上。覆盖索引对于I/O密集型的应用也有帮助，因为索引比数据更小，更容易全部放入内存中（这对于MyISAM尤其正确，因为MyISAM能压缩索引以变得更小）。

2. 因为索引是按照列值顺序存储的（至少在单个页内是如此），所以对于I/O密集型的范围查询会比随机从磁盘读取每一行数据的I/O要少得多。对于某些存储引擎，例如MyISAM和PerconaXtraDB，甚至可以通过OPTIMIZE命令使得索引完全顺序排列，这让简单的范围查询能使用完全顺序的索引访问。

3. 一些存储引擎如MyISAM在内存中只缓存索引，数据则依赖于操作系统来缓存，因此要访问数据需要一次系统调用。这可能会导致严重的性能问题，尤其是那些系统调用占了数据访问中的最大开销的场景。

4. 由于InnoDB的聚簇索引，覆盖索引对InnoDB表特别有用。InnoDB的二级索引在叶子节点中保存了行的主键值，所以如果二级主键能够覆盖查询，则可以避免对主键索引的二次查询。

不是所有类型的索引都可以成为覆盖索引。覆盖索引必须要存储索引列的值，而哈希索引、空间索引和全文索引等都不存储索引列的值，所以MySQL只能使用BTree索引做覆盖索引。另外，不同的存储引擎实现覆盖索引的方式也不同，而且不是所有的引擎都支持覆盖索引

4.2 使用索引扫描来做排序

查询结果的排序有两种方式：查询到表行后进行排序操作，或是按照索引顺序扫描。

扫描索引本身是很快的，因为只需要从一条索引记录移动到紧接着的下一条记录。但如果索引不能覆盖查询所需的全部列，那就不得不每扫描一条索引记录就都回表查询一次对应的行。这基本上都是随机I/O，因此按索引顺序读取数据的速度通常要比顺序地全表扫描慢，尤其是在I/O密集型的工作负载时。MySQL可以使用同一个索引既满足排序，又用于查找行。因此，如果可能，设计索引时应该尽可能地同时满足这两种任务，这样是最好的。

只有当索引的列顺序和ORDERBY子句的顺序完全一致，并且所有列的排序方向（倒序或正序）都一样时，MySQL才能够使用索引来对结果做排序(14)。如果查询需要关联多张表，则只有当ORDERBY子句引用的字段全部为第一个表时，才能使用索引做排序。ORDERBY子句和查找型查询的限制是一样的：需要满足索引的最左前缀的要求；否则，MySQL都需要执行排序操作，而无法利用索引排序。

有一种情况下ORDERBY子句可以不满足索引的最左前缀的要求，就是前导列为常量的时候。如果WHERE子句或者JOIN子句中对这些列指定了常量，就可以“弥补”索引的不足。例如，下列查询语句，当索引列设计为a,b时，可以进行索引排序。

select
	*
from
	tb
where
	a=${a}
order by b desc

 

引用：

[1] 高性能MySQL

[2] 数据密级型应用系统设计

[3] 数据库索引设计与优化

[4] HBase权威指南

[5] https://www.zhihu.com/question/19887265

[6] https://liudanking.com/arch/lsm-tree-summary/