1、什么是索引

在日常学习中，最常见使用索引的例子就是词典，通过对字母进行排序，并设置对应的页数，从而循序定位某个单词，除了词典，如火车站的车次表、图书的目录等都是使用了索引。它们的原理都是一样的，通过不断的缩小想要获得数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是我们总是通过同一种查找方式来锁定数据。

数据库中，索引的定义就是帮助存储引擎快速获取数据的一种数据结构，形象的说就是索引是数据的目录。由存储引擎决定其结构。

MySQL 存储引擎有 MyISAM 、InnoDB，其中 InnoDB 是在 MySQL 5.5 之后成为默认的存储引擎。

小结：把随机的事件变成顺序的事件，快速查找和定位某个数据

2、索引的分类

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

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

2.1 按物理存储分类

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

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

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

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

小结：回表的次数越少，查询的效率越高

2.2 按字段特性分类

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

主键索引

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

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

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

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

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

唯一索引

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

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

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

建表后，如果要创建唯一索引，可以使用这面这条命令：

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

普通索引

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

在创建表时，创建普通索引的方式如下：

CREATE TABLE table_name  (
  ....
  INDEX(index_column_1,index_column_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))
);

建表后，如果要创建前缀索引，可以使用这面这条命令：

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

2.2 按字段个数分类

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

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

联合索引

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

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

CREATE INDEX index_product_no_name ON product(product_no, name);

联合索引(product_no, name)的 B+Tree 示意图如下（图中叶子节点之间我画了单向链表，但是实际上是双向链表）。

可以看到，联合索引的非叶子节点用两个字段的值作为 B+Tree 的 key 值。当在联合索引查询数据时，先按 product_no 字段比较，在 product_no 相同的情况下再按 name 字段比较。

也就是说，联合索引查询的 B+Tree 是先按 product_no 进行排序，然后再 product_no 相同的情况再按 name 字段排序。

因此，使用联合索引时，存在最左匹配原则，也就是按照最左优先的方式进行索引的匹配。在使用联合索引进行查询的时候，如果不遵循「最左匹配原则」，联合索引会失效，这样就无法利用到索引快速查询的特性了。

3、索引的原理（重要）

先说答案：Mysql的

搞懂索引的原理可以解决如下问题：

1、最左前缀匹配原则的原理及作用？

2、聚簇索引和二级索引的区别，以及什么是覆盖索引？

要解决上面两个问题，首先要明确为什么需要索引，正如我们在前文提到的索引的目的是为了快速定位和查找数据，将随机IO，变为顺序IO，或者通过O(1)的时间复杂度直接拿到。

不拿想到可以通过哈希表活着红黑树的方式去实现索引

(1) 哈希表
哈希虽然能够提供O(1)的单数据行的查询性能，但是对于范围查询和排序却无法很好支持，需全表扫描。

(2) 红黑树
红黑树(Red Black Tree)是一种自平衡二叉查找树，在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能，由于磁盘的I/O次数，取决于树的高度，所有在数据量较大时，红黑树会因为树的高度较大而造成磁盘I/O较多，从而影响查找效率。

但是对于Mysql来说还不够，作为一个关系型数据库的索引数据结构，不仅需要考虑查询的效率还需要考虑插入时对整个索引数据结构的影响。这个时候在设计索引的数据结构时，就必须得考虑下面的问题：

1、在大量数据下，生成索引的结构组织要尽量减少查找过程中磁盘的I/O的次数。

2、在进行插入，更新，删除操作时对数据结构变动较小。

3、在大量数据下，能够高效的支持顺序和范围查找。

(3) B-Tree
B树中的B代表平衡(Balance)，而不是二叉(Binary)，B树是从平衡二叉树演化而来的。

为了降低树的高度(也就是减少磁盘I/O次数)，把原来瘦高的树结构变得矮胖，B树会在每个节点存储多个元素(红黑树每个节点只会存储一个元素)，并且节点中的元素从左到右递增排列。如下图所示：

B-Tree在查询的时候比较次数其实不比二叉查找树少，但在内存中的大小比较、二分查找的耗时相比磁盘IO耗时几乎可以忽略。 B-Tree大大降低了树的高度，所以也就极大地提升了查找性能。

(4) B+Tree
B+Tree是在B-Tree基础上进一步优化，使其更适合实现存储索引结构。InnoDB存储引擎就是用B+Tree实现其索引结构。

B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个节点的存储空间是有限的，如果data值较大时将会导致每个节点能存储的key的数量很小，这样会导致B-Tree的高度变大，增加了查询时的磁盘I/O次数，进而影响查询性能。在B+Tree中，所有data值都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以增大每个非叶子节点存储的key值数量，降低B+Tree的高度，提高效率。

这里补充一点相关知识 在计算机中，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

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

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。预读的长度一般为页(page)的整数倍。

页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页(许多操作系统的页默认大小为4KB)，主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时操作系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。(如下命令可以查看操作系统的默认页大小)

$ getconf PAGE_SIZE
4096

数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为操作系统的页大小的整数倍，这样每个节点只需要一次I/O就可以完全载入。

InnoDB存储引擎中也有页(Page)的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB。

mysql> show variables like 'innodb_page_size';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.01 sec)

一般表的主键类型为INT（占4个字节）或BIGINT（占8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为10^3）。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿条记录。

B+Tree的高度一般都在2到4层。mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1到3次磁盘I/O操作。

随机I/O对于MySQL的查询性能影响会非常大，而顺序读取磁盘中的数据会很快，由此我们也应该尽量减少随机I/O的次数，这样才能提高性能。在B-Tree中由于所有的节点都可能包含目标数据，我们总是要从根节点向下遍历子树查找满足条件的数据行，这会带来大量的随机I/O，而B+Tree所有的数据行都存储在叶子节点中，而这些叶子节点通过双向链表依次按顺序连接，当我们在B+树遍历数据(比如说范围查询)时可以直接在多个叶子节点之间进行跳转，保证顺序、倒序遍历的性能。

另外，对以上提到的数据结构不熟悉的朋友，这里推荐一个在线数据结构可视化演示工具，有助于快速理解这些数据结构的机制：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

3.1 在看主键索引和二级索引

回头在看主键索引，就明白了为什么Mysql存储引擎InnoDB会使用B+树作为数据结构了

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

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

主键索引的 B+Tree 如图所示（图中叶子节点之间我画了单向链表，但是实际上是双向链表）：

1、覆盖索引

通过二级索引查询商品数据的过程，主键索引的 B+Tree 和二级索引的 B+Tree 区别如下：

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

我这里将前面的商品表中的 product_no （商品编码）字段设置为二级索引，那么二级索引的 B+Tree 如下图（图中叶子节点之间我画了单向链表，但是实际上是双向链表）。

其中非叶子的 key 值是 product_no（图中橙色部分），叶子节点存储的数据是主键值（图中绿色部分）。

如果我用 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 就能找到数据。

2、最左前缀匹配原则

最左前缀匹配原则指的是在使用联合索引时，MySQL 会根据索引中的字段顺序，从左到右依次匹配查询条件中的字段。如果查询条件与索引中的最左侧字段相匹配，那么 MySQL 就会使用索引来过滤数据，这样可以提高查询效率。

最左匹配原则会一直向右匹配，直到遇到范围查询（如 >、<）为止。对于 >=、<=、BETWEEN 以及前缀匹配 LIKE 的范围查询，不会停止匹配（相关阅读：联合索引的最左匹配原则全网都在说的一个错误结论open in new window）。

假设有一个联合索引(column1, column2, column3)，其从左到右的所有前缀为(column1)、(column1, column2)、(column1, column2, column3)（创建 1 个联合索引相当于创建了 3 个索引），包含这些列的所有查询都会走索引而不会全表扫描。

我们在使用联合索引时，可以将区分度高的字段放在最左边，这也可以过滤更多数据。

我们这里简单演示一下最左前缀匹配的效果。

1、创建一个名为 student 的表，这张表只有 id、name、class这 3 个字段。

CREATE TABLE `student` (
  `id` int NOT NULL,
  `name` varchar(100) DEFAULT NULL,
  `class` varchar(100) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `name_class_idx` (`name`,`class`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

2、下面我们分别测试三条不同的 SQL 语句。

# 可以命中索引
SELECT * FROM student WHERE name = 'Anne Henry';
EXPLAIN SELECT * FROM student WHERE name = 'Anne Henry' AND class = 'lIrm08RYVk';
# 无法命中索引
SELECT * FROM student WHERE class = 'lIrm08RYVk';

3.2 索引下推

索引下推（Index Condition Pushdown，简称 ICP）是 MySQL 5.6 版本中提供的一项索引优化功能，它允许存储引擎在索引遍历过程中，执行部分 WHERE字句的判断条件，直接过滤掉不满足条件的记录，从而减少回表次数，提高查询效率。

假设我们有一个名为 user 的表，其中包含 id, username, zipcode和 birthdate 4 个字段，创建了联合索引(zipcode, birthdate)。

CREATE TABLE `user` (
  `id` int NOT NULL AUTO_INCREMENT,
  `username` varchar(20) CHARACTER SET utf8mb4 COLLATE utf8mb4_0900_ai_ci NOT NULL,
  `zipcode` varchar(20) CHARACTER SET utf8mb4 COLLATE utf8mb4_0900_ai_ci NOT NULL,
  `birthdate` date NOT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_username_birthdate` (`zipcode`,`birthdate`) ) ENGINE=InnoDB AUTO_INCREMENT=1001 DEFAULT CHARSET=utf8mb4;

# 查询 zipcode 为 431200 且生日在 3 月的用户
# birthdate 字段使用函数索引失效
SELECT * FROM user WHERE zipcode = '431200' AND MONTH(birthdate) = 3;

• 没有索引下推之前，即使 zipcode 字段利用索引可以帮助我们快速定位到 zipcode = '431200' 的用户，但我们仍然需要对每一个找到的用户进行回表操作，获取完整的用户数据，再去判断 MONTH(birthdate) = 3。
• 有了索引下推之后，存储引擎会在使用zipcode 字段索引查找zipcode = '431200' 的用户时，同时判断MONTH(birthdate) = 3。这样，只有同时满足条件的记录才会被返回，减少了回表次数。

再来讲讲索引下推的具体原理，先看下面这张 MySQL 简要架构图。

MySQL 可以简单分为 Server 层和存储引擎层这两层。Server 层处理查询解析、分析、优化、缓存以及与客户端的交互等操作，而存储引擎层负责数据的存储和读取，MySQL 支持 InnoDB、MyISAM、Memory 等多种存储引擎。

索引下推的下推其实就是指将部分上层（Server 层）负责的事情，交给了下层（存储引擎层）去处理。

我们这里结合索引下推原理再对上面提到的例子进行解释。

没有索引下推之前：

• 存储引擎层先根据 zipcode 索引字段找到所有 zipcode = '431200' 的用户的主键 ID，然后二次回表查询，获取完整的用户数据；
• 存储引擎层把所有 zipcode = '431200' 的用户数据全部交给 Server 层，Server 层根据MONTH(birthdate) = 3这一条件再进一步做筛选。

有了索引下推之后：

• 存储引擎层先根据 zipcode 索引字段找到所有 zipcode = '431200' 的用户，然后直接判断 MONTH(birthdate) = 3，筛选出符合条件的主键 ID；
• 二次回表查询，根据符合条件的主键 ID 去获取完整的用户数据；
• 存储引擎层把符合条件的用户数据全部交给 Server 层。

可以看出，除了可以减少回表次数之外，索引下推还可以减少存储引擎层和 Server 层的数据传输量。

最后，总结一下索引下推应用范围：

1. 适用于 InnoDB 引擎和 MyISAM 引擎的查询。
2. 适用于执行计划是 range, ref, eq_ref, ref_or_null 的范围查询。
3. 对于 InnoDB 表，仅用于非聚簇索引。索引下推的目标是减少全行读取次数，从而减少 I/O 操作。对于 InnoDB 聚集索引，完整的记录已经读入 InnoDB 缓冲区。在这种情况下使用索引下推 不会减少 I/O。
4. 子查询不能使用索引下推，因为子查询通常会创建临时表来处理结果，而这些临时表是没有索引的。
5. 存储过程不能使用索引下推，因为存储引擎无法调用存储函数。

4、总结

明确一点：

MySQL跟B+树没有直接的关系，真正与B+树有关系的是MySQL的默认存储引擎InnoDB，MySQL中存储引擎的主要作用是负责数据的存储和提取，除了InnoDB之外，MySQL中也支持比如MyISAM等其他存储引擎

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

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

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 表索引有着更广泛的适用场景的原因。

4.2 如何正确建立索引和使用索引

• 不为 NULL 的字段：索引字段的数据应该尽量不为 NULL，因为对于数据为 NULL 的字段，数据库较难优化。如果字段频繁被查询，但又避免不了为 NULL，建议使用 0,1,true,false 这样语义较为清晰的短值或短字符作为替代。
• 被频繁查询的字段：我们创建索引的字段应该是查询操作非常频繁的字段。
• 被作为条件查询的字段：被作为 WHERE 条件查询的字段，应该被考虑建立索引。
• 频繁需要排序的字段：索引已经排序，这样查询可以利用索引的排序，加快排序查询时间。
• 被经常频繁用于连接的字段：经常用于连接的字段可能是一些外键列，对于外键列并不一定要建立外键，只是说该列涉及到表与表的关系。对于频繁被连接查询的字段，可以考虑建立索引，提高多表连接查询的效率。

原则1：被频繁更新的字段应该慎重建立索引

虽然索引能带来查询上的效率，但是维护索引的成本也是不小的。 如果一个字段不被经常查询，反而被经常修改，那么就更不应该在这种字段上建立索引了。

原则2：限制每张表上的索引数量

索引并不是越多越好，建议单张表索引不超过 5 个！索引可以提高效率同样可以降低效率。

索引可以增加查询效率，但同样也会降低插入和更新的效率，甚至有些情况下会降低查询效率。

因为 MySQL 优化器在选择如何优化查询时，会根据统一信息，对每一个可以用到的索引来进行评估，以生成出一个最好的执行计划，如果同时有很多个索引都可以用于查询，就会增加 MySQL 优化器生成执行计划的时间，同样会降低查询性能。

原则3：尽可能的考虑建立联合索引而不是单列索引

因为索引是需要占用磁盘空间的，可以简单理解为每个索引都对应着一颗 B+树。如果一个表的字段过多，索引过多，那么当这个表的数据达到一个体量后，索引占用的空间也是很多的，且修改索引时，耗费的时间也是较多的。如果是联合索引，多个字段在一个索引上，那么将会节约很大磁盘空间，且修改数据的操作效率也会提升。

原则4：注意避免冗余索引

冗余索引指的是索引的功能相同，能够命中索引(a, b)就肯定能命中索引(a) ，那么索引(a)就是冗余索引。如（name,city ）和（name ）这两个索引就是冗余索引，能够命中前者的查询肯定是能够命中后者的 在大多数情况下，都应该尽量扩展已有的索引而不是创建新索引。

原则5：字符串类型的字段使用前缀索引代替普通索引

前缀索引仅限于字符串类型，较普通索引会占用更小的空间，所以可以考虑使用前缀索引带替普通索引。

4.3 索引失效的原因

索引失效也是慢查询的主要原因之一，常见的导致索引失效的情况有下面这些：

• 使用 SELECT * 进行查询; SELECT * 不会直接导致索引失效（如果不走索引大概率是因为 where 查询范围过大导致的），但它可能会带来一些其他的性能问题比如造成网络传输和数据处理的浪费、无法使用索引覆盖;
• 创建了组合索引，但查询条件未遵守最左匹配原则;
• 在索引列上进行计算、函数、类型转换等操作;
• 以 % 开头的 LIKE 查询比如 LIKE '%abc';;
• 查询条件中使用 OR，且 OR 的前后条件中有一个列没有索引，涉及的索引都不会被使用到;
• IN 的取值范围较大时会导致索引失效，走全表扫描(NOT IN 和 IN 的失效场景相同);
• 发生隐式转换open in new window;
• ……

推荐阅读这篇文章：美团暑期实习一面：MySQl 索引失效的场景有哪些？open in new window。

参考文献：

https://www.cnblogs.com/bytesfly/p/mysql-index-theory-and-best-practice.html

MySQL索引详解 | JavaGuide

B+ Tree Visualization

CodingLabs - MySQL索引背后的数据结构及算法原理