索引在MYSQL中也叫键（key），其基本功能是：存储引擎用于快速找到记录的一种数据结构。
不恰当的索引在数据量小时，对性能影响不明显，当数据量逐渐增大时，性能会急剧下降。
索引是对查询性能优化最有效的手段，一个“最优”的索引有时比“好的”索引性能提高好几个数量级。而创建一个“最优”索引经常需要重写查询。

5.1 索引基础

5.1.1 索引的类型

Mysql中，索引是存储引擎层而不是服务器层实现的。

B-Tree 索引

实际上B-Tree索引大多是B+Tree索引，区别在于增加了每个叶子节点都包含了指向下一个叶子节点的指针（方便叶子节点的范围遍历）。本书只讨论B+Tree结构。
MyISAM：前缀压缩使得索引更小，索引通过数据的物理位置引用被索引的行。
InnoDB：按照原数据格式存储，根据主键引用被索引的行。
B-Tree索引通常意味所有的值都是按顺序存储的，并且每个叶子页到根的距离相同。存储引擎不再需要进行全表扫描，取而代之的是从索引的根节点开始搜索，通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点，找到结果。如图5-1：
image.png
叶子节点的指针指向的是被索引的数据，而不是其他节点页。图5-1绘制了一个节点和其叶子节点关系，其实根节点和叶子节点之间的层数和表的大小直接相关。
B-Tree对索引列是顺序组织的，所以很适合查找范围数据。
多列索引的保存结构如图5-2：
image.png
可以使用B-Tree索引的查询类型：

  • 全值匹配
  • 最左前缀
  • 列前缀
  • 范围值
  • 精确匹配某一列并范围匹配另外一列
  • 只访问索引的查询

查询还可以用于查询中的ORDER BY操作，一般来说，如果可以通过B-Tree找到数据，那么也可以通过order by这些条件来进行排序。
B-Tree索引的限制：

  • 如果不是按照索引的最左列开始查找，则无法使用索引
  • 不能跳过索引中的列

  • 如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找

    哈希索引

    哈希索引（hash index）基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每行数据，会把索引列计算出一个哈希码（hash code），将哈希码存储在哈希索引中，同时在哈希表中保存指向每个数据行的指针。
    MySQL中，Memory和NDB显示支持哈希索引，Memory引擎支持非唯一哈希索引，当出现多个一样的哈希值时，索引会以链表的方式存放多个记录指针到同一个哈希条目中（哈希条目对应的槽号是顺序的，但是数据行不是）。
    哈希索引限制：

  • 不能使用索引来避免读取行

  • 无法用于排序
  • 不支持部分索引列匹配查找
  • 只支持等值比较查询（=, IN(), <=>），不支持范围查询
  • 访问哈希索引的数据非常快，除非有很多哈希冲突，当发生冲突时需要遍历链表
  • 如果哈希冲突很多，一些索引维护成本代价也会很高

InnoDB引擎有一个特殊功能“自适应哈希索引（adaptive hash index）”。当InnoDB注意到某些索引值使用得非常频繁时，会在内存中基于B-Tree索引之上再创建一个哈希索引，让B-Tree索引也具有哈希索引的一些优点。这是一个自动的内部行为，用户无法控制或配置（可以关闭该功能）。
因此：

  • InnoDB用户无法手动创建哈希索引：InnoDB不支持哈希索引；
  • InnoDB自适应哈希索引，InnoDB自己会建立相关哈希索引：InnoDB支持哈希索引；

InnoDB和MyISAM都无法用户侧使用hash索引，及时创建索引时可以指定hash索引，但是本质还是通过B-Tree实现，可以通过 SHOW INDEXES FROM 看到具体索引情况。

空间数据索引（R-Tree）

MyISAM支持，InnoDB不支持。R-Tree可以用作地理数据存储，无须前缀查询可任意维度组合，空间索引会从所有维度来索引数据。必须使用GIS相关函数来维护数据。数据库PostgreSQL的插件PostGIS做的比较好。

全文索引

查找的是文本中的关键词，而不是直接比较索引中的值。类似搜索引擎要做的事情。适用MATCH AGAINST操作，而不是普通的WHERE条件操作。
要注意：听用词、词干和复数、布尔搜索等。

其他索引类别

5.2 索引的优点

索引优点：

  • 可以大大减少了服务器需要扫描的数据量
  • 可以帮助服务器避免排序和临时表
  • 可以将随机I/O变为顺序I/O

“三星索引系统”（three-star system）：索引将相关的记录放到一起则获得一星；索引中的数据顺序和查询中的排序顺序一致则获得二星；索引中的列包含了查询中需要的全部列则获得三星。

索引总是最好的解决方案？ 小的表：大部分情况下简单的全表扫描更高效 中到大型的表：索引非常有效 特大型表：建立和维护索引成本随之增加，可以使用分区技术，区分出查询需要的一组数据 数据特别多：建立一个元数据信息表，用来查询需要用到的某些特性。（例如执行那些需要聚合在多个表的数据的查询，则需要记录“哪个用户的信息存在哪个表”的元数据） TB级别的数据：定位单条记录的意义不大，所以经常会使用块级别的元数据技术来替代索引。

5.3 高性能的索引策略

5.3.1 独立的列

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

5.3.2 前缀索引和索引选择性

一般情况下，某个列前缀的选择性也是足够高的，足以满足查询性能。（在MYSQL中对于BLOB、TEXT或很长的VARCHAR类型的列，必须使用前缀索引。）诀窍在于要选择足够长又不能太长的前缀数，使得前缀索引的选择性接近于索引整个列。
计算完整列的选择性：

  1. # 结果是 0.0312
  2. SELECT COUNT(DISTINCT city)/COUNT(*) FROM city_demo

选择性保留3位数，则是0.031，当前缀索引的选择性（或叫基数）接近这个数就可以了：、

  1. # 结果是 0.0239, 0.0293, 0.0305, 0.0309, 0.0310
  2. SELECT COUNT(DISTINCT LEFT(city, 3))/COUNT(*) AS sel3,
  3.     COUNT(DISTINCT LEFT(city, 4))/COUNT(*) AS sel4,
  4.   COUNT(DISTINCT LEFT(city, 5))/COUNT(*) AS sel5,
  5.   COUNT(DISTINCT LEFT(city, 6))/COUNT(*) AS sel6,
  6.   COUNT(DISTINCT LEFT(city, 7))/COUNT(*) AS sel7
  7. FROM city_demo

可以看到当前缀长度为7时，已经接近目标基数了，再增长对于性能提升幅度不大，而且会增加维护成本。
如果数据分布不很均匀，可能就会有陷阱，导致通过前缀索引查询的结果有很多。
前缀索引缺点：

  • 无法使用前缀索引做ORDER BY 和 GROUP BY

  • 无法实现覆盖扫描

    5.3.3 多列索引

    常见错误：

  • 为每个列创建独立的索引

  • 按照错误的顺序创建多列索引

索引合并：MySQL5.0 及更新版本引入了一定程度上可以利用表上的多个单列索引来定位指定的行，当查询时同时使用两个单列索引进行扫描，并将结果进行合并。这种算法有三个变种：OR条件的联合（union），AND条件的相交（intersection），组合前两种。

  1. # 形如：
  2. SELECT film_id, actor_id FROM file_actor WHERE actor_id = 1 OR film_id = 1

与此同时，索引合并呈现的问题是：

  • 此表索引有优化空间，可以通过一个多列索引来实现功能
  • 通常会消耗大量CPU、内存资源在缓存、排序和合并操作
  • 可能被优化器低估查询成本，导致性能可能不如全表扫描

参数 optimizer switch可以关闭索引合并功能，或者使用 IGNORE INDEX 来忽略某个索引。

5.3.4 选择合适的索引列顺序

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

  • 如果不考虑排序和分组，将选择性最高的列放在最前面通常是优解
  • 需要考虑最差情况的选择性（比如默认赋值，这时候的查询可能会让整个系统崩溃），这时有可能需要重构程序

  • 需要分组、排序和范围查询时，需要根据具体数据量来平衡选择出优解

    5.3.5 聚簇索引

    聚簇索引（在Oracle叫“索引组织表”）是一种数据存储方式（不是一种索引类型），在同一个结构中保存了B-Tree索引和数据行。数据行存放在索引的叶子页中（因为无法把数据行同时存在两个不同的地方，所以一个表只有一个聚簇索引）。
    “聚簇”：数据行和相邻的键值紧凑地存储在一起（这并非总成立）。
    图5-3为聚簇索引数据存放方式，叶子页存了行数据，节点页只存了索引列（InnoDB中，该索引列为主键）：
    image.png
    如果InnoDB表没有设置主键，则引擎会自动选择一个唯一的非空列作为主键，再没有则会隐式定义一个主键。
    InnoDB只聚集在同一个页面中的记录，包含相邻键值的页面可能会相距甚远。
    聚簇索引优点：

  • 相关数据保存在一起，可能可以减少I/O

  • 数据访问更快，因为键值与数据保存在同一个B-Tree中
  • 使用覆盖索引扫描的查询可以直接使用叶节点中的主键值

聚簇索引缺点：

  • 如果数据全放在内存中，减少了I/O，优势就不明显了
  • 插入速度严重依赖插入顺序，若按照主键顺序插入则速度最快，否则插入后最好使用 OPTIMIZE TABLE 命令重新组织表
  • 更新聚簇索引列的代价高，InnoDB会强制将每个被更新的行移动到新的位置
  • 插入行或主键被更新导致移动行时，可能面临“页分裂”的问题。当行的主键值要求必须将这一行插入到某个已满的页中时，存储引擎会将该页分裂成两个页来存
  • 可能导致全表扫描变慢，当行比较稀疏或页分裂导致不连续时
  • 二级索引（非聚簇索引）可能比想象的要大，叶子节点包含了引用行的主键列（不是物理位置指针）
  • 二级索引访问需要两次索引查找（，自适应哈希索引能减少这样的重复工作），甚至可能更多次（当行更新的时候可能无法存储在原来的位置，这会导致表中出现行的碎片化或者移动行并在原位置保存“向前指针”）

    InnoDB 和 MyISAM 的数据分布对比

    以下表为例：
    1. CREATE TABLE layout_test (
    2.  col1 int NOT NULL,
    3.  col2 int NOT NULL,
    4.  PRIMARY KEY(col1),
    5.  KEY(col2)
    6. );
    主键 col1 取值1 ~ 10000，随机插入并做 OPTIMIZE TABLE 优化（画外音：数据在磁盘的存储方式已最优，但行顺序是随机的）。col2 随机赋值 1 ~ 100。

    1. MyISAM

    按照数据插入顺序存储在磁盘。
    image.png
    image.png
    image.png
    MyISAM的主键索引和其他索引区别在于，前者是一个名为PRIMARY的唯一非空索引。

    2. InnoDB

    image.png
    image.png
    图5-7为InnoDB的聚簇索引，该结构包含了整个表，而不止有索引，聚簇索引“就是”表，所以不像MyISAM需要独立的行存储。
    聚簇索引的每一个叶子节点都包含了主键值、事务ID、用于事务和MVCC的回滚指针以及所有的剩余列。
    二级索引的叶子节点存储的不是行指针，而是主键值，以此为指向行的“指针”。减少了出现行移动或者数据页分裂时二级索引的维护工作，同时增加了占用空间。如图5-8。

    如果还心存疑问，请往下后后看。

在 InnoDB 表中按主键顺序插入行

可以定义一个自增列作为主键，避免随机（不连续且值的分布范围非常大）的聚簇索引，特别是I/O密集型的应用。（例如：用UUID作为聚簇索引会很糟糕，它使得聚簇索引的插入变得完全随机，使得数据没有任何聚集特性）
如图5-10所示，主键的值是顺序的，所以InnoDB把每一条记录都存储在上一条记录的后面。当达到最大填充因子时（InnoDB中默认值为页大小的15/16，流出的空间用于以后修改），下一条记录会写到新页中。（二级索引页可能是不一样的）
image.png
如图5-11，主键的值不一定比前一条插入的大，所以InnoDB无法简单地总把新行插入到最后，而要寻找合适的位置——通常是已有数据的中间位置——并且分配空间。其缺点：

  • 增加很多额外工作
  • 导致数据分布不够优化
  • 可能导致大量随机I/O（目标页不在内存时，要从磁盘读取目标页到内存中）
  • 频繁地做页分裂，移动大量数据，修改三个页
  • 页变得稀疏并被不规则地填充，最终数据会有碎片

在载入随机主键行到聚簇索引后，也许要做一次 OPTIMIZE TABLE 来重建表并优化页的填充。
image.png

顺序主键什么时候会造成更坏的结果？

  • 并发插入：
    • 间隙锁竞争
    • 热点AUTO_INCREMENT锁机制

5.3.6 覆盖索引

MySQL如果通过索引叶子节点中已包含查询需要的所有数据，则不需要回表再查一次，这种索引就是“覆盖索引”。因此只有B-Tree索引才能实现。
覆盖索引的好处：

  • 极大减少数据访问量。对于I/O密集型的应用很有帮助，因为索引更小，容易全部加载到内存中。
  • 索引按照列值顺序存储（至少单个页内如此），甚至可以通过 OPTIMIZE 使得索引完全顺序排列，这让简单的范围查询能使用完全顺序的索引访问。
  • 一些存储引擎（如MyISAM）在内存中只缓存索引，数据则依赖于操作系统来缓存，因此要访问数据需要一次系统调用（这可能会导致严重性能问题）。
  • 如果二级索引能够覆盖查询，则能避免对主键索引的二次查询。

在EXPLAIN的Extra列可以看到“Using index”的信息时，表明查询可以使用覆盖索引。
例：

  1. # 原查询
  2. SELECT * FROM products WHERE actor='SEAN CARREY' AND title lieke '%APOLLO%'

优化如下：

  1. 创建索引(actor, title, prod_id)

  2. 重写查询：

    1. # 优化结果
    2. SELECT * FROM products JOIN (
    3. SELECT prod_id FROM products WHERE actor='SEAN CARREY' AND title lieke '%APOLLO%'
    4. ) AS t1 ON (t1.prod_id = products.prod_id)

    这中方式叫“延迟关联”。

    5.3.7 使用索引扫描来做排序

    MySQL生成有序结果的方式：

    • 通过排序操作（EXPLAIN的type为“filesort”）
    • 按索引顺序扫描（EXPLAIN的type为“index”）

用索引对结果做排序的条件：

  • 只有当索引的列顺序和ORDER BY子句的顺序完全一致，且所有列的排序方向（asc 或 desc）都一致时。
  • 如果查询需要关联多张表，则只有当ORDER BY子句引用的字段全部为第一表时。

  • 需要满足最左前缀的要求（或前导列为常量）。

    5.3.8 压缩（前缀压缩）索引

    只针对MyISAM引擎。

    5.3.9 冗余和重复索引

    重复索引：在相同的列上按照相同的顺序创建的相同类型的索引，这是应该避免和需要删除掉的。（key(col) 和 fulltext key(col) 是不同类型的索引。）
    冗余索引：若有B-Tree索引(A, B)，再创建B-Tree索引(A)就是冗余索引。或者已有索引(A)，再创建(A, ID)。大多数情况下都不需要冗余索引，应该扩展现有的索引列，但也有时候出于性能方面的考虑需要冗余的索引。

    5.3.10 未使用的索引

    服务器永远不用的索引，要删除掉。

    5.3.11 索引和锁

    索引可以让查询锁定更少的行，如果查询从不访问那些不需要的行，那么就会锁定更少的行。好处在于：

  • 减少额外锁定多行的开销

  • 减少锁争用，提高并发性

InnoDB只有在访问行的时候才会对其加锁，索引能够减少InnoDB访问的行数，从而减少锁的数量。但这只有当InnoDB在存储引擎能够过滤掉所有不需要的行时才有效，否则在InnoDB检索到的数据放回给服务器层以后，MySQL服务器才能应用WHERE子句（MySQL5.6可能有优化），这时已无法避免锁定了，直到适当的时候才释放。（MySQL5.1及之后版本，InnoDB可以在服务器端过滤掉行后就释放锁。之前的版本需要提交事务才释放锁。）
即使使用了索引，InnoDB也有可能锁住一些不需要的数据。但如果没有使用索引，MySQL会全表扫描，锁住所有的行。如下例：

  1. SELECT actor_id FROM actor WHERE actor_id < 5 AND actor_id <> 1 FOR UPDATE;

InnoDB的B-Tree索引获取actor < 5的记录，然后将数据返回到MySQL服务器层，再使用WHERE条件来过滤出查询结果（可以通过EXPLAIN的Extra看到“Using where，Using index”，其中 Using where 表明MySQL服务器层使用where条件来过滤数据）。
细节：InnoDB在二级索引上使用共享锁，但访问主键索引需要排它锁。这消除了使用覆盖索引的可能性，并且使得 SELECT FOR UPDATE 比 LOCK IN SHARE MODE 或 非锁定查询 要慢很多。

5.4 索引案例学习

5.5 维护索引和表

正确地创建了合适的索引之后，还需要维护表和索引来确保都正常高效地工作。目的：

  • 找到并修复损坏的表
  • 维护准确的索引统计信息

  • 减少碎片

    5.5.1 找到并修复损坏的表

    表损坏：对于MyISAM通常是系统崩溃导致，其他引擎也会由于硬件问题、MySQL或操作系统问题导致。InnoDB的设计一般不容易损坏。
    索引损坏会导致查询返回错误的结果或莫须有的主键冲突等，甚至导致数据库崩溃。
    如果遇到古怪问题可以尝试运行 CHECK TABLE 来找出大多数表或索引的错误，用 REPAIR TABLE 修复。但不是所有引擎都支持这两命令（或通过不做操作的ALTER来重建表 ALTER TBALE tbl ENGINE=INNODB;）。

    5.5.2 更新索引统计信息

    MySQL通常会通过两个API了解存储引擎的索引值分布，以决定如何使用索引：

  • records_in_range( )

  • info( )

前者向存储引擎传入两个边界值获取范围内大概数据量（MyISAM是精确值，InnoDB是估算值）。后者返回各种类型的数据，包括索引的基数（索引列有多少个取值，每个键值有多少数据）。
若API返回数据不准确，或执行计划本身太复杂以致无法准确获取各个阶段匹配的行数，则优化器会使用索引统计信息来估算扫描行数。MySQL优化器使用的是基于成本的模型，而衡量成本的主要指标就是查询需要扫描行数。若统计信息偏离，优化器就可能做出错误的决定。
可通过 ANALYZE TABLE 来重新生成统计信息，其运行成本：

  • MyISAM：索引统计信息存在磁盘中，运行需要一次全索引扫描来计算索引基数。整个过程需要锁表。
  • InnoDB：直到MySQL5.5，不在磁盘存储索引统计信息，而是通过随机索引访问进行评估并存在内存。

可通过 SHOW INDEX FROM 查看索引基数（Cardinality）。
InnoDB通过抽样来计算统计信息，随机读取少量索引页面（新版本可设置不为8）。当表首次打开，或执行了 ANALYZE TABLE，或表的大小发生非常大的变化（十六分之一或新增20亿）会触发索引统计。

5.5.3 减少索引和数据的碎片

B-Tree索引可能会碎片化以很差或无序的方式存储在磁盘上，降低查询效率。
根据设计B-Tree需要随机磁盘访问才能定位到叶子页，若叶子页在物理分布上是顺序且紧密的，则查询性能会提升，否则对于范围查询、索引覆盖扫描等操作的性能速度影响尤为明显。
表数据存储也可能碎片化，其复杂度比索引碎片化更高。
有三种类型的数据碎片：

  • 行碎片

数据行被存储为多个地方的多个片段中

  • 行间碎片

逻辑上顺序的页或者行，在磁盘上不是顺序存储的

  • 剩余空间碎片

数据页中有大量的空余空间
MyISAM可能发生这三类碎片化，InnoDB不会出现行碎片（会移动行并重写到一个片段中）。可以通过 OPTIMIZE TABLE 、ALTER TABLE 、删除再添加索引 或 导出再导入 等方式来重新整理数据。

5.6 总结