【MySQL是怎样运行的-读书笔记】第7章好东西也得先学会怎么用-B+树索引的使用

一时失言乱红尘 2024-04-03 14:15 22阅读 0赞

## 1. 索引的代价 ##

索引在空间和时间上都会拖后腿：

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

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

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

*  表中的主键是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 的示意图：

![image-20221018141018758][]

再次强调一下，内节点中存储的是目录项记录，叶子节点中存储的是用户记录（由于不是聚簇索引，所以用户记录是不完整的，缺少country 列的值）。从图中可以看出，这个idx\_name\_birthday\_phone\_number 索引对应的B+ 树中页面和记录的排序方式就是这样的：

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

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

### 2.1 全值匹配 ###

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

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 这几个搜索列的顺序对查询的执行过程有影响么？**

答案是：没影响。MySQL 中的**查询优化器**，会分析这些搜索条件并且按照可以使用的索引中列的顺序来决定先使用哪个搜索条件，后使用哪个搜索条件。

### 2.2 匹配左边的列 ###

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

### 2.3 匹配列前缀 ###

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

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

### 2.4 匹配范围值 ###

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

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

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

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

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

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+ 树索引的。

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

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

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+ 树索引了，只能遍历上一步查询得到的记录。

### 2.6 用于排序 ###

我们在写查询语句的时候经常需要对查询出来的记录通过`ORDER BY` 子句按照某种规则进行排序。一般情况下，我们只能把记录都加载到内存中，再用一些排序算法，比如快速排序、归并排序等等在内存中对这些记录进行排序，有的时候**可能查询的结果集太大以至于不能在内存中进行排序的话，还可能暂时借助磁盘的空间来存放中间结果**，排序操作完成后再把排好序的结果集返回到客户端。在MySQL 中，把这种**在内存中或者磁盘上进行排序的方式统称为文件排序**（英文名： `filesort`），跟文件这个词儿一沾边儿，就显得这些排序操作非常慢了。但是如果`ORDER BY`子句里使用到了我们的索引列，就有可能省去在内存或文件中排序的步骤，比如下边这个简单的查询语句：

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

这个查询的结果集需要先按照name 值排序，如果记录的name 值相同，则需要按照birthday 来排序，如果birthday 的值相同，则需要按照phone\_number 排序。大家可以回过头去看我们建立的  
`idx_name_birthday_phone_number` 索引的示意图，因为这个B+ 树索引本身就是按照上述规则排好序的，所以直接从索引中提取数据，然后进行回表操作取出该索引中不包含的列就好了。

#### 2.6.1 使用联合索引进行排序注意事项 ####

对于联合索引有个问题需要注意， `ORDER BY` 的子句后边的**列的顺序也必须按照索引列的顺序给出**，如果给出ORDER BY phone\_number, birthday, name 的顺序，那也是用不了B+ 树索引，这种颠倒顺序就不能使用索引的。

当联合索引左边列的值为常量，也可以使用后边的列进行排序，比如这样：

SELECT * FROM person_info WHERE name = 'A' ORDER BY birthday, phone_number LIMIT 10;

这个查询能使用联合索引进行排序是因为name 列的值相同的记录是按照birthday , phone\_number 排序的。

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

ASC、DESC混用

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

小贴士：

ORDER BY子句后的列如果不加ASC或者DESC默**认是按照ASC排序规则排序的，也就是升序排序的。**

如果查询中的各个排序列的排序顺序是一致的，比方说下边这两种情况：

*      ORDER BY name, birthday LIMIT 10
    
    这种情况直接从索引的最左边开始往右读10行记录就可以了。
 *      ORDER BY name DESC, birthday DESC LIMIT 10 ，
    
    这种情况直接从索引的最右边开始往左读10行记录就可以了。

但是如果我们查询的需求是先按照name 列进行升序排列，再按照birthday 列进行降序排列的话，比如说这样的查询语句：

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

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

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

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

WHERE子句中出现非排序使用到的索引列

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

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

这个查询只能先把符合搜索条件`country = 'China'`的记录提取出来后再进行排序，是使用不到索引。注意和下边这个查询作区别：

SELECT * FROM person_info WHERE name = 'A' ORDER BY birthday, phone_number LIMIT 10;

虽然这个查询也有搜索条件，但是name = ‘A’ 可以使用到索引idx\_name\_birthday\_phone\_number ，而且过滤剩下的记录还是按照birthday 、phone\_number 列排序的，所以还是可以使用索引进行排序的。

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

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

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

排序列使用了复杂的表达式

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

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

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

### 2.7 用于分组 ###

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

SELECT name, birthday, phone_number, COUNT(*) FROM person_info GROUP BY name, birthday, phone_number

这个查询语句相当于做了3次分组操作：

1.  先把记录按照`name` 值进行分组，所有`name` 值相同的记录划分为一组。
2.  将每个`name` 值相同的分组里的记录再按照`birthday` 的值进行分组，将`birthday` 值相同的记录放到一个**小分组**里，所以看起来就像在一个**大分组**里又化分了好多**小分组**。
3.  再将上一步中产生的小分组按照`phone_number` 的值分成更小的分组，所以整体上看起来就像是先把记录分成一个**大分组**，然后把大分组分成若干个**小分组**，然后把若干个小分组再细分成更多的**小小分组**。

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

## 3. 回表的代价 ##

以idx\_name\_birthday\_phone\_number 索引为例，看下边这个查询：

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

在使用idx\_name\_birthday\_phone\_number 索引进行查询时大致可以分为这两个步骤：

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

由于索引idx\_name\_birthday\_phone\_number 对应的B+ 树中的记录首先会按照name 列的值进行排序，所以值在Asa ～ Barlow 之间的记录在磁盘中的存储是相连的，集中分布在一个或几个数据页中，我们可以很快的把这些连着的记录从磁盘中读出来，这种读取方式我们也可以称为**顺序I/O** 。根据第1步中获取到的记录的id 字段的值可能并不相连，而在**聚簇索引中记录是根据id （也就是主键）的顺序排列的**，所以根据这些并不连续的id值到聚簇索引中访问完整的用户记录可能分布在不同的数据页中，这样读取完整的用户记录可能要访问更多的数据页，这种读取方式我们也可以称为**随机I/O** 。一般情况下，顺序I/O比随机I/O的性能高很多，所以步骤1的执行可能很快，而步骤2就慢一些。所以这个使用索引idx\_name\_birthday\_phone\_number 的查询有这么两个特点：

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

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

那什么时候采用全表扫描的方式，什么时候使用采用**二级索引 + 回表**的方式去执行查询呢？这个就是传说中的**查询优化器**做的工作，查询优化器会事先对表中的记录计算一些统计数据，然后再利用这些统计数据根据查询的条件来计算一下需要回表的记录数，需要回表的记录数越多，就越倾向于使用全表扫描，，反之倾向于使用**二级索引 + 回表**的方式。

### 3.1 覆盖索引 ###

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

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

把这种只需要用到索引的查询方式称为**索引覆盖**。排序操作也优先使用覆盖索引的方式进行查询，比方说这个查询：

SELECT name, birthday, phone_number FROM person_info ORDER BY name, birthday, phone_number;

虽然这个查询中没有LIMIT 子句，但是采用了覆盖索引，所以查询优化器就会直接使用  
idx\_name\_birthday\_phone\_number 索引进行排序而不需要回表操作了。

当然，如果业务需要查询出索引以外的列，那还是以保证业务需求为重。

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

## 4. 如何挑选索引 ##

我们在建立索引时或者编写查询语句时就应该注意的一些事项。

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

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

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

像查询列表中的birthday 、country 这两个列就不需要建立索引，我们只需要为出现在WHERE 子句中的name列创建索引就可以了。

### 4.2 考虑列的基数 ###

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

### 4.3 索引列的类型尽量小 ###

我们在定义表结构的时候要显式的指定列的类型，以整数类型为例，有TINYINT 、MEDIUMINT 、INT 、BIGINT这么几种，它们占用的存储空间依次递增，我们这里所说的**类型大小**指的就是该类型表示的数据范围的大小。

能表示的整数范围当然也是依次递增，如果我们想要对某个整数列建立索引的话，在表示的整数范围允许的情况下，尽量让索引列使用较小的类型，比如我们能使用INT 就不要使用BIGINT ，能使用MEDIUMINT 就不要使用INT ～ 这是因为：

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

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

### 4.4 索引字符串值的前缀 ###

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

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

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

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

name(10) 就表示在建立的B+ 树索引中只保留记录的前10 个字符的编码，这种只索引字符串值的前缀的策略是我们非常鼓励的，尤其是在字符串类型能存储的字符比较多的时候。

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

假设表中有一个整数列my\_col ，我们为这个列建立了索引。下边的两个WHERE 子句虽然语义是一致的，但是在效率上却有差别：

1.      WHERE my_col * 2 < 4
2.      WHERE my_col < 4/2

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

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

### 4.6 主键插入顺序 ###

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

![image-20221018153124756][]

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

![image-20221018153138029][]

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

### 4.6 冗余和重复索引 ###

储的主键值在1~100 之间：

\[外链图片转存中…(img-lllEnAPe-1666078525948)\]

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

\[外链图片转存中…(img-fBmIBHh0-1666078525949)\]

### 4.6 冗余和重复索引 ###

要避免定义重复的索引。

[image-20221018141018758]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/d0d0beea26ce417a86bf3aa40db15d82.png
[image-20221018153124756]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/07d46b8300e14933a09b7760c8bc4d26.png
[image-20221018153138029]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f97190e74b254286b2027b7ac10abef0.png