索引背后的故事

计算机中最重要的存储介质分为几类：硬盘、内存、二级缓存、寄存器。它们之间的对比如下：

从上面的图中，我们可以看出，从下往上，速度从慢到快，制造成本也越来越高。几种有代表性的存储设备的典型访问速度如下：

从这个图中，我们可以很明显的看出：高速缓存的访问速度是主存的 10~100 倍，而主存的访问速度则是硬盘的 1～10W 倍。

大概就是走路和坐飞机的差别了。虽然坐飞机是飞一样的感觉，但是走路还是我们最常用的移动方式。数据存储也一样，对于一台独立的计算机，数据最后还是要落地到磁盘上。所以，我们来看看机械硬盘的结构。

机械硬盘中的大致结构如下图，类似很多电影和电视剧中的留声机：

机械硬盘中，每一个磁盘盘面的组成结构如下：

英文名词解释：

每个机械磁盘都有很多个盘面组成。整个机械磁盘的组成结构如下：

单词解释：

常见磁盘平均物理寻道时间为：

常见硬盘的旋转延迟时间为：

了解磁盘读取数据的原理以各种延迟后，我们再来看看顺序读取和随机读取的差别：

因为机械硬盘的磁头移动至正确的磁道上需要时间，随机读写时，磁头不停的移动，时间都花在了磁头寻道上，导致的就是性能不高。所以，对于机械硬盘来说，连续读写性很好，但随机读写性能很差。具体对比如下：

加州大学 Berkeley 分校统计的各种读取介质的延迟： Numbers Every Programmer Should Know By Year

由于存储介质的特性，硬盘本身存取就比主存慢很多，再加上机械运动耗费，硬盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘 I/O。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高 I/O 效率。磁盘往往也不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

MySQL 在读取的时候，并不是每条每条读取，而是每次读取一页，一页通常包含好多条。

接下来，我们了解一下算法相关的背景知识。

时间复杂度用来检验某个算法处理一定量的数据要花多长时间。

重要的不是数据量，而是当数据量增加时运算如何增加。

数据量低时，O(1) 和 O(n²)的区别可以忽略不计。粗略计算，假设现在的计算机每秒可以处理 1* 10⁹ 条指令每秒。比如，你有个算法要处理2000条元素。

在数据量非常小的情况下，最快 4 毫秒，最慢也只有 11 纳秒。人类几乎感知不出什么差别。但是，如果处理 1,000,000 条元素（这对数据库来说也不算大）。

O(\(n^2\)) 与 O(\(n*log_{2}n\)) 相差了 \(\frac{1.00 * 10^{3}}{1.99*10^{-2}} = 502512.56\) 倍。我们把数据扩大到 10,000,000 条元素：

O(\(n^2\)) 与 O(\(n*log_{2}n\)) 相差了 \(\frac{1.00 * 10^{5}}{0.233} = 429184.5\) 倍。

这里可以明白：

合并排序基于这样一个技巧：将 2 个大小为 N/2 的已排序序列合并为一个 N 元素已排序序列仅需要 N 次操作。这个方法叫做合并。

这个算法有两点特别棒的优势：

树，这种数据结构就能满足我们的需求，我们可以只把树的上面几级保存到内存中，方便操作。如下图：

树的节点也可以保持有序状态：

我们来看一下最简单的树结构。

在二叉查找树和在有序数组中查找某一个指定元素的对比如下：

二叉查找树中每个节点要保证两点：

这个查询的成本是 log₂(n)。

二叉查找树在线演示

上面的是理想状况下的情况。但在极端情况下，二叉查找树的查询成本有可能是 n。例如：

平衡二叉搜索树在添加元素时，通过旋转来保证自身的平衡性。

不仅能左旋，还可以右旋。左右旋转示意图：

为了解决高效查找某一个范围内的元素的问题，我们引入一个修订后的树：B+树。这也是目前大部分现代数据库索引使用的数据结构。在一个B+树里：

找到了 M 个后续节点，树总共有 N 个节点。对指定节点的搜索成本是 log(N)，跟上一个树相同。但是当你找到这个节点，你得通过后续节点的连接得到 M 个后续节点，这需要 M 次运算。那么这次搜索只消耗了 M+log(N) 次运算，区别于上一个树所用的 N 次运算。

为了构建一个哈希表，你需要定义：

真正的挑战是找到好的哈希函数，让哈希桶里包含非常少的元素。如果有了好的哈希函数，在哈希表里搜索的时间复杂度是 O(1)。

InnoDB 存储引擎是面向列的（row-oriented），也就是说数据是按行进行存放的。每个页存放的行记录是有硬性定义的，最多允许存放 16KB / 2-200 行的记录，即 7992 行记录。

“独立的列”是指索引列不能是表达式的一部分，也不能是函数的参数。

应该养成简化 WHERE 条件的习惯，始终将索引列单独放在比较符合的一侧。

当索引很长的字符列，会让索引变得大且慢，一个策略是前面提到过的模拟哈希索引。

通常可以索引开始的部分字符，可以大大节约索引空间，从而提高索引效率。但这样会降低索引的选择性。

索引的选择性是指，不重复的索引值（也称为基数，cardinality）和数据表的记录总数（#T）的比值，范围从 1/#T 到1之间。索引的选择性越高则查询效率越高，因为选择性高的索引可以让 MySQL 在查找时过滤掉更多的行。唯一索引的选择性是 1，这是最好的索引选择性，性能也是最好的。

一般情况下某个列前缀的选择性也是足够高的，足以满足查询性能。对于 BLOB、 TEXT 或者很长的 VARCHAR 类型的列，必须使用前缀索引。

诀窍在于要选择足够长的前缀以保证较高的选择性，同时又不能太长（以便节约空间）。前缀应该足够长，以是的前缀索引的选择性接近于索引整个列。换句话说，前缀的“基数”应该接近于完整列的“基数”。

为了觉得前缀的合适长度，需要找到最常见的值的列表，然后和最常见的前缀列表进行比较。

根据统计，我们只需要针对前六个字符建立前缀索引即可：

前缀索引时一种能使索引更小、更快的有效办法；也有缺点，MySQL 无法使用前缀索引做 ORDER BY 和 GROUP BY，也无法使用前缀索引做覆盖索引。

一个常见的场景是针对很长的十六进制唯一 ID 使用前缀索引。例如 SessionID。

一个常见的错误就是，为每个列创建独立的索引，或者按照错误的顺序创建多列索引。

在多个列上山里独立的单列索引大部分情况下并不能提高 MySQL 的查询性能。 MySQL 5.0 和更新版本引入了一种“索引合并”（index merge）的策略，一定程度上可以使用表上的多个单列索引来定位指定的行。

索引合并测试有时候是一种优化的结果，但实际上更多时候说明了表上的索引建的很糟糕：

如果在 EXPLAIN 中看到有索引合并，应该好好检查一下查询和表的结构，看是不是已经是最优的。

最容易引起困惑的问题就是索引列的顺序。正确的顺序依赖于使用该索引的查询，并且同时需要考虑如何更好地满足排序和分组的需要。本节内容适用于 B-Tree 索引。

在一个多列 B-Tree 索引中，索引列的顺序意味着索引首先按照最左列进行排序，其次是第二列，以此类推。所以，索引可以按照升序或者降序进行扫描，以满足精确符合列顺序的 ORDER BY、 GROUP BY 和 DISTINCT 等子句的查询需求。

在 Lahdenmaki 和 Leach 的“三星索引”系统中，列顺序也决定了一个索引是否能够成为一个真正的“三星索引”。

对于如何选择索引的列顺序有一个经验法则：将选择性最高的列放到索引最前列。通常不如避免随机 IO 和排序那么重要。

当不需要考虑排序和分组时，将选择性最高的列放到索引最前列通常是很好的。

性能不只是依赖于所有索引列的选择性（整体基数），也和查询条件的具体值有关，也就是和值的分布有关。

可能需要根据那些运行效率最高的查询来调整索引列的顺序。

尽管关于选择性和基数的经验法则值得去研究和分析，但一定要记住别忘了 WHERE 子句中的排序、分组和范围条件等其他因素，这些因素可能对查询的性能早晨非常大的影响。

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。InnoDB 的聚簇索引实际上在同一结构中保存了 B-Tree 索引和数据行。

当表有聚簇索引时，它的数据行实际上存放在索引的叶子页（leaf page）中。术语“聚簇”表示数据行和相邻的键值紧凑地存储在一起。因此，一个表只有一个聚簇索引（不过，覆盖索引可以模拟多个聚簇索引的情况）。

InnoDB 通过主键聚集数据。如果没有定义主键， InnoDB 会选择一个唯一的非空索引代替；如果没有这样的索引， InnoDB 会隐式定义哥主键来作为聚簇索引。

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

聚集数据的一些缺点：

二级索引叶子节点保存的不是指向行的物理位置的指针，而是行的主键值。二级索引要两次 B-Tree 查找而不是一次，对于 InnoDB，自适应哈希索引能够减少这样的重复工作。为什么能减少？

设计优秀的索索引应该考虑到整个查询，而不单单是 WHERE 条件部分。

如果一个索引包含（或者说覆盖）所有需要查询的字段的值，则称之为“覆盖索引”。

覆盖索引时非常有用的工具，能够极大地提高性能。优点如下：

不是所有的索引都可以成为覆盖索引。覆盖索引必须要存储索引列的值，而哈希索引、空间索引和全文索引等都不存储索引列的值，所以 MySQL 只能使用 B-Tree 索引做覆盖索引。也不是所有的存储引擎都支持覆盖索引，比如 Memory 不支持。

索引覆盖查询还有很多陷阱可能会导致无法实现优化。 MySQL 查询优化器会在执行查询前判断是否有一个索引能进行覆盖。

从下面的查询来看：

这里索引无法覆盖该查询，有两个原因：

可以重新查询并巧妙地设计索引，先将索引扩展至覆盖三个数据列（actor、title、prod_id），然后如下方式重写查询：

这种方式叫做延迟关联（deferred join），因为延迟了对列的访问。在查询的第一阶段 MySQL 可以使用覆盖索引，在 FROM 子句的子查询中找到匹配的 prod_id，然后根据这些 prod_id 值在外层查询匹配获取需要的所有列值。

这种优化方式在数据量很大，符合条件的数据很小时，优化效果明显；在数据量很大，符合条件的数据很大时，效果不明显，因为大部分时间是花在读取和发送数据了；如果数据量很小，子查询反而会拖慢查询。

这里还有一点需要特别点出： InnoDB 的二级索引中还存放的是指向数据行的主键 ID。所以，除了索引列外，还有主键 ID 也可以在覆盖索引中使用。

MySQL 有两种方式可以生成有序的结果：通过排序操作；或者按索引顺序扫描。

MySQL 可以使用同一个索引既满足排序，又用于查找行。设计索引时应该尽可能地同时满足这两种任务。

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

还有一种情况下 ORDER BY 子句可以不满足索引的最左前缀的要求，就是前导列为常量的时候。可以在 WHERE 子句或者 JOIN 子句中对这些列指定了常量，就可以 “弥补” 索引的不足。

使用索引做排序的一个最重要的用法是当查询同时有 ORDER BY 和 LIMIT 子句的时候。

MyISAM 使用前缀压缩来减少索引的大小，可让更多索引放入内存中，某些情况可以极大提高性能。默认只压缩字符串，通过参数设置可以对整数做压缩。

MyISAM 压缩每个索引块的方法是，先完全保存索引块中的第一个值，然后将其他值和第一个值进行比较得到相同前缀的字节数和剩余的不同后缀部分，把这部分存储起来即可。

压缩块使用更少的空间，代价是某些操作可能更慢。 MyISAM 查找时无法再索引块使用二分查找而只能从头开始扫描。正序的扫描速度还不错，但是如果是倒序扫描，就惨了！

对于 CPU 密集型应用，压缩使得 MyISAM 在索引查找上要慢好几倍。

可以在 CREATE TABLE 语句汇总指定 PACK_KEYS 参数来控制索引压缩的方式。

重复索引指在相同的列上按照相同的顺序创建的相同类型的索引。

MySQL 的唯一限制和主键限制都是通过索引实现的。

冗余索引和重复索引有一些不同。如果创建了索引（A，B），再创建索引（A）就是冗余索引。

还有一种情况是将一个索引扩展为（A，ID），其中 ID 是主键，对于 InnoDB 来说主键列已经包含在二级索引中，这也是冗余。

大多数情况下都不需要冗余索引，应该尽快扩展已有的索引而不是创建新索引。但有时处于性能的考虑需要冗余，因为扩展已有的索引会导致其变得太大，从而影响其他使用该索引的查询的性能。

有时为了覆盖查询，也需要扩展索引。

一般来说，增加新索引将会对导致 INSERT、 UPDATE、 DELETE 等操作的速度变慢，特别是当新增加索引后导致达到了内存瓶颈的时候。

解决冗余索引和重复索引的方法很简单，删除这些索引即可，但首先要做的是找出这样的索引。

在决定哪些索引可以被删除的时候要非常小心。要考虑查询、排序等。可以使用 Percona 工具箱中的 pt-upgrade 工具来检查计划中的索引变更。

除了冗余索引和重复索引，可能还会有一些服务器永远不用的索引，完全是累赘，建议考虑删除。

索引可以让查询锁定更少的行。锁定超过需要的行会增加锁争用并减少并发性。

InnoDB 只有在访问行的时候才会对其加锁，而索引能够减少 InnoDB 访问的行数，从而减少锁的数量。

InnoDB 在二级索引上使用共享（读）锁，但访问主键索引需要排他（写）锁。

现在有表如下：

如下查询是否符合三星索引的标准：

根据上面的分析，我们得到了两个可选项：(last_name, city_id, first_name, cust_id) 或 (city_id, last_name, first_name, cust_id)。那么，我们改如何选择呢？

前面的 选择合适的索引列顺序 中，提到了如何选择索引列顺序的一条经验法则：将选择性最高的列放到索引最前列。在不考虑其他业务，只关注当前查询SQL的情况下，我们可以遵循这条法则。前文 选择合适的索引列顺序 提到一个确定字段选择性的示例 SQL，这里修改如下：

我们只需要根据这里的结构，选择数字最大的字段在前面即可。根据结果，更合适的索引序列为：(city_id, last_name, first_name, cust_id)。

结合 MySQL InnoDB 引擎的自身特性，(city_id, last_name, first_name, cust_id) 是最佳方案吗？为什么？

下面，来看一下带有范围谓词的示例：

这个查询该如何建立“三星索引”呢？

综上，理想索引会有几颗星呢？首先，它一定能有第三颗星。其次，只能有第一颗星或第二颗星，不能同时拥有两者。换句话说，我们只能二选一：

具体选择，就要看业务需求。

需要看看哪些列拥有很多不同的取值，哪些列在 WHERE 子句中出现得最频繁。有更多不同值的列上创建索引的选择性会更好。

损坏的索引导会导致查询返回错误的结果或者莫须有的主键冲突等问题，严重时甚至还会导致数据库的崩溃。

CHECK TABLE 通常能够找出大多数表和索引的错误。

REPAIR TABLE 来修复损坏的表。

如果存储引擎不支持，也可以通过一个不做任何操作的 ALTER 操作来重建表。

如果 InnoDB 引擎的表出现了损坏，那一定是发生了严重的错误，需要立刻调查一下原因。

如果遇到数据损坏，最重要的是找出是什么导致了损坏，而不只是简单地修复，否则很有可能还会不断损坏。

MySQL 优化器使用的是基于成功的模型，而衡量成本的主要指标就是一个查询需要扫描多少行。如果信息不准确，优化器可能做出错误的决定。

ANALYZE TABLE 来重新生成统计信息。

SHOW INDEX FROM 来查看索引的基数（Cardinality）。

InnoDB 的统计信息值得深入研究。 InnoDB 引擎通过抽样的方式来计算统计信息，首先随机地读取少量的索引页面，然后以此为样本计算索引的统计信息。

InnoDB 会在表首次打开，或者执行 ANALYZE TABLE，抑或表的大小发生非常大的变化时计算索引的统计信息。

B-Tree 索引可能会碎片化，这会降低查询的效率。碎片化的索引可能会以很差或者无序的方式存储在磁盘上。

根据设计，B-Tree 需要随机磁盘访问才能定位到叶子页，所以随机访问是不可避免的。然而，如果叶子页在物理分布上是顺序且紧密的，那么查询的性能就会更好。否则，对于范围查询、索引覆盖扫描等操作来说，速度可能会降低很多倍；对于索引覆盖扫描这一点更加明显。

如果叶子页在物理分布上是顺序且紧密的，那么查询的性能就会更好。

数据存储的碎片化有三种类型：

对于 MyISAM 表，这三类碎片化都可能发生。但 InnoDB 不会出现短小的行碎片；InnoDB 会移动短小的行并重写到一个片段中。

OPTIMIZE TABLE 或者导出再导入的方式重新整理数据。

对不支持 OPTIMIZE TABLE 的存储引擎，可以通过一个不做任何操作的 ALTER TABLE 操作来重建表。只需要将表的存储引擎修改为当前的引擎即可：