MySQL索引

整理一些MySQL索引相关的常见问题和内容。

索引的分类

按数据结构来分：B+树索引、Hash索引、Full-text索引

按物理存储来分：聚簇索引、二级索引

按字段特性来分：主键索引、唯一索引、普通索引、前缀索引

按字段个数来分：单列索引、联合索引

按数据结构分类

在创建表时，InnoDB会根据不同的场景选择不同的列作为索引：

如果有主键，默认会使用主键作为聚簇索引的索引键（key）；
如果没有主键，就选择第一个不包含 NULL 值的唯一列作为聚簇索引的索引键（key）；
在上面两个都没有的情况下，InnoDB 将自动生成一个隐式自增 id 列作为聚簇索引的索引键（key）；

其它索引都属于辅助索引，也被称为二级索引或非聚簇索引。创建的主键索引和二级索引默认使用的是 B+树索引。

B+树索引demo

创建一个商品表，以id作为主键：

CREATE TABLE `product`  (
  `id` int(11) NOT NULL,
  `product_no` varchar(20)  DEFAULT NULL,
  `name` varchar(255) DEFAULT NULL,
  `price` decimal(10, 2) DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE
) CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;

B+树是一种多叉树，只有叶子节点存放数据，且每个叶子节点的数据按照主键排序，每个叶子节点有前驱指针和后继指针，所有叶子节点构成一个双向链表，非叶子节点只存放索引；商品表的数据用主键索引的B+树存储如图所示：

通过主键查询数据的过程

1	select * from product where id = 5;

查询过程是这样的，B+树会自顶向下逐层进行查找：

将 5 与根节点的索引数据 (1，10，20) 比较，5 在 1 和 10 之间，所以根据 B+树的搜索逻辑，找到第二层的索引数据 (1，4，7)；
在第二层的索引数据 (1，4，7)中进行查找，因为 5 在 4 和 7 之间，所以找到第三层的索引数据（4，5，6）；
在叶子节点的索引数据（4，5，6）中进行查找，然后我们找到了索引值为 5 的行数据。

数据库的索引和数据都是存储在硬盘的，我们可以把读取一个节点当作一次磁盘 I/O 操作。那么上面的整个查询过程一共经历了 3 个节点，也就是进行了 3 次 I/O 操作。

通过二级索引查询数据的过程

主键索引的B+树和二级索引的B+树区别如下：

主键索引的B+树的叶子节点存放的是实际数据，所有完整的用户记录都存放在主键索引的B+树的叶子节点里；
二级索引的B+树的叶子节点存放的是主键值，而不是实际数据。

若把product表中的product_no字段设置为二级索引，则对应的B+树如下：

如果用二级索引查询数据，例如

1	select * from product where product_no = '0002';

则会优先检索二级索引对应的B+树，找到相应的叶子节点，获取到主键值，然后通过主键索引的B+树查询到相应的叶子节点并获取数据。这就是回表，即需要查两个B+树才能查到结果数据。

若查询的目标数据本来就存储在二级索引的B+树叶子节点里，则不需要进行回表操作，例如

1	select id from product where product_no = '0002';

id字段本身就存储在二级索引B+树的叶子节点中，因此不需要回表；这就是覆盖索引，即只需要查一个B+树就能获得数据。

为什么InnoDB选择B+树作为索引的数据结构

B+树 vs B树

B+树只在叶子节点存储数据，而B树的非叶子节点也要存储数据，所以B+树的单个节点数据量更小，在相同的IO次数下，能查询更多的节点；并且，B+树的叶子节点构成一个双向链表，适合MySQL中的范围顺序查找，B树无法做到这一点。
B+树 vs 二叉树

对于有N个叶子节点的B+树，其搜索复杂度为O(logdN)，其中d表示节点允许的最大子节点个数，一般是大于100的；而二叉树的节点所能允许的最大子节点个数为2，其搜索复杂度为O(logN)，因此需要更多IO次数才能查到目标。
B+树 vs Hash

Hash做等值查询时，搜索复杂度为O(1)，但无法实现范围查询，因此适用场景有限。

按物理存储分类

从物理存储的角度来看，索引分为聚簇索引（主键索引）、二级索引（辅助索引）。

这两个区别在前面也提到了：

主键索引的B+树的叶子节点存放的是实际数据，所有完整的用户记录都存放在主键索引的 B+Tree 的叶子节点里；
二级索引的B+树的叶子节点存放的是主键值，而不是实际数据。

所以，在查询时使用了二级索引，如果查询的数据能在二级索引里查询的到，那么就不需要回表，这个过程就是覆盖索引。如果查询的数据不在二级索引里，就会先检索二级索引，找到对应的叶子节点，获取到主键值后，然后再检索主键索引，就能查询到数据了，这个过程就是回表。

按字段特性分类

从字段特性的角度来看，索引分为主键索引、唯一索引、普通索引、前缀索引。

主键索引

主键索引就是建立在主键字段上的索引，通常在建表的时候一起创建，一张表最多有一个主键索引，索引列的值不允许有空值。

建表时，创建主键索引的方式如下：

CREATE TABLE table_name  (
  ....
  PRIMARY KEY (index_column_1) USING BTREE
);

唯一索引

唯一索引是建立在UNIQUE字段上的索引，一张表可以有多个唯一索引，索引列的值必须唯一，允许有空值。

建表时，创建唯一索引的方式如下：

CREATE TABLE table_name  (
  ....
  UNIQUE KEY(index_column_1,index_column_2,...) 
);

建表后，创建唯一索引的方式如下：

1 2	CREATE UNIQUE INDEX index_name ON table_name(index_column_1,index_column_2,...);

普通索引

普通索引就是建立在普通字段上的索引，没有任何要求。

建表时和建表后创建普通索引的方式分别如下：

CREATE TABLE table_name  (
  ....
  INDEX(index_column_1,index_column_2,...) 
);

1 2	CREATE INDEX index_name ON table_name(index_column_1,index_column_2,...);

前缀索引

前缀索引是指对字符类型字段的前几个字符建立的索引，而不是在整个字段上建立的索引，前缀索引可以建立在字段类型为char、varchar、binary、varbinary的列上。

使用前缀索引的目的是为了减少索引占用的存储空间，提升查询效率。

建表时和建表后创建前缀索引的方式分别如下：

CREATE TABLE table_name(
    column_list,
    INDEX(column_name(length))
);

1 2	CREATE INDEX index_name ON table_name(column_name(length));

按字段个数分类

从字段个数的角度来看，索引分为单列索引、联合索引（复合索引）。

建立在单列上的索引称为单列索引，比如主键索引；
建立在多列上的索引称为联合索引

联合索引

比如，将product表中的product_no和name字段组合成联合索引(product_no, name)，创建联合索引的方式如下：

1	CREATE INDEX index_product_no_name ON product(product_no, name);

其对应的B+树如图所示：

联合索引查询的B+树是先按product_no进行排序，然后在product_no相同的情况再按name字段排序。因此，使用联合索引时，存在最左匹配原则，也就是按照最左优先的方式进行索引的匹配。

比如，如果创建了一个(a, b, c)联合索引，如果查询条件是以下这几种，就可以匹配上联合索引：

where a = 1;
where a = 1 and b = 2 and c = 3;
where a = 1 and b = 2;

因为有查询优化器，所以 a 字段在 where 子句的顺序并不重要。

但是，如果查询条件是以下这几种，因为不符合最左匹配原则，所以就无法匹配上联合索引，联合索引就会失效：

where b = 2;
where c = 3;
where b = 2 and c = 3;

联合索引的最左匹配原则会一直向右匹配直到遇到「范围查询」就会停止匹配。也就是范围查询的字段可以用到联合索引，但是在范围查询字段的后面的字段无法用到联合索引。

例1：

1	select * from mytable where a > 2 and b = 1;

这条查询语句只有 a 字段用到了联合索引进行索引查询，而 b 字段并没有使用到联合索引。因为在a > 2的记录范围里，b是无序的，不能根据b = 1这个条件进一步减少扫描量。

例2：

1	select * from mytable where a >= 1 and b = 2;

这条查询语句 a 和 b 字段都用到了联合索引进行索引查询。虽然在a >= 1的二级索引记录范围内，b是无序的，但是对于符合a = 1的二级索引记录的范围里，b字段的值是「有序」的。

例3：

1	select * from mytable where a between 2 and 8 and b = 2;

查询条件为2 <= a <= 8和b = 2。因此类似于例2，这条查询语句 a 和 b 字段都用到了联合索引进行索引查询。

例4：

1	select * from mytable where name like 'j%' and age = 22;

与例3和例2同理，这条查询语句 name 和 age 字段都用到了联合索引进行索引查询。

索引下推

对于联合索引(a, b)，在B+树中找到第一个满足条件的a值后，对于b值，是在联合索引里判断，还是回主键索引去判断呢？

答案是会利用索引下推，减少回表次数。具体可阅读文章MySQL架构中关于索引下推的部分。

索引区分度

在实际开发中，建立联合索引时要将区分度大的字段排在前面，区分度指的是某个字段不同值的个数除以表的总行数：
$$
Index Selectivity = \frac{disctinct(column)}{count(*)}
$$

索引的适用情况

适用索引的场景

字段有唯一性限制的，比如商品编码；
经常用于 WHERE 查询条件的字段，这样能够提高整个表的查询速度，如果查询条件不是一个字段，可以建立联合索引。
经常用于 GROUP BY 和 ORDER BY 的字段，这样在查询的时候就不需要再去做一次排序了，因为我们都已经知道了建立索引之后在 B+树中的记录都是排序好的。

不需要索引的场景

WHERE 条件，GROUP BY，ORDER BY 里用不到的字段，索引的价值是快速定位，如果起不到定位的字段通常是不需要创建索引的，因为索引是会占用物理空间的。
字段中存在大量重复数据，不需要创建索引，比如性别字段，只有男女，如果数据库表中，男女的记录分布均匀，那么无论搜索哪个值都可能得到一半的数据。在这些情况下，还不如不要索引，因为 MySQL 还有一个查询优化器，查询优化器发现某个值出现在表的数据行中的百分比很高的时候，它一般会忽略索引，进行全表扫描。
表数据太少的时候，不需要创建索引；
经常更新的字段不用创建索引，比如不要对电商项目的用户余额建立索引，因为索引字段频繁修改，由于要维护B+树的有序性，那么就需要频繁的重建索引，这个过程是会影响数据库性能的。