Mysql查询优化实战剖析（附InnoDB引擎利用的索引结构B+树说明）

一旦涉及到查询优化，就离不开索引的应用，本文选取mysql常用的引擎InnoDB作为研究对象，针对InnoDB引擎利用的索引结构B+树做个简单说明。

InnoDB的B+树

假设我们创建表Student，主键为id：

CREATE TABLE `Student` (
  `id` int(16) NOT NULL AUTO_INCREMENT,
  `name` varchar(10) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;复制代码

插入12条数据：

insert into Student(id,name) valuse(1,'XiaoHong')
insert into Student(id,name) valuse(2,'XiaoMing')
insert into Student(id,name) valuse(3,'XiaoFang')
....
insert into Student(id,name) valuse(12,'XiaoYou')
复制代码

此时，Innodb引擎将会根据主键id自行创建一个B+树的索引结构，我们有如下图的抽象：

如何理解图中结构的形态？

表数据首先会根据主键id的顺序存储在磁盘空间，图中叶节点存放表中每行的真实数据，可以认识到表数据本身属于主键索引的一部分，如下图，每行数据根据主键id按序存放：

我们设定id为Int类型占据4个字节，name字段为固定10字节的Char类型，Student表每行将占据14个字节的磁盘空间。在理想状况下，我们可以简化成这样的一个认识：假定图中第一行（1，XiaoHong）在磁盘地址0x01，那么第二行（2，XiaoMing）则在磁盘地址0x0f（0x01+14=0x0f），以此类推下去。

非叶节点存放索引值和对应的指针，我们看到这12行数据根据主键id分成了五个节点（一个非叶节点四个叶节点），真实环境下Mysql利用磁盘按块读取的原理设定每个磁盘块（也可理解为页，一般为4kb，innodb中将页大小设定为16kb）为一个树节点大小，这样每次一个磁盘I/O产生的内容就可以获取对应节点所有数据。

对于非叶节点每个索引值左边的指针指向小于这个索引值的对应数据的节点地址，索引值右边的指针指向大于或等于该索引值的对应数据的节点地址：

如上图，索引值为4的左边指针的指向结点数据必定都是小于4的，对应右指针指向节点范围必定是大于或等于4的。而且，在索引值数目一定的情况下，B+树为了控制树的高度尽可能小，会要求每个非页节点尽可能存放更多数据，一般要求非叶节点索引值的个数至少为（n-1)/2，n为一个页块大小最多能容纳的值个数。按照上图假设的构造形态，我们知道每个页块最多只能容纳三个索引值或三行数据（实际会大很多），在这样的前提下，如果继续插入行数据，那么首先是叶节点将没有空间容纳新数据，此时叶节点通过分裂来增加一个新叶节点完成保存：

可以想象的是，我们试图继续插入2条数据：

insert into Student(id,name) valuse(13,'XiaoRui')
insert into Student(id,name) valuse(14,'XiaoKe')复制代码

最终将会变成如下形态：

因为每个非页节点最多容纳3个索引值和对应的4个指针（扇出），整个查询的复杂度为O(log4N)，N为表的行数。对于拥有1000个学生数据的Student表来说，根据id查询的复杂度为log41000=5，在这里，查询复杂度在B+树中可以直观地理解为树的高度，通过非叶节点一层层的递进判断最终定位到目标数据所在的页块地址。

因此，innodb引擎的表数据是通过主键索引结构来组织的，叶节点存放着行数据，是一种B+树文件组织，如果通过主键定位行数据将拥有极大的效率，所以在创建表时无论有没明确定义主键索引，引擎内部都会自动为表创建一个主键索引继而构造出一个B+树文件组织。在实际应用中，当通过主键去查询某些数据时，首先是通过B+树定位到具体的叶节点地址，因为叶节点刚好设定为磁盘块连续地址的整数倍大小，所以通过连续地址的快速I/O将整个节点内容加载到内存，然后从内存中对节点内容进行筛选找出目标数据！

但innodb引擎还允许我们对表其它字段单独构建索引，也就是常说的辅助索引，比如我们这样创建Student表：

CREATE TABLE `Student` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(10) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `index_name` (`name`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;复制代码

插入示例数据：

insert into Student(id,name) valuse(1,'A')
insert into Student(id,name) valuse(2,'A')
insert into Student(id,name) valuse(3,'B')
......
......
insert into Student(id,name) valuse(12,'F')复制代码

如何理解name字段索引结构存在的形式？直接上图：

可见，辅助索引同样会构建一个B+树索引结构，只不过叶节点存放的是主键id值，非数字的索引在索引结构中按照预先设定的字符集排序规则进行排序，比如name=A在对应排序规则中是比B要小的。

按照上图的结构，假定我们进行如下操作：

select * from Student where name='A';复制代码

那么首先会利用辅助索引定位到叶节点1，然后加载到内存，在内存中检索发现有两个主键id：1、2 符合条件，然后通过主键id再从主键索引进行检索，把行数据全部加载出来！

在辅助索引中，innodb还支持组合索引的形式，把多个字段按序组合而成一个索引，比如我们创建如下Student表：

CREATE TABLE `StudentTmp` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(10) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `index_name_age` (`name`,`age`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;复制代码

name和age组合构成一个索引，对应B+树索引结构有如下形式：

在该组合索引中，叶节点内容先是按照name字段进行排序，在name字段值相同情况下再按照age字段进行排序，这样在对name和age作为组合条件查询时将充分利用两个字段的排序关系实现多级索引的定位。

好的，我们不在纠结B+树的更多细节，我们只需先在脑海中构建索引结构的大体形态，想象着索引的查询是在一个树状结构中层层递进最终定位到目标数据的过程，并且认识到查询复杂度和B+树非叶节点中指针个数存在着联系，这对于我们形成查询成本的敏感性是非常有帮助的。

通过Explain方法来了解查询成本

体会了索引构造带来的查询效率的提升，在实际应用中我们又该如何了解每个查询Sql对索引的利用情况呢？Explain方法可以在执行前辅助我们进行判断，通过相关参数特别是对于多层嵌套或连接的复杂查询语句具有非常大的帮助。

通过在查询sql前面加上explain关键字就可以完成计划分析：

explain select id from Student where id=1;

执行后有如下结果：

我们看到结果表单有id、table、select_type...等10个参数，每个参数有对应的结果值，接下来我们一步步做好认识。

id:用于标识各个子查询的执行顺序，值越大执行优先级越高

上文查询只是一个简单查询，故id只有一个1，我们现在增加一个子查询后：

explain select name from Student where id=(select max(id) from Student);

有:

可以看到有两个结果行，说明这个sql有两个查询计划，table字段用于指明该查询计划对应的表名，而id值的作用在于提示我们哪个查询计划是优先执行的。

table:指定对应查询计划关联的表名

上文关于id字段的示例说明中，我们发现id=2的查询计划（select max(id) from Student）对应表名是空的，这似乎不符合常规，难道这个查询计划不涉及到表操作？我们在Extra字段中找到了这样一个说明：Select tables optimized away这个语句告诉我们，引擎对该查询计划做了优化，基于索引层面的优化像min/max操作或者count(*)操作，不需要等到执行阶段对表进行检索，该值可能预先保存在某些地方直接读取。笔者猜想的一种情况是，因为id字段本身属于Student表的主键索引，引擎本身实时保存着min(id)、max(id)的值供查询，或者直接读取主键索引树第一个、最后一个叶节点数据来获取，所以类似查询计划在实际执行中具有极大的执行效率。

select_type:标识查询计划的类型

select_type主要有如下几种不同类型：

• SIMPLE：简单SELECT,不使用UNION或子查询等
• PRIMARY：查询中若包含任何复杂的子部分,最外层的select被标记为PRIMARY
• UNION：UNION中的第二个或后面的SELECT语句
• SUBQUERY：子查询中的第一个SELECT
• DERIVED(派生表的SELECT, FROM子句的子查询)

对于 explain select id from Student where id=1;

select_type为SIMPLE，表示该sql是最简单形式的查询

对于 explain select name from Student union select name from Course;有：

我们看到有两个查询计划，对于最外层Student表的查询为PRIMARY，表示该语句是复杂语句，包含着其它查询计划，而这个包含的查询计划就是Course查询计划，Course查询计划的select_type为UNION，印证了上面对UNION类型的说明。结合id字段代表的意义，我们了解到引擎先是执行Course表计划再是执行Student表计划。

对于 explain select id,(select count(*) from Course) as count from Student; 有：

这次同样是两个查询计划，但区别在于我们构建了一个对Course表的子查询语句，相应的select_type为SUBQUERY，通过id可知，该sql会优先执行Course表的查询计划再执行Student表的查询计划。

对于 explain select name from (select name from Student where id=1) tb;有：

这个语句的特别之处在于对Student表的子查询计划被外面包裹了一层，因此对应的select_type为DERIVED。

到这里，我们认识到一个sql在执行过程中会被拆分一个以上的查询计划，计划间有一定的执行优先级，而select_type则很好地定义了不同计划存在的形式，这使得我们可以把复杂sql进行结构上的拆解，针对不同的查询计划一个个分析最后完成整体的优化。

接下来我们开始重点关注explian分析表单的其它几个字段：

• type
• possible_keys：查询计划可能用到的索引
• key：查询计划实际采用的索引
• rows：查询复杂度，亦可简单理解为查询计划需要处理的行数

这些字段和索引紧密联系，将真正为我们查询成本的分析提供参考，我们可以通过这些字段很好地判断索引的利用情况了。

type:对表进行数据查询时所利用的检索方式

type指明了该查询计划是否利用了索引结构，以及检索上存在的具体特点，具体类别有：

• ALL：没用到索引， MySQL将遍历全表以找到匹配的行
• index: 只利用索引结构，在innodb可以理解为只在B+树上进行全局检索，不直接对表进行操作
• range:只检索给定范围的行，使用一个索引来选择行
• ref: 通过索引检索，只不过该索引是非唯一索引，可能检索出多个相同值的记录
• eq_ref: 类似ref，区别就在使用的索引是唯一索引，对于每个索引键值，表中只有一条记录匹配，简单来说，就是多表连接中使用primary key或者 unique key作为关联条件
• const、system: 当MySQL对查询某部分进行优化，并转换为一个常量时，使用这些类型访问。如将主键置于where列表中，MySQL就能将该查询转换为一个常量，system是const类型的特例，当查询的表只有一行的情况下，使用system
• NULL: MySQL在优化过程中分解语句，执行时甚至不用访问表或索引，例如从一个索引列里选取最小值可以通过单独索引查找完成

对于 explain select name from Student where name='学生1';有：

type 为 ALL，即name在Student表中不是索引，为了查询name为'学生1'的数据，数据库将必要地对表数据进行全局检索，其中rows说明了需要检索的量级，我们可以理解为查询复杂度，因为数据库需要对表数据一行行处理，上面rows=699323我们可以判断出Student表大概是70万行的量级。

对于 explain select name from Student; 有：

type 为 index，因为我们对name已经事先构建了辅助索引，所以查询表中所有的name信息只需在name对应的B+树上扫描即可：

如上图，直接在辅助索引树的最左叶节点开始扫描，查询出所有name信息，查询出来的数据本身是按序排好的，如果你对sql刚好有排序需求：

select name from Student order by name asc;复制代码

那么查询速度相较于从表数据结构获取将有大幅的提升！

对于 explain select * from Student where id>1 and id