MySql —— 索引

可以按照四个角度来分类索引。

• 按「数据结构」分类：B+tree索引、Hash索引、Full-text索引。
• 按「物理存储」分类：聚簇索引（主键索引）、二级索引（辅助索引）。
• 按「字段特性」分类：主键索引、唯一索引、普通索引、前缀索引。
• 按「字段个数」分类：单列索引、联合索引。

按数据结构分类

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

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

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

B+Tree

• B+Tree 是一种多叉树，叶子节点才存放数据，非叶子节点只存放索引，而且每个节点里的数据是按主键顺序存放的。
• 在叶子节点中，包括了所有的索引值信息，并且每一个叶子节点都有两个指针，分别指向下一个叶子节点和上一个叶子节点，形成一个双向链表。

这条语句使用了主键索引查询 id 号为 5 的商品。查询过程是这样的，B+Tree 会自顶向下逐层进行查找：

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

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

B+Tree 存储千万级的数据只需要 3-4 层高度 就可以满足，这意味着从千万级的表查询目标数据最多需要 3-4 次磁盘 I/O，所以B+Tree 相比于 B 树和二叉树来说，最大的优势在于查询效率很高，因为即使在数据量很大的情况，查询一个数据的磁盘 I/O 依然维持在 3-4次。

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

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

 如果我用 product_no 二级索引查询商品，如下查询语句：

select * from product where product_no = '0002';

会先检二级索引中的 B+Tree 的索引值（商品编码，product_no），找到对应的叶子节点，然后获取主键值，然后再通过主键索引中的 B+Tree 树查询到对应的叶子节点，然后获取整行数据。这个过程叫「回表」，也就是说要查两个 B+Tree 才能查到数据。如下图

 不过，当查询的数据是能在二级索引的 B+Tree 的叶子节点里查询到，这时就不用再查主键索引查，比如下面这条查询语句：

select id from product where product_no = '0002';

这种在二级索引的 B+Tree 就能查询到结果的过程就叫作「覆盖索引」，也就是只需要查一个 B+Tree 就能找到数据。

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

前面已经讲了 B+Tree 的索引原理，现在就来回答一下 B+Tree 相比于 B 树、二叉树或 Hash 索引结构的优势在哪儿？

之前我也专门写过一篇文章，想详细了解的可以看这篇：「女朋友问我：为什么 MySQL 喜欢 B+ 树？我笑着画了 20 张图 (opens new window)」，这里就简单做个比对。

1、B+Tree vs B Tree

B+Tree 只在叶子节点存储数据，而 B 树 的非叶子节点也要存储数据，所以 B+Tree 的单个节点的数据量更小，在相同的磁盘 I/O 次数下，就能查询更多的节点。

另外，B+Tree 叶子节点采用的是双链表连接，适合 MySQL 中常见的基于范围的顺序查找，而 B 树无法做到这一点。

2、B+Tree vs 二叉树

对于有 N 个叶子节点的 B+Tree，其搜索复杂度为O(logdN)，其中 d 表示节点允许的最大子节点个数为 d 个。

在实际的应用当中， d 值是大于100的，这样就保证了，即使数据达到千万级别时，B+Tree 的高度依然维持在 3~4 层左右，也就是说一次数据查询操作只需要做 3~4 次的磁盘 I/O 操作就能查询到目标数据。

而二叉树的每个父节点的儿子节点个数只能是 2 个，意味着其搜索复杂度为 O(logN)，这已经比 B+Tree 高出不少，因此二叉树检索到目标数据所经历的磁盘 I/O 次数要更多。

3、B+Tree vs Hash

Hash 在做等值查询的时候效率贼快，搜索复杂度为 O(1)。

但是 Hash 表不适合做范围查询，它更适合做等值的查询，这也是 B+Tree 索引要比 Hash 表索引有着更广泛的适用场景的原因。

按物理存储分类

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

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

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

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

按字段特性分类

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

主键索引

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

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

唯一索引

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

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

普通索引

普通索引就是建立在普通字段上的索引，既不要求字段为主键，也不要求字段为 UNIQUE。

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

前缀索引

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

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

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

按字段个数分类

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

• 建立在单列上的索引称为单列索引；
• 建立在多列上的索引称为联合索引；

联合索引

通过将多个字段组合成一个索引，该索引就被称为联合索引。

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

CREATE INDEX index_product_no_name ON product(product_no, name);

联合索引的非叶子节点用 两个字段的值 作为 B+Tree 的 key 值。当在联合索引查询数据时，先按 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 子句的顺序并不重要。

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

• where b=2；
• where c=3；
• where b=2 and c=3；

上面这些查询条件之所以会失效，是因为(a, b, c) 联合索引，是先按 a 排序，在 a 相同的情况再按 b 排序，在 b 相同的情况再按 c 排序。所以，b 和 c 是全局无序，局部相对有序的，这样在没有遵循最左匹配原则的情况下，是无法利用到索引的。

可以看到，a 是全局有序的（1, 2, 2, 3, 4, 5, 6, 7 ,8），而 b 是全局是无序的（12，7，8，2，3，8，10，5，2）。因此，直接执行 where b = 2 这种查询条件没有办法利用联合索引的，利用索引的前提是索引里的 key 是有序的。

只有在 a 相同的情况才，b 才是有序的，比如 a 等于 2 的时候，b 的值为（7，8），这时就是有序的，这个有序状态是局部的，因此，执行where a = 2 and b = 7是 a 和 b 字段能用到联合索引的，也就是联合索引生效了。

联合索引范围查询

联合索引的最左匹配原则会一直向右匹配直到遇到「范围查询」就会停止匹配。

因为范围查询比如 a<1 是通过索引先找到 a 这个叶子节点，再通过叶子节点的双向链表向前查找范围。

也就是范围查询的字段可以用到联合索引，但是在范围查询字段的后面的字段无法用到联合索引。

Q1

select * from t_table where a > 1 and b = 2；联合索引（a, b）哪一个字段用到了联合索引的 B+Tree？

只有 a 用到了索引，找到 a=1 的叶子节点后，在叶子节点的双向链表向前查找 a>1 的全部叶子节点，从这些叶子节点中再找 b=2 的，所以 b 没有用到联合索引

Q2

select * from t_table where a >= 1 and b = 2；联合索引（a, b）哪一个字段用到了联合索引的 B+Tree？

这条查询语句 a 和 b 字段都用到了联合索引进行索引查询。

当二级索引记录的 a 字段值为 1 时，可以通过 b = 2 条件减少需要扫描的二级索引记录范围（只有 a=1 的那一点数据用到了）

也就是说从 a=1 b=2 的第一条开始记录开始扫描，而不需要从 a=1 的第一条记录开始扫描。

Q3

SELECT * FROM t_table WHERE a BETWEEN 2 AND 8 AND b = 2；联合索引（a, b）哪一个字段用到了联合索引的 B+Tree？

在 MySQL 中，BETWEEN 包含了 value1 和 value2 边界值，类似于 >= and =<。而有的数据库则不包含 value1 和 value2 边界值（类似于 > and <）。

因此 Q3 这条查询语句 a 和 b 字段都用到了联合索引进行索引查询。

Q4

SELECT * FROM t_user WHERE name like 'j%' and age = 22；联合索引（name, age）哪一个字段用到了联合索引的 B+Tree？

由于联合索引（二级索引）是先按照 name 字段的值排序的，所以前缀为 ‘j’ 的 name 字段的二级索引记录都是相邻的， 于是在进行索引扫描的时候，可以定位到符合前缀为 ‘j’ 的 name 字段的第一条记录，然后沿着记录所在的链表向后扫描，直到某条记录的 name 前缀不为 ‘j’ 为止。

 虽然在符合前缀为 ‘j’ 的 name 字段的二级索引记录的范围里，age 字段的值是「无序」的，但是对于符合 name = j 的二级索引记录的范围里，age字段的值是「有序」的

于是，在确定需要扫描的二级索引的范围时，当二级索引记录的 name 字段值为 ‘j’ 时，可以通过 age = 22 条件减少需要扫描的二级索引记录范围（age 字段可以利用联合索引进行索引查询的意思）。

也就是说，从符合 name = 'j' and age = 22 条件的第一条记录时开始扫描，而不需要从第一个 name 为 j 的记录开始扫描。如下图的右边：

(前面 a>=1 and b=2 同理，从 a=1 b=2 的第一条开始记录开始扫描，而不需要从 a=1 的第一条记录开始扫描。)

所以，Q4 这条查询语句 a 和 b 字段都用到了联合索引进行索引查询。