《MySQL是怎样运行的 —— 从跟上理解MySQL》—— 第七章

InnoDB存储引擎B+树索引结论：

每个索引都对应一棵B+树。B+树分为好多层，最下边一层是叶子节点，其余的是内节点。所有用户记录都存储在 B+树的叶子节点，所有目录项记录都存储在内节点。
InnoDB存储引擎会自动为主键建立聚簇索引（如果没有显式指定主键或者没有声明不允许存储NUUL的UNIQUE键，它会自动添加主键，即6字节的隐藏列row_id），聚簇索引的叶子节点包含完整的用户记录。
可以为必要的列建立二级索引，二级索引的叶子节点包含的用户记录由索引列和主键组成。如果想通过二级索引查找完整的用户记录，需要执行回表操作。
B+树中的每层节点都按照索引列的值从小到大的顺序排序组成了双向链衰，而且每个页内的记录（无论是用户记录还是目录项记录）都按照索引列的值从小到大的顺序形成了一个单向链表。如果是联合索引，则页面和记录先按照索引列中前面的列的值排序；如果该列的值相同，再按照索引列中后面的列的值排序。
通过索引查找记录时，是从B+树的根节点开始一层一层向下搜索的.由于每个页面（无论是非叶子节点页面还是叶子节点页面）中的记录都划分成了若干个组，每个组中索引列值最大的记录在页内的偏移量会被当作槽依次存放在页目录中，因此可以在页目录中通过二分法快速定位到索引列等于某个值的记录。

一、B+树索引示意图的简化

示例表结构：

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_partl, key_part2, key_part3)
) Engine=InnoOB 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列除外，其余的列插入随机值即可。

现在，我们来把single_table表的聚簇索引示意图简化成下面这个样子：

上图忽略了页的结构，直接把所有的叶子节点中的记录都放在一起展示。突出了聚簇索引的一个特点：聚簇索引记录是按照主键值由小到大的顺序排列的。接着简化：

通过聚簇索引对应的B+树，我们可以很容易地定位到主键值等于某个值的聚簇索引记录。

比如定位id值为1438的记录：

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

该二级索引的叶子结点中包括key1列和id列。这些记录是按照key1列的值由小到大的顺序排序的。如果key1列值相同，则按照id列的值进行排序。

如果想查找key1值等于某个值的二级索引记录，那么通过idx_key1对应的B+树，可以很容易地定位到第一条key1列的值等于某个值的二级索引记录，然后沿着记录所在的单向链表向后扫描即可。

比如定位key1值为'abc'的第一条记录：

二、索引的代价

索引虽然对提高查询的性能能提供帮助，但是它也是付出很多代价的。

1）空间上的代价

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

2）时间上的代价

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

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

三、应用B+树索引

3.1 扫描区间和边界条件

针对于查询而言，全表扫描是一种很笨的执行方案，但却是一种万能的执行方案，所有的查询都可以使用这种方案来执行。对于使用InnoDB存储引擎的表来说，全表扫描意味着从聚簇索引第一个叶子节点的第一条记录开始，沿着记录所在的单向链表向后扫描，直到最后一个叶子节点的最后一条记录。

那么可以利用B+树查找索引列值等于某个值的记录，这样可以明显减少需要扫描的记录数量。由于B+树叶子节点中的记录是按照索引列值由小到大的顺序排序的，所以只扫描某个区间或者某些区间中的记录也可以明显减少需要扫描的记录数量。

扫描区间：带扫描记录的列值（where语句后的列）所在的区间；

边界条件：形成相应扫描区间的搜索条件。

比如下面这个查询语句：

SELECT * FROM single_table WHERE id >= 2 AND id <= 100;

扫描区间就是 [2, 100]，即id列所在区间。

对于全表扫描来说，对应的扫描区间为(-∞, +∞)。

对于下面这个查询语句：

SELECT * FROM single_table WHERE key2 IN(1438, 6328) OR (key2 >= 38 AND key2 <= 79);

查询的条件中涉及key2列，该列上建立了索引。使用这个二级索引查询，相当于从下面三个扫描区间中获取二级索引记录：

[1438, 1438]: 对应的边界条件就是key2 IN (1438)
[6328, 6328] : 对应的边界条件就是key2 IN (6328)
[38, 79]: 对应的边界条件就是key2 >= 38 AND key2 <= 79

把像[1438，1438]、 [6328，6328] 这样只包含一个值的扫描区间称为单点扫描区间，把[38，79]这样包含多个值的扫描区间称为范围扫描区间。

并不是所有的搜索条件都可以成为边界条件。比如：

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%' 形成的扫描区间相当于['a', 'b')

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

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

SELECT * FROM single_table WHERE key2 > 100 AND key2 > 200;

在使用uk_key2执行查询时， key2 > 100和 key2 > 200这两个小的搜索条件都可以形成一个扫描区间。由于这两个小的搜索条件是使用AND操作符连接的，所以最终的扫描区间就是对这两个小的搜索条件形成的扫描区间取交集后的结果。

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

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

OR 意味着需要取各个扫描区间的并集。

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

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

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

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'并不能减少需要扫描的二级索引记录数量，也就是说此时该搜索条件生成的扫描区间其实就是(-∞, +∞)。由于 key2> 100和 common_field= 'abc'这两个小的搜索条件是使用 AND操作符连接起来的，所以对两个扫描区间取交集后得到的结果是(100, +∞)。即在使用uk_key2执行上述查询时，最终对应的扫描区间就是(100, +∞) ，形成该扫描区间的条件就是 key2 > 100。

在上述的描述中，我们可以发现在使用uk_key2执行查询时，在寻找对应的扫描区间的过程中，搜索条件common_field='abc'没有起到任何作用，可以直接把该条件替换成TRUE：

SELECT * FROM single_table WHERE key2 > 100 AND TRUE;
-- 化简后
SELECT * FROM single_table WHERE key2 > 100; -- 搜索区间(100，+∞)

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.1.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这三列，其中key1列有普通二级索引idx_key1，key2列有唯一二级索引uk_key2。
对于那些可能用到的索引，分析它们的扫描区间。

假设使用idx_key1执行查询

此时需要把那些不能形成合适扫描区间的搜索条件暂时移除掉，即把他们替换为TRUE。

上面的查询中除了有关key2和common_field列的搜索条件不能形成合适的扫描区间外， keyl LIKE '%suf'形成的扫描区间是(-∞, +∞)，所以也需要将它替换为TRUE。把这些不能形成合适扫描区间的搜索条件替换为TRUE之后，搜索条件如下所示：

(key1 > 'xyz' AND TRUE) OR 
(key1 < 'abc' AND key1 > 'lmn') OR 
(TRUE AND key1 > 'zzz' AND (TRUE OR TRUE));

-- 化简后

(key1 > 'xyz') OR (key1 < 'abc' AND key1 > 'lmn') OR (key1 > 'zzz');

然后替换替换掉永真或者永假的条件。

(key1 > 'xyz') OR (key1 > 'zzz');

-- 继续化简

key1 > 'xyz';

=> 如果使用idx_key1索引执行查询，对应的扫描区间是('xyz', +∞)。

假设使用uk_key2执行查询

化简之后剩下：TRUE

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

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

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

联合索引的索引列包含多个列，B+ 树中的每一层页面以及每个页面中的记录采用的排序规则较为复杂。

以 single_table表的idx_key_part联合索引为例，它采用的排序规则如下所示:

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

SELECT * FROM single_table WHERE key_part1 = 'a';

由于二级索引记录是先按照 key_part1列的值排序的，所以符合key_part1='a'条件的所有记录肯定是相邻的。

因此可以定位到符合key_part1='a'条件的第一条记录，然后沿着记录所在的单向链表向后扫描，如果本页面中的记录扫描完了，就根据叶子节点的双向链表找到下一个页面中的第一条记录，继续沿着记录所在的单向链表向后扫描，直到某一条记录不符合key_part1='a'条件为止。

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

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'条件的二级索引记录肯定是相邻的。

如果使用idx_key_part索引执行该查询语句，可以形成扫描区间[('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'条件的记录为止的所有二级索引记录。

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'条件的二级索引记录肯定是相邻的。

如果使用idx_key_part索引执行该查询语句，可以形成扫描区间`[('a', 'b', 'c'), ('a', 'b', 'c')]，形成这个扫描区间的边界条件就是 key_part1 = 'a' AND key_part2 = 'b' AND key_part3 = 'c'。

SELECT * FROM single_table WHERE key_part1 < 'a';

由于二级索引记录是先按照key_part1列的值排序的，所以符合key_part1 < 'a'条件的所有记录肯定是相邻的。

=> 形成扫描区间[(-∞, 'a')]，形成这个扫描区间的边界条件就是key_part1 < 'a'。

SELECT * FROM single_table WHERE key_part1 = 'a' AND key_part2 > 'a' AND key_part2 < 'd';

=>=> 形成扫描区间[('a', 'a'), ('a', 'd')]，形成这个扫描区间的边界条件就是key_part1 = 'a' AND key_part2 > 'a' AND key_part2 < 'd'。

SELECT * FROM single_table WHERE key_part2 = 'a';

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

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索引执行该扫描语句的过程中，对应的扫描区间其实是['a', 'a']，形成该扫描区间的边界条件是key_part1 = 'a'，与key_part3 = 'c'无关。

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

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索引执行该查询语句的过程中，对应的扫描区间其实是[-∞, 'b']，形成该扫描区间的边界条件是key_part1 < 'b'，与key_part2 = 'a'无关。

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

符合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索引执行该查询语句，可以形成扫描区间[(-∞,-∞), ('b','a')]，形成这个扫描区间的边界条件就是 key_part1 <= 'b' AND key_part2 = 'a'。

3.2 索引用于排序

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

在MySQL中，把这种在内存中或者磁盘上进行排序的方式统称为filesort。但是如果ORDER BY子句里使用到了我们的索引列，就有可能省去在内存或文件中排序的步骤。

SELECT * FROM single_table ORDER BY key_part1, key_part2, key_part3 LIMIT 10;

这个查询的结果集需要先按照key_part1值排序，如果记录的key_part1值相同，则需要按照key_part2来排序，如果key_part2的值相同，则需要按照key_part3排序。而建立的idx_key_part索引，因为这个B+树索引本身就是按照上述规则排好序的，所以直接从索引中提取数据，然后进行回表操作取出该索引中不包含的列就好了。

3.2.1 使用联合索引进行排序的注意事项

对于联合索引有个问题需要注意，ORDER BY的子句后边的列的顺序也必须按照索引列的顺序给出。

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

ASC、DESC混用

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

尽管 B+树的每层页面之间是用双向链表连接起来的，但是在一个页内的记录却是按照记录从小到大的顺序，以单向链表的形式连接起来的。如果 ORDER BY子句要求以升序排序，那么使用索引查询可以很好理解，但是反回来ORDER BY子句要求以降序排序，还能使用索引进行查询么？

是的，完全可以！这还得得益于页目录中的槽。在查找当前记录的上一条记录时，找到该记录所在组的第一条记录（一直根据记录的next_record属性找下一条记录，直到某条记录的头信息的o_owned属性值不为0，该记录就是本组中的“带头大哥”，然后再从页目录中找到“带头大哥”记录对应的糟的上一个槽，该槽对应记录的下一条记录就是本组中的第一条记录），从第一条记录开始遍历该组中的记录，直到找到当前记录的前一条记录。很显然，找某条记录的上一条记录要比找下一条记录复杂一些。

回顾索引idx_key_part的结构：

先按照记录的key_part1列的值进行升序排列。
如果记录的key_part1列的值相同，再按照key_part2列的值进行升序排列。
如果记录的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列进行降序排列的话，比如：

SELECT * FROM single_table ORDER BY key_part1, key_part2 DESC LIMIT 10;

这样如果使用索引排序的话过程就是这样的：

先从索引的最左边确定key_part1列最小的值，然后找到key_part1列等于该值的所有记录，然后从key_part1列等于该值的最右边的那条记录开始往左找10条记录。
如果key_part1列等于最小的值的记录不足10条，再继续往右找key_part1值第二小的记录，重复上面那个过程，直到找到10条记录为止。

这样不能高效使用索引，而要采取更复杂的算法去从索引中取数据，MySQL觉得这样还不如直接文件排序来的快，所以就规定使用联合索引的各个排序列的排序顺序必须是一致的。

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

有时候用来排序的多个列不是一个索引里的，这种情况也不能使用索引进行排序，比如：

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

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

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

SELECT * FROM single_table ORDER BY key_part1, key_part3 LIMIT 10;

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

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

如果WHERE子句中出现了非排序使用到的索引列，那么排序依然是使用不到索引的，

SELECT * FROM single_table WHERE key1 = 'a' ORDER BY key2 LIMIT 10;

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

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

要想使用索引进行排序操作，必须保证索引列是以单独列的形式出现，而不是修饰过的形式，比如：

SELECT * FROM single_table ORDER BY UPPER(key1) LIMIT 10;

使用了UPPER函数修饰过的列就不是单独的列，这样就无法使用索引进行排序。

3.3 索引用于分组

有时候我们为了方便统计表中的一些信息，会把表中的记录按照某些列进行分组。

SELECT key_part1, 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的值分成更小的分组，所以整体上看起来就像是先把记录分成一个大分组，然后把大分组分成若干个小分组，然后把若干个小分组再细分成更多的小小分组。

然后针对那些小小分组进行统计，比如在我们这个查询语句中就是统计每个小小分组包含的记录条数。如果没有索引的话，这个分组过程全部需要在内存（产生临时表）里实现，而如果有了索引的话，恰巧这个分组顺序又和我们的B+树中的索引列的顺序是一致的，而我们的B+树索引又是按照索引列排好序的，所以可以直接使用B+树索引进行分组。

四、回表的代价

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

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

执行该语句的两种方式：

全表扫描：扫描聚簇索引
使用idx_key1执行查询：扫描索引树获取ID，然后回表

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

idx_key1在扫描区间('a','c')中的二级索引记录所在的页面的页号会尽可能相邻。即使这些页面的页号不相邻，但起码一个页面可以存放很多记录，也就是说在执行完一次页面I/O后，就可以把很多二级索引记录从磁盘加载到内存中。

=> 读取在扫描区间 ('a','c') 中的二级索引记录时，所付出的代价还是较小的。不过扫描区间 ('a', 'c')中的二级索引记录对应的 id值的大小是毫无规律的，每读取一条二级索引记录，就需要根据该二级索引记录的 id 值到聚簇索引中执行回表操作。如果对应的聚簇索引记录所在的页面不在内存中，就需要将该页面从磁盘中加载到内存中。由于要读取很多 id值并不连续的聚簇索引记录，而且这些聚簇索引记录分布在不同的数据页中，这些数据页的页号也毫无规律，因此会造成大量的随机I/O。

需要执行回表操作的记录越多，使用二级索引进行查询的性能也就越低，某些查询宁愿使用全表扫描也不使用二级索引。

那么在执行查询时，什么时候采用全表扫描，什么时候使用二级索引+回表的方式呢？这就是查询优化器应该做的工作。查询优化器会事先针对表中的记录计算一些统计数据，然后再利用这些统计数据或者访问表中的少量记录来计算需要执行回表操作的记录数，如果需要执行回表操作的记录数越多，就越倾向于使用全表扫描，反之则倾向于使用二级索引+回表的方式。

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

五、更好的创建和使用索引

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

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

5.2 考虑索引列中不重复值的个数

不重复值的个数 —— 基数

列的基数指的是某一列中不重复数据的个数，比方说某个列包含值2, 5, 8, 2, 5, 8, 2, 5, 8，虽然有9条记录，但该列的基数却是3。

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

5.3 索引列类型尽量小

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

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

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

5.4 为列前缀建立索引

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

B+树索引中的记录需要把该列的完整字符串存储起来，而且字符串越长，在索引中占用的存储空间越大。
如果B+树索引中索引列存储的字符串很长，那在做字符串比较时会占用更多的时间。

索引列的字符串前缀其实也是排好序的，所以可以只对字符串的前几个字符进行索引，即在二级索引的记录中只保留字符串前几个字符。这样在查找记录时虽然不能精确的定位到记录的位置，但是能定位到相应前缀所在的位置，然后根据前缀相同的记录的主键值回表查询完整的字符串值，再对比就好了。这样只在B+树中存储字符串的前几个字符的编码，既节约空间，又减少了字符串的比较时间，还大概能解决排序的问题。

只索引字符串值的前缀的策略是推荐的，尤其是在字符串类型能存储的字符比较多的时候。

5.5 覆盖索引

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

比如：

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

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

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

排序操作也优先使用覆盖索引的方式进行查询，比如：

SELECT key1, id FROM single_table ORDER BY key1;

虽然这个查询语句中没有LIMIT子句，但是由于可以采用覆盖索引，所以查询优化器会直接使用 idx_key1索引进行排序，而不需要执行回表操作。

如果业务需要查询出索引以外的列，那还是以保证业务需求为重。但是很不推荐用*号作为查询列表，最好把需要查询的列依次标明。

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

下面的两个WHERE子句虽然语义是一致的，但是在效率上却有差别：

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

第1个WHERE子句中my_col列并不是以单独列的形式出现的，而是以my_col * 2这样的表达式的形式出现的，存储引擎会依次遍历所有的记录，计算这个表达式的值是不是小于4，所以这种情况下是使用不到为my_col列建立的B+树索引的。而第2个WHERE子句中my_col列并是以单独列的形式出现的，这样的情况可以直接使用B+树索引。

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

5.7 主键插入顺序

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

假设某个数据页存储的记录已经满了，它存储的主键值在1~100之间：

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

此时就需要把当前页面分裂成两个页面，把本页中的一些记录移动到新创建的这个页中。页面分裂和记录移位意味性能损耗。

避免这样无谓的性能损耗，最好让插入的记录的主键值依次递增，这样就不会发生这样的性能损耗了。

推荐让主键具有AUTO_INCREMENT，让存储引擎为表生成主键，而不是手动插入。

5.8 冗余和重复索引

针对single_table表，可以单独针对key_part1列建立一个idx_key_part1索引。

ALTER TABLE single_table ADD INDEX idx_key_part1(key_part1);

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

另一种情况，我们可能会对某个列重复建立索引，比方说这样：

CREATE TABLE repeat_index_demo (
    c1 INT PRIMARY KEY,
    c2 INT,
    UNIQUE uidx_c1 (c1),
    INDEX idx_c1 (c1)
);

c1既是主键、又给它定义为一个唯一索引，还给它定义了一个普通索引，可是主键本身就会生成聚簇索引，所以定义的唯一索引和普通索引是重复的，这种情况要避免。

六、总结

B+树索引在空间和时间上都有代价，所以只在需要的时候建立索引。
B+树索引适用于下面这些情况：
- 全值匹配
- 匹配左边的列
- 匹配范围值
- 精确匹配某一列并范围匹配另外一列
- 用于排序
- 用于分组
在使用索引时需要注意下面这些事项：
- 只为用于搜索、排序或分组的列创建索引
- 为列的基数大的列创建索引
- 索引列的类型尽量小
- 可以只对字符串值的前缀建立索引
- 只有索引列在比较表达式中单独出现才可以适用索引
- 为了尽可能少的让聚簇索引发生页面分裂和记录移位的情况，建议让主键拥有AUTO_INCREMENT属性。
- 定位并删除表中的重复和冗余索引
- 尽量使用覆盖索引进行查询，避免回表带来的性能损耗

youyichannel

重拾MySQL —— B+树的使用

一、B+树索引示意图的简化

二、索引的代价

三、应用B+树索引

3.1 扫描区间和边界条件

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

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

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

假设使用idx_key1执行查询

假设使用uk_key2执行查询

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

3.2 索引用于排序

3.2.1 使用联合索引进行排序的注意事项

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

ASC、DESC混用

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

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

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

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

3.3 索引用于分组

四、回表的代价

五、更好的创建和使用索引

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

5.2 考虑索引列中不重复值的个数

5.3 索引列类型尽量小

5.4 为列前缀建立索引

5.5 覆盖索引

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

5.7 主键插入顺序

5.8 冗余和重复索引

六、总结

一、B+树索引示意图的简化

二、索引的代价

三、应用B+树索引

3.1 扫描区间和边界条件

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

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

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

假设使用idx_key1执行查询

假设使用uk_key2执行查询

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

3.2 索引用于排序

3.2.1 使用联合索引进行排序的注意事项

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

ASC、DESC混用

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

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

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

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

3.3 索引用于分组

四、回表的代价

五、更好的创建和使用索引

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

5.2 考虑索引列中不重复值的个数

5.3 索引列类型尽量小

5.4 为列前缀建立索引

5.5 覆盖索引

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

5.7 主键插入顺序

5.8 冗余和重复索引

六、总结

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