5.1 索引基础

索引是存储引擎用于快速找到记录的一种数据结构。

索引可以包含一个或多个列。如果索引包含多个列，那么列的顺序也十分重要，因为MySQL只能高效地使用索引的最左前缀列。创建一个包含两个列的索引，和创建两个包含一列的索引是大不相同的。

5.1.1 索引的类型

在MySQL中索引是存储引擎层而不是服务器层实现的。所以，并没有统一的索引标准：不同的存储引擎的索引工作方式并不一样，也不是所有的存储引擎都支持所有类型的索引。即使多个存储引擎支持同一个类型的索引，其底层的实现也可能不同。

B+Tree，每一个叶子节点都包含指向下一个叶子节点的指针。

B-Tree索引

InnoDB使用的是B+Tree。

B-Tree索引能够加快访问数据的速度。因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的从索引的根节点开始搜索。根节点的槽中存放了指向叶子节的指针，存储引擎根据这些指针向下层查找。通过比较节点的值和要查找的值可以找打合适的指针进入下层子节点，这些指针实际上定义了子节点页中值的上限和下限。最终存储引擎要么是找到对应的值，要么该记录不存在。
B-Tree对索引列是顺序组织存储的，所以很适合查找范围数据。例如，这一个基本文本域的索引树上，按字母顺序传递连续的值进行查找是非常合适的，所以像“找出所有以I到K开头的名字”这样的查找效率会非常高。

假设有如下数据表。

  1. CREATE TABLE People (
  2.   last_name     VARCHAR (50) NOT NULL,
  3.   first_name     VARCHAR (50) NOT NULL,
  4.   dob          DATE NOT NULL,
  5.   gender     ENUM ('m', 'f') NOT NULL,
  6.   KEY (last_name, first_name, dob)
  7. ) ;

对于表中的每一个行数据，索引包含了last_name,first_name,dob列的值。
需要注意的是，索引对多个值进行排序的依据是CREATE TABLE 语句中定义索引时列的顺序。如果两个人的姓和名都一样，则根据他们的出生日期来排列顺序。

可以使用B-Tree索引的查询类型

B-Tree索引适用于全键值、键值范围或键前缀查找。其中键前缀查找只适用于根据最左前缀的查找。前面所述的索引对如下类型的查询是有效

  • 全值匹配：全值匹配指的是和索引中的所有列进行匹配
  • 匹配最左前缀：即只使用索引的第一列
  • 匹配列前缀：只匹配某一列的值开头的部分。
  • 匹配范围值：
  • 精确匹配某一列并范围匹配另外一列：例如查找所有姓为Allen并且名字是字母K开头的人，即第一列last_name全匹配，第二列first_name范围匹配。
  • 只访问索引的查询：B-Tree通常可以支持“只访问索引的查询”，即查询值需要访问索引，而无须访问数据行。(覆盖索引)

因为索引树的节点是有序的，所以除了按值查找之外，索引还用于查询中的ORDER BY操作(按顺序查找)。一般来说，如果B-tree可以按照某种方式查找到值，那么也可以按照这种方式用于排序。所以，如果ORDER BY子句满足前面列出的几种查询类型，则整个索引也可以满足对应的排序需求。
下面是一些关于B-Tree索引的限制

  • 如果不是按照索引的最左列开始查找，则无法使用索引。例如上面的例子中的索引无法用于查找名字为bill的人，也无法查找某个特定生日的人，因为这两列都不是最左数据列。类似地，也无法查找姓氏以某个字母结尾的人。
  • 不能跳过索引中的列。也就是说，前面所述的索引无法用于查找姓为Smith并且在某个特定的日期出生的人。如果不指定名(first_name)，则MySQL只能使用索引的第一列。
  • 如果查询中有某个列的范围查询，则其右边所有的列都无法使用索引优化查询。例如查询where last_name='Smith' and fitst_name like 'J%' and dob='1976-12-23'，这个查询只能使用索引的前两列，因为这里like是一个范围条件(但是服务器可以把其余的列用于其他目的)。如果范围查询列值的数量有限，那么可以通过使用多个等于条件来替代范围查询。

也有些限制并不是B-Tree本身导致的，而是MySQL优化器和存储引起使用索引的方式导致的，这部分限制在未来的版本中可能就不再是限制了。

哈希索引

哈希索引(hash index)基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引哈希计算一个哈希码，哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时哈希表中保存指向每个数据行的指针。
在MySQL中，只有Memory引擎显示支持哈希索引。这也是Memory引擎的默认索引类型，Memory引擎同时也支持B-Tree索引。值得一提的是，Memory引擎是支持非唯一哈希索引的，这这数据库世界里面是比较与众不同的。如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。

CREATE TABLE testhash(
fname VARCHAR (50) NOT NULL,
lname VARCHAR (50) NOT NULL,
KEY USING HASH(fname)
)ENGINE=MEMORY;
insert into testhash values('Arjen','Lentz'),('Baron','Schwartz'),('Peter','Zaitsev'),('Vadim','Tkachenko');

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

  • 哈希索引只包含哈希值和行指针，而不存储字段值，所以不能够使用索引中的值来避免读取行。不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能的影响并不明显。
  • 哈希索引数据并不是按照索引值顺序存储，所以也无法用于排序。
  • 哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如，在数据列(A,B)上建立索引，如果查询只有数据量A，则无法使用该索引。
  • 哈希索引只支持等值比较查询，包括= in <>，也不支持任何范围查询。
  • 访问哈希索引的数据非常快，除非有很多哈希冲突。当出现哈希冲突的时候，存储引擎必须遍历链表中的所有行指针，逐行进行比较，直到找到所有符合条件的行。
  • 如果哈希冲突很多的话，一些索引维护操作的代价也会很高。例如，如果某个选择性很低(哈希冲突很多)的列上建立哈希索引，那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应的引用。冲突越多，代价越大。

如果采用这种方式，记住不要使用SHA1()和MD5()作为哈希函数，因为这两个函数计算出来的哈希值是非常长的字符串，，会浪费大量空间，比较时也比较慢，SHA1()和MD5()是强加密函数，设计目标是最大限度消除冲突。

处理哈希冲突。当使用哈希索引进行查询的时候，必须在WHERE子句中包含常量值。
select id from url where url_crc=CRC32('http://www.mysql.com') and url='htp://www.mysql.com'

空间数据索引(R-Tree)

MyISAM表支持空间索引，可以作为地里数据存储。和B-Tree索引不同，这类索引无须前缀查询。空间索引会从所有维度来检索数据。查询时，可以有效地使用任意维度来组合查询。必须使用MySQL的GIS相关函数来维护数据。MySQL的GIS支持并不完善，所以大部分人都不会使用和这个特性。开源关系数据库系统中对GIS的解决方案做得比较好的是PostgreSQL的PostGIS。

全文索引

全文索引是一种比较特殊类型的索引，它查找的是文本中的关键字，而不是直接比较索引中的值。全文搜索和其他几类索引的匹配方式完全不一样。它有许多需要注意的细节，如停用词，词干和复数，布尔搜索等。全文索引更类似于搜索引擎做的事情，而不是简单的WHERE条件匹配。
在相同的列上同时创建全文索引和基于值的B-Tree索引不会有冲突，全文索引适用于MATCH AGAINST操作，而不是普通的WHERE条件操作。

5.2 索引的优点

索引可以让服务器快速地定位到指定的位置。但这并不是索引的唯一作用。
最常见的B-Tree索引，按照顺序存储数据，所以MySQL可以用来做ORDER BY和GROUP BY操作。因为数据是有序的，所以B-Tree也就会将相关的列值存储在一起，最后，因为索引中存储了实际的列值，所以某些查询只使用索引就能够完成全部查询，据此特性，总结下来索引有如下三个优点。

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

5.3 高性能的索引策略

5.3.1 独立的列

“独立的列”是指索引列不能是表达式的一部分，也不能是函数的参数。
例如：select actor_id from skaila.actor where actor_id+1=5

5.3.2 前缀索引和索引选择性

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

使用示例库Sakila的数据，从中生成一个实例表，以进行演示。

CREATE TABLE sakila.city_demo (city VARCHAR(50) NOT NULL );
INSERT INTO sakila.city_demo(city) SELECT city FROM sakila.city;
-- replace the next statement five times;
INSERT INTO sakila.city_demo(city) SELECT city FROM sakila.city_demo;
UPDATE sakila.`city_demo` SET city= (SELECT city FROM sakila.city ORDER BY RAND() LIMIT 1 );

SELECT COUNT(*) AS cnt ,city 
FROM sakila.`city_demo` GROUP BY city ORDER BY cnt DESC LIMIT 10;

查找上面每个值最频繁出现的城市前缀，先从3个前缀字母开始。

SELECT COUNT(*) AS cnt ,LEFT(city,3) AS pref
FROM sakila.`city_demo`  GROUP BY pref ORDER BY cnt DESC LIMIT 10;

创建前缀索引

ALTER TABLE sakila.`city_demo` ADD KEY(city(7));

前缀索引是一种使索引更小，更快的有效方法，但另一个方面也有其缺点：MySQL无法使用前缀索引做ORDER BY和GROUP BY，也无法使用前缀索引做覆盖索引。
**

5.3.5 聚簇索引

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。具体的细节依赖于其实现方式，但InnoDB的聚簇索引实际上在同一个结构保存了B-Tree索引和数据行。
当表有聚簇索引时，它的数据行实际上存放在索引的叶子页，术语“聚簇”表示数据行和相邻的键值紧凑地存储在一起。因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。
因为存储引擎主要是负责实现索引，因此不是所有的存储引擎都支持聚簇索引。本节关注InnoDB。

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

  • 可以把相关的数据保存在一起。例如实现电子邮箱时，可以根据用户ID来聚集数据，这样只需要从磁盘读取少数的数据页就能获取某个用户的全部邮件。如果没有使用聚簇索引，则每封邮件都可能导致一次磁盘I/O。
  • 数据访问更快。聚簇索引将索引和数据保存在同一B-Tree中，因此从聚簇索引中获取数据通常比在非聚簇索引中查找要快。
  • 使用覆盖索引扫描的查询可以直接使用页节点的主键值。

如果在设计表和查询时能够充分利用上面的优点，那就能极大地提升性能。同时，聚簇索引也有一些缺点。

  • 聚簇数据最大限度地提高了I/O密集型应用的性能。但如果数据全部都放在内存中，则访问的顺序就没那么重要了，聚簇索引也就没有什么优势了。
  • 插入速度严重依赖于插入顺序。按照主键的顺序插入是加载数据到InnoDB表中速度最快的方式。但如果不是按照主键顺序加载数据，那么在加载完成后最好使用OPTIMIZE TABLE命令重新组织一下。
  • 更新聚簇索引列的代价很高，因为会强制InnoDB将每个被更新的行移动到新的位置。
  • 基于聚簇索引的表在插入新行，或者主键被更新导致需要移动行的时候，可能面临“页分裂”的问题。当行的主键值要求必须将这一行插入到某个已满的页中时，存储引擎会将页分裂成两个页面来容纳该行，这就是一次页分裂操作。页分页会导致表占用更多的磁盘空间。
  • 聚簇索引可能导致全表扫描变慢，尤其是行比较稀疏，或者由于页分裂导致数据存储不连续的时候。
  • 二级索引(非聚簇索引)可能比想象的要更大，因为在二级索引的叶子节点包含了引用行的主键列。
  • 二级索引访问需要两次索引查找，而不是一次。

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

如果正在使用InnoDB表并且没有什么数据需要聚集，那么可以 定义一个代理键作为主键，这种主键的数据应该和应用无关，最简单的方法是使用AUTO_INCREMENT自增列，这样就可以保证数据行式按顺序写入，对于根据主键做关联操作的性能也会更好。

最好避免随机的(不连续且值的分布范围非常大)聚簇索引，特别是对于I/O密集型的应用。例如，从性能的角度考虑，使用UUID来作为聚簇索引则会很糟糕：它使得聚簇索引的插入变得完全随机，这是最坏的情况，使得数据没有任何聚集特性。

使用DDUI主键插入行不仅花费更长的时间，而且索引占用的空间也更大。这一方面是由于主键字段更长，另一方面毫无疑问是由于页分裂和碎片导致的。

UUID聚簇索引的问题：

  • 写入的目标也可能已经刷新到磁盘上并从缓存中移除，或者是还没有被加载到缓存中，InnoDB在插入之前不得不先找到并从磁盘读取目标也到内存中。这将导致大量的随机I/O。
  • 因为写入时乱序的，InnoDB不得不频繁地做页分页操作，以便为新的行分配空间。页分裂会导致移动大量数据，一次插入最少需要修改三个页而不是一个页。
  • 由于频繁的页分页，页也变得稀疏并将不规则地填充，所以最终数据有碎片。

5.3.6 覆盖索引

如果一个索引包含(或者说覆盖)所有需要查询的字段的值，我们就称为“覆盖索引”。
覆盖索引是非常有用的工具，能够极大地提高性能。如果查询只需要扫描索引而无须会表，会带来很好好处：

  • 索引条目通常远小于数据行大小，所以如果只需要读取索引，那MySQL就会极大地减少数据访问量。这对于缓存的负载非常重要，因为这总情况下响应时间大部分花费在数据拷贝上。覆盖索引对于I/O密集型的应用也很有帮助，因为索引比数据更小，更容易全部放入内存中(这对于MyISAM尤其正确，因为MyISAM能压缩以变得更小)
  • 因为索引是按照列值顺序存储的(至少在单个页内是如此)，所以对于I/O密集型的范围查询会比随机磁盘读取每一行数据的I/O要少得多，对于某些存储引擎，甚至可以通过OPTIMZE命令使得索引完全顺序排列，这让简单的范围查询能使用完全顺序的索引访问、
  • 一些存储引擎如MyISAM在内存中值缓存索引，数据则依赖操作系统来缓存，因此要访问数据需要一次系统调用。这可能会导致严重的性能问题，尤其是那些系统调用占用了数据访问中的最大开销的场景。
  • 由于InnoDB的聚簇索引，覆盖索引对InnoDB表特别有用。InnoDB的二级索引在叶子节点中保存了行的主键值，所以如果二级索引主键能够覆盖查询，则可以避免对主键索引的二次查询。

不是所有类型的的索引都可以成为覆盖索引。覆盖索引必须要存储索引列的值，而哈希索引、空间索引和全文索引都不存储索引列的值，所以MySQL只能使用B-Tree索引做覆盖索引。另外，不同的存储引擎实现覆盖索引的方式也不同，而且不是所有的引擎都支持覆盖索引。
当发起一个被索引覆盖的查询是，在EXPLAIN的Extra列可以看到Using index 的信息。
image.png

索引覆盖查询还有很多陷阱可能会导致无法实现优化。MySQL查询优化器会在执行查询前判断是否有一个索引能进行覆盖，假设索引覆盖了WHERE条件中的字段，但不是整个查询涉及的字段，如果条件为假，MySQL和更早的版本也总是会表获取数据行，尽管并不需要这一行且最终会被过滤掉。

    -- 创建一个只有2个字段的表
    drop table if exists products;
    create table products (
      actor varchar(20),
      title varchar(20)
    );

    -- 创建覆盖所有字段的索引, 并未指定索引长度
    create index idx_prod_actor on products (actor);

    -- 索引执行LIKE操作, 查看explain结果
    explain select * from products   where actor = 'SEAN' and title like '%APOLLO%'  \G

5.3.7 使用索引扫描来做排序

MySQL有两种方式可以生成有序的结果：通过排序操作；或者按照索引顺序扫描；如果EXPLAIN出来的type列的值为index，则说明MySQL使用了索引扫描来做排序。

只有当索引的列顺序和ORDER BY子句的顺序完全一致，并且所有列的排序方向(倒叙或者正序)都一样时，MySQL才能够使用索引来对结果做排序。如果查询需要关联的过账表，则只有当ORDER BY子句引用的字段全部为第一个表时，才能使用索引做排序，ORDER BY子句和查找型号查询的限制是一样的：需要满足索引最左前缀的要求；否则，MySQL都需要执行排序操作，而无法利用索引排序。
有一种情况下ORDER BY子句可以不满足索引的最左前缀的要求，就是前导列为常量的时候。如果WHERE子句或者JOIN子句对这些列指定了常量，就可以“弥补”索引的不足。
例如示例数据库 rental在列(rental_date,inventory_id,customer_id) 上的索引

CREATE TABLE rental (
  rental_id INT NOT NULL AUTO_INCREMENT,
  rental_date DATETIME NOT NULL,
  inventory_id MEDIUMINT UNSIGNED NOT NULL,
  customer_id SMALLINT UNSIGNED NOT NULL,
  return_date DATETIME DEFAULT NULL,
  staff_id TINYINT UNSIGNED NOT NULL,
  last_update TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  PRIMARY KEY (rental_id),
  UNIQUE KEY  (rental_date,inventory_id,customer_id),
  KEY idx_fk_inventory_id (inventory_id),
  KEY idx_fk_customer_id (customer_id),
  KEY idx_fk_staff_id (staff_id),
  CONSTRAINT fk_rental_staff FOREIGN KEY (staff_id) REFERENCES staff (staff_id) ON DELETE RESTRICT ON UPDATE CASCADE,
  CONSTRAINT fk_rental_inventory FOREIGN KEY (inventory_id) REFERENCES inventory (inventory_id) ON DELETE RESTRICT ON UPDATE CASCADE,
  CONSTRAINT fk_rental_customer FOREIGN KEY (customer_id) REFERENCES customer (customer_id) ON DELETE RESTRICT ON UPDATE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

MariaDB [(none)]> EXPLAIN SELECT rental_id, staff_id FROM sakila.rental
    ->   WHERE rental_date = '2005-05-25'
    ->   ORDER BY inventory_id, customer_id \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: rental
         type: ref
possible_keys: rental_date
          key: rental_date
      key_len: 5
          ref: const
         rows: 1
        Extra: Using where
1 row in set (0.005 sec)

虽然ORDER BY 子句不满足索引的最左前缀要求，也可以用于排序，这是因为索引的第一列被指定为一个常数。
还有更多可以使用索引做排序查询示例。下面这个查询可以利用索引排序，是因为查询为索引的第一列提供了常量条件，而使用第二列进行排序，将两列组合在一起，就形成了索引的最左前缀：

... WHERE rental_date = '2005-05-25' ORDER BY inventory_id DESC;

下面这个查询也没有问题，因为ORDER BY使用的两列就是索引的最左前缀：

... WHERE rental_date >'2005-05-25' ORDER BY rental_date, inventory_id;

下面是一些不能使用索引做排序的查询

  • 下面这个查询使用了两种不同的排序方向，但是索引列时正序排列

    ... WHERE rental_date ='2005-05-25' ORDER BY inventory_id DESC,customer_id  AES;

  • 下面这个查询的ORDER BY子句中引用了一个不再索引中的列

    ... WHERE rental_date ='2005-05-25' ORDER BY inventory_id ,staff_id;

  • 下面这个查询的WHERE 和order by 中的列无法组合成索引的最左前缀：

    ... WHERE rental_date ='2005-05-25' ORDER BY customer_id;

  • 下面这个查询在索引列的第一列是范围条件，所以MySQL无法使用索引的其余列

    ... WHERE rental_date >'2005-05-25' ORDER BY inventory_id ,customer_id  ;

  • 这个查询在inventor_id列上有多个等于条件。对于排序来说，这也是一种范围查询：

    ... WHERE rental_date >'2005-05-25'  and  inventory_id in (1,2)ORDER BY   customer_id  ;

下面的这个例子可以使用索引进行关联排序，但由于编译器在优化时将film_actor当做关联的第二张表，所以实际上无法使用索引。

EXPLAIN select actor_id, title from sakila.film_actor 
inner join sakila.film using(film_id) order by actor_id ;

+------+-------------+------------+---------------------------------+
| id   | select_type | table      | Extra                           |
+------+-------------+------------+---------------------------------+
|    1 | SIMPLE      | film       | Using temporary; Using filesort |
|    1 | SIMPLE      | film_actor | Using index                     |
+------+-------------+------------+---------------------------------+