以下内容来自掘金小册 MySQL 是怎样运行的：从根儿上理解 MySQL
版权归原作者所有！
InnoDB数据页结构
-
InnoDB为了不同的目的而设计了不同类型的页，我们把用于存放记录的页叫做
数据页。 -
一个数据页可以被大致划分为7个部分，分别是
File Header，表示页的一些通用信息，占固定的38字节。Page Header，表示数据页专有的一些信息，占固定的56个字节。Infimum + Supremum，两个虚拟的伪记录，分别表示页中的最小和最大记录，占固定的26个字节。User Records：真实存储我们插入的记录的部分，大小不固定。Free Space：页中尚未使用的部分，大小不确定。Page Directory：页中的某些记录相对位置，也就是各个槽在页面中的地址偏移量，大小不固定，插入的记录越多，这个部分占用的空间越多。File Trailer：用于检验页是否完整的部分，占用固定的8个字节。
-
每个记录的头信息中都有一个
next_record属性，从而使页中的所有记录串联成一个单链表。 -
InnoDB会为把页中的记录划分为若干个组，每个组的最后一个记录的地址偏移量作为一个槽，存放在Page Directory中，所以在一个页中根据主键查找记录是非常快的，分为两步：
- 通过二分法确定该记录所在的槽。
- 通过记录的next_record属性遍历该槽所在的组中的各个记录。
-
每个数据页的
File Header部分都有上一个和下一个页的编号，所以所有的数据页会组成一个双链表。 -
为保证从内存中同步到磁盘的页的完整性，在页的首部和尾部都会存储页中数据的校验和和页面最后修改时对应的
LSN值，如果首部和尾部的校验和和LSN值校验不成功的话，就说明同步过程出现了问题。
InnoDB记录结构
-
页是
MySQL中磁盘和内存交互的基本单位，也是MySQL是管理存储空间的基本单位。 -
指定和修改行格式的语法如下：
CREATE TABLE 表名 (列的信息) ROW_FORMAT=行格式名称ALTER TABLE 表名 ROW_FORMAT=行格式名称 -
InnoDB目前定义了4种行格式
COMPACT行格式
具体组成如图：
Redundant行格式
具体组成如图：
Dynamic和Compressed行格式
这两种行格式类似于COMPACT行格式，只不过在处理行溢出数据时有点儿分歧，它们不会在记录的真实数据处存储字符串的前768个字节，而是把所有的字节都存储到其他页面中，只在记录的真实数据处存储其他页面的地址。
另外，Compressed行格式会采用压缩算法对页面进行压缩。
一个页一般是16KB，当记录中的数据太多，当前页放不下的时候，会把多余的数据存储到其他页中，这种现象称为行溢出。
B+树索引
- 每个索引都对应一棵
B+树，B+树分为好多层，最下边一层是叶子节点，其余的是内节点。所有用户记录都存储在B+树的叶子节点，所有目录项记录都存储在内节点。
InnoDB存储引擎会自动为主键（如果没有它会自动帮我们添加）建立聚簇索引，聚簇索引的叶子节点包含完整的用户记录。- 我们可以为自己感兴趣的列建立
二级索引，二级索引的叶子节点包含的用户记录由索引列 + 主键组成，所以如果想通过二级索引来查找完整的用户记录的话，需要通过回表操作，也就是在通过二级索引找到主键值之后再到聚簇索引中查找完整的用户记录。 B+树中每层节点都是按照索引列值从小到大的顺序排序而组成了双向链表，而且每个页内的记录（不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单链表。如果是联合索引的话，则页面和记录先按照联合索引前边的列排序，如果该列值相同，再按照联合索引后边的列排序。- 通过索引查找记录是从
B+树的根节点开始，一层一层向下搜索。由于每个页面都按照索引列的值建立了Page Directory（页目录），所以在这些页面中的查找非常
首先我们需要知道在innoDB中一条记录的格式:
将记录格式的其他信息去掉并把它竖起来的效果就是这样
注意record_type的取值不同，代表着该条记录有不同的含义:
一个页面里面里的记录通过next_record指针串成一个链表，为了查找方便，为这个链表设置了两个虚拟头节点: 最小记录和最大记录:
record_type = 1表示是最小记录，record_type = 3表示是最大记录。
record_type = 0表示是普通用户记录。
record_type = 2表示是索引项目记录。这个后面再说。
页分裂
假设我们的每个数据页最多能存放3条记录（实际上一个数据页非常大，可以存放下好多记录），innoDB在插入数据项的时候，会按照主键值的大小顺序串联成一个单向链表:
这个两表连接查询共需要查询1次t1表，2次t2表。当然这是在特定的过滤条件下的结果，如果我们把t1.m1 > 1这个条件去掉，那么从t1表中查出的记录就有3条，就需要查询3次t2表了。也就是说在两表连接查询中，驱动表只需要访问一次，被驱动表可能被访问多次。
内连接和外连接
内连接：对于
内连接的两个表，驱动表中的记录在被驱动表中找不到匹配的记录，该记录不会加入到最后的结果集。外连接：对于
外连接的两个表，驱动表中的记录即使在被驱动表中没有匹配的记录，也仍然需要加入到结果集。在
MySQL中，根据选取驱动表的不同，外连接仍然可以细分为2种：
左外连接
选取左侧的表为驱动表。
右外连接
选取右侧的表为驱动表。
WHERE子句
WHERE子句中的过滤条件就是我们平时见的那种，不论是内连接还是外连接，凡是不符合WHERE子句中的过滤条件的记录都不会被加入最后的结果集。
ON子句中的过滤条件把
ON子句放到外连接中，如果无法在被驱动表中找到匹配ON子句中的过滤条件的记录，那么该记录仍然会被加入到结果集中，对应的被驱动表记录的各个字段使用NULL值填充；把ON子句放到内连接中，MySQL会把它和WHERE子句一样对待，内连接中的WHERE子句和ON子句是等价的。一般情况下，我们都把只涉及单表的过滤条件放到
WHERE子句中，把涉及两表的过滤条件都放到ON子句中，我们也一般把放到ON子句中的过滤条件也称之为连接条件。对于左（外）连接和右（外）连接来说，必须使用ON子句来指出连接条件。内连接和外连接的根本区别就是在驱动表中的记录不符合
ON子句中的连接条件时会不会把该记录加入到最后的结果集连接的本质就是把各个连接表中的记录都取出来依次匹配的组合加入结果集并返回给用户。不论哪个表作为驱动表，两表连接产生的笛卡尔积肯定是一样的。而对于内连接来说，由于凡是不符合
ON子句或WHERE子句中的条件的记录都会被过滤掉，其实也就相当于从两表连接的笛卡尔积中把不符合过滤条件的记录给踢出去，所以对于内连接来说，驱动表和被驱动表是可以互换的，并不会影响最后的查询结果。但是对于外连接来说，由于驱动表中的记录即使在被驱动表中找不到符合ON子句连接条件的记录，所以此时驱动表和被驱动表的关系就很重要了，也就是说左外连接和右外连接的驱动表和被驱动表不能轻易互换。连接的原理
对于两表连接来说，驱动表只会被访问一遍，但被驱动表却要被访问到好多遍，具体访问几遍取决于对驱动表执行单表查询后的结果集中的记录条数。
通用的两表连接过程如下图所示：
如果有3个表进行连接的话，那么步骤2中得到的结果集就像是新的驱动表，然后第三个表就成为了被驱动表，重复上边过程，也就是步骤2中得到的结果集中的每一条记录都需要到t3表中找一找有没有匹配的记录
用伪代码表示一下这个过程就是这样：
for each row in t1 { #此处表示遍历满足对t1单表查询结果集中的每一条记录 for each row in t2 { #此处表示对于某条t1表的记录来说，遍历满足对t2单表查询结果集中的每一条记录 for each row in t3 { #此处表示对于某条t1和t2表的记录组合来说，对t3表进行单表查询
if row satisfies join conditions, send to client
}
}
}
这个过程就像是一个嵌套的循环，所以这种驱动表只访问一次，但被驱动表却可能被多次访问，访问次数取决于对驱动表执行单表查询后的结果集中的记录条数的连接执行方式称之为嵌套循环连接（Nested-Loop Join），这是最简单，也是最笨拙的一种连接查询算法。
使用索引加快连接速度
我们知道在嵌套循环连接的步骤2中可能需要访问多次被驱动表，如果访问被驱动表的方式都是全表扫描的话，要扫描很多次。 但是别忘了，查询t2表其实就相当于一次单表扫描，我们可以利用索引来加快查询速度。
以
SELECT * FROM t1, t2 WHERE t1.m1 > 1 AND t1.m1 = t2.m2 AND t2.n2 < 'd';
为例
原来的t1.m1 = t2.m2这个涉及两个表的过滤条件在针对t2表做查询时关于t1表的条件就已经确定了，所以我们只需要单单优化对t2表的查询了，上述两个对t2表的查询语句中利用到的列是m2和n2列，
-
在
m2列上建立索引，因为对m2列的条件是等值查找，比如t2.m2 = 2、t2.m2 = 3等，所以可能使用到ref的访问方法，假设使用ref的访问方法去执行对t2表的查询的话，需要回表之后再判断t2.n2 < d这个条件是否成立。这里有一个比较特殊的情况，就是假设
m2列是t2表的主键或者唯一二级索引列，那么使用t2.m2 = 常数值这样的条件从t2表中查找记录的过程的代价就是常数级别的。我们知道在单表中使用主键值或者唯一二级索引列的值进行等值查找的方式称之为const，而设计MySQL的大叔把在连接查询中对被驱动表使用主键值或者唯一二级索引列的值进行等值查找的查询执行方式称之为：eq_ref。 -
在
n2列上建立索引，涉及到的条件是t2.n2 < 'd'，可能用到range的访问方法，假设使用range的访问方法对t2表的查询的话，需要回表之后再判断在m2列上的条件是否成立。
假设m2和n2列上都存在索引的话，那么就需要从这两个里边儿挑一个代价更低的去执行对t2表的查询。当然，建立了索引不一定使用索引，只有在二级索引 + 回表的代价比全表扫描的代价更低时才会使用索引。
另外，有时候连接查询的查询列表和过滤条件中可能只涉及被驱动表的部分列，而这些列都是某个索引的一部分，这种情况下即使不能使用eq_ref、ref、ref_or_null或者range这些访问方法执行对被驱动表的查询的话，也可以使用索引扫描，也就是index的访问方法来查询被驱动表。所以我们建议在真实工作中最好不要使用*作为查询列表，最好把真实用到的列作为查询列表。
基于块的嵌套循环连接（Block Nested-Loop Join）
扫描一个表的过程其实是先把这个表从磁盘上加载到内存中，然后从内存中比较匹配条件是否满足。
如果表太大，内存里可能并不能完全存放的下表中所有的记录，所以在扫描表前边记录的时候后边的记录可能还在磁盘上，等扫描到后边记录的时候可能内存不足，所以需要把前边的记录从内存中释放掉。我们前边又说过，采用嵌套循环连接算法的两表连接过程中，被驱动表要被访问多次，如果这个被驱动表中的数据特别多而且不能使用索引进行访问，那就相当于要从磁盘上读好几次这个表，这个I/O代价就非常大了，所以我们得想办法：尽量减少访问被驱动表的次数。
我们可以在把被驱动表的记录加载到内存的时候，一次性和多条驱动表中的记录做匹配，这样就可以大大减少重复从磁盘上加载被驱动表的代价了。所以提出一个join buffer的概念，join buffer就是执行连接查询前申请的一块固定大小的内存，先把若干条驱动表结果集中的记录装在这个join buffer中，然后开始扫描被驱动表，每一条被驱动表的记录一次性和join buffer中的多条驱动表记录做匹配，因为匹配的过程都是在内存中完成的，所以这样可以显著减少被驱动表的I/O代价。使用join buffer的过程如下图所示：
最好的情况是join buffer足够大，能容纳驱动表结果集中的所有记录，这样只需要访问一次被驱动表就可以完成连接操作了。这种加入了join buffer的嵌套循环连接算法称之为基于块的嵌套连接（Block Nested-Loop Join）算法。
join buffer的大小是可以通过启动参数或者系统变量join_buffer_size进行配置，默认大小为262144字节（也就是256KB），最小可以设置为128字节。当然，对于优化被驱动表的查询来说，最好是为被驱动表加上效率高的索引，如果实在不能使用索引，并且自己的机器的内存也比较大可以尝试调大join_buffer_size的值来对连接查询进行优化。
另外需要注意的是，驱动表的记录并不是所有列都会被放到join buffer中，只有查询列表中的列和过滤条件中的列才会被放到join buffer中，所以再次提醒我们，最好不要把*作为查询列表，只需要把我们关心的列放到查询列表就好了，这样可以在join buffer中放置更多的记录。
