第07章-B+树索引的使用

我们必须熟悉下面这些结论：

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

索引的代价 #

使用索引的代价：

空间上的代价一颗很大的B+树由许多数据页组成，这将占用很大的一片存储空间。
时间上的代价每当对表中的数据进行增删改操作时，都需要修改各个B+树索引。

应用B+树索引 #

扫描区间和边界条件 #

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

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

我们把待扫描记录所在的区间成为扫描区间，把形成这个扫描区间的搜索条件称为形成这个扫描区间的边界条件。

我们把只包含一个值的扫描区间成为单点扫描区间，把包含多个值的扫描区间成为范围扫描区间。

对于每个扫描区间来说，仅需要通过B+树定位到该扫描区间中的第一条记录，然后就可以沿着记录所在的单向链表向后扫描，直到某条记录不符合形成该扫描区间的边界条件为止。

有以下几点需要注意：

IN操作符的语义与若干个等值匹配操作符（=）之间用OR连接起来的语义是一样的，都会产生多个单点扫描区间。
!=产生的扫描区间是两个范围扫描区间的并集：如，对于索引列key1来说，key1!=1产生的扫描区间是(-∞,1)和(1,+∞)的并集。
对于LIKE操作符，只有在匹配完整的字符串或者匹配字符串前缀时才产生合适的扫描区间。

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

所有搜索条件都可以生成合适的扫描区间的情况。
有的搜索条件不能生成合适的扫描区间的情况。
大体意思：
1. 将用不到的条件替换为true。
2. 对语句进行简化。
```
这是查询优化器的工作。
```
从复杂的搜索条件中找出扫描区间。
使用联合索引执行查询时对应的扫描区间。联合所有的排序规则如下：
- 先按照第一列的值进行排序；
- 在第一列的值相同的情况下，按照第二列的值进行排序；
- 依次类推。

索引用于排序 #

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

ORDER BY 子句后面的列的顺序必须按照索引列的顺序给出。

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

ASC、DESC混用。使用联合索引进行排序时，我们要求各个排序列的排序规则是一致的。找某条记录的上一条记录要比找下一跳记录更复杂一些。

这点在MySQL8中有所改变。MySQL8中引入了descending index，可以让索引列的排序规则与ORDER BY子句中的排序规则不一致。
例如，我们在某张表的c、d两列上建立了联合索引，索引列的排序规则是c ASC, d DESC：
alter table t3_des
add index `idx_cd` (c asc,d desc);
那么，我们可以使用该索引来执行如下查询：
select * from t3_des order by c asc, d asc limit 0,10;
反而用不到索引，我们来看explain的结果：
但是，如果我们执行如下查询：
select * from t3_des order by c asc, d desc limit 0,10;
反而可以使用到索引：

排序列包含非同一个索引的列。
排序列是某个联合索引的索引列，但是这些排序列在联合索引中并不连续。
用来形成扫描区间的索引列与排序列不同。
排序列不是以单独列名的形式出现在ORDER BY 子句中。

索引用于分组 #

分组列的顺序也需要与索引列的顺序一致。也可以只使用索引列中左边连续的列进行分组。

回表的代价 #

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

需要执行回表操作的记录越多，使用二级索引进行查询的性能也就越低。

更好地创建和使用索引 #

注意事项如下：

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

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

不重复值的个数占全部记录条数的比例太低，说明该列包含过多重复值，那么在通过二级索引+回表的方式执行查询时，就有可能执行太多次回表操作。

有些资料中，也叫这种情况为“基数过低”或”区分度过低“。

索引列的类型尽量小 #

数据类型越小，索引占用的存储空间就越少，在一个数据页内就可以存放更多的记录，磁盘I/O带来的性能损耗也就越小（依次页面I/O可以将更多的记录加载到内存中），读写效率也就更高。

为列前缀建立索引 #

覆盖索引 #

查询列表中只包含索引列，可以避免回表操作带来的性能损耗。

如果查询列表是*，或者一定要包含非索引列，只要索引中包含所有条件列和排序列，也可以先试用索引查询到主键id，然后再根据id值到聚簇索引中查询到完整的用户记录。这一点，本书的坐在在相关的掘金小册中也有提到。