《MySQL是怎样运行的：从根儿上理解MySQL》读书笔记（五）

7 B+树索引的使用

我们前边详细、详细又详细的唠叨了InnoDB存储引擎的B+树索引，我们必须熟悉下边这些结论：

• 每个索引都对应一棵B+树，B+树分为好多层，最下边一层是叶子节点，其余的是内节点。所有用户记录都存储在B+树的叶子节点，所有目录项记录都存储在内节点。
• InnoDB存储引擎会自动为主键建立聚簇索引（如果没有显式指定主键或者没有声明不允许存储 NULL 的 UNIQUE 键，它会自动添加主键），聚簇索引的叶子节点包含完整的用户记录。
• 我们可以为感兴趣的列建立二级索引，二级索引的叶子节点包含的用户记录由索引列 + 主键组成。如果想通过二级索引查找完整的用户记录，需要执行回表操作，也就是在通过二级素引找到主键值之后，再到聚族索引中查找完整的用户记录。
• B+树中的每层节点都按照索引列的值从小到大的顺序排序组成了双向链表，而且每个页内的记录（无论是用户记录还是目录项记录，都按照索引列的值从小到大的顺序形成了一个单向链表。如果是联合索引，则页面和记录先按照索引列中前面的列的值排序；如果该列的值相同，再按照索引列中后面的列的值排序。比如，我们对列 c2 和 c3 建立了联合索引 idx c2_03 (c2, c3)，那么该索引中的页面和记录就先按照 c2列 的值进行排序；如果 c2列 的值相同，再按照 c3列 的值排序。
• 通过索引查找记录时，是从B+树的根节点开始一层一层向下搜索的。由于每个页面（无论是内节点页面还是叶子节点页面）中的记录都划分成了若干个组，每个组中索引列值最大的记录在页内的偏移量会被当作槽依次存放在Page Directory（页目录）中（当然，规定 Supremum 记录比任何 用户记录都大），因此可以在页目录中通过二分法快速定位到索引列等于某个值的记录。

7.1 B+ 树索引示意图的简化

我们需要先建立一个表：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

CREATE TABLE single_table ( id INT NOT NULL AUTO_INCREMENT, key1 VARCHAR(100), key2 INT, key3 VARCHAR(100), key_part1 VARCHAR(100), key_part2 VARCHAR(100), key_part3 VARCHAR(100), common_field VARCHAR(100), PRIMARY KEY (id), KEY idx_key1 (key1), UNIQUE KEY uk_key2 (key2), KEY idx_key3 (key3), KEY idx_key_part(key_part1, key_part2, key_part3) ) Engine=InnoDB CHARSET=utf8;

我们为这个 single_table 表建立了1个聚簇索引和4个二级索引，分别是：

• 为id列建立的聚簇索引。
• 为key1列建立的idx_key1二级索引。
• 为key2列建立的uk_key2二级索引，而且该索引是唯一二级索引。
• 为key3列建立的idx_key3二级索引。
• 为key_part1、key_part2、key_part3列建立的idx_key_part二级索引，这也是一个联合索引。

然后我们需要为这个表插入10000行记录，除id列外其余的列都插入随机值就好了，具体的插入语句我就不写了，自己写个程序插入吧（id列是自增主键列，不需要我们手动插入）。

为了方便大家理解，第6章把 B+树 的完整结构画了出来，包括它的内节点和叶子节点，以及各个节点中的记录。不过我们现在己经掌握了 B+树 的基本原理，知道了 B+树 其实是个“矮矮的大胖子”，并且学习了如何利用 B+树 快速地定位记录。所以，是时候简化一下 B+树 的示意图了。比如我们可以把 single_table 表的聚簇索引示意图简化为如图所示的样子：

在图中，我们把聚簇索引对应的复杂的 B+树 结构进行了极度精简。可以看到，图中忽略掉了页的结构，直接把所有的叶子节点中的记录都放在一起展示。方便起见，我们后面把聚簇索引叶子节点中的记录称为聚簇索引记录。虽然图很简陋，但还是突出了聚簇索引的一个非常重要的特点：聚簇索引记录是按照主键值由小到大的顺序排序的。当然，为了追求视觉上的极致简洁，图中的“其他列”也可以略去，只需要保留 id列 即可。再次简化后的 B+树 示意图如图所示：

通过聚簇索引对应的 B+ 树， 我们可以很容易地定位到主键值等于某个值的聚簇索引记录。比如我们想通过这个 B+ 树定位到 id 值为 1438 的记录，那么示意图就如图所示：

下边以二级索引 idx_key1 为例，画一下二级索引简化后的 B+树 示意图：

如图所示，我们在二级索引 idx_key1 对应的 B+树 中保留了叶子节点的记录，这些记录包括 key1列 以及 id列，这些记录是按照 key1列 的值由小到大的顺序排序的，如果 key1列 的值相同，则按照id列的值进行排序。为了方便，我们之后就把二级索引叶子节点中的记录称为二级索引记录。

如果我们想查找 key1 值等于某个值的二级索引记录，那么可以通过 idx_key1 对应的 B+树，很容易的定位到第一条 key1列 的值等于某个值的二级索引记录，然后沿着记录所在单向链表向后扫描即可。比方说我们想通过这个 B+树 定位到第一条 key1值 为 'abc' 的记录，那么示意图就如下所示：

7.2 索引的代价

在熟悉了B+树索引原理之后，本篇文章的主题是唠叨如何更好的使用索引，虽然索引是个好东西，可不能乱建，在介绍如何更好的使用索引之前先要了解一下使用这玩意儿的代价——它在空间和时间上都会拖后腿：

• 空间上的代价

  这个是显而易见的，每建立一个索引都为要它建立一棵B+树，每一棵B+树的每一个节点都是一个数据页，一个页默认会占用16KB的存储空间，一棵很大的B+树由许多数据页组成，那可是很大的一片存储空间呢。

• 时间上的代价 每次对表中的数据进行增、删、改操作时，都需要去修改各个B+树索引。而且我们讲过，B+树每层节点都是按照索引列的值从小到大的顺序排序而组成了双向链表。不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位，页面分裂、页面回收啥的操作来维护好节点和记录的排序。如果我们建了许多索引，每个索引对应的B+树都要进行相关的维护操作，这还能不给性能拖后腿么？

  另外还有一点就是在执行查询语句前，首先要生成一个执行计划。一般情况下，一条查询语句在执行过程中最多使用一个二级索引（当然也有例外，这将在第 10 章详细唠叨），在生成执行计划时需要计算使用不同索引执行查询时所需的成本，最后选取成本最低的那个索引执行查询（关于如何计算查询的成本，将在第 12 章详细唠叨）。此时如果建了太多索引，可能会导致成本分析过程耗时太多，从而影响查询语句的执行性能。

所以说，一个表上索引建的越多，就会占用越多的存储空间，在增删改记录的时候性能就越差。为了能建立又好又少的索引，我们先得学学这些索引在哪些条件下起作用的。

7.3 应用 B+ 树索引

7.3.1 扫描区间和边界条件

对于某个查询来说，最粗暴的执行方案就是扫描表中的所有记录，针对每一条记录都判断一下该记录是否符合搜索条件，如果符合的话就将其发送到客户端，否则就跳过该记录。这种执行方案也被称为全表扫描。对于使用 InnoDB 存储引擎的表来说，全表扫描意味着从聚簇索引第一个叶子节点的第一条记录开始，沿着记录所在的单向链表向后扫描，直到最后一个叶子节点的最后一条记录为止。虽然全表扫描是一种很笨的执行方案，但却是一种万能的执行方案，所有的查询都可以使用这种方案来执行。

前文讲到，利用 B+树 查找索引列值等于某个值的记录，这样可以明显减少需要扫描的记录数量。其实由于 B+树 的叶子节点中的记录是按照索引列值由小到大的顺序排序的，所以我们只扫描在某个区间或者某些区间中的记录也可以明显减少需要扫描的记录数量。比方说对于下边这个查询语句来说：

1 2	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 >= 2 AND id <= 100 称为形成这个扫描区间的边界条件。

其实对于全表扫描来说， 相当于扫描 id 值在 (-∞，+∞ ) 区间中 的记录，也就是说全表扫描对应的扫描区间是 (-∞，+∞ ) 。

对于下面这个查询语句：

1	SELECT * FROM single_table WHERE key2 IN (1438, 6328) QR (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_keypart 都可以执行上述查询。以 idx_key1 为例，很显然我们无法通过搜索条件形成合适的扫描区间来减少需要扫描的 idx_key 二级索引记录数量，只能扫描 idx_key1 的全部二级索引记录。针对获取到的每一条二级索引记录，都需要执行回表操作来获取完整的用户记录。我们也可以说此时使用 idx_key1 执行查询时对应的扫描区间就是 (-∞, +∞)。这样子虽然行得通，但我们图啥呢？最粗暴的全表扫描方式已经要扫描全部的聚簇索引记录了，你这里除了要访问全部的聚簇索引记录，还要扫描全部的 idx_key1 二级索引记录，这不是费力不讨好么。在这个过程中没有减少需要扫描的记录数量，反而效率比全表扫描更差，所以如果我们想使用某个索引来执行查询，但是又无法通过搜索条件形成合适的扫描区间来减少需要扫描的记录数量时，那么我们是不考虑使用这个索引执行查询的。

并不是所有的搜索条件都可以成为边界条件，比方说下边这个查询：

1 2 3 4

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 连接起来的语义是一样的，都会产生多个单点扫描区间。比如下面这两个语句的语义效果是一样的：

  1 2	SELECT * FROM single table WHERE key2 IN (1438, 6328) SELECT * FROM single _table WHERE key2 = 1438 OR key2 = 6328;

• != 产生的扫描区间比较有趣，也容易被大家忽略，比如：

  1	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’)。

前面介绍的几个例子的搜索条件都比较简单，在使用某个索引执行查询时，我们可以很容易识别出对应的扫描区间，以及形成该扫描区间的边界条件。在日常的工作中，一个查询语句中的 WHERE 子句可能有很多个小的搜索条件，这些搜索条件使用 AND 或者 OR 操作符连接 起来.虽然大家都知道这两个操作符的作用，但这里还是要再强调一遍：

• cond1 AND cond2 : 只有当 cond1 和 cond2 都为 TRUE 时，整个表达式才为 TRUE。
• cond1 OR cond2 : 只要 cond1 或者 cond2 中有一个为 TRUE，整个表达式就为 TRUE。

在我们执行一个查询语句时，首先需要找出所有可用的索引以及使用它们时对应的扫描区间。下面我们来看一下怎么从包含若干个 AND 或 OR 的复杂搜索条件中提取出正确的扫描区间。

7.3.1.1 所有的搜索条件都可以生成合适的扫描区间的情况

在使用某个索引执行查询时，有时每个小的搜索条件都可以生成一个合适的扫描区间来减少需要扫描的记录数量。比如下面这个查询语句：

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 操作符将多个搜索条件连接在一起的情况。来看下面这个查询语句：

1	SELECT * FROM single_table WHERE key2 > 100 OR key2 > 200;

OR 意味着需要取各个扫描区间的并集。取并集的过程如图所示：

也就是说上面这个查询语句使用 uk_key2 索引执行查询时对应的扫描区间就是 (100, +∞) ，形成该扫描区间的边界条件就是 key2 > 100。

7.3.1.2 有的搜索条件不能生成合适的扫描区间的情况

在使用某个索引执行查询时，有时某个小的搜索条件不能生成合适的扫描区间来减少需要扫描的记录数量。比如下面这个查询语句：

1	SELECT * FROM single_table WHERE key2 > 100 AND common_field = 'abc';

使用 uk_key2 执行查询时，很显然 key2 > 100 可以形成扫描区间 (100, +∞) 。但是，由于 uk_key2 的二级索引记录并不按照 common_field 列进行排序（其实 uk_key2 二级索引记录中压根儿就不包含 common_field 列），所以仅凭搜索条件 common_field = 'abc’ 并不能减少需要扫描的二级索引记录数量。也就是说此时该搜索条件生成的扫描区间其实就是 (-∞, +∞) ，所以对 (100, +∞) 和 (-∞, +∞) 这两个扫描区间取交集后得到的结果自然是 (100, +∞) 。由于 key2 > 100 和 common_field = 'abc' 这两个小的搜索条件是使用 AND 操作符连接起来的，所以对 (100, +∞) 和 (-∞, +∞) 这两个扫描区间取交集后得到的结果自然是 (100, +∞) 。也就是说在使用 uk_key2 执行上述查询时，最终对应的扫描区间就是 (100, +∞) ，形成该扫描区间的条件就是 key2 > 100。

其实，在使用 uk_key2 执行查询时，在寻找对应的扫描区间的过程中，搜索条件 common_field = 'abc’ 没起到任何作用，我们可以直接把 common_field = 'abc’ 搜索条件替换为 TRUE，如下所示：

1	SELECT * FROM single_table WHERE key2 > 100 AND TRUE;

在化简之后如下所示：

1	SELECT * FROM single_table WHERE key2 > 100;

也就是说上面那个查询语句在使用 uk_key2 执行查询时对应的扫描区间就是 (100, +∞)。

再来看一下使用 OR 操作符的情况.查询语句如下所示：

1	SELECT * FROM single_table WHERE key2 > 100 OR common_field = 'abc';

同理，我们把使用不到 uk_key2 索引的搜索条件替换为 TRUE ，如下所示：

1	SELECT * FROM single_table WHERE key2 > 100 OR TRUE;

接着化简，结果如下所示：

1	SELECT * FROM single_table WHERE TRUE;

可 ， 如果强制使用 uk_key2 执行查询，对应的扫描区间就是 (∞, +∞) ，也就是需要扫描 uk_key2 的全部二级索引记录，并且对于获取到的每一条二级索引记录，都需要执行回表操作。这个代价肯定要比执行全表扫描的代价都大。在这种情况下，我们是不考虑使用 uk_key2 来执行查询的。

7.3.1.3 从复杂的搜索条件中找出扫描区间

有些查询语句的搜索条件可能特别复杂，光是找出在使用某个索引执行查询时对应的扫描区间就挺麻烦。比如下面这个查询语句：

1 2 3 4 5

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 之后，搜索条件如下所示：

1	(key1 > ‘xyz’ AND TRUE) OR (key1 < ‘abc’ and key1 > ‘lmn’) OR (TRUE AND key1 > ‘zzz’ AND (TRUE OR TRUE))

对这个搜索条件进行化简，结果如下所示：

1	(key1 > ‘xyz’) OR (key1 < ‘abc’ and key1 > ‘lmn’) OR (key1 > ‘zzz’)

下面替换掉永远为 TRUE 或 FALSE 的条件。由于 key1 < 'abc’ AND key1 > 'lmn’ 永远为 FALSE，上面的搜索条件可以写成下面这样：

1	(key1 > ‘xyz’) OR (key1 > ‘zzz’)

继续化简。由于 key1 > 'xyz' 和 key1 > 'zzz' 之间是使用 OR 操作符连接起来的，这意味着要取并集，所以最终的化简结果就是 key1 > 'xyz'。 也就是说， 最初的查询语句如果使用 idx_key1 索引执行查询，则对应的扫描区间就是 ('xyz', +∞)。也就是需要把满足 key1 > 'xyz' 条件的所有二级索引记录都取出来，针对获取到的每一条二级索引记录，都要用它的主键值再执行回表操作， 在得到完整的用户记录之后再使用其他的搜索条件进行过滤。

假设使用 uk_key2 执行查询

我们需要把那些不能形成合适的扫描区间的搜索条件暂时使用TRUE替换掉，其中有关 key1 和common_field 的搜索条件都需要被替换掉，替换后的结果如下所示：

1	（TRUE AND key2 = 748） OR (TRUE AND TRUE) OR (TRUE AND TRUE AND (key2 < 8000 OR TRUE))

哎呀呀，key2 < 8000 OR TRUE 的结果肯定是 TRUE 呀，也就是说化简之后的搜索条件成下面这样了：

1	key2 = 748 OR TRUE

这个化简之后的结果就更简单了：

1

TRUE

这个结果也就意味着如果要使用 uk_key2 索引执行查询，则对应的扫描区间就是 (-∞, +∞) ，也就是需要扫描 uk_key2 的全部二级索引记录，针对获取到的每一条二级索引记录还 要进行回表操作。这不是得不偿失么！所以在这种情况下是不会使用 uk_key2 索引的。

在使用 idx_key1 执行上述查询时，搜索条件 key1 LIKE '%suf’ 比较特殊，虽然它不能作为形成扫描区间的边界条件，但是 idx_key1的二级索引记录是包含 key1 列的，因此，我们可以先判断获取到的二级索引记录是否符合这个条件。如果符合再执行回表操作，如果不符合就不执行回表操作了。这样可能减少因回表操作二带来的性能损耗，这种优化方式成为索引条件下推。

7.3.1.4 使用联合索引执行查询时对应的扫描区间

联合索引的索引列包含多个列，B+树 每一层页面以及每个页面中的记录采用的排序规则较为复杂，以single_table 表的 idx_key_part 联合索引为例，它采用的排序规则如下所示：

• 先按照 key_part1 列的值进行排序。
• 在 key_part1 列的值相同的情况下，再按照 key_part2 列的值进行排序。
• 在 key_part1 和 key_part2 列的值都相同的情况下，再按照 key_part3 列的值进行排序。

我们画一下 idx_key_part 索引的示意图：

对于查询语句 Q1 来说：

1 2	Q1：SELECT * FROM single_table WHERE key_part1 = 'a';

由于二级索引记录是先按照 key_part1 列的值进行排序的，所以所有符合 key_part1 = 'a' 条件的记录肯定是相邻的，我们可以定位到第一条符合 key_part1 = 'a' 条件的记录，然后沿着记录所在的单向链表向后扫描，直到某条记录不符合 key_part1 = 'a' 条件为止（当然，对于获取到的每一条二级索引记录都要执行回表操作，我们这里就不展示回表操作了），如下图所示：

也就是说， 如果使用 idx_key_part1 索引 执行查询语句 Q1，对应的扫描区间就是 ['a', 'a']，形成这个扫描区间的边界条件就是 key_part1 = 'a'。

对于查询语句 Q2 来说：

1 2 3

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_part 索引中，从第一条符合 key_part1 = 'a' AND key_part2 = 'b' 条件的记录开始，到最后一条符合 key_part1 = 'a' AND key_part2 = 'b' 条件的记录为止的所有二级索引记录。

对于查询语句 Q3 来说：

1 2 3 4

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 来说：

1 2	Q4：SELECT * FROM single_table WHERE key_part1 < 'a';

由于二级索引记录是先按照 key_part1 列的值进行排序的，所以所有符合 key_part1 < 'a' 条件的记录肯定是相邻的，我们可以定位到第一条符合 key_part1 < 'a' 条件的记录（其实就是 idx_key_part 索引第一个叶子节点的第一条记录），然后沿着记录所在的单向链表向后扫描，直到某条记录不符合 key_part1 < 'a' 为止（当然，对于获取到的每一条二级索引记录都要执行回表操作，我们这里就不展示回表操作了），如下图所示：

也就是说，如果我们使用 idx_key_part 索引执行查询 Q4 时，可以形成扫描区间 (-∞, 'a')，形成这个扫描区间的条件就是 key_part1 < 'a'。

对于查询语句 Q5 来说：

1 2 3 4

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 < 'c' 条件的记录，然后沿着记录所在的单向链表向后扫描，直到某条记录不符合 key_part1='a' 条件或者 key_part2 > 'a' 条件或者 key_part2 < 'd' 条件为止（当然，对于获取到的每一条二级索引记录都要执行回表操作，我们这里就不展示回表操作了），如下图所示：

也就是说，如果我们使用 idx_key_part 索引执行查询 Q5 时，可以形成扫描区间 (('a', 'a'), ('a', 'd'))，形成这个扫描区间的条件就是 key_part1 = 'a' AND key_part2 > 'a' AND key_part2 < 'd'。

对于查询语句 Q6 来说：

1 2	Q6：SELECT * FROM single_table WHERE key_part2 = 'a';

由于二级索引记录不是直接按照 key_part2 列的值排序的，所以符合 key_part2 = 'a' 的二级索引记录可能并不相邻，也就意味着我们不能通过这个 key_part2 = 'a' 搜索条件来减少需要扫描的记录数量。在这种情况下，我们是不会使用 idx_key_part 索引执行查询的。

对于查询语句 Q7 来说：

1 2 3

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 = 'c' 无关。

针对获取到的每一条二级索引记录，如果没有开启索引条件下推特性的话，则必须先进行回表操作，获取到完整的用户记录后再判断 key_part3 = 'c' 这个条件是否成立；如果开启了索引条件下推特性的话，可以立即判断该二级索引记录是否符合 key_part3 = 'c' 这个条件，如果符合则再进行回表操作，如果不符合则不进行回表操作，直接跳到下一条二级索引记录。索引条件下推特性是在 MySQL 5.6 中引入的，默认是开启的。

对于查询语句 Q8 来说：

1 2 3

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 来说：

1 2 3

Q9：SELECT * FROM single_table WHERE key_part1 <= 'b' AND key_part2 = 'a';

很显然 Q8 和 Q9 长得非常像，只不过在涉及 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' 的记录扫描完，示意图如下：

也就是说，如果我们使用 idx_key_part 索引执行查询Q9时，可以形成扫描区间 ((-∞, -∞), ('b', 'a')) ，形成这个扫描区间的条件就是 key_part1 <= 'b' AND key_part2 = 'a'。对比查询 Q8，我们必须将所有符合 key_part1 < 'b' 的记录都扫描完，key_part2 = 'a' 这个条件在查询 Q8 中并不能起到减少需要扫描的二级索引记录范围的作用。

可能将查询 Q9 转换为下边的这个形式后更容易理解使用 idx_key_part 索引执行它时对应的扫描区间以及形成扫描区间的条件：

1 2 3

SELECT * FROM single_table WHERE (key_part1 < 'b' AND key_part2 = 'a') OR (key_part1 = 'b' AND key_part2 = 'a');

7.3.2 B+树索引适用的条件

B+树索引并不是万能的，并不是所有的查询语句都能用到我们建立的索引。下边介绍几个我们可能使用B+树索引来进行查询的情况。

我们需要先创建一个表，这个表是用来存储人的一些基本信息的：

1 2 3 4 5 6 7 8 9

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表我们需要注意两点：

• 表中的主键是id列，它存储一个自动递增的整数。所以InnoDB存储引擎会自动为id列建立聚簇索引。

• 我们额外定义了一个二级索引idx_name_birthday_phone_number，它是由3个列组成的联合索引。所以在这个索引对应的B+树的叶子节点处存储的用户记录只保留name、birthday、phone_number这三个列的值以及主键id的值，并不会保存country列的值。

从这两点注意中我们可以再次看到，一个表中有多少索引就会建立多少棵B+树，person_info表会为聚簇索引和idx_name_birthday_phone_number索引建立2棵B+树。下边我们画一下索引idx_name_birthday_phone_number的示意图，不过既然我们已经掌握了InnoDB的B+树索引原理，那我们在画图的时候为了让图更加清晰，所以在省略一些不必要的部分，比如记录的额外信息，各页面的页号等等，其中内节点中目录项记录的页号信息我们用箭头来代替，在记录结构中只保留name、birthday、phone_number、id这四个列的真实数据值，所以示意图就长这样（留心的同学看出来了，这其实和《高性能MySQL》里举的例子的图差不多，我觉得这个例子特别好，所以就借鉴了一下）：

为了方便大家理解，我们特意标明了哪些是内节点，哪些是叶子节点。再次强调一下，内节点中存储的是目录项记录，叶子节点中存储的是用户记录（由于不是聚簇索引，所以用户记录是不完整的，缺少country列的值）。从图中可以看出，这个idx_name_birthday_phone_number索引对应的B+树中页面和记录的排序方式就是这样的：

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

这个排序方式十分、特别、非常、巨、very very very重要，因为只要页面和记录是排好序的，我们就可以通过二分法来快速定位查找。下边的内容都仰仗这个图了，大家对照着图理解。

7.3.2.1 全值匹配

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

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

我们建立的idx_name_birthday_phone_number索引包含的3个列在这个查询语句中都展现出来了。大家可以想象一下这个查询过程：

• 因为B+树的数据页和记录先是按照name列的值进行排序的，所以先可以很快定位name列的值是Ashburn的记录位置。

• 在name列相同的记录里又是按照birthday列的值进行排序的，所以在name列的值是Ashburn的记录里又可以快速定位birthday列的值是'1990-09-27'的记录。

• 如果很不幸，name和birthday列的值都是相同的，那记录是按照phone_number列的值排序的，所以联合索引中的三个列都可能被用到。

有的同学也许有个疑问，WHERE子句中的几个搜索条件的顺序对查询结果有啥影响么？也就是说如果我们调换name、birthday、phone_number这几个搜索列的顺序对查询的执行过程有影响么？比方说写成下边这样：

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

答案是：没影响哈。MySQL有一个叫查询优化器的东东，会分析这些搜索条件并且按照可以使用的索引中列的顺序来决定先使用哪个搜索条件，后使用哪个搜索条件。我们后边儿会有专门的章节来介绍查询优化器，敬请期待。

7.3.2.2 匹配左边的列

其实在我们的搜索语句中也可以不用包含全部联合索引中的列，只包含左边的就行，比方说下边的查询语句：

1	SELECT * FROM person_info WHERE name = 'Ashburn';

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

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

那为什么搜索条件中必须出现左边的列才可以使用到这个B+树索引呢？比如下边的语句就用不到这个B+树索引么？

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

是的，的确用不到，因为B+树的数据页和记录先是按照name列的值排序的，在name列的值相同的情况下才使用birthday列进行排序，也就是说name列的值不同的记录中birthday的值可能是无序的。而现在你跳过name列直接根据birthday的值去查找，臣妾做不到呀～ 那如果我就想在只使用birthday的值去通过B+树索引进行查找咋办呢？这好办，你再对birthday列建一个B+树索引就行了，创建索引的语法不用我唠叨了吧。

但是需要特别注意的一点是，如果我们想使用联合索引中尽可能多的列，搜索条件中的各个列必须是联合索引中从最左边连续的列。比方说联合索引idx_name_birthday_phone_number中列的定义顺序是name、birthday、phone_number，如果我们的搜索条件中只有name和phone_number，而没有中间的birthday，比方说这样：

1	SELECT * FROM person_info WHERE name = 'Ashburn' AND phone_number = '15123983239';

这样只能用到name列的索引，birthday和phone_number的索引就用不上了，因为name值相同的记录先按照birthday的值进行排序，birthday值相同的记录才按照phone_number值进行排序。

7.3.2.3 匹配列前缀

我们前边说过为某个列建立索引的意思其实就是在对应的B+树的记录中使用该列的值进行排序，比方说person_info表上建立的联合索引idx_name_birthday_phone_number会先用name列的值进行排序，所以这个联合索引对应的B+树中的记录的name列的排列就是这样的：

1 2 3 4 5 6 7 8 9 10 11 12

Aaron Aaron ... Aaron Asa Ashburn ... Ashburn Baird Barlow ... Barlow

字符串排序的本质就是比较哪个字符串大一点儿，哪个字符串小一点，比较字符串大小就用到了该列的字符集和比较规则，这个我们前边儿唠叨过，就不多唠叨了。这里需要注意的是，一般的比较规则都是逐个比较字符的大小，也就是说我们比较两个字符串的大小的过程其实是这样的：

• 先比较字符串的第一个字符，第一个字符小的那个字符串就比较小。

• 如果两个字符串的第一个字符相同，那就再比较第二个字符，第二个字符比较小的那个字符串就比较小。

• 如果两个字符串的第二个字符也相同，那就接着比较第三个字符，依此类推。

所以一个排好序的字符串列其实有这样的特点：

• 先按照字符串的第一个字符进行排序。

• 如果第一个字符相同再按照第二个字符进行排序。

• 如果第二个字符相同再按照第三个字符进行排序，依此类推。

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

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

但是需要注意的是，如果只给出后缀或者中间的某个字符串，比如这样：

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

MySQL就无法快速定位记录位置了，因为字符串中间有'As'的字符串并没有排好序，所以只能全表扫描了。有时候我们有一些匹配某些字符串后缀的需求，比方说某个表有一个url列，该列中存储了许多url：

1 2 3 4 5 6 7 8 9

+----------------+ | url | +----------------+ | www.baidu.com | | www.google.com | | www.gov.cn | | ... | | www.wto.org | +----------------+

假设已经对该url列创建了索引，如果我们想查询以com为后缀的网址的话可以这样写查询条件：WHERE url LIKE '%com'，但是这样的话无法使用该url列的索引。为了在查询时用到这个索引而不至于全表扫描，我们可以把后缀查询改写成前缀查询，不过我们就得把表中的数据全部逆序存储一下，也就是说我们可以这样保存url列中的数据：

1 2 3 4 5 6 7 8 9

+----------------+ | url | +----------------+ | moc.udiab.www | | moc.elgoog.www | | nc.vog.www | | ... | | gro.otw.www | +----------------+

这样再查找以com为后缀的网址时搜索条件便可以这么写：WHERE url LIKE 'moc%'，这样就可以用到索引了。

7.3.2.4 匹配范围值

回头看我们idx_name_birthday_phone_number索引的B+树示意图，所有记录都是按照索引列的值从小到大的顺序排好序的，所以这极大的方便我们查找索引列的值在某个范围内的记录。比方说下边这个查询语句：

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

由于B+树中的数据页和记录是先按name列排序的，所以我们上边的查询过程其实是这样的：

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

不过在使用联合进行范围查找的时候需要注意，如果对多个列同时进行范围查找的话，只有对索引最左边的那个列进行范围查找的时候才能用到B+树索引，比方说这样：

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

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

1. 通过条件name > 'Asa' AND name < 'Barlow' 来对name进行范围，查找的结果可能有多条name值不同的记录，

2. 对这些name值不同的记录继续通过birthday > '1980-01-01'条件继续过滤。

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

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

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

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

这个查询的条件可以分为3个部分：

1. name = 'Ashburn'，对name列进行精确查找，当然可以使用B+树索引了。

2. birthday > '1980-01-01' AND birthday < '2000-12-31'，由于name列是精确查找，所以通过name = 'Ashburn'条件查找后得到的结果的name值都是相同的，它们会再按照birthday的值进行排序。所以此时对birthday列进行范围查找是可以用到B+树索引的。

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

同理，下边的查询也是可能用到这个idx_name_birthday_phone_number联合索引的：

1	SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1980-01-01' AND AND phone_number > '15100000000';

7.3.3 索引用于排序

我们在编写查询语句时，经常需要使用 ORDER BY 子句对查询出来的记录按照某种规则进行排序。在一般情况下，我们只能把记录加载到内存中，然后再用 一些排序算法在内存中对这些记录进行排序。有时查询的结果集可能太大以至于无法在内存中进行排序，此时就需要暂 时借助磁盘的空间来存放中间结果，在排序操作完成后再把排好序的结果集返回客户端。

在 MySQL 中，这种在内存或者磁盘中进行排序的方式统称为文件排序 (fìlesort) 。但是 ， 如果 ORDER BY 子句中使用了索引列，就有可能省去在内存或磁盘中排序的步骤。

比如下边这个简单的查询语句：

1	SELECT * FROM single_table QRDER BY key_partl, key_part2, key_part3 LIMIT 10;

这个查询语句的结果集需要先按照 key_part1 值排序。如果记录的 key_part1 值相同，再按照 key_part2 值排序，如果记录的 key_part1 和 key_part2 值都相同，再按照 key_part3 值排序。

如图，该二级索引的记录本身就是按照上述规则排好序的，所以我们可 以从第一条 key_part1 二级索引记录开始，沿着记录所在的单向链表向后扫描，取 10 条二 级索引记录即可。当然，针对获取到的每一条二级索引记录都执行一次回表操作，在获取到完整的用户记录之后发送给客户端就好了。这样是不是就变得简单多了，还省去了我们给 10000 条记录排序的时间——索引就是这么厉害！

请注意，本例的查询语句中加了 LIMIT 子句，这是因为如果不限制需要获取的记录数量，会导致为大量二级索引记录执行回表操作，这样会影响整体的查询性能。关于回表操作造成的影响，我们稍后再详细唠叨。

7.3.3.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+树 索引的。另外，当联合索引的索引列左边连续的列为常量时，也可以使用联合索引对右边的列进行排序。比如下面这个查询：

1	SELECT * FROM sinle_ table WHERE key part1 = 'a' AND key part2 = "b' ORDER BY key part3 LIMIT 10;

这个查询语句能使用联合索引进行排序，原因是 key_part1 值为 'a'、key_part2 值为 'b' 的二级索引记录是按照 key_part3 列的值进行排序的。

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

ASC、DESC混用

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

可能有同学会有疑问：尽管 B+树 的每层页西之问是用双向链表连接起来的，但是在一个页内的记录却是按照记录从小到大的顺序，以单向链表的形式连接起来的。如果 ORDER BY 子句要求以升序排序，那么使用索引查询可以很好理解，但是如果 ORDER BY 子句要求以降序排序，还能使用索引进行查询么？是的，完全可以！这还得得益于页目录中的槽。在查找当前记录的上一条记录时，找到该记录所在组的第一条记录（一直根据记录的 next_record 属性找下一条记录直到菜条记录的头信息的 n_owned 属性值不为0，该记录就是本组中的“带头大哥”然后再从页目录中找到“带头大哥”记录对应的槽的上一个槽，该槽对应记录的下一条记录就是本组中的第一条记录），从第一条记录开始遍历该组中的记录，直到我到当前记录的前一条记录。很显然，找某条记录的上一条记录要比找下一条记录复杂一些。

为啥会有这种规定呢？还得回头想想 idx_key_part 联合索引中的二级索引记录的排序规则：

• 先按照 key_part1 值升序排序；

• 如果记录的 key_part1 值相同，再按照 key_part2 值升序排序；

• 如果记录的 key_part1 和 key_part2 值都相同，再按照 key_part3 值升序排序。

  如果查询语句中各个排序列的排序规则是一致的，比如下面这两种情况。

• ORDER BY key_part1, key_part2 LIMIT 10

  我们可以直接从联合索引最左边的那条二级素引记录开始，向右读 10 条二级索引记录就可以了。

• ORDER BY key_part1 DESC, key_part2 DESC LIMIT 10 我们可以直接从联合索引最右边的那条二级索引记录开始，向左读 10 条二级索引记录 就可以了。

  如果查询的需求是先按照 key_part1 列升序排序，再按照 key_part2 列降序排序，比如下面这个查询语句：

  1	SELECT * FROM single_ table ORDER BY key_part1, key_part2 DESC LIMIT 10;

  此时，如果使用联合索引执行具有排序需求的上述查询，过程就是下面这样。

• 先找到联合索引最左边的那条二级索引记录的 key_part1 值（将其称为 min_value)，然后向右找到 key_part1 值等于 min_value 的所有二级索引记录，然后再从 key_part1 值等于 min_value 的最后一条二级索引记录开始，向左找 10条二级索引记录。

  可是我们怎么知道 key_part1 值等于 min_value 的二级索引记录有多少条呢？我们没有办法知道，只能“傻傻地”一直向右扫描。

• 如果 key_part1 值等于 min_value 的二级索引记录共有几条（且n<10），那就得找到 key_part1 值为 min_value 的最后一条二级素引记录的下一条一级索引记录。假设访一级索引记录的 key_part1 值为 min_value2，那就得再找到 key_part1 值为 min_value2 的所有二级索引记录，然后再从 key_part1 值等于 min_value2 的最后一条二级索引记录开始，向左找 10-n 条记录。

• 如果 key_part1 值为 min_value1 和 min_value2 的二级索引记录还不够10条，那就该怎么办呢？我觉得你懂的。

  这样查询累不累？累！这种需要较为复杂的算法从索引中读取记录的方式，不能高效地使用索引，所以在这种情境下是不会使用联合索引执行排序操作的。

MySQL 8.0 引入了一种称为 Descending lndex 的特性，可以支持 ORDER BY 子句中 ASC、DESC 混用的情况.具体情况可以参考文档。

排序列包含非同一个索引的列

有时用来排序的多个列不是同一个素引中的，这种情况也不能使用索引进行排序。比如下面这个查询语句：

1	SELECT * FROM single_table ORDER BY key1, key2 LIMIT 10;

对于 idx_key1 的二级素引记录来说，只按照 key1 列的值进行排序。而且在 key1 值相同的情况下是不按照 key2 列的值进行排序的，所以不能使用 idx_key1 素引执行上述查询。

排序列是某个联合索引的索引列，但是这些排序列在联合索引中并不连续

比如下面这个查询语句：

1	SELECT * FROM single_table ORDER BY key_partl, key_part3 LIMIT 10;

key_part1 和 key_part3 在联合素引 idx_key_part 中并不连续，中间还有个 key_part2。对于 idx_key_part 的二级索引记录来说，key_part1 值相同的记录并不是按照 key_part3 排序的，所以不能使用 idx_key_part 执行上述查询。

用来形成扫描区间的索引列与排序列不同

比如下面这个查询语句：

1	SELECT * FROM single table WHERE key1 = 'a' ORDER BY key2 LIMIT 10:

在这个查询语句中，搜索条件 key1 ='a' 用来形成扫描区间，也就是在使用 idx_key1 执行该查询时，仅需要扫描 key1 值为 'a' 的二级索引记录即可。此时无法使用 uk_key2 执行上述查询。

排序列不是以单独列名的形式出现在 ORDER BY 子句中

要想使用索引进行排序操作，必须保证索引列是以单独列名的形式（而不是修饰过的形式）出现。比如下面这个查询语句：

1	SELECT * FROM single table ORDER BY UPPER (key) LIMIT 10;

因为 key1 列是以 UPPER(key1) 函数调用的形式出现在 ORDER BY 子句中的（UPPER 函数用于将字符串转为大写形式），所以不能使用 idx_key1 执行上述查询。

7.3.4 索引用于分组

有时候我们为了方便统计表中的一些信息，会把表中的记录按照某些列进行分组。比如下边这个分组查询：

1	SELECT key_partl, key_part2, key_part3, COUNT (*) FROM single_ 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+树 索引进行排序差不多，分组列的顺序也需要与索引列的顺序一致；也可以只使用索引列中左边连续的列进行分组。

7.4 回表的代价

对于下面这个查询语句来说：

1	SELECT * FROM single_table WHERE key1 > 'a' AND keyl < 'c';

我们可以选择下面这两种方式来执行。

• 以全表扫描的方式执行该查询

  也就是直接扫描全部的聚簇索引记录，针对每一条聚筷索引记录，都判断搜索条件是否成立，如果成立则发送到客户端，否则跳过该记录。

• 使用 idx_key1 执行该查询

  可以根据搜索条件 key1 >'a' AND key1＜ 'c' 得到对应的扫描区间 ('a', 'c')，然后扫描该扫描区间中的二级索引记录。由于idx_key1 索引的叶子节点存储的是不完整的用户记录，仅包含 key1、id 这两个列，而查询列表是 *，这意味着我们需要获取每条二级索引记录对应的聚簇索引记录，也就是执行回表操作，在获取到完整的用户记录后再发送到客户端。

  对于使用 InnoDB 存储引擎的表来说，索引中的数据页都必须存放在磁盘中，等到需要时再加载到内存中使用。这些数据页会被存放到磁盘中的一个或者多个文件中，页面的页号对应着该页在磁盘文件中的偏移量。以 16KB 大小的页面为例，页号为 0 的页面对应着这些文件中偏移量为 0 的位置，页号为 1页面对应着这些文件中偏移量为 16KB 的位置。

  前面章节讲过，B+树 的每层节点会使用双向链表连接起来，上一个节点和下一个节点的页号可以不必相邻。不过在实际实现中，设计 InnoDB 的大叔还是尽量让同一个索引的叶子节点的页号按照顺序排列，这一点会在稍后讨论表空间时再详细唠叨。

  也就是说，idx_key1 在扫描区间 ('a', 'c') 中的二级索引记录所在的页面的页号会尽可能相邻。即使这些页面的页号不相邻，但起码一个页面可以存放很多记录，也就是说在执行完一次 页面I/O 后，就可以把很多二级索引记录从磁盘加载到内存中。总而言之，就是读取在扫描区间 ('a', 'c') 中的二级索引记录时，所付出的代价还是较小的。不过扫描区间 ('a', 'c') 中的二级索引记录对应的 id 值的大小是毫无规律的，我们每读取一条二级索引记录，就需要根据该二级索引记录的计值到聚簇索引中执行回表操作。如果对应的聚筷索引记录所在的页面不在内存中，就需要将该页面从磁盘加载到内存中。由于要读取很多 id 值并不连续的聚族索引记录，而且这些聚簇索引记录分布在不同的数据页中，这些数据页的页号也毫无规律，因此会造成大量的随机I/O。

  需要执行回表操作的记录越多，使用二级索引进行查询的性能也就越低，某些查询宁愿使用全表扫描也不使用二级索引。比如，假设 key1 值在 'a' ~ 'c'。之间的用户记录数量占全部记录数量的 99% 以上，如果使用 idx_key1 索引，则会有 99% 以上的 id 值需要执行回表操作。这不是吃力不讨好么，还不如直接执行全表扫描。

  那么在执行查询时，什么时候采用全表扫描，什么时候使用 二级索引＋回表 的方式呢？这就是查询优化器应该做的工作。查询优化器会事先针对表中的记录计算一些统计数据，然后再利用这些统计数据或者访问表中的少量记录来计算需要执行回表操作的记录数。如果需要执行回表操作的记录数越多，就越倾向于使用全表扫描，反之则倾向于使用 二级索引＋回表 的方式。当然，查询优化器所做的分析工作没有这么简单，但大致上是这样一个过程。第12章会进行定量的分析。

  一般情况下，可以给查询语句指定 LIMIT 子句来限制查询返回的记录数，这可能会让查询优化器倾向于选择使用二级索引十回表的方式进行查询，原因是回表的记录越少，性能提升就越高。比如，上面的查询语句可以改写成下面这样：

  1	SELECT * FROM single table WHERE key1 > 'a' AND keyl < 'c' LIMIT 10;

  添加了 LIMIT 10 子句后的查询语句更容易让查询优化器采用二级索引＋回表的方式来执行。

  对于需要对结果进行排序的查询，如果在采用二级索引执行查询时需要执行回表操作的记录特别多，也倾向于使用全表扫描＋文件排序的方式执行查询。比如下面这个查询语句：

  1	SELECT * FROM single_table ORDER BY keyl;

  由于查询列表是 *，如果使用二级索引进行排序，则需要对所有二级索引记录执行回表操作。这样操作的成本还不如直接遍历聚簇素引然后再进行文件排序低，所以查询优化器会倾向于使用全表扫描的方式执行杳询。如果添加了 LIMIT 子句，比如下面这个查询语句。

  1	SELECT * FROM single_table ORDER BY key1 LIMIT 10;

  这个查询语句需要执行回表操作的记录特别少，查询优化器就会倾向于使用二级索引＋回表的 方式来执行。

7.5 更好地创建和使用索引

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

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

1	SELECT common_field, key_part3 FROM single_table WHERE key1 = 'a';

查询列表中的 common_field、key_part3 这两个列就没有必要创建索引。我们只需要为出现在 WHERE 子句中的 key1 列创建索引就可以了。

7.5.2 考虑列的基数

列的基数指的是某一列中不重复数据的个数，比方说某个列包含值2, 5, 8, 2, 5, 8, 2, 5, 8，虽然有9条记录，但该列的基数却是3。也就是说，在记录行数一定的情况下，列的基数越大，该列中的值越分散，列的基数越小，该列中的值越集中。这个列的基数指标非常重要，直接影响我们是否能有效的利用索引。假设某个列的基数为1，也就是所有记录在该列中的值都一样，那为该列建立索引是没有用的，因为所有值都一样就无法排序，无法进行快速查找了～ 而且如果某个建立了二级索引的列的重复值特别多，那么使用这个二级索引查出的记录还可能要做回表操作，这样性能损耗就更大了。所以结论就是：最好为那些列的基数大的列建立索引，为基数太小列的建立索引效果可能不好。

7.5.3 索引列的类型尽量小

我们在定义表结构的时候要显式的指定列的类型，以整数类型为例，有TINYINT、MEDIUMINT、INT、BIGINT这么几种，它们占用的存储空间依次递增，我们这里所说的类型大小指的就是该类型表示的数据范围的大小。能表示的整数范围当然也是依次递增，如果我们想要对某个整数列建立索引的话，在表示的整数范围允许的情况下，尽量让索引列使用较小的类型，比如我们能使用INT就不要使用BIGINT，能使用MEDIUMINT就不要使用INT～ 这是因为：

• 数据类型越小，在查询时进行的比较操作越快（这是CPU层次的东东）

• 数据类型越小，索引占用的存储空间就越少，在一个数据页内就可以放下更多的记录，从而减少磁盘I/O带来的性能损耗，也就意味着可以把更多的数据页缓存在内存中，从而加快读写效率。

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

7.5.4 索引字符串值的前缀

我们知道一个字符串其实是由若干个字符组成，如果我们在MySQL中使用utf8字符集去存储字符串的话，编码一个字符需要占用1~3个字节。假设我们的字符串很长，那存储一个字符串就需要占用很大的存储空间。在我们需要为这个字符串列建立索引时，那就意味着在对应的B+树中有这么两个问题：

• B+树索引中的记录需要把该列的完整字符串存储起来，而且字符串越长，在索引中占用的存储空间越大。

• 如果B+树索引中索引列存储的字符串很长，那在做字符串比较时会占用更多的时间。

前文说过，索引列的字符串前缀其实也是排好序的，所以索引的设计者提出了个方案 — 只对字符串的前几个字符进行索引也就是说在二级索引的记录中只保留字符串前几个字符。这样在查找记录时虽然不能精确的定位到记录的位置，但是能定位到相应前缀所在的位置，然后根据前缀相同的记录的主键值回表查询完整的字符串值，再对比就好了。这样只在B+树中存储字符串的前几个字符的编码，既节约空间，又减少了字符串的比较时间，还大概能解决排序的问题，何乐而不为，比如我们可以这样修改 idx_key1 索引，让索引中只保留字符串的前 10 个字符：

1 2	ALTER TABLE single table DROP INDEX idx_keyl; ALTER TABLE single table ADD INDEX idx_key1 (keyl (10)) ;

然后再执行下面这个查询语句：

1	SELECT * FROM single_table WHERE key1 = abcdefghijklmn';

由于在 idx_key1 的二级索引记录中只保留字符串的前10个字符，所以我们只能定位到前缀为 'abcdefghij' 的二级素引记录，在扫描这些二级素引记录时再判断它们是否满足 key1 = 'abcdefghijklmn' 条件。当列中存储的字符串包含的字符较多时，这种为列前缀建立索引的方式可以明显减少索引大小。

不过，在只对列前级建立索引的情况下，下面这个查询语向就不能使用索引来完成排序需求了：

1	SELECT * FROM sinale_table ORDER BY kev1 LIMIT 10;

因为二级索引 idx_key1 中不包含完整的 key1 列信息，所以在仅使用 idx_key1 索引执行查询时，无法对 key1 列前 10个字符相同但其余字符不同的记录进行排序。也就是说，只为列前缀建立索引的方式无法支持使用索引进行排序的需求。上述查询语句只好乖乖地使用全表扫描＋文件排序的方式来执行了。

7.5.5 覆盖索引

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

1	SELECT key1, id FROM single_table WHERE key1 > 'a' AND key1 < 'c';

由于我们只查询 key1 列和 id 列的值，所以在使用 idx_key1 索引来扫描 ('a', 'c') 区间中的二级索引记录时，可以直接从获取到的二级索引记录中读出 key1 列和 id 列的值，而不需要再通过 id 值到聚簇索引中执行回表操作了，这样就省去了回表操作带来的性能损耗。我们把这种索引中已经包含所有需要读取的列的查询方式称为覆盖索引。排序操作也优先使用覆盖索引进行查询，比如下面这个查询语句：

1	SELECT keyl FROM single_table ORDER BY key1;

虽然这个查询语句中没有 LIMIT 子句，但是由于可以采用覆盖索引，所以查询优化器会直接使用 idx_key1 索引进行排序，而不需要执行回表操作。当然，如果业务需要查询索引列以外的列，那还是以保证业务需求为重。如无必要，最好仅把业务中需要的列放在查询列表中，而不是简单地以* 替代。

7.5.6 让索引列以列名的形式在搜索条件中单独出现

在下面这两个查询语句中，搜索条件的语义是一样的。

1 2	SELECT * FROM s1 single_ table WHERE key2 * 2 < 4; SELECT * FROM s1 single_table WHERE key2 ＜4/2;

在第一个查询语句的搜索条件中，key2 列并不是以单独列名的形式出现的，而是以 key2 * 2 这样的表达式的形式出现的。MySQL 并不会尝试简化 key2 * 2 < 4 表达式，而是直接认为这个搜索条件不能形成合适的扫描区间来减少需要扫描的记录数量，所以该查询语句只能以全表扫描的方式来执行。

在第二个查询语句的搜索条件中，key2 列是以单独列名的形式出现的，MySQL 可以分析出：如果使用 uk_key2 执行查询，对应的扫描区间就是 (-∞, 2)，这可以减少需要扫描的记录数量。所以 MySQL 可能使用 uk_key2 来执行查询。

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

7.5.7 新插入记录时主键大小对效率的影响

我们知道，对于一个使用InnoDB存储引擎的表来说，在我们没有显式的创建索引时，表中的数据实际上都是存储在聚簇索引的叶子节点的。而记录又是存储在数据页中的，数据页和记录又是按照记录主键值从小到大的顺序进行排序，所以如果我们插入的记录的主键值是依次增大的话，那我们每插满一个数据页就换到下一个数据页继续插，而如果我们插入的主键值忽大忽小的话，这就比较麻烦了，假设某个数据页存储的记录已经满了，它存储的主键值在1~100之间：

如果此时再插入一条主键值为9的记录，那它插入的位置就如下图：

可这个数据页已经满了啊，再插进来咋办呢？我们需要把当前页面分裂成两个页面，把本页中的一些记录移动到新创建的这个页中。页面分裂和记录移位意味着什么？意味着：性能损耗！所以如果我们想尽量避免这样无谓的性能损耗，最好让插入的记录的主键值依次递增，这样就不会发生这样的性能损耗了。所以我们建议：让主键具有AUTO_INCREMENT，让存储引擎自己为表生成主键，而不是我们手动插入 。

7.5.6 冗余和重复索引

针对 single_table 表，可以单独针对 key_part1 列建立一个 idx_key_part 1 索引：

1	ALTER TABLE single_table ADD INDEX idx_key_part1(key partl);

其实现在我们已经有了一个针对 key_part1、key_part2、key_part3 列建立的联合素引 idx_key_part。 idx_key_part 索引的二级索引记录本身就是按照 key_part1 列的值排序的，此时再单独为 key_part1 列建立一个索引其实是没有必要的。我们可以把这个新建的 idx_key_part1 索引看作一个元余索引，该冗余索引是没有必要的。

有时，我们可能会对同一个列创建多个索引，比如下面这两个添加索引的语句：

1 2	ALTER TABLE single_table ADD UNIQUE KEY uk_id(id) : ALTER TABLE single_table ADD INDEX idx_id(id):

我们针对 id 列又建立了一个唯一二级索引 uk_id，还建立了一个普通二级索引 idx_id。可是 id 列本身就是 single_table 表的主键， InnoDB 自动为该列建立了聚簇索引，此时 uk_id 和 idx_id 就是重复的，这种重复索引应该避免。