概述
前文详细介绍了InnoDB数据页的7个组成部分，我们知道了各个数据页可以组成一个双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表。每个数据页都会存储在它里面的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速定位找到指定的记录。
其中，页a、页b、页c…这些页可以不在物理结构上相连，只要通过双向链表相关联即可。
没有索引时进行查找
我们需要了解没有索引时是怎么查找记录的。
SELECT [查询列表] FROM 表名 WHERE 列名 = xxx;
在一个页中查找
假设目前表中的记录比较少，所有的记录都可以存放到一个页中。在查找记录时，可以根据搜索条件的不同分为两种情况。
- 以主键为搜索条件：这个查找过程我们已经很熟悉了，可以在页中使用二分法快速定位到对应的槽；然后再遍历该槽对应分组中的记录，即可快速定位到指定的记录。
- 以其他列作为搜索条件：对非主键列的查找可就不那么幸运了，因为在数据页中并没有为非主键列建立所谓的页目录，所以无法通过二分法快速定位相应的槽。在这种情况下，只能从Infimum记录开始依次遍历单向链表中的每条记录，然后对比每条记录是否符合搜索条件。很显然，这种查找的效率非常低。
在很多页中查找
在很多时候，表中存放的记录都是非常多的，需要用到好多的数据页来存储这些记录。在很多页中查找记录可以分为两个步骤：
定位到记录所在的页；
从所在的页内查找对应的记录；
在没有索引的情况下，无论是根据主键列还是其他列的值进行查找，由于我们不能快速地定位到记录所在的页，所以只能从第一页沿着双向链表一直往下找。在每一页中我们根据刚刚说过的查找方式查找指定的记录。因为要遍历所有的数据页，所以这种方式显然非常耗时。
索引
mysql> CREATE TABLE index_demo (
-> c1 INT,
-> c2 INT,
-> c3 CHAR(1),
-> PRIMARY KEY(c1)
-> ) ROW_FORMAT = COMPACT;
Query OK, 0 rows affected (0.03sec)
这个新建的index_demo表中有2个INT类型的列、1个CHAR(1)类型的列，而且我们规定c1列为主键。这个表使用COMPACT行格式来实际存储记录。为了理解上的方便，我们简化了index_demo表的行格式示意图，如图6-2所示。
record_type：记录头信息的一项属性，表示记录的类型。其中，0表示普通记录；2表示Infimum记录；3表示Supremum记录；1还没用过。
next_record：记录头信息的一项属性，表示从当前记录的真实数据到下一条记录的真实数据的距离。
各个列的值：这里只展示在index_demo表中的3个列，分别是c1、c2和c3.
其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。
一个简单的索引方案
回到正题，我们在根据某个搜索条件查找一些记录时，为什么要遍历所有的数据页呢？原因是各个页中的记录并没有规律，我们并不知道搜索条件会匹配到哪些页中的记录，所以不得不依次遍历所有的数据页。如果想快速定位到需要查找的记录在哪些数据页中，该咋办？我们可以想办法快速定位记录所在的数据页而建立一个别的目录，在建这个目录的过程中必须完成两件事。
1、下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。
假设每个数据页最多只能存放3条记录。
INSERT INTO index_demo VALUES(1,4,'u'),(3,9,'d'),(5,3,'y'),(4,4,'a');
结果如下图：
新分配的页号为28是因为新分配的数据页编号可能并不是连续的，也就是说我们使用的这些页在磁盘上可能并不挨着。它们只是通过维护上一页和下一页的编号而建立了链表关系。另外，页10中用户记录最大的主键值是5，而页28中有一条记录的主键值是4，因为5 > 4，所以这就不符合下一个数据页中用户的记录的主键值必须大于上一个页中用户记录的主键值的要求，所以在插入主键值4的记录时需要伴随着一次记录移动，也就是把主键值5的记录移动到页28中，再把主键值为4的记录插入到页10中。
结果如下所示：
这个过程表明，在对页中的记录进行增删改操作的过程中，我们必须通过一些诸如记录移动的操作来始终保证这个状态一直成立：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程也可以称为页分裂。
2、给所有的页建立一个目录项
由于数据页的编号可能并不是连续的，所以在向index_demo表中插入许多条记录后，可能如下图所示。
由于这些大小为16KB的页在磁盘上可能并不挨着，如果想从这么多页中根据主键值快速定位某些记录所在的页，就需要给他们编制一个目录，每个页对应一个目录项，每个目录项包括下面两个部分：
- 页的用户记录中最小的主键值，用key来表示
- 页号，用page_no表示
以页28为例，它对应目录项2，这个目录项中包含着该页的页号28以及该页中用户记录的最小主键值5.我们只需要把几个目录项在物理存储器上连续存储，比如把它们放到一个数组中，就可以实现根据主键值快速查找到某条记录的功能了。比如，我们向查找主键值为20的记录，具体查找过程分为两步。
- 先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中（因为12 < 20 < 209），它对应的页是页9。
- 再根据前文将的在页中查找记录的方式去页9中定位具体的记录。
InnoDB中的索引方案
之所以说刚才为每个数据页制作目录项的过程是一个简易的索引方案，是因为我们在根据主键值进行查找时，为了使用二分法快速定位具体的目录项，而假设所有目录项都可以在物理存储器上连续存储。但是这样做有下面几个问题。
1、InnoDB使用页作为管理存储空间的基本单位，也就是说最多只能保证16kb的连续存储空间。虽然一个目录项占用不了多大的存储空间，但是表中记录会越来越多。此时需要非常大的连续的存储空间才能把所有的目录项都放下，这对记录数量非常多的表来说是不现实的。
2、我们时常会对记录执行增删改的操作，假设我们把页28中的记录都删除，页28也就没有了存在的必要。这也就意味着目录项2也没有了存在的必要，这就需要把目录项2后的目录项都向前移动一下。这种牵一发而动全身的设计并不是什么好主意。又或者不移动目录项2，而是将其作为冗余放在目录项列表中，从而浪费了很多存储空间。
所以，InnoDB需要一种可以灵活管理所有目录项的方式。最后InnoDB复用了之前存储用户记录的数据页来存储目录项。为了与用户记录进行区分，我们把这些用来表示目录项的记录称为目录项记录。InnoDB是通过record_type属性来区分普通的用户记录还是目录项记录。
0：普通的用户记录。
1：目录项记录。
2：Infimum记录。
3：Supremum记录。
目录项记录和普通用户记录的不同点：
- 目录项记录的record_type值是1，普通用户记录的record_type值是0
- 目录项记录只有主键和页的编号两个列，而普通用户记录的列是用户自己定义的，可能包含很多列，另外还有InnoDB自己添加的隐藏列。
- 只有目录项的min_rec_flag才可能为1，普通用户记录的min_rec_flag属性都是0
除了上述几点外，这两者就没有区别了，它们用的是一样的数据页，页的组成结构也是一样的，都会为主键值生成Page Dictionary，从而按照主键值进行查找时可以使用二分法来加快查询速度。
现在以查找主键为20的记录为例，根据某个主键值去查找记录的步骤可以大致拆分为两步。
1、先到存储目录项记录的页（也就是页30）中通过二分法快速定位到对应的目录项记录，因为12 < 20 < 209，所以定位到对应的用户记录所在的页就是页9.
2、再到存储用户记录的页9中根据二分法快速定位到主键值为20的用户记录。
无论是存放用户记录的数据页，还是存放目录项记录的数据页，我们都把它们存放到B+树这个数据结构中。我们也将这些数据页称为B+树的节点。从图中可以看出，我们真正的用户记录其实都是存放在B+树最底层的节点上，这些也称为叶子结点或叶节点。其余用来存放目录项记录的节点称为非叶节点或者内节点，其中B+树最上边的那个节点也称为根节点。
在一般情况下，我们用到的B+树都不会超过4层。这样一来，在通过主键值去查找某条记录时，最多只需要进行4个页面内的查询。又因为在每个页面内存在Page Directory（页目录），所以在页面内也可以通过二分法快速定位记录。
聚簇索引
前面介绍的B+树本身就是一个目录，或者说本身就是一个索引，它有下面两个特点。
1、使用记录主键值的大小进行记录和页的排序，这包括3方面的含义
1.1 页内的记录按照主键的大小顺序排成一个单向链表，页内的记录被划分成若干个组，每个组中主键值最大的记录在页内的偏移量会被当做槽依次存放在页目录中，我们可以在页目录中通过二分法快速定位到主键列等于某个值的记录。
1.2 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
1.3 存放目录项记录的页分为不同的层级，在同一层级中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
2、B+树的叶子节点存储的是完整的用户记录。所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。
我们把具有这两个特点的B+树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在MySQL中显示地使用INDEX语句去创建。InnoDB存储引擎会自动地为我们创建聚簇索引。另外，在InnoDB存储引擎中，聚簇索引就是数据的存储方式，也就是所谓的索引即数据，数据即索引。
二级索引
聚簇索引只能在搜索条件是主键值时才能发挥作用，原因是B+树种的数据都是按照主键进行排序的。如果我们想以别的列作为搜索条件则需要再建一颗B+树。
1、使用记录c2列的大小进行记录和页的排序，这包括3方面的含义。
1.1、页（包括叶子节点和内节点）内的记录是按照c2列的大小顺序排成一个单向链表，页内的记录被划分成若干个组，每个组中c2列值最大的记录在页内的偏移量中会被当做槽依次存放到页目录中，我们可以在页目录中通过二分法快速定位到c2列等于某个值的记录。
1.2、各个存放用户记录的页也是根据页中记录的c2列大小顺序排成一个双向链表。
1.3、存放目录项记录的页分为不同的层级，在同一层级中的页也是根据页中目录项记录的c2列大小顺序排成一个双向链表。
2、B+树的叶子节点存储的并不是完整的用户记录，而只是c2列+主键列这两个列的值。
3、目录项记录中不再是主键+页号的搭配，而变成了c2列+页号的搭配
现在比方说我们想要查找满足搜索条件c2=4的记录，就可以使用刚刚建好的这颗B+树。不过我们这里需要注意下，因为c2列并没有唯一约束，也就是说满足搜索条件c2=4的记录可能有很多条，其实我们只需要在该B+树的叶子节点处定位到第一条满足搜索条件c2=4的那条记录，然后沿着由记录组成的单向链表一直向后扫描即可。另外，各个叶子节点组成了双向链表，搜索完本页面的记录后可以很顺利地跳到下一个页面中的第一条记录，然后继续沿着记录组成的单向链表向后扫描。
二级索引的查找过程如下：
步骤1、确定第一条符合c2=4条件的目录项记录所在的页。根据根页面（也就是页44）可以快速定位到第一条符合c2=4条件的目录项记录所在的页为页42（因为2<4<9）。
步骤2、通过第一条符合c2=4条件的目录项所在的页面确定第一条符合c2=4条件的用户记录所在的页。根据页42可以快速定位到第一条符合条件的用户记录所在的页为页34或者页35中，（因为2<4=4）
步骤3、在真正存储第一条符合c2=4条件的用户记录的页中定位到具体的记录。到页34和页35中定位到具体的用户记录（如果在页34中使用页目录定位到第一条符合条件的用户记录，就不需要再到页35中使用页目录去定位第一条符合条件的用户记录了）
步骤4、这个B+树的叶子节点中的记录只存储了c2和c1（也就是主键）两个列。在这个B+树的叶子节点处定位到第一条符合条件的那条用户记录之后，我们需要根据该记录中的主键信息到聚簇索引中查找到完整的用户记录。这个通过携带主键信息到聚簇索引中重新定位完整的用户记录的过程也称为回表。然后再返回到这颗B+树的叶子节点处，找到刚才定位到的符合条件的那条用户记录，并沿着记录组成的单项链表向后继续搜索其他也满足c2=4的记录，每找到一条的话就继续进行回表操作。重复这个过程，直到下一条记录不满足c2=4的这个条件为止。
因为这种以非主键列的大小为排序规则而建立的B+树需要执行回表操作才可以定位到完整的用户记录，所以这种B+树也称为二级索引或者辅助索引。
联合索引
我们也可以同时把多个列的大小作为排序规则，也就是同时为多个列建立索引。比如，我们想让B+树按照c2和c3列的大小进行排序，这里面包含两层含义：
- 先把各个记录和页按照c2列进行排序
- 在记录的c2列相同的情况下，再采用c3列进行排序
- 每条目录项记录有c2列、c3列、页号这3部分组成。各条记录先按照c2列的值进行排序，如果记录的c2列相同，则按照c3列的值进行排序。
- B+树叶子节点处的用户由c2列、c3列和主键c1列组成。
千万要注意的是，以c2和c3列的大小为排序规则建立的B+树称为联合索引，也称为复合索引或多列索引。它的本质也是一个二级索引，它的索引列包括c2、c3。
InnoDB中B+树索引的注意事项
1、根页面不变
实际上B+树的形成过程是下面这样的。
1、每当为某个表创建一个B+树索引时，都会为这个索引创建一个根节点页面。最开始表中没有数据的时候，每个B+树索引对应的根节点中既没有用户记录，也没有目录项记录。
2、随后向表中插入用户记录时，先把用户记录存储到这个根节点中。
3、在根节点中可用空间用完时继续插入记录，此时会将根节点中的所有记录复制到一个新分配的页中，然后对这个新页进行页分裂操作，得到另一个新页。这时新插入的记录会分配到新页中。根节点此时便升级为存储目录项记录的页，也就需要把新页对应的目录项记录插入到根节点中。
在这个过程中，需要特别注意的是，一个B+树索引的根节点自创建之日起便不会再移动。这样只要我们对某个表建立一个索引，那么它的根节点的页号便会被记录到某个地方，后续凡是InnoDB存储引擎需要用到这个索引时，都会从那个固定的地方取出根节点的页号，从而访问这个索引。
2、内节点中目录项的唯一性
为了让新插入的记录能找到自己在哪个页中，就需要保证B+树同一层内节点的目录项记录除页号这个字段以外是唯一的。所以二级索引的内节点的目录项记录的内容实际上是由3部分组成的：
- 索引列的值
- 主键值
- 页号
也就是我们把主键值也添加到二级索引内节点中的目录项记录中，这样就能保证B+树每一层节点中各条目录项除页号这个字段外是唯一的。
对于二级索引来说，是先按照二级索引列的值进行排序，在二级索引列值相同的情况下，在按照主键值进行排序。所以，为c2列建立索引其实相当于为（c2、c1）列建立了一个联合索引。另外，对于唯一二级索引来说，也可能出现多条记录键值相同的情况，唯一二级索引的内节点的目录项记录也会包含记录的主键值。
3、一个页面至少容纳2条记录
总结
InnoDB存储引擎是一颗B+树，完整的用户记录都存储在B+树第0层的叶子节点；其他层次的节点都属于内节点，内节点中存储的是目录项记录。
InnoDB的索引分为两种。
- 聚簇索引：以主键值的大小作为页和记录的排序规则，在叶子节点处存储的记录包含了表中所有的列。
- 二级索引：以索引列的大小作为页和记录的排序规则，在叶子节点处存储的记录是索引列+主键。
InnoDB存储引擎的B+树根节点自创建之后就不再移动。
在二级索引的B+树内节点中，目录项记录由索引列的值，主键值和页号组成。
一个数据页至少可以容纳2条记录。
B+树索引的使用
InnoDB存储引擎的B+树索引，我们必须熟悉下面这些结论：
- 每个索引都对应一颗B+树。B+树分为好多层，最下边一层是叶子节点，其余的是内节点。所有的用户记录都存储在B+树的叶子节点，所有的目录项记录都存储在内节点。
- InnoDB存储引擎会自动为主键建立聚簇索引（如果没有显示指定主键或者没有声明不允许存储NULL的UNIQUE键，它会自动添加主键），聚簇索引的叶子节点包含完整的用户记录。
- 我们可以为感兴趣的列建立二级索引，二级索引的叶子节点包含的用户记录由索引列和主键组成。如果想通过二级索引查找完整的用户记录，需要执行回表操作，也就是在通过二级索引找到主键值之后，再到聚簇索引中查找完整的用户记录。
- B+树中的每层的节点都按照索引列的值从小到大的顺序排序组成了双向链表，而且每个页内的记录（无论是用户记录还是目录项记录）都按照索引列的值从小到大的顺序形成了一个单向链表。如果是联合索引，则页面和记录先按照索引列中前面的列的值排序；如果该列的值相同，再按照索引列中后面的列的值顺序。
- 通过索引查找记录时，是从B+树的根节点开始一层一层向下搜索的。由于每个页面（无论是内节点还是叶子节点页面）中的记录都划分成若干个组，每个组中索引列值最大的记录在页内的偏移量会被当做槽依次存放到页目录中，因此可以在页目录中通过二分法快速定位到索引列等于某个值的记录。
索引的代价
- 空间上的代价：这个是显而易见的，因为每建立一个索引，都需要为它建立一颗B+树。每一颗B+树的每一个节点都是一个数据页。一个数据页默认会占用16kb的存储空间，而一颗很大的B+树由许多数据页组成，这将占用很大一片存储空间。
- 时间上的代价：每当对表中的数据进行增删改操作时，都需要修改各个B+树索引。而且我们前面讲过，B+树中的每层的节点都按照索引列的值从小到大的顺序排序组成了双向链表。无论是叶子节点中的记录还是内节点中的记录（也就是无论是用户记录还是目录项记录），都按照索引列的值从小到大的顺序形成了一个单向链表。而增删改操作可能会对节点和记录的顺序造成破坏，所以存储引擎需要额外的时间进行页面分裂，页面回收等操作，以维护节点和记录的顺序。如果建立了许多索引，每个索引对应的B+树都需要进行相关的维护操作。另外还有一点，就是在执行查询语句前，首先要生成一个执行计划。一般情况下，一条查询语句在执行过程中最多使用一个二级索引，在生成执行计划时需要计算使用不同索引执行查询时所需的成本，最后选取成本最低的那个索引执行查询。此时如果建立了太多的索引，可能会导致成本分析过程耗时太多，从而影响了查询语句的执行性能。
所以，在一个表中建立的索引越多，占用的存储空间也就越多，在增删改记录或者生成执行计划时性能也就越差。
应用B+树索引
扫描区间和右边界条件
对于某个查询来说，最简单的执行方案就是扫描表中的所有记录，判断每一条记录是否符合搜索条件。如果符合，就将其发送到客户端，否则跳过该记录。这种方案也成为全表扫描。
对于使用InnoDB存储引擎的表来说，全表扫描意味着从聚簇索引第一个叶子结点开始，沿着记录所在的单向链表向后扫描，直到最后一个叶子结点的最后一条记录，这是一种很笨的执行方案，但却是一种万能的执行方案，所有的查询都可以使用这种方案来执行。
前文讲到，可以利用B+树查找索引列值等于某个值的记录，这样可以明显减少需要扫描的记录的数量。由于B+树叶子节点中的记录是按照索引列值由小到大的顺序排序的，所以某个区间或者某些区间中的记录也可以明显减少需要扫描的记录数量。比如，下面这个语句
select * from single_table where id >= 2 and id <= 100;
这个语句其实是想查找id值在[2, 100]区间中的所有聚簇索引记录。我们可以通过聚簇索引的B+树快速地定位到id值为2的那条聚簇索引记录，然后沿着记录所在的单向链表向后扫描直到某条聚簇索引记录的id值不在[2, 100]区间中为止（即id值不再符合id <= 100条件）。
与扫描全部的聚簇索引记录相比，扫描id值在[2, 100]区间中的记录已经很大程度地减少了需要扫描的记录数量，所以提升了查询效率。简单起见，我们把这个例子中待扫描记录的id值所在的区间称为扫描区间，把形成这个扫描区间的搜索条件称为形成这个扫描区间的边界条件。
其实对于全表扫描来说，相当于扫描id值在（-∞,+∞）区间中的记录，也就是说全表扫描对应的扫描区间是（-∞,+∞）
对于下面这个查询语句：
SELECT * FROM single_table WHERE key2 IN (1438, 6328) OR (key2 >= 38 AND key2 <=79);
当然可以直接使用全表扫描的方式执行该查询，但是我们发现该查询的搜索条件涉及key2列，而我们又正好为key2列建立了uk_key2索引。如果使用uk_key2索引执行这个查询，则相当于从下面的3个扫描区间中获取二级索引记录。
- [1438，1438]：对应的边界条件就是key2 IN (1438)
- [6328, 6328]：对应的边界条件就是key2 IN (6328)
- [38, 79]：对应的边界条件就是key2 >= 38 AND key2 <= 79
方便起见，我们把像[1438,1438]、[6328,6328]这样只包含一个值的扫描区间称为单点扫描区间，把[38,79]这样包含多个值的扫描区间称为范围扫描区间。另外，由于我们的查询列表是*也就是需要读取完整的用户记录，所以从上述扫描区间中每获取一条二级索引记录，就需要根据该二级索引记录的id列的值执行回表操作，也就是到聚簇索引中找到相应的聚簇索引记录。
其实我们不仅仅可以使用uk_key2执行上述查询，还可以使用idx_key1、idx_key3、idx_key_part执行上述查询。以idx_key1为例，很显然无法通过搜索条件形成合适的扫描区间来减少需要扫描的idx_key1二级索引记录的数量，只能扫描idx_key1的全部二级索引记录。针对获取到的每一条二级索引记录，都需要执行回表操作来获取完整的用户记录。我们也可以说，使用idx_key1执行查询时对应的扫描区间就是（-∞,+∞）。这样虽然行得通，但是我们图啥呢？最简单粗暴的全表扫描方式已经需要扫描全部的聚簇索引记录了，这里除了需要访问全部的聚簇索引记录，还要扫描全部的idx_key1二级索引记录，这不是费力不讨好么。可见，在这个过程中并没有减少需要扫描的记录数量，效率反而比全表扫描更差。所以如果想使用某个索引来执行查询，但是又无法通过搜索条件形成合适的扫描区间来减少需要扫描的记录数量时，则不考虑使用这个索引执行查询。
并不是所有的搜索条件都可以成为边界条件，比如这个查询语句：
SELECT * FROM single_table WHERE key1 < 'a' AND key3 > 'z' AND common_field = 'abc';
如果使用idx_key1执行查询，那么相应的扫描区间就是（-∞,‘a’），形成该扫描区间的边界条件就是key1<‘a’。而key3 >‘z’ AND common_field=‘abc’ 就是普通的搜索条件，这些普通的搜索条件需要在获取到idx_key1的二级索引记录后，需要执行回表操作，在获取到完整的用户记录后才能去判断它们是否成立。
如果使用idx_key3执行查询，那么相应的扫描区间就是(‘z’,+∞)，形成该扫描区间的边界条件就是key3>‘z’。而key1<‘a’ AND common_field='abc’就是普通的搜索条件，这些普通的搜索条件需要在获取到idx_key3的二级索引后，再执行回表操作，在获取到完整的用户记录后才能去判断它们是否成立。
从上述描述中可以看到，在使用某个索引执行查询时，关键的问题就是通过搜索条件找出合适的扫描区间，然后再到相应的B+树中扫描索引列值在这些扫描区间的记录。对于每个扫描区间来说，仅需要通过B+树定位到该区间中的第一条记录，然后就可以沿着记录所在的单向链表向后扫描，直到某条记录不符合形成该扫描区间的边界条件为止。其实对于B+树索引来说，只要索引列和常数使用=、<=>、IN、NOT IN、IS NULL、IS NOT NULL、>、<、>=、<=、BETWEEN、!=或者LIKE操作符连接起来，就可以产生所谓的扫描区间。
不过需要有下面几点需要注意。
- IN操作符的语义与若干个等值匹配操作符(=)之间用OR连接起来的语义是一样的，都会产生多个单点扫描区间。比如下面这两个语句的语义效果是一样的。
SELECT * FROM single_table WHERE key2 IN (1438,6328);
SELECT * FROM single_table WHERE key2 = 1438 OR key2 = 6328;
- !=产生的扫描区间 比如
SELECT * FROM single_table WHERE key1 != 'a';
此时使用idx_key1执行查询时对应的扫描区间就是(-∞,‘a’)和(‘a’,+∞)
- LIKE比较特殊，只有在匹配完整的字符串或者匹配字符串前缀时才产生合适的扫描区间。
比较字符串的大小其实就是相当于依次比较每个字符的大小、字符串的比较过程如下所示。
- 先比较字符串的第一个字符：第一个字符小的字符串就比较小。
- 如果两个字符串的第一个字符相同，再比较第二个字符；第二个字符比较小的那个字符串就比较小；
- 如果两个字符串的前两个字符相同，那就接着比较第三个字符；以此类推。
对于某个索引列来说，字符串前缀相同的记录在由记录组成的单向链表中肯定是相邻的，比如我们有一个搜索条件是key1 LIKE ‘a%’, 对于二级索引idx_key1来说，所有字符串前缀为’a’的二级索引记录是肯定相邻的。这也就意味着我们只要定位到key1值的字符串前缀’a’的第一条记录，就可以沿着记录所在的单向链表向后扫描，直到某条二级索引记录的字符串前缀不为’a’为止。
很显然，key1 LIKE ‘a%’ 形成的扫描区间相当于[‘a’, ‘b’).
1、所有搜索条件都可以生成合适的扫描区间的情况
在使用某个索引执行查询时，有时每个小的搜索条件都可以生成一个合适的扫描区间来减少扫描的记录数量。比如下面的查询语句：
SELECT * FROM single_table WHERE key2 > 100 AND key2 > 200;
在使用uk_key2执行查询时，key2 > 100 和key2 >200 这两个小的搜索条件都可以形成一个扫描区间。由于这两个小的搜索条件是使用AND操作符连接的，所以最终形成的扫描区间就是对这两个搜索条件形成的扫描区间取交集后的结果。
key2 > 100和key2 > 200的交集当然就是key2 > 200了，也就是说上面这个查询语句使用uk_key2索引执行查询时对应的扫描区间就是(200,+∞)，形成该扫描区间的边界条件就是key2 > 200。
我们再看一下使用OR操作符将多个搜索条件连接在一起的情况。来看一下下面这个查询语句：
SELECT * FROM single_table WHERE key2 > 100 OR key2 > 200;
OR意味着需要取各个扫描区间的并集。也就是说上面这个查询语句在使用uk_key2索引执行查询时，对应的扫描区间就是(100,+∞)，形成扫描区间的条件就是key2 > 100。
2、有的搜索条件不能生成合适的扫描区间的情况
在使用某个索引执行查询时，有时某个小的搜索条件不能生成合适的扫描区间来减少需要扫描的记录数量。比如下面这个查询语句：
SELECT * FROM single_table WHERE key2 > 100 AND common_field = 'abc';
在使用uk_key2执行查询时，很显然搜索条件key2 > 100 可以形成扫描区间(100,+∞)，但是，由于uk_key2的二级索引记录并不按照common_field列进行排序，所以仅凭搜索条件common_field='abc’并不能减少需要扫描的二级索引记录的数量。也就是说此时该搜索条件生成的扫描区间其实就是(-∞,+∞)。由于key2 > 100 和common_field='abc’这两个小的搜索条件是使用AND操作符连接起来的，所以对(100,+∞)和(-∞,+∞)这两个扫描区间取交集后得到的结果自然是(100,+∞)，形成该扫描区间的条件就是key2>100。
其实，在使用uk_key2执行查询时，在寻找对应的扫描区间的过程中，搜索条件common_field = 'abc’没起到任何作用，我们可以直接把common_field = ‘abc’搜索条件替换为TRUE，如下所示：
SELECT * FROM single_table WHERE key2 > 100 AND TRUE;
在化简之后如下所示：
SELECT * FROM single_table WHERE key2 > 100;
也就是说上面那个查询语句在使用uk_key2执行查询时对应的扫描区间就是(100,+∞)。
再来看一下使用OR操作符的情况。查询语句如下所示：
SELECT * FROM single_table WHERE key2 > 100 OR common_field = 'abc';
同理，我们把使用不到uk_key2索引的搜索条件替换为TRUE，如下所示：
SELECT * FROM single_table WHERE key2 > 100 OR TRUE;
接着化简，结果如下所示：
SELECT * FROM single_table WHERE TRUE;
可见，如果强制使用uk_key2执行查询，对应的扫描区间就是(-∞,+∞)，也就是需要扫描uk_key2的全部二级索引记录，并且对于获取到的每一条二级索引记录，都需要执行回表操作。这个代价肯定要比执行全表扫描的代价都大。在这种情况下，我们是不需要考虑使用uk_key2来执行查询的。
3、从复杂的搜索条件中找出扫描区间
有些查询语句的搜索条件可能特别复杂，光是找出在使用某个索引执行查询时对应的扫描区间就挺麻烦的。比如下面这个查询语句：
SELECT * FROM single_table WHERE
(key1 > 'xyz' AND key2 = 748) OR
(key1 < 'abc' AND key1 > 'lmn') OR
(key1 LIKE '%suf' AND key1 > 'zzz' AND (key2 < 8000 OR common_field = 'abc'));
我们按照下面的套路分析一下。
- 首先查看WHERE子句中的搜索条件都涉及到了哪些列，以及我们为哪些列建立了索引。这个查询语句的搜索条件涉及了key1、key2、common_field这3个列，其中key1列有普通的二级索引idx_key1，key2列有唯一二级索引uk_key2。
- 对于那些可能用到的索引，分析它们的扫描区间。
假设使用idx_key1执行查询
我们需要把那些不能形成合适扫描区间的搜索条件暂时移除掉。移除方法也很简单，直接把他们替换成TRUE就好了。上面的查询中除了有关key2和common_field列的搜索条件不能形成合适的扫描区间外，key1 LIKE '%suf’形成的扫描区间是(-∞,+∞)，所以也需要将它替换为TRUE。把这些不能形成合适扫描区间的搜索条件替换为TRUE之后，搜索条件如下所示：
(key1 > 'xyz' AND TRUE) OR (key1 < 'abc' AND key1 > 'lmn') OR (key1 LIKE '%suf' AND key1 > 'zzz' AND (TRUE OR TRUE))
对这个搜索条件进行化简，结果如下所示：
(key1 > 'xyz') OR (key1 < 'abc' AND key1 > 'lmn') OR (key1 LIKE '%suf' AND key1 > 'zzz'
下面替换掉永远为TRUE或FALSE的条件。由于 key1 < ‘abc’ AND key1 > ‘zzz’ 永远为FALSE，所以上面的搜索条件可以写成下面这样：
key1 > 'xyz' OR key1 > 'zzz'
继续化简。由于key1 > ‘xyz’ 和 key1 > 'zzz’之间是使用OR操作符连接起来的，这意味着要取并集，所以最终的化简结果就是key1 > ‘xyz’。也就是说，最初的查询语句如果使用idx_key1索引执行查询，则对应的扫描区间就是(‘xyz’,+∞)。也就是说需要把满足key1 > 'xyz’条件的所有二级索引记录都取出来，针对获取到的每一条二级索引记录，都要用它的主键值再执行回表操作，在得到完整的用户记录之后再使用其他的搜索条件进行过滤。
假设使用idx_key2执行查询
我们需要把那些不能形成合适扫描区间的搜索条件暂时使用TRUE替换掉，其中有关key1和common_field的搜索条件都需要被替换掉，替换后的结果如下所示：
(TRUE AND key2 = 748) OR (TRUE AND TRUE) OR (TRUE AND TRUE AND (key2 < 8000 OR TRUE));
化简之后
key2 = 748 OR TRUE
这个化简之后就更简单了
TRUE
这个结果也就意味着如果要使用idx_key2索引执行查询，则对应的扫描区间就是(-∞,+∞)，也就是需要扫描uk_key2的全部二级索引记录，针对获取到的每一条二级索引记录还要进行回表操作。这不是得不偿失么！所以在这种情况下是不会使用uk_key2索引的。
在使用idx_key1执行上述查询时，搜索条件key1 LIKE '%suf’比较特殊。虽然它不能作为形成扫描空间的边界条件，但是idx_key1的二级索引记录是包含key1列的。因此我们可以先判断获取到的二级索引记录是否符合这个条件。如果符合再执行回表操作，如果不符合就不执行回表操作了。这样可能减少因回表操作而带来的性能损耗，这种优化方式称为索引条件下推。
4、使用联合索引执行查询时对应的扫描区间
联合索引的索引列包含多个列，B+树中的每一层页面以及每个页面中的记录采用的排序规则较为复杂。以single_table表的idx_key_part联合索引为例，它采用的排序规则如下所示：
- 先按照key_part1列的值进行排序
- 在key_part1列的值相同的情况下，再按照key_part2列的值进行排序
- 在key_part1和key_part2列的值都相同的情况下，再按照key_part3列的值进行排序
对于查询语句Q1来说：
SELECT * FROM single_table WHERE key_part1 = 'a';
由于二级索引是先按照key_part1列的值进行排序的，所以符合key_part1='a’条件的所有记录肯定是相邻的。我们可以定位到符合key_part1='a’的第一条记录，然后沿着记录所在的单向链表向后扫描（如果在本页面中的记录扫描完了，就根据叶子节点的双向链表找到下一个页面中的第一条记录，继续沿着记录所在的单向链表向后扫描），直到某条记录不符合key_part1='a’条件为止。
也就是说，如果使用idx_key_part索引执行查询语句Q1，对应的扫描区间就是[‘a’,‘a’]，形成这个扫描区间的边界条件就是key_part1=‘a’。
对于查询语句Q2来说：
SELECT * FROM single_table WHERE key_part1 = 'a' AND key_part2 = 'b';
由于二级索引记录是先按照key_part1列的值进行排序的，在key_part1列的值相等的情况下，再按照key_part2列进行排序，所以符合key_part1 = ‘a’ AND key_part2 = 'b’条件的二级索引记录肯定是相邻的。我们可以定位到符合key_part1 = ‘a’ AND key_part2 = 'b’条件的第一条记录，然后沿着记录所在的单向链表向后扫描，直到某条记录不符合key_part1 = 'a’条件或者key_part2 = 'b’条件为止（当然，对于获取到的每一条二级索引记录都需要执行回表操作。）
也就是说，如果使用idx_key_part索引执行查询语句Q2，可以形成扫描区间[(‘a’,‘b’),(‘a’,‘b’)]，形成这个扫描区间的边界条件就是key_part1 = ‘a’ AND key_part2 = ‘b’。
[(‘a’,‘b’),(‘a’,‘b’)]代表在idx_key_part1索引中，从第一条符合key_part1 = ‘a’ AND key_part2 = 'b’条件的记录开始，到最后一条符合key_part1 = ‘a’ AND key_part2 = 'b’的记录为止的所有二级索引记录。
对于查询语句Q3来说：
SELECT * FROM single_table WHERE key_part1 = 'a' AND key_part2 = 'b' AND key_part3 = 'c';
由于二级索引记录是先按照key_part1列的值排序的，在key_part1列的值相等的情况下再按照key_part2列进行排序；在key_part1和key_part2列的值都相等的情况下，再按照key_part3列进行排序，所以符合key_part1 = ‘a’ AND key_part2 = ‘b’ AND key_part3 = 'c’条件的二级索引肯定是相邻的。我们可以定位到key_part1 = ‘a’ AND key_part2 = ‘b’ AND key_part3 = 'c’条件的第一条记录，然后沿着记录所在的单向链表向后扫描，直到某条记录不符合key_part1 = ‘a’ 或者 key_part2 = ‘b’ 或者 key_part3 = 'c’条件为止。（当然，对于获取到的每一条二级索引记录都要执行回表操作）
如果使用idx_key_part索引执行查询语句Q3，可以形成扫描区间[(‘a’,‘b’,‘c’),(‘a’,‘b’,‘c’)]，形成这个扫描区间的边界条件就是key_part1 = ‘a’ AND key_part2 = ‘b’ AND key_part3 = ‘c’。
对于扫描语句Q4来说：
SELECT * FROM single_table WHERE key_part1 < 'a';
由于二级索引记录是先按照key_part1列的值进行排序的，所以符合key_part1<'a’条件的所有记录肯定是相邻的。我们可以定位到符合key_part1<'a’条件的第一条记录（其实就是idx_key_part索引第一个叶子节点的第一条记录），然后沿着记录所在的单向链表向后扫描，直到某条记录不符合key_part1<'a’条件为止（当然，对于获取到的每一条二级索引记录都要执行回表操作）
对于扫描语句Q5来说：
SELECT * FROM single_table WHERE key_part1 = 'a' AND key_part2 > 'a' AND key_part2 < 'd';
由于二级索引是先按照key_part1列的值进行排列的，在key_part1列的值相等的情况下再按照key_part2列进行排序。也就是说，在符合key_part1=‘a’条件的二级索引记录中，这些记录时按照key_part2的值进行排序的，那么此时符合key_part1 = ‘a’ AND key_part2 > ‘a’ AND key_part2 < 'd’条件的索引记录肯定是相邻的。我们可以定位到符合key_part1 = ‘a’ AND key_part2 > ‘a’ AND key_part2 < 'd’条件的第一条记录，然后沿着所在的单向链表向后扫描，直到某条记录不符合key_part1 = ‘a’ 或者 key_part2 > ‘a’ 或者 key_part2 < 'd’条件为止。
也就是说，如果使用idx_key_part1索引执行的查询语句Q5，可以形成扫描区间[(‘a’,‘a’),(‘a’,‘b’)]，形成这个扫描区间的边界条件就是key_part1 = ‘a’ AND key_part2 > ‘a’ AND key_part2 < ‘d’。
对于查询语句Q6来说：
SELECT * FROM single_table WHERE key_part2 = 'a';
由于二级索引记录不是直接按照key_part2列的值进行排序的，所以符合key_part2 = ‘a’的二级索引记录可能并不相邻，也就意味着我们不能通过这个key_part2 = ‘a’搜索条件来减少需要扫描的记录数量。在这种情况下，我们是不会使用idx_key_part索引来执行查询的。
对于查询语句Q7来说：
SELECT * FROM single_table WHERE key_part1 = 'a' AND key_part3 = 'c';
由于二级索引是先按照key_part1列的值排序的，所以符合key_part1 = 'a’的条件的二级索引记录肯定是相邻的。但是对于符合key_part1=‘a’条件的二级索引记录来说，并不是直接按照key_part3列进行排序的，也就是说我们不能根据搜索条件 key_part3 = 'c’来进一步减少需要扫描的记录数量。那么如果使用idx_key_part索引执行查询，可以定位到符合key_part1 = 'a’条件的第一条记录，然后沿着记录所在的单向链表向后扫描，直到某条记录不符合key_part1='a’条件为止。所以在使用idx_key_part索引执行查询语句Q7的过程中，对应的扫描区间其实是[‘a’,‘a’]，形成扫描区间的边界条件是key_part1 = 'a’与key_part3无关。
针对获取到的每一条二级索引记录，如果没有开启索引条件下推特性，则必须先执行回表操作，在获取到完整的用户记录后再判断key_part3='c’条件是否成立。如果开启了索引条件下推特性，可以立即判断该二级索引记录是否符合key_part3 = 'c’条件。如果符合该条件，则再执行回表操作；如果不符合则不执行回表操作，直接跳到下一条二级索引记录，索引条件下推特性是在MySQL5.6中引入的，且默认是开启的。
对于查询语句Q8来说：
SELECT * FROM single_table WHERE key_part1 < 'b' AND key_part2 = ‘a’;
由于二级索引是先按照key_part1列的值排序的，所以符合key_part1 < 'b’条件的二级索引记录肯定是相邻的。但是对于符合key_part1 < 'b’条件的二级索引来说，并不是直接按照key_part2列排序的。也就是说，我们不能根据搜索条件key_part2 = ‘a’ 来进一步减少需要扫描的记录数量。那么，如果使用idx_key_part索引执行查询，可以定位到符合key_part1 < 'b’条件的第一条记录（其实就是idx_key_part索引的第一个叶子节点的第一条记录）然后沿着记录所在的单向链表向后扫描，直到某条记录不符合key_part1 < 'b’条件不成立为止。
所以在使用idx_key_part索引执行查询语句Q8的过程中，对应的扫描区间其实是[-∞,‘b’)，形成该扫描区间的边界条件是key_part1 < 'b’与key_part2 = 'a’无关。
对于查询语句Q9来说：
SELECT * FROM single_table WHERE key_part1 <= 'b' AND key_part2 = 'a';
很显然Q9和Q8很像，但是在涉及key_part1的条件时，Q8中的条件是key_part1 < ‘b’，Q9中的条件时key_part1 <= ‘b’。很显然符合key_part1 <= 'b’条件的二级索引记录是相邻的。但是对于符合key_part1 <= 'b’条件的二级索引来说，并不是直接按照key_part2列排序的。但是，对于符合key_part1 = 'b’的二级索引记录来说，是按照key_part2列的值排序的。那么在确定扫描的二级索引记录的范围时，当二级索引记录的key_part1 = 'b’时，也可以通过key_part2 = 'a’条件减少需要扫描的二级索引记录范围。也就是说，当扫描到不符合key_part1 <= ‘b’ AND key_part2 = 'a’条件的第一条记录时，就可以结束扫描，而不需要将所有key_part1列值为’b’的记录扫描完。
索引用于排序
我们在编写查询语句时，经常需要使用ORDER BY子句对查询出来的记录按照某种规划进行排序。在一般情况下，我们只能把记录加载到内存中，然后再用一些排序算法在内存中对这些记录进行排序。有时查询的结果集可能太大以至于无法在内存中进行排序，此时就需要暂时借助磁盘的空间来存放中间结果，在排序完成后再把排好序的结果返回客户端。
在MySQL中，这种在内存或者磁盘中进行排序的方式称为文件排序。但是如果ORDER BY子句中使用了索引列，就有可能省去在内存或磁盘中排序的步骤。
1、使用联合索引进行排序时的注意事项
在使用联合索引时，需要注意一点：ORDER BY子句后面的列的顺序也必须按照索引列的顺序给出；如果给出ORDER BY key_part3,key_part2,key_part1的顺序，则无法使用B+树索引。之所以颠倒排序列就不能使用索引，原因还是联合索引中页面和记录的排序规则是固定的，也就是按照key_part1值排序；如果记录的key_part1值相同，再按照key_part2值排序；如果记录的key_part1和key_part2值都相同，再按照key_part3值排序。如果ORDER BY子句的内容是ORDER BY key_part3,key_part2,key_part1，那就要求先按照key_part3值排序；如果记录的key_part3相同，再按照key_part2值排序；如果记录的key_part3和key_part2值都相同，再按照key_part1值排序。这显然是冲突的。
同理，ORDER BY key_part1和ORDER BY key_part1,key_part2这些仅对联合索引的索引列中左边连续的列进行排序的形式，也是可以利用B+树索引的。另外，当联合索引的索引列左边连续的列为常量时，也可以使用联合索引对右边的列进行排序。
2、不可以使用索引进行排序的几种情况
（1）、ASC和DESC混用：对于使用联合索引进行排序的场景，我们要求各个排序列的顺序规则是一致的，也就是要么各个列都是按照ASC（升序）规则排序，要么都是按照DESC（降序）规则排序。
（2）、排序列包含非同一个索引的列
（3）、排序列是某个联合索引的索引列，但是这些排序列在联合索引中并不连续
（4）、用来形成扫描区间的索引列与排序列不同
（5）、排序列不是以单独列名的形式出现在ORDER BY子句中
索引用于分组
有时为了方便统计表中的一些信息，会把表中的记录按照某些列进行分组。比如下面这个分组查询语句：
SELECT key_part1,key_part2,key_part3,count(*) FROM signle_table GROUP BY key_part1,key_part2,key_part3;
这个查询语句相当于执行了3次分组操作。
- 先按照key_part1值把记录进行分组，key_part1值相同的所有记录划分为一组
- 将key_part1值相同的每个分组中再按照key_part2的值进行分组，将key_part2值相同的记录放到一个小分组中；看起来像是在一个大分组中又细分了好多个小组
- 再将上一步中产生的小分组按照key_part3的值分成更小的组。所以整体上看起来就像是先把记录分成一个大分组，然后再把大分组分成若干个小分组，最后把若干个小分组再细分成更多的小分组
然后针对那些小小分组进行统计，上面这个查询语句就是统计每个小小分组包含的记录条数。如果没有idx_key_part索引，就得建立一个用于统计的临时表，在扫描聚簇索引的记录时将统计的中间结果填入这个临时表。当扫描完后，再把临时表中的结果作为结果集发送给客户端。如果有了索idx_key_part，恰巧这个分组排序又与idx_key_part中的索引列顺序是一致的，而idx_key_part的二级索引记录又是按照索引列的值排好序的。所以可以直接使用idx_key_part索引进行分组，而不用再建立临时表了。
与使用B+树索引进行排序差不多，分组列的顺序也需要与索引列的顺序一致；也可以只使用索引列中左边连续的列进行分组。
回表的代价
对于下面这个查询语句来说
SELECT * FROM single_table WHERE key1 > 'a' AND key1 < 'c';
我们可以选择下面两种方式来执行：
- 以全表扫描的方式执行该查询，也就是直接扫描全部的聚簇索引记录，针对每一条聚簇索引记录，都判断搜索条件是否成立，如果成立则发送到客户端，否则跳过该记录。
- 使用idx_key1执行该查询
可以根据搜索条件key1 > ‘a’ AND key1 < ‘c’ 得到对应的扫描区间(‘a’, ‘c’)，然后扫描该扫描区间中的二级索引记录。由于idx_key1索引的叶子节点存储的是不完整的用户记录，仅包含key1、id这两列，而查询列表是* ，这意味着我们需要获取每条二级索引记录对应的聚簇索引记录，也就是执行回表操作，在获取到完整的用户记录后再发送到客户端。
对于使用InnoDB存储引擎的表来说，索引中的数据页都必须存放在磁盘中，等到需要时再加载到内存中使用。这些数据页会被存放到磁盘中的一个或多个文件中，页面的页号对应着该页在磁盘文件中的偏移量。以16KB大小的页面为例，页号为0的页面对应着这些文件中偏移量0的位置，页号为1的页面对应着这些文件中偏移量为16KB的位置。
也就是说，idx_key1在扫描区间(‘a’,‘c’)中的二级索引记录所在的页面的页号尽可能相邻。即使这些页面的页号不相邻，但起码一个页面可以存放很多记录，也就是说在执行完一次页面IO后，就可以把很多二级索引记录从磁盘加载到内存中。总而言之，就是读取在扫描区间(‘a’,‘c’)中的二级索引记录时，所付出的代价还是较小的。不过扫描区间(‘a’,‘c’)中的二级索引记录的id值的大小是毫无规律的，我们每读取一条二级索引记录，就需要根据该二级索引记录的id值到聚簇索引中执行回表操作。如果对应的聚簇索引记录所在的页面不在内存中，就需要将该值从磁盘加载到内存中。由于要读取很多id值并不是连续的聚簇索引记录，而且这些聚簇索引记录分布在不同的数据页中，这些数据页毫无规律，因此会造成大量的随机IO。
需要执行回表操作的记录越多，使用二级索引进行查询的性能也就越低，某些查询宁愿使用全表扫描也不使用二级索引。比如，假设key1值在’a’~'c’之间的用户记录数量占用全部记录数量的99%以上，如果使用idx_key1索引，则会有99%以上的id值需要执行回表操作。这不是吃力不讨好么，还不如直接执行全表扫描。
那么在执行查询时，什么时候采用全表扫描，什么时候使用二级索引+回表的方式呢？这就是查询优化器应该做的工作。查询优化器会事先对表中的记录计算一些统计数据，然后再利用这些统计数据或者访问表中的少量记录来计算需要执行回表操作的记录数。如果需要执行回表操作的记录越多，就越倾向于使用全表扫描，反之则倾向于使用二级索引+回表的方式。当然，查询优化器所做的分析工作没有那么简单，但大致上是这样一个过程。
一般情况下，可以给查询语句指定LIMIT子句来限制查询返回的条数，这可能会让查询优化器倾向于选择使用二级索引+回表的方式进行查询，原因是回表的记录越少，性能提升就越高。比如，上面的查询语句可以改写成下面这样：
SELECT * FROM single_table WHERE key1 > 'a' AND key1 < 'c' LIMIT 10;
添加了LIMIT 10子句后的查询语句更容易让查询优化器采用二级索引+回表的方式来执行。
对于需要对结果进行排序的查询，如果在采用二级索引执行查询时需要执行回表操作的记录特别多，也倾向于使用全表扫描+文件排序的方式执行查询。比如下面这个查询语句：
SELECT * FROM single_table ORDER BY key1;
由于查询列表是*，如果使用二级索引进行排序，则需要对所有的二级索引记录执行回表操作。这样的操作的成本还不如直接遍历聚簇索引然后再进行文件排序低，所以查询优化器会倾向于使用全表扫描的方式执行查询。如果添加了LIMIT子句，比如下面这个查询语句：
SELECT * FROM single_table ORDER BY key1 LIMIT 10;
这个查询语句需要执行回表操作的记录特别少，查询优化器就会倾向于使用二级索引+回表的方式来执行。
更好地创建和使用索引
只为用于搜索、排序或分组的列创建索引
我们只为出现在WHERE子句中的列、连续子句中的连接列，或者出现在ORDER BY或GROUP BY子句中的列创建索引。仅出现在查询列表中的列就没必要建立索引了。
考虑索引列中不重复值的个数
在通过二级索引+回表的方式执行查询时，某个扫描区间中包含的二级索引记录数量越多，就会导致回表操作的代价越大。我们在为某个列创建索引时，需要考虑该列中不重复值的个数占全部记录条数的比例。如果比例太低，则说明该列包含过多的重复值，那么在通过二级索引+回表的方式执行查询时，就有可能执行太多次回表操作。
索引列的类型尽量小
因为数据类型越小，索引占用的存储空间就越少，在一个数据页内就可以存放更多的记录，磁盘IO带来的性能损耗也就越小（一次页面IO可以将更多的记录加载到内存中），读写效率也就越高。
这个建议对于表的主键来说更加适用，因为不仅聚簇索引会存储主键值，其他所有的二级索引的节点都会存储一份记录的主键值。如果主键使用更小的数据类型，也就意味着能节省更多的存储空间。
为列前缀建立索引
我们知道，一个字符串其实是由若干个字符组成。如果在MySQL中使用utf8字符集存储字符串，则需要1~3字节来编码一个字符。假设字符串很长，那么在存储这个字符串时就需要占用很大的存储空间。在需要为这个字符串所在的列建立索引时，就意味着对应的B+树中的记录中，需要把该列的完整字符串存储起来。字符串越长，在索引列中占用的存储空间越大。
前文说过，索引列的字符串前缀其实也是排好序的，所以索引的设计人员提出了一个方案，即只将字符串的前几个字符存放在索引中，也就是说在二级索引的记录中只保留了字符串的前几个字符。比如我们可以这样修改idx_key1索引，让索引中只保留字符串的前10字符：
ALTER TABLE single_table DROP INDEX idx_key1;
ALTER TABLE single_table ADD INDEX idx_key1(key1(10));
然后再执行下面这个查询语句：
SELECT * FROM single_table WHERE key1 = 'abcdefghijklmn';
由于在idx_key1的二级索引记录中只保留字符串的前10个字符，所以我们只能定位到前缀为abcdefghij的二级索引记录，在扫描这些二级索引记录时再判断它们是否满足key1=‘abcdefghijklmn’。当列中存储的字符串包含的字符较多时，这种为列前缀建立索引的方式明显减少索引大小。
不过，在只对列前缀建立索引的情况下，下面这个查询语句就不能使用索引来完成排序需求了：
SELECT * FROM single_table ORDER BY key1 LIMIT 10;
因为二级索引idx_key1中不包含完整的key1列信息，所以在仅使用idx_key1索引执行查询时，无法对key1列前10字符相同但其余字符不同的记录进行排序。也就是说，只为列前缀建立索引的方式无法支持使用索引进行排序的需求。
覆盖索引
为了彻底告别回表操作带来的性能损耗，建议最好在查询列表中只包含索引列，比如下面这个查询语句：
SELECT key1,id FROM single_table WHERE key1 > 'a' AND key1 < 'c';
由于我们只查询key1列和id列的值，所以在使用idx_key1索引来扫描(‘a’,‘c’)区间中的二级索引记录时，可以直接从获取到的二级索引记录中，读出key1列和id列的值，而不需要再通过id值到聚簇索引中执行回表操作了，这样就省去了回表操作带来的性能损耗。我们把这种索引中已经包含所有需要读取的列的查询方式称为覆盖索引。排序也优先使用覆盖索引进行查询。比如下面这个查询语句：
SELECT key1 FROM single_table ORDER BY key1;
虽然这个查询语句中没有LIMIT语句，但是由于可以采用覆盖索引，所以查询优化器会直接使用idx_key1索引进行排序，而不需要执行回表操作。
让索引列以列名的形式在搜索条件中单独出现
新插入记录时主键大小对效率的影响
最好让插入记录的主键值依次递增。
冗余和重复索引
单表访问方法
MySQL Server有一个称为优化器的模块。MySQL server在对一条查询语句进行语法解析之后，就会将其交给优化器来优化，优化的结果就是生成一个所谓的执行计划。这个执行计划表明了应该使用哪些索引进行查询、表之间的连接顺序是啥样的，等等。最后会按照执行计划中的步骤调用存储引擎提供的接口来真正地执行查询，并将查询结果返回给客户端。
访问方法概念
我们平时所写的那些查询语句本质上只是一种声明式的语法，只是告诉MySQL要获取的数据符合哪些规则，至于MySQL背地里是如何把查询结果搞出来的则是MySQL自己的事儿。
MySQL执行查询语句的方式称为访问方法（access method）或者访问类型。同一个查询语句可以使用多种不同的访问方法来执行，虽然最后的查询结果都是一样的，但是不同的执行方式花费的时间成本可能差距甚大。
const
有时可以通过主键列来定位一条记录，比如下面这个查询：
SELECT * FROM single_table WHERE id = 1438;
MySQL会直接利用主键值在聚簇索引中定位对应的用户记录。
与之类似，我们根据唯一二级索引列来定位一条记录的速度也很快。
SELECT * FROM single_table WHERE key2 = 3841;
这个查询的执行过程分为下面两步：
- 在uk_key2对应的B+树索引中，根据key2列与常数的等值比较条件定位到一条二级索引记录。
- 然后再根据该记录的id值到聚簇索引中获取完整的用户记录。
MySQL认为，通过主键或者唯一二级索引列与常数的等值比较来定位一条记录是很快的，所以把这种通过主键或者唯一二级索引列来定位一条记录的访问方法称为const（意思是常数级别的，代价可以忽略不计的）。不过这种const访问方法只能在主键列或者唯一二级索引列与一个常数进行等值比较时才有效。如果主键或者唯一二级索引的索引列由多个列构成，则只有在索引列中的每一个列都与常数进行等值比较时，这个const访问方法才有效（这事因为只有在该索引的每一个列都采用等值比较时，才可以保证最多只有一条记录符合搜索条件）。
对于唯一二级索引列来说，在查询列为NULL值时，情况比较特殊。
SELECT * FROM single_table WHERE key2 IS NULL;
因为唯一二级索引列并不限制NULL值的数量，所以上述语句可能访问到多条记录。也就是说上面这个语句不可以使用const访问方法来执行。
ref
有时，我们需要将某个普通的二级索引列与常数进行等值比较，比如：
SELECT * FROM single_table WHERE key1 = 'abc';
对于这个查询，当然可以选择全表扫描的方式来执行。不过也可以使用idx_key1来执行，此时对应的扫描区间就是[‘abc’, ‘abc’]，这也是一个单点的扫描区间。我们可以定位到key1 = 'abc’条件的第一条记录，然后沿着记录所在的单向链表向后扫描，直到某条记录不符合key1 = 'abc’条件为止。由于查询列表是*，因此针对获取到的每一条二级索引记录，都需要根据这条记录的id值执行回表操作，到聚簇索引中获取到完整的用户记录后再发送到客户端。
由于普通二级索引并不限制索引列值的唯一性，所以位于扫描空间中的二级索引记录可能有多条，此时使用二级索引执行查询的代价就是取决于该扫描空间中的记录条数。如果该扫描空间中的记录较少，则回表操作的代价还是比较低的。搜索条件为二级索引列与常数进行等值比较，形成的扫描空间为单点扫描区间，采用二级索引来执行查询的访问方法称为ref。
采用二级索引来执行查询时，其实每获取一条二级索引记录，就会立刻对其执行回表操作，而不是将所有二级索引记录的主键值都收集起来后再统一执行回表操作。
对于普通的二级索引来说，通过索引列等值比较后可能会匹配到多条连续的二级索引记录，而不是像主键或者唯一二级索引那样最多只能匹配到一条记录。所以这种ref访问方法比const差了那么一点。这里需要注意下面两种情况：
- 在二级索引列允许存储NULL值时，无论是普通的二级索引，还是唯一二级索引，他们的索引列并不限制NULL值得数量，所以在执行包含 key IS NULL形式的搜索条件的查询时，最多只能使用ref访问方法，而不能使用const访问方法。
- 对于索引列中包含多个列的二级索引来说，只要最左边连续的列是与常数进行等值比较，就可以使用ref访问方法
ref_or_null
有时，我们不仅想找出某个二级索引列的值等于某个常数的记录，而且还想把该列中的值为NULL的记录也找出来。比如下面这个查询：
SELECT * FROM single_table WHERE key1 = 'abc' OR key1 IS NULL;
当使用二级索引而不是全表扫描的方式执行该查询时，对应的扫描区间就是[NULL,NULL]以及[‘abc’,‘abc’]，此时执行这种类型的查询所使用的访问方法就称为ref_or_null。
可以看到，ref_or_null访问方法只是比ref访问方法多扫描了一些值为NULL的二级索引记录。
值为NULL的记录会被放在索引的最左边。
range
在对索引列与一个常数进行等值比较时，才会使用到ref_of_null
SELECT * FROM single_table WHERE key2 IN (1438,6328) OR (key2 >= 38 AND key2 <= 79);
MySQL设计者把使用索引执行查询时，对应的扫描区间为若干个单点扫描区间或者范围扫描区间的访问方法称为range（仅包含一个单点扫描区间的访问方法不能称为range访问方法，扫描区间为(负无穷，正无穷)的访问方法也不能称为range访问方法）
index
SELECT key_part1, key_part2, key_part3 FROM single_table WHERE key_part2 = 'abc;
由于key_part2并不是联合索引idx_key_part的索引列中最左边的列，所以无法形成合适的范围空间来减少需要扫描的记录数量，从而无法使用ref或者range访问方法来执行这个语句。但是这个查询符合下面的两个条件：
- 它的查询列表只有key_part1, key_part2, key_part3这三个列，而索引idx_key_part又恰好包含这三个列；
- 搜索条件中只有key_part2列，这个列页包含在索引idx_key_part中。
也就是说，我们可以直接遍历idx_key_part索引的所有二级索引记录，针对获取到的每一条二级索引记录，都判断key_part2='abc’条件是否成立。如果成立，就从中读取出key_part1, key_part2, key_part3这三个列的值并将他们发送到客户端。很显然，在这种使用idx_key_part索引来执行上述查询的情况下，对应的扫描区间就是(-∞,+∞)。
由于二级索引记录比聚簇索引记录小的多，而且这个过程也不用执行执行回表操作，所以直接扫描全部的二级索引记录比直接扫描全部的聚簇索引记录的成本要小得多。MySQL把这种扫描全部二级索引记录的访问方法称为index访问方法。
另外，当通过全表扫描对使用InnoDB存储引擎的表执行查询时，如果添加了"ORDER BY 主键"的语句，那么语句在执行时也会被人为地认定为使用的是index访问方法，如下面这个查询：
SELECT * FROM single_table ORDER BY id;
all
最直接的查询执行方式就是全表扫描了，对于InnoDB表来说就是直接扫描全部的聚簇索引记录。MySQL把这种使用全表扫描执行查询的访问方法称为ALL访问方法。
注意事项
重温二级索引+回表
在使用索引来减少需要扫描的记录数量时，一般情况下只会为单个索引生成扫描区间。比如：
SELECT * FROM single_table WHERE key1 = 'abc' AND key2 > 1000;
查询优化器会识别到这个查询中的搜索条件：
- key1 = ‘abc’
- key2 > 1000
如果使用idx_key1执行查询，对应的扫描区间就是[‘abc’,‘abc’]；如果使用uk_key2执行查询，对应的扫描区间就是(1000,+∞)。优化器会通过访问表中的少量数据或者直接根据事先生成的统计数据，来计算[‘abc’,‘abc’]扫描区间包含多少条记录，再计算(1000,+∞)扫描区间包含多少条记录，之后在通过一定算法来计算使用这两个扫描区间执行查询时的成本分别是多少，最后选择成本更小的那个扫描区间对应的索引执行查询。假设使用idx_key1索引来执行查询，那么整个查询的执行如下所示：
- 先通过idx_key1对应的B+树定位到扫描区间[‘abc’,‘abc’]中的第一条二级索引记录。
- 根据步骤1中得到的二级索引记录的主键值执行回表操作，得到完整的用户记录，再检测该记录是否满足key2>1000条件。如果满足则将其发送给客户端，否则将其忽略。
- 再根据该记录所在的单向链表找到下一条二级索引记录，重复步骤2中的操作，直到某条二级索引记录不满足key1='abc’条件为止。
从上文可以看出，每次从二级索引中读取到一条记录后，就会根据该记录的主键值执行回表操作。而在某个扫描区间中的二级索引记录的主键值是无序的，也就是说这些二级索引对应的聚簇索引记录所在的页面的页号是无序的。每次执行回表操作时都相当于要随机读取一个聚簇索引页面，而这些随机IO带来的性能开销比较大。于是MySQL设计者提出了一个名为Disk-Sweep Multi-Range Read（MRR，多范围读取）的优化措施，即先读取一部分二级索引记录，将它们的主键值排好序之后再统一执行回表操作。相对于每读取一条二级索引记录就立即执行回表操作，这样会节省一些IO开销。
索引合并
MySQL一般情况下，只会为单个索引生成扫描区间，但还存在特殊情况。在这些特殊情况下，MySQL也可能为多个索引生成扫描区间。MySQL设计者把这种使用多个索引来生成一次查询的执行方法称为index merge（索引合并）。具体索引合并有下面3种。
1、Intersection索引合并
SELECT * FROM single_table WHERE key1 = 'a' AND key3 = 'b';
同时使用idx_key1和idx_key3执行查询。也就是在idx_key1中扫描key1值在区间[‘a’,‘a’]区间中的二级索引记录，同时在idx_key3中扫描key3值在[‘b’,‘b’]区间中的二级索引记录，然后从两者的操作结果中找出id列值相同的记录。然后再根据这些共有id值执行回表操作。
Intersection索引合并指的就是对从不同索引中扫描到的记录的id值取交集，只为这些id值执行回表操作，如果使用Intersection索引合并的方式执行查询，并且每个使用到的二级索引的话，则要求从每个索引中获取到的二级索引记录都是按照主键值排序的。比如上面的查询中，在idx_key1的[‘a’,‘a’]扫描区间中的二级索引记录都是按照主键值排序的，在idx_key3的[‘b’,‘b’]扫描区间中的二级索引记录也都是按照主键值进行排序的。
为什么要求从不同的二级索引中获取到的二级索引记录都是按照主键值排好序呢？这主要由于两方面的考虑：
- 从两个有序的集合中取交集比两个无序的集合中取交集要容易的多。
- 如果获取到的id值是有序的，则在根据这些id值执行回表操作时就不再是进行单纯的随机IO（这些id值是有序的），从而会提高效率。
假设idx_key1的扫描区间[‘a’,‘a’]中的二级索引记录的id值是排好序的，且顺序为1,3,5；idx_key3的扫描区间[‘b’,‘b’]中二级索引记录的id值也是排好序的，且顺序为2,3,4，那么这个查询在使用Intersection索引合并来执行时，过程如下所示：
步骤1：先从idx_key1索引的扫描区间[‘a’,‘a’]中取出第一条二级索引记录，该记录的主键值为1,。然后从idx_key3索引的扫描区间[‘b’,‘b’]中取出的二级索引记录的主键值为2。因为1<2，所以直接把从idx_key1索引中取出的那条主键值为1二级索引记录丢弃。
步骤2：接着继续从idx_key1索引的扫描区间[‘a’,‘a’]中取出下一条二级索引记录，该记录的主键值为3.步骤1中从idx_key3索引的扫描区间[‘b’,‘b’]中取出的二级索引记录的主键值为2,。因为3>2，所以直接把步骤1中idx_key3索引的扫描区间[‘b’,‘b’]中取出的主键值为2的那条二级索引记录丢弃。
步骤3：接着继续从idx_key3索引的扫描区间[‘b’,‘b’]中取出下一条二级索引记录，该记录的主键值为3，步骤2中从idx_key1索引的扫描区间[‘a’,‘a’]中取出的二级索引记录的主键值为3。因为3=3，也就意味着获取主键交集成功，然后根据该主键值执行回表操作，获取到完整的用户记录后将其发送给客户端。
步骤4：接着从idx_key1索引的扫描区间[‘a’,‘a’]中取出下一条二级索引记录，该记录的主键值为5.然后从idx_key3索引的扫描区间[‘b’,‘b’]中取出下一条二级索引记录，该记录的主键值为4.因为5>4，所以直接把从idx_key3索引的扫描区间[‘b’,‘b’]中取出的那条主键值为4的二级索引记录丢弃。
步骤5：接着从idx_key3索引的扫描区间[‘b’,‘b’]中取出下一条符合条件的二级索引记录，发现没有了，然后结束查询。
如果在使用某个二级索引执行查询时，从对应的扫描区间中读取的二级索引记录不是按照主键值排序的，则不可以使用Intersection索引合并来执行查询。比如下面这个查询：
SELECT * FROM single_table where key1 > 'a' AND key3 = 'b';
因为从idx_key1的扫描区间(a,+∞)获取到的记录并不是按照主键值排序的，所以上述查询不能使用Intersection索引合并的方式执行。
再看另一个例子
SELECT * FROM single_table WHERE key1 = 'a' AND key_part1 = 'a';
对于idx_key_part索引来说，它的二级索引记录是先按照key_part1列的值进行排序的；在key_part1值相同的情况下，再按照key_part2值进行排序。那么在idx_key_part二级索引中，key_part1值为’a’的二级索引记录并不是按照主键值进行排序的，所以上述查询也不能使用Intersection索引合并的方式执行。
另外聚簇索引是比较特殊的存在，因为聚簇索引记录本身就是按照主键值进行排序的。比如对于下面这个查询：
SELECT * FROM single_table WHERE key1 = 'a' AND id > 1000;
从idx_key1的扫描区间[‘a’,‘a’]中获取的二级索引是按照主键值排序的，从聚簇索引的扫描区间(9000,+∞)中获取的聚簇索引记录也是按照主键值排序的，所以上述查询可以使用Intersection索引合并的方式执行。不过实际在实现这种包含聚簇索引的Intersection索引合并方法时，并不会真正的扫描聚簇索引记录。那么它是怎么实现的呢？大家都知道二级索引记录是包含索引列和主键列的，在索引列值相同的情况下，二级索引记录是按照主键值进行排序的。所以上述查询在使用Intersection索引合并时，搜索条件id>9000其实并不会为聚簇索引形成扫描区间[9000,+∞]，而是与搜索条件key1='a’一起为idx_key1形成扫描区间((‘a’,9000),(‘a’,+∞))。也就是说我们可以直接使用idx_key1执行查询，定位到符合key1 = ‘a’ AND id > 9000条件的第一条二级索引记录，然后沿着记录所在的单向链表向后扫描，直到某条记录不符合条件为止。当然，针对获取到的每一条二级索引记录，都需要执行回表操作。在这个执行过程中不需要扫描聚簇索引的扫描区间(9000,+∞)中的聚簇索引。
2、UNION索引合并
SELECT * FROM single_table WHERE key1 = 'a' OR key3 = 'b';
我们可以同时使用idx_key1和idx_key3来执行查询。也就是在idx_key1中扫描区间[‘a’,‘a’]中的二级索引记录，同时在idx_key3中扫描key3值位于[‘b’,‘b’]区间中的二级索引记录，然后根据二级索引记录的id值在两者的结果中进行去重，再根据去重后的id执行回表操作。这样重复的id值只需要回表一次。这种方案就是所谓的Union索引合并。Union索引合并指的就是对从不同索引中扫描到的记录的id值取并集，为这些id值执行回表操作。
如果使用UNION索引合并的方式执行查询，并且每个使用到的索引都是二级索引的话，则要求从每个索引中获取到的二级索引记录都是按照主键值排序的。这也是出于下面两个方面的考虑：
- 从两个有序集合执行去重操作比从两个无序集合中执行去重操作容易一些。
- 如果获取到的id值是有序的话，那么在根据这些id值执行回表操作时就不是进行单纯的随机IO（这些id值是有序的），从而会提高效率。
如果在使用某个二级索引执行查询时，从对应的扫描区间中读取出的二级索引记录不是按照主键值排序的，则不可以使用Union索引合并的方式执行查询。比如下面这个查询：
SELECT * FROM single_table WHERE key1 > 'a' OR key3 = 'b';
因为从idx_key1的扫描区间中获取到的(‘a’,+∞)中获取到的记录并不是按照主键值排序的，所以上述查询不能使用Union索引合并的方式执行。
再看另一个例子：
SELECT * FROM single_table WHERE key1 = 'a' AND key_part1 = 'a';
对于从idx_key_part索引来说，它的二级索引记录先按照key_part1列的值进行排序，在key_part1值相同的情况下，再按照key_part2值进行排序。那么在idx_key_part二级索引中，key_part1值为’a’的二级索引记录并不是按照主键值进行排序的，所以上述查询也不能使用Union索引合并的方式执行。
另外，聚簇索引是比较特殊的存在，因为聚簇索引记录本身就是按照主键值进行排序的。比如对于下面这个查询：
SELECT * FROM single_table WHERE key1 = 'a' OR id > 9000;
从idx_key1的扫描区间[‘a’,‘a’]中获取的二级索引记录是按照主键值排序的，从聚簇索引的扫描区间(9000,+∞)中获取的聚簇索引记录也是按照主键值进行排序的，所以上述查询也可以使用Union索引合并的方式执行。
对于下面这个查询：
SELECT * FROM single_table WHERE (key_part1 = 'a' AND key_part2 = 'b' AND key_part3 = 'c') OR (key1 = 'a' AND key3 = 'b');
我们可以先通过idx_key1和idx_key3执行Intersection索引合并，这样可以找到与搜索条件 (key1 = ‘a’ AND key3 = ‘b’)匹配的记录，然后通过idx_key_part执行Union索引合并即可。
3、Sort-union索引合并
union索引合并太苛刻，它必须要求从各个索引中扫描到的记录的主键值是有序的。
SELECT * FROM single_table WHERE key1 < 'a' OR key3 > 'z';
- 先根据key1<'a’条件从idx_key1二级索引中获取二级索引记录，并且将获取到的二级索引记录的主键值进行排序
- 再根据key3 > 'z’条件从idx_key3二级索引中获取二级索引记录，并将获取到的二级索引记录的主键值进行排序
- 因为上述两个二级索引都是排好序的，所以剩下的操作就是与union索引合并方式一样了
连接的原理
连接过程简介
从本质上来说，连接就是把各个表中的记录都取出来进行依次匹配，并把匹配后的组合发送给客户端。把t1和t2两个表连接起来的过程如图所示。
这个过程看起来就是把t1表中的记录和t2表中的记录连起来组成一个新的更大的记录，所以这个查询过程称为连接查询。如果连接查询的结果集中包含一个表中的每一条记录与另一个表中的每一条记录相互匹配的组合，那么这样的结果集就可以称为笛卡尔积。
我们可以连接任意数量的表。但是如果不附加任何限制条件，这些表连接起来产生的笛卡尔积可能是非常巨大的。所以在连接时过滤掉特定的记录组合是有必要的。在连接查询中的过滤条件可以分成下面两种。
- 涉及单表的条件
- 涉及两表的条件、
SELECT * FROM t1,t2 WHERE t1.m1 > 1 AND t1.m1 = t2.m2 AND t2.n2 < 'd';
在这个查询中，我们指明了3个过滤条件：
- t1.m1 > 1
- t1.m1 = t2.m2
- t2.n2 < ‘d’
这个连接查询的执行过程大致如下：
步骤1. 首先确定第一个需要查询的表，这个表称为驱动表。这里假设使用t1作为驱动表，那么就需要到t1表中查找满足t1.m1 > 1的记录。这里采用全表扫描的方式执行单表查询。
步骤2. 步骤1中从驱动表每获取到一条记录，都需要到t2表中查找匹配的记录。
所谓匹配的记录，指的是符合过滤条件的记录。因为是根据t1表中的记录去找t2表中的记录，所以t2表也可以称为被驱动表。步骤1从驱动表中得到了2条记录，也就意味着需要查询2次t2表。此时涉及两个表的列的过滤条件t1.m1 = t2.m2。
对于从t1表中查询得到的第一条记录，也就是当t1.m1 = 2时，过滤条件t1.m1 = t2.m2就相当于t2.m2 = 2。所以此时t2表相当于有了t2.m2 = 2、t2.n2 < 'd’这两个过滤条件，然后到t2表中执行单表查询。
对于从t1表中查询得到的第二条记录，也就是当t1.m1 = 3时，过滤条件t1.m1 = t2.m2就相当于t2.m2 = 3。所以此时t2表相当于有了t2.m2 = 2、t2.n2 < 'd’这两个过滤条件，然后到t2表中执行单表查询。
在两表的连接查询中，驱动表只需要访问一次，被驱动表可能需要访问多次。
这里需要强调一下，并不是将所有满足条件的驱动表记录先查询出来放到一个地方，然后再去被驱动表中查询的，而是每获取到一条驱动表的记录，就立即到被驱动表中寻找匹配的记录。
针对驱动表中的某条记录，即使在被驱动表中没有找到与之匹配的记录，也仍然需要把该驱动表记录加入到结果集。为了解决这个问题，就有了内连接和外连接的概念。
- 对于内连接的两个表，若驱动表中的记录在被驱动表中找不到匹配的记录，则该记录不会加入到最后的结果集，前面提到的连接都是内连接。
- 对于外连接的两个表，即使驱动表中记录在被驱动表中没有匹配的记录，也仍然需要加入到结果集。
在MYSQL中，根据选取的驱动表的不同，外连接可以细分为2种。
- 左连接：选取左侧的表为驱动表
- 右连接：选取右侧的表为驱动表
- WHERE子句中的过滤条件 凡是不符合WHERE子句中过滤条件的记录都不会被加入到最后的结果集。
- ON子句中的过滤条件 对于外连接的驱动表中的记录来说，如果无法在被驱动表中找到匹配的ON子句中的过滤条件的记录，那么该驱动表记录仍然会被加入到结果集中，对应的被驱动表记录的各个字段的使用NULL值填充。
1、左外连接的语法
SELECT * FROM t1 LEFT [OUTER] JOIN t2 ON 连接条件 [普通的过滤条件]
其中，中括号里的OUTER单词是可以忽略的。对于LEFT JOIN类型的连接来说，我们把放在左边的表称为外表或者驱动表，放在右边的表称为内表或者被驱动表。所以上述查询语句中，t1就是外表或者驱动表，t2就是内表或者被驱动表。需要注意的是，对于左外连接和右外连接来说，必须使用ON子句来指出连接条件（内连接不必要包含ON子句）
2、右外连接的语法
与上类似
3、内连接语法
内连接和外连接的根本区别就是在驱动表中的记录不符合ON子句中的连接条件时，内连接不会把该记录加入到最后的结果集中。这里需要注意的是，由于在内连接中ON子句和WHERE子句是等价的，所以内连接中不要求强制写明ON子句。
我们前面说过，连接就是把各个表中的记录都取出来依次进行匹配，并把匹配后的组合表送给客户端。无论哪个表作为驱动表，两表连接产生的笛卡尔积肯定是一样的。而对于内连接来说，凡是不符合ON子句或WHERE子句中条件的记录都会被过滤掉，也就相当于从两表连接的笛卡尔积中把不符合过滤条件的记录都踢出去。所以对于内连接来说，驱动表和被驱动表是可以互换的，并不会影响最后的查询结果。但是对于外连接来说，由于驱动表中的记录即使在被驱动表中找不到符合ON子句连接条件的记录，也会被加入到结果集，此时驱动表和被驱动表的关系就很重要了。也就是说，左外连接和右外连接的驱动表和被驱动表不能轻易互换。
连接的原理
嵌套循环连接
对于两表连接来说，驱动表只会访问一遍，但被驱动表却要被访问好多遍；具体访问几遍取决于对驱动表执行单表查询后的结果集中有多少条记录。对于内连接来说，选取哪个表为驱动表都没关系；而外连接的驱动表是固定的，也就是说左（外）连接的驱动表就是左边的那个表，右（外）连接的驱动表就是右边的那个表。
步骤1，选取驱动表，使用与驱动表相关的过滤条件，选取代价最低的单表访问方法来执行对驱动表的单表查询。
步骤2，对步骤1中查询驱动表得到的结果集中的每一条记录，都分别到被驱动表中查找匹配的记录。
如果有三个表进行连接，那么步骤2中得到的结果集就是新的驱动表，然后第三个表就成为了被驱动表。
这种驱动表只访问一次，但被驱动表却可能访问多次，且访问次数取决于对驱动表执行单表查询后的结果集中有多少条记录，的连接执行方式称为嵌套循环连接，这是最简单也是最笨的一种连接算法。
需要注意的是，对于嵌套循环连接算法来说，每当我们从驱动表中得到了一条记录时，就根据这条记录立即到被驱动表中查询一次。如果得到了匹配的记录，就把组合后的记录发送给客户端，然后再到驱动表获取下一条记录；这个过程将重复进行。
使用索引加快连接速度
我们知道，在嵌套循环连接中可能需要访问多次被驱动表。如果访问被驱动表的方式都是全表扫描，那么会很影响性能。我们可以利用索引来加快查询速度。下面查询语句：
SELECT * FROM t1,t2 WHERE t1.m1 > 1 AND t1.m1 = t2.m2 AND t2.n2 < 'd';
这个连接查询使用的其实是嵌套循环连接算法。
查询驱动表t1后的结果集中有2条记录，嵌套循环连接算法需要查询被驱动表2次：
- 当t1.m1=2时，查询一遍t2表，对t2表的查询语句相当于：
SELECT * FROM t2 WHERE t2.m2 = 2 AND t2.n2 < 'd';
- 当t1.m1=3时，再去查询一遍t2表，此时对t2表的查询语句相当于：
SELECT * FROM t2 WHERE t2.m2 = 3 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表的主键，或者是不允许存储NULL值的唯一二级索引列，那么使用“t2.m2=常数值”这样的条件从t2表中查找记录时，代价就是常数级别的。我们知道，在单表中使用主键值或者唯一二级索引列的值进行等值查找的方式称为const，而在连接查询中对被驱动表的主键或者不允许存储NULL值的唯一二级索引进行等值查找使用的访问方法称为eq_ref。 - 在n2列上建立索引，涉及条件是t2.n2<‘d’，可能用到range访问方法。假设使用range访问方法对t2表进行查询，需要在回表之后再判断包含m2列的条件是否成立。
假设m2和n2列上都存在索引，那么就需要从这两个里面挑一个代价更低的索引来查询t2表。
另外，连接查询的查询列表和过滤条件中有时可能只涉及被驱动表的部分列，而这些列都是某个二级索引的一部分，在这种情况下即使不能使用eq_ref、ref、ref_or_null或者range等访问方法来查询被驱动表，也可以通过扫描全部二级索引记录（即使用index访问方法）来查询驱动表。所以建议最好不要使用* 作为查询列表，而是把真正用到的列作为查询列表。
基于块的嵌套循环连接
现实生活中的表可不像t1、t2这样只有3条记录，成千上万记录都是少的，几百万、几千万甚至几亿条的表到处都是。现在假设我们不能使用索引加快被驱动表的查询过程，所以对于驱动表结果集中的每一条记录，都需要对被驱动表执行全表扫描。这样在被驱动表进行全表扫描时，可能表前面的记录还在内存中，而表后面的记录还在磁盘上。而等到扫描表中后面的记录时，有可能由于内存不足，需要把表前面的记录从内存中释放掉给现在正在扫描的记录腾地方。我们前面强调过，在采用嵌套循环连接算法的两表连接过程中，被驱动表可是要被访问很多次。如果这个被驱动表中的数据特别多而且不能使用索引进行访问，那就相当于要从磁盘上读这个表好多次，这个IO代价就非常大了。所以我们得想办法，尽量减少被驱动表的访问次数。
通过上面的叙述我们了解到，驱动表结果集中有多少条记录，就可能把被驱动表从磁盘加载到内存中多少次，我们是否可以在把被驱动表中的记录加载到内存时，一次性地与驱动表中的多条记录进行匹配呢？这样就可以大大减少重复从磁盘上加载被驱动表的代价了。所以MySQL提出了一个名为Join Buffer（连接缓冲区）的概念。Join Buffer就是在执行连接查询前申请一块固定大小的内存。先把若干条驱动表结果集中的记录装在这个Join Buffer中，然后开始扫描被驱动表，每一条被驱动表的记录一次性地与Join Buffer中的多条驱动表记录进行匹配。由于匹配过程都是在内存中完成的，所以这样可以显著减少被驱动表的IO代价。
最好的情况是Join Buffer足够大，能容纳驱动表结果集中所有记录，这样只需要访问一次被驱动表就可以完成连接操作了。MySQL把这种加入了Join Buffer的嵌套循环连接算法称为基于块的嵌套循环连接（Block Nested-Loop Join）算法。
这个Join Buffer的大小可以通过启动选项或者系统变量join_buffer_size进行配置，默认大小为262144字节（也就是256KB），最小可以设置128字节。当然，在我们优化对被驱动表的查询时，最好是为被驱动表加上高效率的索引。如果实在不能使用索引，并且自己机器的内存也比较大，则可以尝试调大join_buffer_size的值来对连接查询进行优化。
另外需要注意的是，Join Buffer中并不会存放被驱动表记录的所有列，只有查询列表中的列和过滤条件中的列才会被放到Join Buffer中，所以这也再次提醒我们，最好不要把 * 作为查询条件，只需要把关心的列放到查询列表就好了；这样还可以在Join Buffer中放置更多的记录。
总结
从本质上来说，连接就是把各个表中的记录都取出来依次进行匹配，并把匹配后的组合发送给客户端。如果不加任何过滤条件，产生的结果集就是笛卡尔积。
在MYSQL中，连接分为内连接和外连接，其中外连接又可以分为左外连接和右外连接。内连接和外连接的根本区别就是，在驱动表中的记录不符合ON子句中的连接条件时，内连接不会把该记录加入到最后的结果集中，而外连接会。
嵌套循环连接算法是指驱动表只访问一次，但被驱动表却可能访问多次，访问次数取决于对驱动表执行单表查询后的结果集中有多少条记录，大致过程如下。
步骤1，选取驱动表，使用与驱动表相关的过滤条件，选取代价最低的单表访问方法来执行对驱动表的单表查询。
步骤2，对步骤1中查询驱动表得到的结果集中的每一条记录，都分别到被驱动表中查找匹配的记录。
由于被驱动表可能会访问很多次，因此可以为被驱动表建立合适的索引以加快查询速度。
如果被驱动表非常大，多次访问被驱动表可能会导致很多次的磁盘IO，此时可以使用基于块的嵌套循环连接算法来缓解由此造成的性能损耗。
索引与算法
InnoDB存储引擎索引概述
InnoDB存储引擎支持一下几种常见的索引：
- B+树索引
- 全文索引
- 哈希索引
InnoDB存储引擎支持的哈希索引是自适应的，InnoDB存储引擎会根据表的使用情况自动为表生成哈希索引，不能人为干预是否在一张表中生成哈希索引。
B+树中的B不是代表二叉（binary），而是代表平衡（balance），因为B+树是从最早的二叉树演化来的，但是B+树不是二叉树。
B+树索引并不能找到一个给定键值的具体行。B+树索引能找到的只是被查找数据行所在的页。然后根据数据库通过把页读入到内存中，再在内存中进行查找，最后得到要查找的数据。
二分查找法
二分查找法（binary search）也称为折半查找法，用来查找一组有序的记录数组中的某一记录，其基本思想是：将记录按有序化（递增或递减）排列，在查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。
二叉树和平衡二叉树
在二叉树中，左子树的键值总是小于根的键值，右子树的键值总是大于根的键值。
平衡二叉树的定义如下：首先符合二叉查找树的定义，其次必须满足任何节点的两个子树的高度最大差为1。
B+树
B+树和二叉树、平衡二叉树一样，都是经典的数据结构。B+树由B树和索引顺序访问的方式演化来的。
在B+树中，所有记录的节点都是按照键值的大小顺序存在在同一层的叶子节点上，由各叶子节点指针进行连接。
聚集索引
InnoDB存储引擎表是索引组织表，即表中数据按照主键顺序存放。而聚集索引就是按照每张表的主键构造一颗B+树，同时叶子节点中存放的是行记录的数据，也将聚集索引的叶子节点称为数据页。同B+树结构一样，每个数据页都通过一个双向链表来进行连接。