概述

索引是帮助数据库高效获取数据的一种数据结构，是基于数据表创建的，它包含了一个表中某些列的值以及记录对应的地址，并且把这些值存在一个数据结构中，常见的有使用哈希表、B+树作为索引。

以下是需要创建索引的常见场景，为了对比，创建测试表（a带索引、d无索引）：

mysql> create table test( --创建测试表
    -> id int(10) not null AUTO_INCREMENT,
    -> a int(10) default null,
    -> b int(10) default null,
    -> c int(10) default null,
    -> d int(10) default null,
    -> primary key(id), --主键索引
    -> key idx_a(a), --辅助索引
    -> key idx_b_c(b,c) --联合索引
    -> )engine=InnoDB charset=utf8mb4;
Query OK, 0 rows affected, 5 warnings (0.09 sec)

mysql> drop procedure if exists insert_test_data;
Query OK, 0 rows affected, 1 warning (0.00 sec)

mysql> delimiter | --创建存储过程，插入十万个数据
mysql> create procedure insert_test_data()
    -> begin
    -> declare i int;
    -> set i=1;
    -> while(i<=100000) do
    -> insert into test(a,b,c,d)values(i,i,i,i);
    -> set i=i+1;
    -> end while;
    -> end |
Query OK, 0 rows affected (0.11 sec)

mysql> delimiter ;
mysql> call insert_test_data(); --执行存储过程
Query OK, 1 row affected (11 min 44.13 sec)

• 数据检索时在条件字段添加索引
  

• 聚合函数对聚合字段添加索引
  

• 对排序字段添加索引
  

• 为了防止回表添加索引
  

• 关联查询在关联字段添加索引
  

可以看出使用索引后，对查询速度优化提升是巨大的，本文将从底层到实践搞懂MySQL索引。

从二叉树到B+树

正式介绍MySQL索引前，需要先了解树这种数据结构，植入：
二叉树面试题-你已经是棵成熟的二叉树了，要学会自己解题
二叉树：
二叉树（Binary Tree）是指至多只有两个子节点的树形数据结构，没有父节点的节点为根节点，没有子节点的节点称为叶子节点。
二叉搜索树就是任何节点的左子节点小于当前节点键值，右子节点大于当前节点键值。
如下图的二叉搜索树，我们最多只需要$?log(n)?$即三次即可匹配到数据，而线性查找的话最坏情况需要$n$次才可匹配到。

但是二叉树可能会退化成链表的情况，如下图所示，这样就相当于全部扫描了，导致效率不高，为了解决这个问题，需要确保二叉树一直保持平衡，即平衡二叉树。

平衡二叉树：
平衡二叉树（AVL树）在满足二叉树特性的基础上，要求每一个节点的左右子树高度差不能超过1。它保证了树构造的一个平衡，当插入或删除数据导致不平衡时，会进行节点调整来保持平衡（具体算法略），确保查找效率。

平衡二叉树的一个节点对应一个键值和数据，我们每次查找数据就需要从磁盘中读取一个节点，也就是我们说的磁盘块，一个节点对应一个磁盘块。当存储海量数据时，树的节点会非常多，会进行很多次的磁盘I/O，查找效率仍是极低的。这就需要一个单节点能存储多个键值和数据的一种平衡树了。

B树：
B树（Blance Tree）就是可以单节点存储多键值和数据的平衡树，每一个节点我们称之为页（Page），即一页数据。每个节点存储了更多键值和数据，把键值和数据都放在一个页当中，并且每个节点拥有了更多子节点，子节点的个数一般称为阶。B树在查找数据读取磁盘的次数也就大大减少，查找效率比AVL高很多。

如下图的3阶B树中，查找id=42的数据。首先在第一页里判断42键值大于39，根据指针P3找到第4页，再进行比较，小于键值45，又根据指针P1找到第9页，发现匹配有匹配的键值42，即找到相应数据。

B+树：
B+树是对B树的进一步优化。简单说就是B+树的非叶子节点是不存储数据的，仅存放键值。之所以这样做，是因为数据库中页的大学是固定的（InnoDB默认16KB），如果不存储数据，就可以存储更多键值，节点个数就越大，查找数据进行磁盘I/O次数进一步减少。

另外B+树的阶数是等于它的键值数量的，如果一个节点存储1000键值的话，那么只需要三层就可存储10亿数据，所以一般查找10亿数据只需两次磁盘I/O即可（妙啊）。

同时B+树叶节点的数据是按顺序进行排列的，所以B+树适合范围查找、排序查找和分组查找等（B各数据分散在节点上，相对就困难），也就是为什么MySQL采用B+树索引的原因了。

聚集索引

聚集索引或聚簇索引（Clustered Index）是一种对磁盘上实际数据重新组织并按指定的一个或多个列的值排序。数据行的物理顺序与列值（一般是主键那列）的逻辑顺序相同，一个表中只能有一个聚集索引（因为只能以一种物理顺序存放）。

InnoDB就是用的聚集索引，它的表中的数据都会有一个主键，即使你不创建主键，InnoDB会选取一个Unique键作为主键，如果表中连Unique键都没有定义的话，InnoDB会为表添加一个名为row_id的隐藏列作为主键。

也就是说我们通过InnoDB把数据存放到B+树中，而B+树中的键值就是主键，那么在B+树中的叶子节点存储的就是表中的所有数据（即该主键对应的整行数据），数据文件和索引文件是同一个文件，找到了索引便找到了数据，所以我们称之为聚集索引。

（插播反爬信息 ）博主CSDN地址：https://wzlodq.blog.csdn.net/

聚集索引更新代价高。插入新行或更新主键时会强制将每个被更新的行移动到新的位置（因为要按主键排序），而移动行可能还会面临页分裂问题（即页已满），存储引擎会将该页分裂成两个页面来容纳，页分裂会占用更多磁盘空间。即索引重排，造成资源浪费。

聚集索引适合范围查询。聚集索引查询速度很快，特别适合范围检查（between、<、<=、>、>=）或group by、order by的查询。因为聚集索引找到包含第一个值的行后，后续索引值的行在物理上毗连在一起而不必进一步搜索，避免大范围扫描，大大提高查询速度。

比如查询id>=19并且id<30的数据：通常根节点常驻在内存中（即页1已在内存），首先在页1找到了键值19及其对应指针P2，通过P2读页3（此时页3不在内存中，需要从磁盘中加载），然后在页3查找键值19的指针P1，又定位到页8（同样的从磁盘加载到内存），因为数据是按链表进行顺序链接的，可以通过二分找到键值19对应数据。

找到键值19后，因为是范围查找，这时可以在叶子节点里进行链表的查询，依次遍历并匹配满足的条件，一直找到键值21，到最后一个数据仍不能满足我们的要求，此时会拿着页8的指针P去读取页9的数据，页9不在内存中同样需要磁盘加载读进内存，然后依此类推，直到匹配到键值34时不满足条件则终止，这就是通过聚集索引查找数据的一种方法。

非聚集索引

非聚集索引或非聚簇索引(Secondary Index)就是以主键以外的列作为键值构建的B+树索引，索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。在InnoDB中处理主键索引外其他索引都可以称为辅助索引或二级索引。

MySQL中的MyISAM使用的就是非聚集索引。表数据存储顺序与索引数据无关，叶节点包含索引字段值及指向数据页数据行的逻辑指针（其行数量与数据表数据量相同），所以想要查找数据还需要根据主键再去聚集索引中查找，根据聚集索引查找数据的过程就称为回表。

比如定义一张数据表test，他是由test.frm、tsst.myd和test.myi组成的：

• .frm：记录了表定义语句
• .myd：记录了真实表数据
• .myi：记录了索引数据

再检索数据时，先到索引树test.myi中进行查找，取到数据所在test.myd的行位置，拿到数据。所以MyISAM引擎的索引文件和数据文件时独立分开的，找到索引不等于找到数据，即非聚集索引。

一个表可以有不止一个非聚集索引，实际上每个表最多可以建立249个非聚集索引，但是每次给字段建一个新索引，字段中的数据就会被复制出来一份用于生成索引，因此给表添加索引会增加表的体积，占据大量磁盘空间和内存。所以若磁盘空间和内存有限，应限制非聚集索引数量。

此外每当你改变了一个建立非聚集索引的表中数据时，必须同时更新索引，所以非聚集索引会降低插入和更新速度。

比如查找数据36，是用两个数字表示，前面那个数字36代表的是索引的键值，后面那个64代表的是数据的主键。所以说我们找到36后，并没有拿到数据，还要根据它对应的主键去到聚集索引表中去查找数据。

联合索引和覆盖索引

联合索引，顾名思义就是指对表上的多个列联合起来进行索引。在创建联合索引的时候会根据业务需求，把使用最频繁的列放在最左边，因为MySQL的索引查询会遵循最左前缀匹配的原则。

最左前缀匹配原则即最左优先在检索数据的时候，从联合索引的最左边开始匹配，所以当我们创建一个联合索引的时候，如（a,b,c）相当于创建了（a）、（a、b）、（a、b、c）三个索引，这就是最左匹配原则。

覆盖索引（Covering index）只是特定于具体select语录而言的联合索引。也就是说一个联合索引对于某个select语句，通过索引可以直接获取查询结果，而不再需要回表查询啦，就称该联合索引覆盖了这条select语句。可以完美的解决非聚集索引回表查询的问题，但前提是注意查询时索引的最左匹配原则。

B+树索引VS哈希索引

原理：

• B+树索引可能需要多次运用二分查找来找到对应的数据块。
• Hash索引时通过Hash函数，计算出Hash值，在表中找出对应的数据。

哈希索引适合大量不同数据等值精确查询，但不支持模糊查询、范围查询，无法用索引来进行排序，也不支持联合索引的最左匹配原则，而且有大量重复键值的情况下，还会存在哈希碰撞问题。

普通索引和唯一索引

普通索引的字段可以写入重复的值，而唯一索引的字段不能写入重复的值。
先介绍Insert Buffer和Change Buffer：

• Insert Buffer
  对于非聚集索引的插入，先判断插入的非聚集索引是在在缓存池中。若在则直接插入，若不在，则先放入Insert Buffer，之后在一一定频率和情况镜像Insert Buffer和辅助索引页子节点的合并操作。将多次插入合并为一次操作，减少磁盘离散读取。要求索引是辅助索引且不唯一。
• Change Buffer
  是Insert Buffer的升级版，除了插入还支持删改。通过innodb_change_buffer设置使用场景，默认为all（还有none、inserts、changes等值），通过innodb_change_buffer_max_size设置最大使用内存占比（默认25%，最大值50%），但在RR隔离级别下会出现死锁。同样要求索引是辅助索引且不唯一。

唯一索引使用的是Insert Buffer，因为判断是否违反唯一性约束，如果都已经读入内存了，那直接更新内存会更快，就没必要使用Change Buffer。

普通索引查找到满足条件的第一个记录后，继续查找下一个记录直到不满足条件，对唯一索引来说，查到第一个记录就返回结果结束了。但是InnoDB按页读取到内存，后面满足条件的可能都在之前的数据页里，所以普通索引多的几次内存扫描消耗可以忽略不计。

小结：

• 数据修改时，普通索引可用Change Buffer，而唯一索引不行。
• 数据修改时，唯一索引在RR隔离级别下更容易出现死锁。
• 查询数据时，普通索引查到一条记录还需继续判断下一个记录，而唯一索引查到后直接返回。
• 当业务要求某字段唯一时，若代码能保证写入唯一值，则用普通索引，否则用唯一索引。

InnoDB VS MyISAM

对比之下，基本上可以考虑使用InnoDB来替代MyISAM了，InnoDB也是目前MySQL的默认引擎，但是具体问题具体分析，也可根据实际情况对比两者优劣，选择更合适的。

再扩展一下为什么MyISAM查询比InnoDB快？

• InnoDB要缓存数据和索引；MyISAM只缓存索引，换进换出的减少。
• InnoDB寻址要映射到块再到行；MyISAM直接记录文件的OFFSET，定位更快。
• InnoDB还要维护MVCC一致，或许你的场景没有，但也需要检查和维护。

MVCC(Multi-Version Concurrency Control)多版本并发控制
InnoDB为每一行记录添加了两个额外的隐藏值（创建版本号、删除版本号）来实现MVCC，一个记录行数据创建时间，一个记录行数据过期/删除时间。但是InnoDB并不存储这些事件发生的实际时间，相反它只存储这些事件发生时的系统版本号。随着事务的不断创建而不断增长，每个事务在开始时都会记录它自己的系统版本号，每个查询必须去检查每行数据的版本号与事务的版本号是否相同。也就是说每行数据的创建版本号不大于事务版本号，以确保事务创建前行数据是存在的；行数据的删除版本号大于事务版本号或未定义，以确保事务开始前行数据没有被删除。

用explain分析索引使用

explain可以看SQL语句的执行效果，可以帮助选择更好的索引和优化查询语句，语法：explain select... from ... [where...]。

用前面概述那节的test表做测试：

mysql> explain select * from test where a=88888;
+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key   | key_len | ref   | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------+
|  1 | SIMPLE      | test  | NULL       | ref  | idx_a         | idx_a | 5       | const |    1 |   100.00 | NULL  |
+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------+
1 row in set, 1 warning (0.03 sec)

mysql> explain select b,c from test where b=88888;
+----+-------------+-------+------------+------+---------------+---------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key     | key_len | ref   | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+---------+---------+-------+------+----------+-------------+
|  1 | SIMPLE      | test  | NULL       | ref  | idx_b_c       | idx_b_c | 5       | const |    1 |   100.00 | Using index |
+----+-------------+-------+------------+------+---------------+---------+---------+-------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> explain select * from test where a=(select a from test where a=88888);
+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key   | key_len | ref   | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+
|  1 | PRIMARY     | test  | NULL       | ref  | idx_a         | idx_a | 5       | const |    1 |   100.00 | Using where |
|  2 | SUBQUERY    | test  | NULL       | ref  | idx_a         | idx_a | 5       | const |    1 |   100.00 | Using index |
+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+
2 rows in set, 1 warning (0.00 sec)

重点看这三列即可：select_type、type、extra。

1. select_type（使用的查询类型）

2. type（显示这一行的数据是关于哪张表的）

3. extra（解决查询的详细信息）

原创不易，请勿转载（本不富裕的访问量雪上加霜 ）
博主首页：https://wzlodq.blog.csdn.net/
微信公众号：唔仄lo咚锵
如果文章对你有帮助，记得一键三连?