湫枫染墨

B+树索引

7/31/2022 Mysql

摘要

Mysql Version：5.7.36

# 一：前言

Q：没有索引的时，如何查找记录？

下面回答限定条件为：搜索条件对某个列精确匹配的情况。

# 1.1 在一个页中的查找

假设目前表中的记录比较少，所有的记录都可以被存放到一个页中，在查找记录的时候可以根据搜索条件的不同分为两种情况：

  1. 以主键为搜索条件

在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

  1. 以其他列作为搜索条件

在索引页中并没有对非主键列建立所谓的页目录，所以无法通过二分法快速定位相应的槽。这种情况下只能从 最小记录 开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。

# 1.2 在很多页中查找

大部分情况下我们表中存放的记录都是非常多的，需要好多的索引页来存储这些记录。在很多页中查找记录的话可以分为两个步骤：

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

在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找。因为要遍历所有的索引页，所以这种方式显然是超级耗时的。基于这些问题，于是乎就需要 索引

# 二：索引介绍

试验表：

CREATE TABLE index_demo(
    c1 INT,
    c2 INT,
    c3 CHAR(1),
    PRIMARY KEY(c1)
) ROW_FORMAT = Compact;
1
2
3
4
5
6

简化版的 index_demo 表行格式示意图：

  • record_type：记录头信息的一项属性，表示记录的类型，0表示普通记录，1表示目录项记录，2表示最小记录，3表示最大记录；
  • next_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，这里为了方便，后面图使用箭头。

# 2.1 简易索引方案

为快速定位记录所在的索引页而建立一个别的目录，建这个目录必须是，下一个索引页中用户记录的主键值必须大于上一个页中用户记录的主键值。

下面的内容，基于假设每个索引页最多能存放3条记录。

插入三条记录：

INSERT INTO index_demo VALUES
(1, 4, 'u'),
(3, 9, 'd'),
(5, 3, 'y');
1
2
3
4

这些记录按照主键值的大小串联成一个单向链表，如下：

上图3条记录都被插入到编号为10的索引页中。此时再插入一条记录：

INSERT INTO index_demo VALUES(4, 4, 'a');
1

因为页10 最多只能放3条记录，所以再分配一个新页存放，如下：

新分配的索引页编号可能并不是连续的，也就是说我们使用的这些页在存储空间里可能并不挨着。它们只是通过维护着上一个页和下一个页的编号而建立了链表关系。另外，页10 中用户记录最大的主键值是5 ，而页28 中有一条记录的主键值是4 ，因为5 > 4 ，所以这就不符合 下一个索引页中用户记录的主键值必须大于上一个页中用户记录的主键值 的要求，所以在插入主键值为4 的记录的时候需要伴随着一次记录移动，也就是把主键值为5的记录移动到页28 中，然后再把主键值为4 的记录插入到页10 中，这个过程的示意图如下：

这个过程表明了在对页中的记录进行增删改操作的过程中，必须通过一些诸如记录移动的操作来始终保证这个状态一直成立：下一个索引页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程也可以称为 页分裂。

给所有的页建立一个目录项

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

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

  1. 页的用户记录中最小的主键值，暂时用key来表示；
  2. 页号，暂时用page_no表示。

为上面几个页做好的目录，如下：

只需要把几个目录项在物理存储器上连续存储，比如把他们放到一个数组里，就可以实现 根据主键值 快速查找某条记录的功能了。比方说想找主键值为20的记录，具体查找过程分两步：

  1. 先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中(因为 12 < 20 < 209)，它对应的页是页9。
  2. 在页9中定位具体的记录。

至此，针对索引页做的简易目录即索引就搞定了。

# 2.2 InnoDB索引方案

上边之所以称为一个简易的索引方案，是因为我们为了在根据主键值进行查找时使用二分法快速定位具体的目录项而假设所有目录项都可以在物理存储器上连续存储，但是这样做有几个问题：

  1. InnoDB 是使用页来作为管理存储空间的基本单位，也就是最多能保证16KB 的连续存储空间，而随着表中记录数量的增多，需要非常大的连续的存储空间才能把所有的目录项都放下，这对记录数量非常多的表是不现实的。
  2. 我们时常会对记录进行增删，假设把页28 中的记录都删除了，页28 也就没有存在的必要了，那意味着目录项2 也就没有存在的必要了，这就需要把目录项2 后的目录项都向前移动一下，牵一发而动全身。

所以，Mysql 需要一种可以灵活管理所有目录项 的方式。这些目录项 其实长得跟我们的用户记录差不多，只不过目录项 中的两个列是主键 和页号 而已，所以复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录。最后用记录头信息里的 record_type 属性来区分 普通的用户记录 还是 目录项记录。

目录项记录 和普通的用户记录 的不同点：**

  1. 目录项记录 的record_type 值是1，而普通用户记录 的record_type 值是0；
  2. 目录项记录 只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有InnoDB 自己添加的隐藏列；
  3. 记录头信息min_rec_mask 属性，只有在存储目录项记录 的页中的主键值最小的目录项记录 的min_rec_mask 值为1，其他别的记录的min_rec_mask 值都是0 。

Q：如果目录项记录的页有多个，并且页之间在存储空间中也大可能不挨着，那么如何快速定位哪一个存储目录项记录 的页呢？

为这些存储目录项记录 的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页的示意图就是这样子：

我们生成了一个存储更高级目录项的页33，这个页中的两条记录分别代表页30和页32，如果用户记录的主键值在[1, 320)之间 ，则到页30 中查找更详细的目录项记录，如果主键值不小于320 的话，就到页32 中查找更详细的目录项记录。随着表中记录的增加，这个目录的层级会继续增加，如果简化一下，那么我们可以用下边这个图来描述它：

这其实就是一种组织数据的形式，或者说是一种数据结构，B+树*

上面所有的页称为节点。我们的实际用户记录其实都存放在B+树的最底层的节点上，这些节点也被称为叶子节点或叶节点。其余用来存放目录项的节点称为非叶子节点或者内节点。其中B+树最上边的那个节点也称为根节点。Mysql规定最下边的那层，也就是存放用户记录的那层为第0 层。

# 2.3 聚簇索引

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

  1. 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义；

    • 页内的记录是按照主键的大小顺序排成一个单向链表；
    • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表；
    • 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。

  2. B+ 树的叶子节点存储的是完整的用户记录（所谓完整的用户记录，就是指这个记录中存储了所有列的值，包括隐藏列）。

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

# 三：二级索引

上边介绍的聚簇索引只能在搜索条件是主键值时才能发挥作用，因为B+树中的数据都是按照主键进行排序的。那如果我们想以别的列作为搜索条件该办呢？难道只能从头到尾沿着链表依次遍历记录么？

不，我们可以多建几棵B+树，不同的B+树中的数据采用不同的排序规则。比方说我们用c2列的大小作为数据页、页中记录的排序规则，再建一棵B+树，效果如下图所示：

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

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

如果现在想通过c2列的值查找某些记录的话就可以使用刚刚建好的这个B+ 树了。以查找c2列的值为4的记录为例，查找过程如下：

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

上面这种按照 非主键列 建立的B+ 树需要一次回表操作才可以定位到完整的用户记录，所以这种B+ 树也被称为 二级索引(英文名secondary index)，或者 辅助索引。由于使用的是c2 列的大小作为B+ 树的排序规则，所以也称这个B+ 树为 **为c2列建立的索引 **。

# 四：聚合索引

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

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

为c2 和c3 列建立的索引的示意图如下：

以c2和c3列的大小为排序规则建立的B+树称为联合索引，本质上也是一个二级索引。它的意思与分别为c2和c3列分别建立索引的表述是不同的，不同点如下：

  1. 建立 联合索引 只会建立如上图一样的1棵B+ 树；
  2. 为c2和c3列分别建立索引会分别以c2 和c3 列的大小为排序规则建立2棵B+ 树。

# 五：InnoDB的B+树索引注意事项

前边介绍B+ 树索引时，为了理解上的方便，先把存储用户记录的叶子节点都画出来，然后接着画存储目录项记录的内节点，实际上B+ 树的形成过程是这样的：

  1. 每当为某个表创建一个B+ 树索引（聚簇索引不是人为创建的，默认就有）的时候，都会为这个索引创建一个根节点页面。最开始表中没有数据的时候，每个B+ 树索引对应的根节点 中既没有用户记录，也没有目录项记录；
  2. 随后向表中插入用户记录时，先把用户记录存储到这个根节点中；
  3. 当根节点 中的可用空间用完时继续插入记录，此时会将根节点 中的所有记录复制到一个新分配的页，比如页a 中，然后对这个新页进行页分裂 的操作，得到另一个新页，比如页b 。这时新插入的记录根据键值（也就是聚簇索引中的主键值，二级索引中对应的索引列的值）的大小就会被分配到页a 或者页b 中，而根节点 便升级为存储目录项记录的页。

一个B+树索引的根节点自诞生之日起，便不会再移动。

这样只要对某个表建立一个索引，那么它的根节点 的页号便会被记录到某个地方，然后凡是InnoDB 存储引擎需要用到这个索引的时候，都会从那个固定的地方取出根节点 的页号，从而来访问这个索引。

上面说到B+ 树索引的内节点中目录项记录的内容是 索引列 +页号 的搭配，但是这个搭配对于二级索引来说有点儿不严谨。以index_demo 表为例，假设这个表中的数据为：

c1 c2 c3
1 1 'u'
3 1 'd'
5 1 'y'
7 1 'a'

如果二级索引中目录项记录的内容只是 索引列 + 页号 的搭配的话，那么为c2 列建立索引后的B+ 树应该长这样：

如果新插入一行记录，其中 c1、c2 、c3 的值分别是：9、1、'c'，那么在修改这个为c2 列建立的二级索引对应的B+ 树时便碰到了个大问题：由于页3 中存储的目录项记录是由c2列 + 页号 的值构成的，页3 中的两条目录项记录对应的c2 列的值都是1，而新插入的这条记录的c2 列的值也是1，那这条新插入的记录到底应该放到页4 中，还是应该放到页5 呢？

为了让新插入记录能找到自己在那个页里，需要保证在B+树的同一层内节点的目录项记录除页号 这个字段以外是唯一的。所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的：

  • 索引列的值；
  • 主键值；
  • 页号。

所以为c2 列建立二级索引后的示意图实际上应该是这样子的：

这样再插入记录(9, 1, 'c')时，由于页3 中存储的目录项记录是由c2列 + 主键 + 页号 的值构成的，可以先把新记录的c2 列的值和页3 中各目录项记录的c2 列的值作比较，如果c2 列的值相同的话，可以接着比较主键值，因为B+ 树同一层中不同目录项记录的c2列 + 主键 的值肯定是不一样的，所以最后肯定能定位唯一的一条目录项记录，在本例中最后确定新记录应该被插入到页5 中。

一个页面最少存储2条记录

B+树本质上就是一个大的多层级目录，每经过一个目录时都会过滤掉许多无效的子目录，直到最后访问到存储真实数据的目录。那如果一个大的目录中只存放一个子目录是个啥效果呢？那就是目录层级非常非常非常多，而且最后的那个存放真实数据的目录中只能存放一条记录。费了半天劲只能存放一条真实的用户记录？所以InnoDB 的一个数据页至少可以存放两条记录。

# 六：MyISAM中的索引方案简单介绍

InnoDB 中 索引即数据，也就是聚簇索引的那棵B+ 树的叶子节点中已经把所有完整的用户记录都包含了，而MyISAM 的索引方案虽然也使用树形结构，但是却将索引和数据分开存储：

  1. 将表中的记录按照记录的插入顺序单独存储在一个文件中，称之为数据文件。这个文件并不划分为若干个数据页，有多少记录就往这个文件中塞多少记录就成了。可以通过行号而快速访问到一条记录。

  2. MyISAM 记录也需要记录头信息来存储一些额外数据，以index_demo 表为例使用MyISAM作为存储引擎在存储空间中的表示：

由于在插入数据的时候并没有刻意按照主键大小排序，所以并不能在这些数据上使用二分法进行查找。

  1. 使用MyISAM 存储引擎的表会把索引信息另外存储到一个称为索引文件 的文件中。MyISAM 会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是 主键值 + 行号 的组合。也就是先通过索引找到对应的行号，再通过行号去找对应的记录！（这一点和InnoDB 是完全不相同的，在InnoDB 存储引擎中，我们只需要根据主键值对聚簇索引 进行一次查找就能找到对应的记录，而在MyISAM 中却需要进行一次 回表 操作，意味着 MyISAM 中建立的索引相当于全部都是二级索引！）

  2. 也可以对其它的列分别建立索引或者建立联合索引，原理和InnoDB中的索引差不多，不过在叶子节点处存储的是相应的 列 + 行号。这些索引也全部都是 二级索引。

MyISAM的行格式有定长记录格式(Static)、变长记录格式(Dynamic)、压缩记录格式(Compressed)。上边举例的index_demo表采用定长记录格式，也就是一条记录占用存储空间的大小是固定的，这样就可以轻松算出某条记录在数据文件中的地址偏移量。但是变长记录格式就不行了，MyISAM会直接在索引叶子节点处存储该条记录在数据文件中的地址偏移量。通过这个可以看出，MyISAM的回表操作是十分快速的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通过获取主键之后再去聚簇索引里边儿找记录，虽然说也不慢，但还是比不上直接用地址去访问。

# 七：B+树索引的使用

# 7.1 索引的代价

  1. 空间上的代价

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

  1. 时间上的代价

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

所以说，一个表上索引建的越多，就会占用越多的存储空间，在增删改记录的时候性能就越差。

# 7.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)
);
1
2
3
4
5
6
7
8
9

索引 idx_name_birthday_phone_number 的示意图（省略一些不必要的部分，比如记录的额外信息，各页面的页号等等，其中内节点中目录项记录的页号信息用箭头来代替，在记录结构中只保留name 、birthday 、phone_number 、id 这四个列的真实数据值）

从图中可以看出，这个该索引对应的B+ 树中页面和记录的排序方式就是这样的：

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

这个排序方式十分重要，因为只要页面和记录是排好序的，才可以通过二分法来快速定位查找。

# 7.3 全值匹配

如果搜索条件中的列和索引列一致的话，这种情况就称为全值匹配，比方下面这句：

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

建立的idx_name_birthday_phone_number 索引包含的3个列在这个查询语句中都展现出来了。查询过程如下：

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

Q：WHERE 子句中的几个搜索条件的顺序对查询结果有啥影响么？

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

# 7.4 匹配左边的列

搜索语句中也可以不用包含全部联合索引中的列，只包含左边的就行，比方说：

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

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

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

下面这一语句就用不到B+数索引

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

因为B+ 树的数据页和记录先是按照name 列的值排序的，在name 列的值相同的情况下才使用birthday 列进行排序，也就是说name 列的值不同的记录中birthday 的值可能是无序的。而现在跳过name 列直接根据birthday 的值去查找，是做不到的。那如果就想在只使用birthday 的值去通过B+ 树索引进行查找咋办呢？只能对birthday 列额外建一个B+ 树索引。

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

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

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

# 7.5 匹配列前缀

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

Aaron
Aaron
...
Aaron
Asa
Ashburn
...
Ashburn
Baird
Barlow
...
Barlow
1
2
3
4
5
6
7
8
9
10
11
12

字符串排序的本质就是比较哪个字符串大一点儿，哪个字符串小一点，比较字符串大小就用到了该列的字符集和比较规则，具体可以查看 字符集和比较规则

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

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

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

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

MySQL 就无法快速定位记录位置了，因为字符串中间有'As' 的字符串并没有排好序，所以只能全表扫描了。

# 7.6 匹配范围值

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

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

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

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

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

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

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

  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.7 精确匹配某一列并范围匹配另外一列

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

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

这个查询的条件可以分为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+ 树索引了，只能遍历上一步查询得到的记录。

# 7.8 用于排序

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

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

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

使用联合索引进行排序注意事项：对于联合索引有个问题需要注意，ORDER BY的子句后边的列的顺序也必须按照索引列的顺序给出。同理，ORDER BY name、ORDER BY name, birthday 这种匹配索引左边的列的形式可以使用部分的B+ 树索引。当联合索引左边列的值为常量，也可以使用后边的列进行排序，比如

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

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

  1. ASC、DESC混用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

# 7.9 用于分组

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

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

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

  1. 先把记录按照name 值进行分组，所有name 值相同的记录划分为一组；

  2. 将每个name 值相同的分组里的记录再按照birthday 的值进行分组，将birthday 值相同的记录放到一个小分组里，所以看起来就像在一个大分组里又化分了好多小分组；

  3. 再将上一步中产生的小分组按照phone_number 的值分成更小的分组，所以整体上看起来就像是先把记录分成一个大分组，然后把大分组 分成若干个小分组 ，然后把若干个小分组 再细分成更多的小小分组 。

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

# 八：回表的代价

查询：

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

在使用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 的查询有这么两个特点：

  1. 会使用到两个B+ 树索引，一个二级索引，一个聚簇索引；

  2. 访问二级索引使用顺序I/O，访问聚簇索引使用随机I/O。

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

Q：什么时候使用全表扫描的方式，什么时候使用采用二级索引 + 回表 的方式去执行查询呢？

这就是查询优化器做的工作，查询优化器会事先对表中的记录计算一些统计数据，然后再利用这些统计数据根据查询的条件来计算一下需要回表的记录数，需要回表的记录数越多，就越倾向于使用全表扫描，反之倾向于使用二级索引 + 回表 的方式。当然优化器做的分析工作不仅仅是这么简单，但是大致上是个这个过程。一般情况下，限制查询获取较少的记录数会让优化器更倾向于选择使用二级索引 + 回表 的方式进行查询，因为回表的记录越少，性能提升就越高，比方说上边的查询可以改写成这样：

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

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

对于有排序需求的查询，上边讨论的采用全表扫描 还是二级索引 + 回表 的方式进行查询的条件也是成立的，比方说下边这个查询：

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

由于查询列表是*，所以如果使用二级索引进行排序的话，需要把排序完的二级索引记录全部进行回表操作，这样操作的成本还不如直接遍历聚簇索引然后再进行文件排序（filesort ）低，所以优化器会倾向于使用全表扫描 的方式执行查询。

# 九：覆盖索引

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

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

因为只查询name , birthday , phone_number 这三个索引列的值，所以在通过索引得到结果后就不必到聚簇索引 中再查找记录的剩余列，这样就省去了回表 操作带来的性能损耗。这种只需要用到索引的查询方式称为 覆盖索引。排序操作也优先使用覆盖索引 的方式进行查询，比方说这个查询：

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

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

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

# 十：如何挑选索引

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

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

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

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

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

# 10.2 考虑列的基数

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

# 10.3 索引列的类型尽量小

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

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

索引字符串值的前缀

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

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

MySQL只对字符串的前几个字符进行索引，也就是说在二级索引的记录中只保留字符串前几个字符。这样在查找记录时虽然不能精确的定位到记录的位置，但是能定位到相应前缀所在的位置，然后根据前缀相同的记录的主键值回表查询完整的字符串值，再对比就好了。这样只在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)
);
1
2
3
4
5
6
7

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

索引列前缀对排序的影响

如果使用了索引列前缀，比方说前边只把name 列的前10个字符放到了二级索引中，下边这个查询可能就有点儿尴尬了：

SELECT * FROM person_info ORDER BY name LIMIT 10;
1

因为二级索引中不包含完整的name 列信息，所以无法对前十个字符相同，后边的字符不同的记录进行排序，也就是使用索引列前缀的方式无法支持使用索引排序，只能用文件排序。

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

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

	WHERE my_col * 2 < 4

	WHERE my_col < 4/2
1
2
3

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

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

主键插入顺序

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

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

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

冗余和重复索引

就对同一个列创建了多个索引，比方说这样写建表语句：

CREATE TABLE person_info(
    id INT UNSIGNED 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(10), birthday, phone_number),
    KEY idx_name (name(10))
);
1
2
3
4
5
6
7
8
9
10

通过idx_name_birthday_phone_number 索引就可以对name 列进行快速搜索，再创建一个专门针对name 列的索引就算是一个 冗余索引，维护这个索引只会增加维护的成本，并不会对搜索有什么好处。

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

CREATE TABLE repeat_index_demo (
    c1 INT PRIMARY KEY,
    c2 INT,
    UNIQUE uidx_c1 (c1),
    INDEX idx_c1 (c1)
);
1
2
3
4
5
6

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

# 十一：参考文献

  • 《MySQL 是怎样运行的 - 小孩子4919》
最后更新: 10/22/2022, 10:41:05 AM

事务