MySQL索引是啥?不懂就问

• 从二叉树到b+树
• b+树索引vs哈希索引
• innodb vs myisam

概述

以下是需要创建索引的常见场景，为了对比，创建测试表（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+树

二叉树：

二叉树（binary tree）是指至多只有两个子节点的树形数据结构，没有父节点的节点为根节点，没有子节点的节点称为叶子节点。

二叉搜索树就是任何节点的左子节点小于当前节点键值，右子节点大于当前节点键值。

如下图的二叉搜索树，我们最多只需要 ⌈ l o g ( n ) ⌉ ⌈log(n)⌉ ⌈log(n)⌉即三次即可匹配到数据，而线性查找的话最坏情况需要 n 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+树中的叶子节点存储的就是表中的所有数据（即该主键对应的整行数据），数据文件和索引文件是同一个文件，找到了索引便找到了数据，所以我们称之为聚集索引。

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

聚集索引适合范围查询。聚集索引查询速度很快，特别适合范围检查（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

	myisam	innodb
数据存储	.frm存储表定义、.myd数据文件、.myi索引文件	不开启独立表空间则.frm文件，否则idb文件
索引实现	非聚集索引随机存储，只缓存索引	聚集索引顺序存储，缓存索引和数据
存储空间	可被压缩，存储空间较小，支持静态表、动态表、压缩表三种格式	需更多内存和存储
备份恢复	文件形式存储可跨平台，可单独针对某个表操作	拷贝数据文件、备份binlog，体量可能非常大
事务	不支持（也不支持外键，更强调性能）	支持（包括外键、安全、回滚等高级功能）
auto_increment	自增长列必须是索引，联合索引中可不是第一列	自增长列必须是索引，联合索引中也必须是第一列
锁	支持表级锁	支持行级锁
全文索引	支持fulltext类型全文索引	不支持fulltext，但可使用sphinx插件
表主键	允许没有任何索引和主键的表存在	会自动生成隐藏主键
总行数	保存有表的总行数	没有保存表的总行数，会使用辅助索引去遍历
crud	相对适合大量查询	相对适合增改删

对比之下，基本上可以考虑使用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。

select_type值	说明
simple	简单查询（不使用关联查询或子查询）
primary	包含关联查询或子查询
union	联合查询中第二个及后面的查询
dependent union	依赖外部的关联查询中第二个及以后的查询
union result	联合查询结果
subquery	子查询中的第一个查询
dependent subquery	依赖外部查询的子查询中的第一个查询
derived	用到派生表的查询
materialized	被物化的子查询
uncacheable subquery	子查询结果不能被缓存，必须重新评估外层查询的每一行

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

type的值	说明
system	查询对象只有一会数据 ，最好的情况
const	基于注解或唯一索引查询，最多返回一条结果
eq_ref	表连接时基于主键或非null的唯一索引完成扫描
ref	基于普通索引的等值查询或表间等值连接
fulltest	全文检索
ref_or_null	表连接类型是ref，但扫描的索引中可能包含null值
index_merge	利用多个索引
unique_subquery	子查询使用唯一索引
index_subquery	子查询使用普通索引
range	利用索引进行范围查询
index	全索引扫描

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

extra的值	说明
using filesort	用的外部排序而不是索引排序
using temporary	需创建一个临时表来存储结构，通常发生在对没有索引的列进行group by时
using index	使用覆盖索引
using where	使用where来处理结果
impossible where	对where子句判断结果总是false而不能选择任何数据
using join buffer	关联查询中，被驱动表的关联字段没有索引
using index condition	先条件过滤索引再查数据
select tables optimized away	使用聚合函数来访问存在索引的某个字段

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注的更多内容!