重拾MySQL —— B+树索引

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

一、没有索引时的进行查找

没有索引的时候是如何查找记录的？以精确匹配来举例：

SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;

1.1 在一个页中查找

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

• 以主键为搜索条件：在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
• 以其他列作为搜索条件：由于没有建立所谓的页目录，这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。查找效率低下。

1.2 在很多页中查找

大部分情况下表中的记录是非常多的，需要很多数据页来存储这些记录。在很多页中查找记录分为两个步骤：

• 定位到记录所在的页
• 从所在的页内查找相应的记录

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

怎么解决？

使用索引。

二、索引

示例表：

mysql> CREATE TABLE index_demo(
    ->     c1 INT,
    ->     c2 INT,
    ->     c3 CHAR(1),
    ->     PRIMARY KEY(c1)
    -> ) ROW_FORMAT = Compact;
Query OK, 0 rows affected (0.03 sec)

index_demo表在行格式简化示意图：

• record_type：记录头信息的一项属性，表示记录的类型，0表示普通记录、2表示最小记录、3表示最大记录、1先按下不表。
• next_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，为了方便理解，下文中箭头来指向下一条记录。
• 各个列的值：这里只记录在index_demo表中的三个列，分别是c1、c2和c3。
• 其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

为了简化，做几点调整：

• 其他信息部分省略
• 行格式图竖着展示

把一些记录存放在页中：

2.1 一个简单的索引方案

问题1：为什么在根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？

因为各个页中的记录并没有规律，我们并不知道搜索条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。

问题2：如何解决？

为快速定位记录所在的数据页而建立一个别的目录。完成的事情：

1）下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。

此处做一个假设：假设每个数据页最多能存放3条记录（实际上一个数据页非常大，可以存放下好多记录）。有了这个假设之后向index_demo表插入3条记录：

mysql> INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
Query OK, 3 rows affected (0.01 sec)
Records: 3  Duplicates: 0  Warnings: 0

那么这些记录已经按照主键值的大小串联成一个单向链表：

从图中可以看出来，index_demo表中的3条记录都被插入到了编号为10的数据页中了。接着插入一条记录：

mysql> INSERT INTO index_demo VALUES(4, 4, 'a');
Query OK, 1 row affected (0.00 sec)

因为页10最多只能放3条记录，所以需要分配一个新页：

新分配的数据页编号可能并不是连续的，它们只是通过维护着上一个页和下一个页的编号建立了链表关系。

那么新插入的记录是放到新分配的页面（假设页号是28）中吗？

如果是这样，那么页10中用户记录最大的主键值是5，而页28中有一条记录的主键值是4，因为5 > 4，所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求。

所以在插入主键值为4的记录的时候需要伴随着一次记录移动，也就是把主键值为5的记录移动到页28中，然后再把主键值为4的记录插入到页10中，这个过程的示意图：

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

这个过程就是页分裂。

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

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

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

• 页的用户记录中最小的主键值，我们用key来表示。
• 页号，我们用page_no表示。

以页28为例，它对应目录项2，这个目录项中包含着该页的页号28以及该页中用户记录的最小主键值5。此时只需要把几个目录项在物理存储器上连续存储，比如把他们放到一个数组里，就可以实现根据主键值快速查找某条记录的功能了。

比方说想找主键值为20的记录，具体查找过程分两步：

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

这个目录就是索引。

2.2 InnoDB中的索引方案

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

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

因此InnoDB采用了一种可以灵活管理所有目录项的方式。仔细观察可以发现，这些目录项其实跟用户记录差不多，只不过目录项中的两个列是主键和页号而已，所以InnoDB复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，把这些用来表示目录项的记录称为目录项记录。

那InnoDB怎么区分一条记录是普通的用户记录还是目录项记录呢？就是通过记录头信息里的record_type属性，它的各个取值代表的意思如下：

• 0：普通的用户记录
• 1：目录项记录
• 2：最小记录
• 3：最大记录

从图中可以看出来，我们新分配了一个编号为30的页来专门存储目录项记录。

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

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

除了上述几点外，这两者就没什么差别了，它们用的是一样的数据页，从而在按照主键值进行查找时可以使用二分法来加快查询速度。

现在以查找主键为20的记录为例，根据某个主键值去查找记录的步骤就可以大致拆分成下面两步：

1. 先到存储目录项记录的页，也就是页30中通过二分法快速定位到对应目录项，因为12 < 20 < 209，所以定位到对应的记录所在的页就是页9。
2. 再到存储用户记录的页9中根据二分法快速定位到主键值为20的用户记录。

问题：虽然说目录项记录中只存储主键值和对应的页号，比用户记录需要的存储空间小多了，但是一个页只有16KB大小，能存放的目录项记录也是有限的，那如果表中的数据太多，以至于一个数据页不足以存放所有的目录项记录，如何解决？

再新增一个存储目录项记录的页。

此处假设一个存储目录项记录的页最多只能存放4条目录项记录，所以如果此时再向上图中插入一条主键值为320的用户记录的话，那就需要分配一个新的存储目录项记录的页：

从图中可以看出，在插入了一条主键值为320的用户记录之后需要两个新的数据页：

• 为存储该用户记录而新生成了页31。
• 因为原先存储目录项记录的页30的容量已满（我们前面假设只能存储4条目录项记录），所以不得不需要一个新的页32来存放页31对应的目录项。

现在因为存储目录项记录的页不止一个，所以如果再想根据主键值查找一条用户记录大致需要3个步骤，以查找主键值为20的记录为例：

1. 确定目录项记录页：现在的存储目录项记录的页有两个，即页30和页32，又因为页30表示的目录项的主键值的范围是[1, 320)，页32表示的目录项的主键值不小于320，所以主键值为20的记录对应的目录项记录在页30中。
2. 通过目录项记录页确定用户记录真实所在的页。
3. 在真实存储用户记录的页中定位到具体的记录。

又有新问题了：在这个查询步骤的第1步中需要定位存储目录项记录的页，但是这些页在存储空间中也可能不挨着，如果表中的数据非常多则会产生很多存储目录项记录的页，那怎么根据主键值快速定位一个存储目录项记录的页呢？

很好解决，为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据。

从图中可以看出，又生成了一个存储更高级目录项的页33，这个页中的两条记录分别代表页30和页32，如果用户记录的主键值在[1, 320)之间，则到页30中查找更详细的目录项记录，如果主键值不小于320的话，就到页32中查找更详细的目录项记录。

随着表中记录的增加，这个目录层级会不断增加，简化一下：

这便是一种组织数据的形式，或者说是一种数据结构，它的名称是B+树。

不论是存放用户记录的数据页，还是存放目录项记录的数据页，InnoDB都把它们存放到B+树这个数据结构中了，所以也称这些数据页为节点。从图中可以看出来，实际用户记录其实都存放在B+树的最底层的节点上，这些节点也被称为叶子节点或叶节点，其余用来存放目录项的节点称为非叶子节点或者内节点，其中B+树最上面的那个节点也称为根节点。

从图中可以看出来，一个B+树的节点其实可以分成好多层，InnoDB规定最下面的那层，也就是存放用户记录的那层为第0层，之后依次往上加。在真实环境中一个页存放的记录数量是非常大的，假设所有存放用户记录的叶子节点代表的数据页可以存放100条用户记录，所有存放目录项记录的内节点代表的数据页可以存放1000条目录项记录，那么：

• 如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放100条记录。
• 如果B+树有2层，最多能存放1000×100=100000条记录。
• 如果B+树有3层，最多能存放1000×1000×100=100000000条记录。
• 如果B+树有4层，最多能存放1000×1000×1000×100=100000000000条记录。

可以看到，4层的B+树就可以存放100000000000条数据了。所以一般情况下，B+树都不会超过4层，那我们通过主键值去查找某条记录最多只需要做4个页面内的查找（查找3个目录项页和一个用户记录页），又因为在每个页面内有所谓的Page Directory（页目录），所以在页面内也可以通过二分法实现快速定位记录，大大提高数据的查询效率。

2.2.1 聚簇索引

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

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

具有这两种特性的B+树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在MySQL语句中显式的使用INDEX语句去创建，InnoDB存储引擎会自动的为我们创建聚簇索引。

此外，在InnoDB存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引。

2.2.2 二级索引

聚簇索引只能在搜索条件是主键值时才能发挥作用，因为B+树中的数据都是按照主键进行排序的。

那么如果想要根据其他的列所谓搜索条件该怎么办？可以多建几棵B+树，不同的B+树中的数据采用不同的排序规则。

比如：使用c2列的大小作为数据页、页中记录的排序规则，建立一棵新的B+树，

这棵B+树与聚簇索引有几处不同：

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

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

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

根据这个以c2列大小排序的B+树只能确定要查找记录的主键值，所以如果想根据c2列的值查找到完整的用户记录的话，仍然需要到聚簇索引中再查一遍，这个过程也被称为回表。也就是根据c2列的值查询一条完整的用户记录需要使用到2棵B+树。

为什么还需要一次回表操作呢？直接把完整的用户记录放到叶子节点不就好了么？

如果把完整的用户记录放到叶子节点是可以不用回表，但是占用空间过多了。相当于每建立一棵B+树都需要把所有的用户记录再都拷贝一遍，这就有点太浪费存储空间了。因为这种按照非主键列建立的B+树需要一次回表操作才可以定位到完整的用户记录，所以这种B+树也被称为二级索引（英文名secondary index），或者辅助索引。

除了可以给数据类型为数字的列建立索引，也可以给存储字符串的列建立索引，因为存在字符集和比较规则，字符串也是可以表大小的。

2.2.3 联合索引

我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引。

比如想让B+树按照c2和c3列的大小进行排序，这个包含两层含义：

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

=> c3列全局无序，局部有序。

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

如图所示，需要注意以下几点：

• 每条目录项记录都由c2、c3、页号这三个部分组成，各条记录先按照c2列的值进行排序，如果记录的c2列相同，则按照c3列的值进行排序。
• B+树叶子节点处的用户记录由c2、c3和主键c1列组成。

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

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

2.3 InnoDB中B+树索引的注意事项

2.3.1 根页面万年不动窝

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

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

这个过程需要特别注意的是：一个B+树索引的根节点自诞生之日起，便不会再移动。这样只要对某个表建立一个索引，那么它的根节点的页号便会被记录到某个地方，然后凡是InnoDB存储引擎需要用到这个索引的时候，都会从那个固定的地方取出根节点的页号，从而来访问这个索引。

2.3.2 内节点中目录项的唯一性

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+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的：

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

也就是把主键值也添加到二级索引内节点中的目录项记录了，这样就能保证B+树每一层节点中各条目录项记录除页号这个字段外是唯一的，所以为c2列建立二级索引后的示意图实际上应该是这样子的：

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

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

前面说过一个B+树只需要很少的层级就可以轻松存储数亿条记录，查询效率非常高。这是因为B+树本质上就是一个大的多层级目录，每经过一个目录时都会过滤掉许多无效的子目录，直到最后访问到存储真实数据的目录。

那如果一个大的目录中只存放一个子目录是什么效果呢？那就是目录层级非常非常非常多，而且最后的那个存放真实数据的目录中只能存放一条记录。这就导致了消耗了很多的代价查询的数据量很少，所以InnoDB的一个数据页至少可以存放两条记录，这也是记录行格式的一个结论。

其实，让B+树的叶子节点只存储一条记录，让内节点存储多条记录，也还是可以发挥B+树作用的。

但是，设计者还是为了避免B+树的层级增长得过高，要求所有数据页都至少能够容纳2条记录。

2.4 MyISAM中的索引方案简介

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

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

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

  

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

• 使用MyISAM存储引擎的表会把索引信息另外存储到一个称为索引文件的另一个文件中。MyISAM会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是主键值 + 行号的组合。也就是先通过索引找到对应的行号，再通过行号去找对应的记录。

  这一点和InnoDB是完全不相同的，在InnoDB存储引擎中，我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在MyISAM中却需要进行一次回表操作，意味着MyISAM中建立的索引相当于全部都是二级索引。

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

MyISAM的行格式有定长记录格式（Static）、变长记录格式（Dynamic）、压缩记录格式（Compressed）。上面用到的index_demo表采用定长记录格式，也就是一条记录占用存储空间的大小是固定的，这样就可以轻松算出某条记录在数据文件中的地址偏移量。但是变长记录格式就不行了，MyISAM会直接在索引叶子节点处存储该条记录在数据文件中的地址偏移量。

通过这个可以看出，MyISAM的回表操作是十分快速的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通过获取主键之后再去聚簇索引里边儿找记录，虽然说也不慢，但还是比不上直接用地址去访问。

=> InnoDB中的索引即数据，数据即索引，而MyISAM中却是索引是索引、数据是数据。

2.5 MySQL中创建和删除索引的语句

InnoDB和MyISAM会自动为主键或者声明为UNIQUE的列去自动建立B+树索引，但是如果我们想为其他的列建立索引就需要我们显式的去指明。

问题：为什么不自动为每个列都建立个索引呢？

每建立一个索引都会建立一棵B+树，每插入一条记录都要维护各个记录、数据页的排序关系，这是很费性能和存储空间的。

在创建表的时候指定需要建立索引的单个列或者建立联合索引的多个列：

CREATE TALBE 表名 (
    各种列的信息 ··· , 
    [KEY|INDEX] 索引名 (需要被索引的单个列或多个列)
)

也可以在修改表结构的时候添加索引：

ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的单个列或多个列);

也可以在修改表结构的时候删除索引：

ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;

【🌰栗子】

在创建index_demo表的时候就为c2和c3列添加一个联合索引，可以这么写建表语句：

CREATE TABLE index_demo(
    c1 INT,
    c2 INT,
    c3 CHAR(1),
    PRIMARY KEY(c1),
    INDEX idx_c2_c3 (c2, c3)
);

在这个建表语句中我们创建的索引名是idx_c2_c3，这个名称可以随便起，不过还是建议以idx_为前缀，后边跟着需要建立索引的列名，多个列名之间用下划线_分隔开。

如果想删除这个索引，可以这么写：

ALTER TABLE index_demo DROP INDEX idx_c2_c3;