MySQL中InnoDB及索引深入剖析

InnoDB页

将数据划分为若干个页，以页作为磁盘和内存之间交互的基本单位，InnoDB中页的大小一般为 16 KB。也就是在一般情况下，一次最少从磁盘中读取16KB的内容到内存中，一次最少把内存中的16KB内容刷新到磁盘中。

InnoDB行格式

我们平时是以记录为单位来向表中插入数据的，这些记录在磁盘上的存放方式也被称为行格式或者记录格式。

记录的额外信息

记录的额外信息：分别是变长字段长度列表、NULL值列表和记录头信息

1.分别是变长字段长度列表
MySQL中比如VARCHAR(M)、VARBINARY(M)、各种TEXT类型，各种BLOB类型这些数据类型的列称为变长字段，变长字段中存储多少字节的数据是不固定的。
所以这些变长字段占用的存储空间分为两部分：真正的数据内容、占用的字节数

在行格式中，把所有变长字段的真实数据占用的字节长度都存放在记录的开头部位，从而形成一个变长字段长度列表，各变长字段数据占用的字节数按照列的顺序逆序存放。

变长字段长度列表中只存储值为非NULL 的列内容占用的长度，值为 NULL 的列的长度是不储存的。

并不是所有记录都有这个变长字段长度列表部分，比方说表中所有的列都不是变长的数据类型的话，这一部分就不需要有。

2.NULL值列表
表中的某些列可能存储NULL值，如果把这些NULL值都放到记录的真实数据中存储会很占地方，所以Compact行格式把这些值为NULL的列统一管理起来，存储到NULL值列表中，它的处理过程是这样的：

首先统计表中允许存储NULL的列有哪些。
如果表中没有允许存储 NULL 的列，则 NULL值列表也不存在了

3.记录头信息

先创建一个表：
mysql> CREATE TABLE page_demo(
    ->     c1 INT,
    ->     c2 INT,
    ->     c3 VARCHAR(10000),
    ->     PRIMARY KEY (c1)
    -> ) CHARSET=ascii ROW_FORMAT=Compact;
Query OK, 0 rows affected (0.03 sec)

主键的生成策略
InnoDB表对主键的生成策略：优先使用用户自定义主键作为主键，如果用户没有定义主键，则选取一个Unique键作为主键，如果表中连Unique键都没有定义的话，则InnoDB会为表默认添加一个名为row_id的隐藏列作为主键。

这个新创建的page_demo表有3个列，其中c1和c2列是用来存储整数的，c3列是用来存储字符串的。需要注意的是，我们把 c1 列指定为主键，所以在具体的行格式中InnoDB就没必要为我们去创建那个所谓的 row_id 隐藏列了。

简化后的行格式示意图就是这样：

InnoDB数据页结构

数据页代表的这块16KB大小的存储空间可以被划分为多个部分，不同部分有不同的功能，各个部分如图所示：

每当我们插入一条记录，都会从Free Space部分，也就是尚未使用的存储空间中申请一个记录大小的空间划分到User Records部分，当Free Space部分的空间全部被User Records部分替代掉之后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要去申请新的页了，这个过程的图示如下：

这里我们继续上面的page_demo例子：

先创建一个表：
mysql> CREATE TABLE page_demo(
    ->     c1 INT,
    ->     c2 INT,
    ->     c3 VARCHAR(10000),
    ->     PRIMARY KEY (c1)
    -> ) CHARSET=ascii ROW_FORMAT=Compact;
Query OK, 0 rows affected (0.03 sec)

向page_demo表中插入几条记录：
mysql> INSERT INTO page_demo VALUES(1, 100, 'aaaa'), 
                                      (2, 200, 'bbbb'), 
                                  (3, 300, 'cccc'), 
                                      (4, 400, 'dddd');
Query OK, 4 rows affected (0.00 sec)
Records: 4  Duplicates: 0  Warnings: 0

那么，这些记录的示意图就是：

delete_mask
这个属性标记着当前记录是否被删除。
这些被删除的记录之所以不立即从磁盘上移除，是因为移除它们之后把其他的记录在磁盘上重新排列需要性能消耗，所以只是打一个删除标记而已。
所有被删除掉的记录都会组成一个所谓的垃圾链表，在这个链表中的记录占用的空间称之为所谓的可重用空间，之后如果有新记录插入到表中的话，可能把这些被删除的记录占用的存储空间覆盖掉。
min_rec_mask
B+树的每层非叶子节点中的最小记录都会添加该标记，min_rec_mask值都是0，意味着它们都不是B+树的非叶子节点中的最小记录。
n_owned
在页目录分组时使用，每个组的最后一条记录（也就是组内最大的那条记录）的头信息中的n_owned属性表示该记录拥有多少条记录，也就是该组内共有几条记录。
heap_no
这个属性表示当前记录在本页中的位置，从图中可以看出来，我们插入的4条记录在本页中的位置分别是：2、3、4、5。
heap_no值为0和1的记录，称为伪记录或者虚拟记录。这两个伪记录一个代表最小记录，一个代表最大记录。
record_type
这个属性表示当前记录的类型，一共有4种类型的记录，0表示普通记录，1表示B+树非叶节点记录，2表示最小记录，3表示最大记录。
next_record
它表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量。比方说第一条记录的next_record值为32，意味着从第一条记录的真实数据的地址处向后找32个字节便是下一条记录的真实数据。
下一条记录指得并不是按照我们插入顺序的下一条记录，而是按照主键值由小到大的顺序的下一条记录。而且规定 Infimum记录（也就是最小记录）的下一条记录就是本页中主键值最小的用户记录，而本页中主键值最大的用户记录的下一条记录就是 Supremum记录（也就是最大记录）

从图中可以看出来，我们的记录按照主键从小到大的顺序形成了一个单链表。
如果从中删除掉一条记录，这个链表也是会跟着变化的，比如我们把第2条记录删掉：
```
mysql> DELETE FROM page_demo WHERE c1 = 2;
Query OK, 1 row affected (0.02 sec)
```
- 第2条记录并没有从存储空间中移除，而是把该条记录的delete_mask值设置为1。
- 第2条记录的next_record值变为了0，意味着该记录没有下一条记录了。
- 第1条记录的next_record指向了第3条记录。
- 还有一点你可能忽略了，就是最大记录的n_owned值从5变成了4
  因为主键值为2的记录被我们删掉了，但是存储空间却没有回收，如果我们再次把这条记录插入到表中：
```
mysql> INSERT INTO page_demo VALUES(2, 200, 'bbbb');
Query OK, 1 row affected (0.00 sec)
```

Page Directory（页目录）

现在我们了解了记录在页中按照主键值由小到大顺序串联成一个单链表，那如果我们想根据主键值查找页中的某条记录该咋办呢？

设计InnoDB的大叔们为我们的记录也制作了一个类似的目录，他们的制作过程是这样的：

将所有正常的记录（包括最大和最小记录，不包括标记为已删除的记录）划分为几个组。
每个组的最后一条记录（也就是组内最大的那条记录）的头信息中的n_owned属性表示该记录拥有多少条记录，也就是该组内共有几条记录
将每个组的最后一条记录的地址偏移量单独提取出来，用作查找。

注意：这个页目录是为主键服务的。

对于最小记录所在的分组只能有 1 条记录，最大记录所在的分组拥有的记录条数只能在 1-8 条之间，剩下的分组中记录的条数范围只能在是 4-8 条之间。

分组是按照下边的步骤进行：

初始情况下一个数据页里只有最小记录和最大记录两条记录，它们分属于两个分组。
之后每插入一条记录，都会从页目录中找到主键值比本记录的主键值大并且差值最小的槽，然后把该槽对应的记录的n_owned值加1，表示本组内又添加了一条记录，直到该组中的记录数等于8个。
在一个组中的记录数等于8个后再插入一条记录时，会将组中的记录拆分成两个组，一个组中4条记录，另一个5条记录。这个过程会在页目录中新增一个槽来记录这个新增分组中最大的那条记录的偏移量。

我们再添加12条记录看看效果：

mysql> INSERT INTO page_demo VALUES(5, 500, 'eeee'), (6, 600, 'ffff'), (7, 700, 'gggg'), (8, 800, 'hhhh'), (9, 900, 'iiii'), (10, 1000, 'jjjj'), (11, 1100, 'kkkk'), (12, 1200, 'llll'), (13, 1300, 'mmmm'), (14, 1400, 'nnnn'), (15, 1500, 'oooo'), (16, 1600, 'pppp');
Query OK, 12 rows affected (0.00 sec)
Records: 12  Duplicates: 0  Warnings: 0

因为把16条记录的全部信息都画在一张图里太占地方，让人眼花缭乱的，所以只保留了用户记录头信息中的n_owned和next_record属性。

因为各个槽代表的记录的主键值都是从小到大排序的，所以我们可以使用所谓的二分法来进行快速查找。

所以在一个数据页中查找指定主键值的记录的过程分为两步：

通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最大的那条记录。
通过记录的next_record属性遍历该槽所在的组中的各个记录。

比方说我们想找主键值为6的记录，过程是这样的：
计算中间槽的位置：(0+4)/2=2，所以查看槽2对应记录的主键值为8，又因为8 > 6，所以设置high=2，low保持不变。
重新计算中间槽的位置：(0+2)/2=1，所以查看槽1对应的主键值为4，又因为4 < 6，所以设置low=1，high保持不变。
因为high – low的值为1，所以确定主键值为6的记录在槽2对应的组中。
我们可以很轻易的拿到槽1对应的记录（主键值为4），该条记录的下一条记录就是槽2中主键值最小的记录，该记录的主键值为5。所以我们可以从这条主键值为5的记录出发，遍历槽2中的各条记录

注意：若查到数据在槽2的分组中，由于槽2是指向最后一个记录，所以需要向上找一个槽位，定位到上一个槽位最后一行，然后再向下找。

File Header（文件头部）

File Header针对各种类型的页都通用，也就是说不同类型的页都会以File Header作为第一个组成部分，它描述了一些针对各种页都通用的一些信息，比方说这个页的编号是多少，它的上一个页、下一个页是谁等。

FIL_PAGE_OFFSET
每一个页都有一个单独的页号，就跟你的身份证号码一样，InnoDB通过页号来可以唯一定位一个页。

FIL_PAGE_PREV和FIL_PAGE_NEXT
FIL_PAGE_PREV和FIL_PAGE_NEXT就分别代表本页的上一个和下一个页的页号。这样通过建立一个双向链表把许许多多的页就都串联起来了

B+树索引

InnoDB数据页的主要组成部分。各个数据页可以组成一个双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在它里边儿的记录生成一个页目录。再通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽。

在一个页中的查找

以主键为搜索条件
这个查找过程我们已经很熟悉了，可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
以其他列作为搜索条件
对非主键列的查找的过程可就不这么幸运了，因为在数据页中并没有对非主键列建立所谓的页目录，所以我们无法通过二分法快速定位相应的槽。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。

在很多页中查找

定位到记录所在的页。
从所在的页内中查找相应的记录。

在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们刚刚唠叨过的查找方式去查找指定的记录。

索引

为了故事的顺利发展，我们先建一个表：

mysql> CREATE TABLE index_demo(
    ->     c1 INT,
    ->     c2 INT,
    ->     c3 CHAR(1),
    ->     PRIMARY KEY(c1)
    -> ) ROW_FORMAT = Compact;
Query OK, 0 rows affected (0.03 sec)

为了我们理解上的方便，我们简化了一下index_demo表的行格式示意图：

record_type
这个属性表示当前记录的类型，一共有4种类型的记录，0表示普通记录，1表示B+树非叶节点记录，2表示最小记录，3表示最大记录。
next_record
记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量

把一些记录放到页里边的示意图就是：

一个简单的索引方案：
我们为根据主键值快速定位一条记录在页中的位置而设立的页目录，目录中记录的数据页必须下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。

我们这里需要做一个假设：假设我们的每个数据页最多能存放3条记录（实际上一个数据页非常大，可以存放下好多记录）。有了这个假设之后我们向index_demo表插入3条记录：

mysql> INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
Query OK, 3 rows affected (0.01 sec)
Records: 3  Duplicates: 0  Warnings: 0

从图中可以看出来，index_demo表中的3条记录都被插入到了编号为10的数据页中了。此时我们再来插入一条记录：

mysql> INSERT INTO index_demo VALUES(4, 4, 'a');
Query OK, 1 row affected (0.00 sec)

因为页10最多只能放3条记录，所以我们不得不再分配一个新页：

页10中用户记录最大的主键值是5，而页28中有一条记录的主键值是4，因为5 > 4，所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求，所以在插入主键值为4的记录的时候需要伴随着一次记录移动，也就是把主键值为5的记录移动到页28中，然后再把主键值为4的记录插入到页10中，这个过程的示意图如下：

这个过程叫做页分裂。

由于数据页的编号可能并不是连续的，所以在向index_demo表中插入许多条记录后，可能是这样的效果：

因为这些16KB的页在物理存储上可能并不挨着，所以如果想从这么多页中根据主键值快速定位某些记录所在的页，我们需要给它们做个目录，每个页对应一个目录项，每个目录项包括下边两个部分：

页的用户记录中最小的主键值，我们用key来表示。
页号，我们用page_no表示。

所以我们为上边几个页做好的目录就像这样子：

比方说我们想找主键值为20的记录，具体查找过程分两步：

先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中（因为 12 < 20 < 209），它对应的页是页9。
再根据前边说的在页中查找记录的方式去页9中定位具体的记录。

这个目录有一个别名，称为索引。

InnoDB中的索引方案

在InnoDB中复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录。

用record_type来区分普通的用户记录还是目录项记录。

一个页只有16KB大小，能存放的目录项记录也是有限的，那如果表中的数据太多，以至于一个数据页不足以存放所有的目录项记录，会再多整一个存储目录项记录的页。

假设一个存储目录项记录的页最多只能存放4条目录项记录（请注意是假设哦，真实情况下可以存放好多条的），所以如果此时我们再向上图中插入一条主键值为320的用户记录的话：

在这个查询步骤的第1步中我们需要定位存储目录项记录的页，但是这些页在存储空间中也可能不挨着，如果我们表中的数据非常多则会产生很多存储目录项记录的页，那我们怎么根据主键值快速定位一个存储目录项记录的页呢？其实也简单，为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页的示意图就是这样子：

随着表中记录的增加，这个目录的层级会继续增加，如果简化一下，那么我们可以用下边这个图来描述它：

从图中可以看出来，我们的实际用户记录其实都存放在B+树的最底层的节点上，这些节点也被称为叶子节点或叶节点，其余用来存放目录项的节点称为非叶子节点或者内节点，其中B+树最上边的那个节点也称为根节点。

聚簇索引

我们上边介绍的B+树本身就是一个目录，或者说本身就是一个索引。它有两个特点：

使用记录主键值的大小进行记录和页的排序
B+树的叶子节点存储的是完整的用户记录。

我们把具有这两种特性的B+树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在MySQL语句中显式的使用INDEX语句去创建（后边会介绍索引相关的语句），InnoDB存储引擎会自动的为我们创建聚簇索引。另外有趣的一点是，在InnoDB存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引。

二级索引

这个B+树与上边介绍的聚簇索引有几处不同：

使用记录c2列的大小进行记录和页的排序，这包括三个方面的含义：
- 页内的记录是按照c2列的大小顺序排成一个单向链表。
- 各个存放用户记录的页也是根据页中记录的c2列大小顺序排成一个双向链表。
- 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的c2列大小顺序排成一个双向链表。
B+树的叶子节点存储的并不是完整的用户记录，而只是c2列+主键这两个列的值。
目录项记录中不再是主键+页号的搭配，而变成了c2列+页号的搭配。

以查找c2列的值为4的记录为例：

确定目录项记录页，也就是页44
通过目录项记录页确定用户记录真实所在的页。
在页42中可以快速定位到实际存储用户记录的页，但是由于c2列并没有唯一性约束，所以c2列值为4的记录可能分布在多个数据页中，又因为2 < 4 ≤ 4，所以确定实际存储用户记录的页在页34和页35中。
在真实存储用户记录的页中定位到具体的记录。
但是这个B+树的叶子节点中的记录只存储了c2和c1（也就是主键）两个列，所以我们必须再根据主键值去聚簇索引中再查找一遍完整的用户记录。这个过程被称为回表。

如果把完整的用户记录放到叶子节点是可以不用回表，但是太占地方了呀～相当于每建立一棵B+树都需要把所有的用户记录再都拷贝一遍，这就有点太浪费存储空间了。

联合索引

我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让B+树按照c2和c3列的大小进行排序：

先把各个记录和页按照c2列进行排序。
在记录的c2列相同的情况下，采用c3列进行排序

如图所示，我们需要注意一下几点：

每条目录项记录都由c2、c3、页号这三个部分组成，各条记录先按照c2列的值进行排序，如果记录的c2列相同，则按照c3列的值进行排序。
B+树叶子节点处的用户记录由c2、c3和主键c1列组成。

索引的代价

空间上的代价
每建立一个索引都要为它建立一棵B+树，每一棵B+树的每一个节点都是一个数据页，一个页默认会占用16KB的存储空间
时间上的代价
每次对表中的数据进行增、删、改操作时，都需要去修改各个B+树索引。

B+树每层节点都是按照索引列的值从小到大的顺序排序而组成了双向链表。不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位，页面分裂、页面回收啥的操作来维护好节点和记录的排序。

B+树索引适用的条件

那么再次建议回过头把前边的内容看完了再来，要不然读文章对你来说是一种折磨。首先，B+树索引并不是万能的，并不是所有的查询语句都能用到我们建立的索引。下边介绍几个我们可能使用B+树索引来进行查询的情况。

CREATE TABLE person_info(
    id INT NOT NULL auto_increment,
    name VARCHAR(100) NOT NULL,
    birthday DATE NOT NULL,
    phone_number CHAR(11) NOT NULL,
    country varchar(100) NOT NULL,
    PRIMARY KEY (id),
    KEY idx_name_birthday_phone_number (name, birthday, phone_number)
);

person_info表会为聚簇索引和idx_name_birthday_phone_number索引建立2棵B+树。

在记录结构中只保留name、birthday、phone_number、id这四个列的真实数据值，所以示意图就长这样：

内节点中存储的是目录项记录，叶子节点中存储的是用户记录（由于不是聚簇索引，所以用户记录是不完整的，缺少country列的值）。

先按照name列的值进行排序。
如果name列的值相同，则按照birthday列的值进行排序。
如果birthday列的值也相同，则按照phone_number的值进行排序。

全值匹配

如果我们的搜索条件中的列和索引列一致的话，这种情况就称为全值匹配，比方说下边这个查找语句：

SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27' AND phone_number = '15123983239';

因为B+树的数据页和记录先是按照name列的值进行排序的，所以先可以很快定位name列的值是Ashburn的记录位置。
在name列相同的记录里又是按照birthday列的值进行排序的，所以在name列的值是Ashburn的记录里又可以快速定位birthday列的值是’1990-09-27’的记录。
如果很不幸，name和birthday列的值都是相同的，那记录是按照phone_number列的值排序的，所以联合索引中的三个列都可能被用到。

调换name、birthday、phone_number这几个搜索列的顺序对查询的执行过程是没有影响的。

匹配左边的列

SELECT * FROM person_info WHERE name = 'Ashburn';

或者包含多个左边的列也行：

SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27';

只有左边的列才能匹配，下边的语句就用不到这个B+树索引：

SELECT * FROM person_info WHERE birthday = '1990-09-27';

因为B+树的数据页和记录先是按照name列的值排序的，在name列的值相同的情况下才使用birthday列进行排序，也就是说name列的值不同的记录中birthday的值可能是无序的。

如果我们想使用联合索引中尽可能多的列，搜索条件中的各个列必须是联合索引中从最左边连续的列。

匹配列前缀

person_info表上建立的联合索引idx_name_birthday_phone_number会先用name列的值进行排序。

也就是说这些字符串的前n个字符，也就是前缀都是排好序的，所以对于字符串类型的索引列来说，我们只匹配它的前缀也是可以快速定位记录的，比方说我们想查询名字以’As’开头的记录，那就可以这么写查询语句：

SELECT * FROM person_info WHERE name LIKE 'As%';

同理，这样也是无法匹配的：

SELECT * FROM person_info WHERE name LIKE '%As%';

匹配范围值

所有记录都是按照索引列的值从小到大的顺序排好序的，所以这极大的方便我们查找索引列的值在某个范围内的记录。

SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';

由于所有记录都是由链表连起来的（记录之间用单链表，数据页之间用双链表），所以他们之间的记录都可以很容易的取出来喽～
找到这些记录的主键值，再到聚簇索引中回表查找完整的记录。

如果对多个列同时进行范围查找的话，只有对索引最左边的那个列进行范围查找的时候才能用到B+树索引，比方说这样：

SELECT * FROM person_info WHERE name > ‘Asa’ AND name < ‘Barlow’ 
AND birthday > '1980-01-01';

上边这个查询可以分成两个部分：

通过条件name > ‘Asa’ AND name < ‘Barlow’来对name进行范围。
对这些name值不同的记录继续通过birthday > ‘1980-01-01’条件继续过滤。

对于联合索引idx_name_birthday_phone_number来说，只能用到name列的部分，而用不到birthday列的部分，因为只有name值相同的情况下才能用birthday列的值进行排序，而这个查询中通过name进行范围查找的记录中可能并不是按照birthday列进行排序的，所以在搜索条件中继续以birthday列进行查找时是用不到这个B+树索引的。

精确匹配某一列并范围匹配另外一列

虽然对多个列都进行范围查找时只能用到最左边那个索引列，但是如果左边的列是精确查找，则右边的列可以进行范围查找，比方说这样：

SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday > '1980-01-01' AND birthday < '2000-12-31' AND phone_number > '15100000000';

由于name列是精确查找，所以通过name = ‘Ashburn’条件查找后得到的结果的name值都是相同的，它们会再按照birthday的值进行排序。所以此时对birthday列进行范围查找是可以用到B+树索引的。

phone_number > ‘15100000000’，通过birthday的范围查找的记录的birthday的值可能不同，所以这个条件无法再利用B+树索引了，只能遍历上一步查询得到的记录。

用于排序

有的时候可能查询的结果集太大以至于不能在内存中进行排序的话，还可能暂时借助磁盘的空间来存放中间结果，排序操作完成后再把排好序的结果集返回到客户端。在MySQL中，把这种在内存中或者磁盘上进行排序的方式统称为文件排序（英文名：filesort）。

但是如果ORDER BY子句里使用到了我们的索引列，就有可能省去在内存或文件中排序的步骤，比如下边这个简单的查询语句：

SELECT * FROM person_info ORDER BY name, birthday, phone_number LIMIT 10;

因为这个B+树索引本身就是按照上述规则排好序的，所以直接从索引中提取数据，然后进行回表操作取出该索引中不包含的列就好了。

使用联合索引进行排序注意事项
ORDER BY的子句后边的列的顺序也必须按照索引列的顺序给出，如果给出ORDER BY phone_number, birthday, name的顺序，那也是用不了B+树索引。

不可以使用索引进行排序的几种情况

1.ASC、DESC混用
对于使用联合索引进行排序的场景，我们要求各个排序列的排序顺序是一致的，也就是要么各个列都是ASC规则排序，要么都是DESC规则排序。

idx_name_birthday_phone_number联合索引中记录的结构：

先按照记录的name列的值进行升序排列。
如果记录的name列的值相同，再按照birthday列的值进行升序排列。
如果记录的birthday列的值相同，再按照phone_number列的值进行升序排列。

2.WHERE子句中出现非排序使用到的索引列
如果WHERE子句中出现了非排序使用到的索引列，那么排序依然是使用不到索引的，比方说这样：

SELECT * FROM person_info WHERE country = ‘China’ ORDER BY name LIMIT 10;

这个查询只能先把符合搜索条件country = ‘China’的记录提取出来后再进行排序，是使用不到索引。

3.排序列包含非同一个索引的列
有时候用来排序的多个列不是一个索引里的，这种情况也不能使用索引进行排序，比方说：

SELECT * FROM person_info ORDER BY name, country LIMIT 10;

4.排序列使用了复杂的表达式
要想使用索引进行排序操作，必须保证索引列是以单独列的形式出现，而不是修饰过的形式，比方说这样：

SELECT * FROM person_info ORDER BY UPPER(name) LIMIT 10;

回表的代价

还是用idx_name_birthday_phone_number索引为例，看下边这个查询：

SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';

在使用idx_name_birthday_phone_number索引进行查询时大致可以分为这两个步骤：

从索引idx_name_birthday_phone_number对应的B+树中取出name值在Asa～Barlow之间的用户记录。
由于索引idx_name_birthday_phone_number对应的B+树用户记录中只包含name、birthday、phone_number、id这4个字段，而查询列表是*，意味着要查询表中所有字段，也就是还要包括country字段。这时需要把从上一步中获取到的每一条记录的id字段都到聚簇索引对应的B+树中找到完整的用户记录，也就是我们通常所说的回表，然后把完整的用户记录返回给查询用户。

读取索引idx_name_birthday_phone_number数据中，在Asa～Barlow之间的记录在磁盘中的存储是相连的，集中分布在一个或几个数据页中，我们可以很快的把这些连着的记录从磁盘中读出来，这种读取方式我们也可以称为顺序I/O。

而获取到的记录的id字段的值可能并不相连，而在聚簇索引中记录是根据id（也就是主键）的顺序排列的，所以根据这些并不连续的id值到聚簇索引中访问完整的用户记录可能分布在不同的数据页中，这样读取完整的用户记录可能要访问更多的数据页，这种读取方式我们也可以称为随机I/O。

所以这个使用索引idx_name_birthday_phone_number的查询有这么两个特点：

会使用到两个B+树索引，一个二级索引，一个聚簇索引。
访问二级索引使用顺序I/O，访问聚簇索引使用随机I/O。

需要回表的记录越多，使用二级索引的性能就越低，甚至让某些查询宁愿使用全表扫描也不使用二级索引。比方说name值在Asa～Barlow之间的用户记录数量占全部记录数量90%以上，那么如果使用idx_name_birthday_phone_number索引的话，有90%多的id值需要回表，这不是吃力不讨好么，还不如直接去扫描聚簇索引（也就是全表扫描）。

查询优化器做的工作，查询优化器会事先对表中的记录计算一些统计数据，然后再利用这些统计数据根据查询的条件来计算一下需要回表的记录数，需要回表的记录数越多，就越倾向于使用全表扫描，反之倾向于使用二级索引 + 回表的方式。

比方说上边的查询可以改写成这样：

SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow' LIMIT 10;

添加了LIMIT 10的查询更容易让优化器采用二级索引 + 回表的方式进行查询。

覆盖索引

为了彻底告别回表操作带来的性能损耗，我们建议：最好在查询列表里只包含索引列。

SELECT name, birthday, phone_number FROM person_info WHERE name > 'Asa' AND name < 'Barlow'

因为我们只查询name, birthday, phone_number这三个索引列的值，所以在通过idx_name_birthday_phone_number索引得到结果后就不必到聚簇索引中再查找记录的剩余列，也就是country列的值了，这样就省去了回表操作带来的性能损耗。

我们把这种只需要用到索引的查询方式称为索引覆盖。

我们很不鼓励用*号作为查询列表，最好把我们需要查询的列依次标明。

如何挑选索引

只为用于搜索、排序或分组的列创建索引

也就是说，只为出现在WHERE子句中的列、连接子句中的连接列，或者出现在ORDER BY或GROUP BY子句中的列创建索引。而出现在查询列表中的列就没必要建立索引了

SELECT birthday, country FROM person_name WHERE name = 'Ashburn';

考虑列的基数

记录行数一定的情况下，列的基数越大，该列中的值越分散，列的基数越小，该列中的值越集中。

假设某个列的基数为1，也就是所有记录在该列中的值都一样，那为该列建立索引是没有用的，因为所有值都一样就无法排序，无法进行快速查找了。

而且如果某个建立了二级索引的列的重复值特别多，那么使用这个二级索引查出的记录还可能要做回表操作，这样性能损耗就更大了。

索引列的类型尽量小

如果我们想要对某个整数列建立索引的话，在表示的整数范围允许的情况下，尽量让索引列使用较小的类型。
因为：

数据类型越小，在查询时进行的比较操作越快（这是CPU层次的东东）
数据类型越小，索引占用的存储空间就越少，在一个数据页内就可以放下更多的记录，从而减少磁盘I/O带来的性能损耗，也就意味着可以把更多的数据页缓存在内存中，从而加快读写效率。

因为不仅是聚簇索引中会存储主键值，其他所有的二级索引的节点处都会存储一份记录的主键值，如果主键适用更小的数据类型，也就意味着节省更多的存储空间和更高效的I/O。

让索引列在比较表达式中单独出现

如：

WHERE my_col * 2 < 4
WHERE my_col < 4/2

第1个WHERE子句中my_col列并不是以单独列的形式出现的，而是以my_col * 2这样的表达式的形式出现的，存储引擎会依次遍历所有的记录，计算这个表达式的值是不是小于4。

如果索引列在比较表达式中不是以单独列的形式出现，而是以某个表达式，或者函数调用形式出现的话，是用不到索引的。

主键插入顺序

对于一个使用InnoDB存储引擎的表来说，在我们没有显式的创建索引时，表中的数据实际上都是存储在聚簇索引的叶子节点的。而记录又是存储在数据页中的，数据页和记录又是按照记录主键值从小到大的顺序进行排序，所以如果我们插入的记录的主键值是依次增大的话，那我们每插满一个数据页就换到下一个数据页继续插。

如果我们插入的主键值忽大忽小的话，就会需要页分裂和记录移位，意味着：性能损耗！所以如果我们想尽量避免这样无谓的性能损耗，最好让插入的记录的主键值依次递增，这样就不会发生这样的性能损耗了。

所以我们建议：让主键具有AUTO_INCREMENT，让存储引擎自己为表生成主键，而不是我们手动插入。