汀的知识碎片

7.0 第7章 InnoDB索引的实现

34 min read

第7章 InnoDB索引的实现

众所周知，MySQL 数据库中的数据是保存于磁盘上的。在6.1节，我们提出了若干问题，涉及如何迅速检索所需数据。在某些情况下，我们可能需要检索单行数据、一系列数据，或是整张数据表。若数据是简单地按照插入顺序追加到数据文件中，那么数据检索过程将变得异常缓慢。因此，索引的概念应运而生。本章先简单地介绍了索引，然后介绍了索引的结构，接着介绍了索引在内存中的管理以及索引的创建，之后以数据检索为例来帮助读者更好地理解索引的实现，最后会介绍索引的分裂、合并以及重组。

7.1 索引简介

大多数业务场景对数据表的操作主要涉及：

  • 插入、删除、更新一条记录。
  • 查找一条记录。
  • 查找一个范围的记录。
  • 查找整个表的记录。

在能处理上述操作的同时，还有一点至关重要：表在数据量增加时，其效率几乎不受影响。那么，何种数据结构能够高效地支持上述操作呢？需要具备精确查询与范围查询的能力，且在数据量增长时对性能影响甚微。针对这样的需求，我们首先会考虑树状数据结构。常见的树状数据结构包括以下几种：

鉴于数据量庞大且需存储于磁盘，二叉树与红黑树便不是很适用，因其数据检索过程将导致频繁的I/O 操作。余下的选择为B 树与B+ 树，接下来将着重阐释B 树与B+ 树之间的差异，并探讨MySQL 采用B+ 树的原因。

7.1.1 B 树和B+ 树

上面提到B 树和B+ 树都可以用来构建索引，下面就来看看B 树和B+ 树的区别。首先来看看两者的结构。

B 树的结构如图7-1 所示。

图7-1 B 树的结构

其结构特点如下：

  • 根节点、内节点、叶子节点都包含数据。
  • 每个节点都是按照大小顺序进行排序的。
  • 叶子节点没有被链接起来。

B+ 树的结构如图7-2 所示。

图7-2 B+ 树的结构

其结构特点如下：

  • 只有叶子节点存储数据，根节点和内节点不存储数据。
  • 每个节点都是按照大小顺序进行排序的。
  • 所有叶子节点都被链接起来了。

这里就不具体介绍B 树和B+ 树结构本身的一些规则了，感兴趣的读者可以自行研究。

根据B 树和B+ 树的结构特点，我们可以看到它们主要有两点不一样：

  • B 树所有节点都存储数据，B+ 树只有叶子节点存储数据。那么，在精准查询一条记录时，B 树的时间复杂度最低为O(1)，B+ 树最低为O(log n)。B 树在精准查询一条记录时的性能可能优于B+ 树。
  • B 树的叶子节点没有被链接起来，B+ 树的叶子节点都被链接起来。那么，在进行范围查询时，B 树进行遍历的时候需要不断遍历叶子节点上的父节点来找到后面的数据，B+ 树则直接遍历叶子节点即可。

通过这个对比，我们其实就知道MySQL 为什么会选择B+ 树来构建索引了。MySQL作为关系数据库，经常会遇到表关联查询和范围查询，所以B+ 树的结构会更加适合。非关系数据库（比如MongoDB）喜欢把所有关联的表放在一个JSON 对象里面，这样其实大部分的场景可能是单点查询，那么B 树索引会更加适合它。

7.1.2 全文索引

通常我们在MySQL 中执行的语句都是等值或范围查询，有时候也会执行模糊查询，例如下面的SQL 语句：

select * from sbtest1 where pad like "zbdba%"

如果pad 上有索引的话是可以用到的，并且可以高效地得到结果。相反，执行如下SQL 语句时：

select * from sbtest1 where pad like  "%zbdba%"

就算使用了索引也是扫描每条记录进行比对，效率会比较差。这个时候就需要引入全文索引。简单来说，全文索引就好比存储一篇文章，我们能快速通过全文索引搜索到具体的关键字信息，这是由于全文索引存储了这篇文章的分词信息。在MySQL 中使用全文索引也有对应的语法，如下所示：

select * from articles where match(content) against "zbdba"

上述是自然语言模式对应的查询语法，MySQL 还支持布尔模式的检索方式。由于篇幅所限，这里只简单介绍一下全文索引，感兴趣的读者可以自行研究相关细节。

7.2 索引的结构

了解B+ 树的结构后，我们来看MySQL 是如何组织这个B+ 树结构的，以及索引的数据在B+ 树上的存储方式。

7.2.1 聚簇索引的结构

聚簇索引的基本架构如图7-3 所示。

聚簇索引主要由根节点与叶子节点构成。无论是根节点还是叶子节点，均包含一对键值（Key-Value）。在此需特别指出，键值的概念仅在逻辑层面存在，在实际的物理存储中并未明确区分键与值，而是直接存储了一条完整的记录。接下来，我们将探讨根节点与叶子节点中键值各自对应的数值。

  • 根节点：Key 为聚簇索引列的值，它对应叶子节点页中最小的主键列的值；Value 为指向索引叶子节点页的页号。
  • 叶子节点：Key 为主键列具体值；Value 为具体的一行记录，行记录在数据文件的章节中已经详细介绍。

了解完根节点和叶子节点存储的具体数据后，我们来介绍这些节点是如何连接起来的。

我们知道B+ 树索引的结构是所有的根节点组成一条单向链表，所有的叶子节点也组成一条单向链表，然后根节点需要指向叶子节点。在MySQL 中，每个节点都会存储一个指针指向下一个节点，然后根节点会指向叶子节点页，这样根节点和叶子节点就连接起来了。刚刚提到在MySQL 中多个节点由索引页进行管理，所以多个索引页还需要维护两个指针，分别指向它的上一个页和下一个页，这样所有的节点都已经连接完成。注意，这里的指针也是逻辑的概念，接下来，我们将深入探讨聚簇索引在MySQL 数据文件中的具体组织方式。

我们知道，索引页负责管理一系列节点，而这些索引页又可以细分为根节点页和叶子节点页。在6.1节中，我们已经阐述了数据文件实际上是由多个页构成的，这些页具有不同的类型。在这些页中，数据页和索引页是存放用户数据的关键位置。因此，在数据文件的上下文中，聚簇索引是由多个索引页构成的集合。聚簇索引的逻辑架构如图7-4 所示。

我们可以看到，索引页在数据文件中其实是无序的，而B+ 树则是有序的，因此只能通过指针将各个索引页顺序地连接起来，索引页中的节点也是通过指针顺序地连接起来的。这样就可以保证逻辑上有序。那这里的指针到底存储的是什么内容呢？分三种情况进行介绍：

  • 数据页之间的指针。每个数据页

7.4 数据检索

本节将从在索引上进行检索、插入、删除、更新四个方面来介绍数据检索的方式，从而帮助读者进一步加深对索引的理解。

7.4.1 聚簇索引数据检索

聚簇索引的数据检索流程主要分为两步：

  1. 在根节点页中搜索符合条件的记录，该记录指向叶子节点页。
  2. 在叶子节点页中搜索符合条件的叶子节点。

除了等值查询的扫描方式，还有全表扫描和范围扫描。这部分内容已在6.1.4小节中详细介绍。

7.4.2 二级索引数据检索

二级索引数据检索前面的步骤与聚簇索引是一致的，只是最后拿到叶子节点的时候，需要判断是否需要去聚簇索引上获取数据：

  • 如果所需字段在二级索引上已经存在，则不需要；
  • 如果不存在，就需要去聚簇索引上获取，这也就是我们常说的回表查询。

去聚簇索引上获取数据的流程跟前面介绍的主键等值查询流程完全一致，这里不再赘述。

NOTE

要读取数据文件的内容，需要先将对应的数据页加载到内存—缓冲区，这部分内容在第5章中详细介绍过。

7.4.3 插入数据

刚刚我们已经知道在MySQL中是如何检索数据的，那么数据的插入流程又是怎样的呢？其实数据的插入主要分为两步：检索需要插入的位置和插入记录。

首先来看检索的流程。在此，我们假设id=10并不存在。若需插入一条id=10的记录，必须先确定插入的位置，即id值小于10的记录A与id值大于10的记录B之间的位置。此流程与6.1.4节中介绍的大致相同。

然后是插入的流程。确定位置之后，便可在记录A之后进行插入操作，这里重点介绍具体流程：

  1. 获取要插入记录的大小。
  2. 在索引页上为该记录分配空间。
  3. 将记录复制到分配的空间上。
  4. 将记录插入记录链表。之前介绍过，索引页的记录链表是一个单向链表，索引插入的流程如图7-10所示。

图7-10 索引插入的流程

图7-10示意：记录链表为单向链表，从Infimum → rec(1) → rec(9) → … → rec(11) → rec(10) → … → Supremum。插入操作在rec(9)与rec(11)之间插入rec(10)。

  1. 将该记录的owned值设置为0。
  2. 将数据页的最近插入记录更新为当前记录。
  3. 更新该记录所在的槽中维护的owned值，将其+1。一旦owned超过最大值，还会触发分裂，具体参见6.1.4节。

7.4.4 删除数据

删除数据和插入数据的流程基本一致，也主要分为两步：检索需要删除的记录和删除记录。

第一步其实就是通过主键等值查询获取对应记录。第二步其实就是从对应的数据页维护的单向记录链表中移除对应的记录。索引删除的流程如图7-11所示。

图7-11 索引删除的流程

图7-11示意：原链表为 Infimum → rec(1) → rec(9) → … → rec(11) → rec(10) → rec(13) → rec(14) → rec(15) → … → Supremum。删除记录rec(10)后，链表变为 Infimum → rec(1) → rec(9) → … → rec(11) → rec(13) → rec(14) → rec(15) → … → Supremum。

7.4.5 更新数据

更新数据和删除数据流程基本一致，主要分为两步：检索需要更新的记录和更新记录。检索流程与之前一样。更新的流程分为两种情况：原地更新和插入更新。这两种情况都在6.1.4小节中介绍过，这里不再赘述。

7.5 索引分裂和合并

单个索引页能保存的记录是有限的，但如果一个索引页用满了，恰好又有一条记录需要插入该索引页，这时候应该怎么办呢？MySQL内部用索引的分裂机制来处理这种情况，并且提供了索引的合并机制来提高空间利用率。下面详细介绍索引分裂和合并的流程。

7.5.1 索引页分裂

索引页的默认大小是16KB，在空间不够的时候就需要进行索引页分裂。简单来说，索引页分裂就是新建一个索引页，然后根据插入记录的位置来判断是否需要将之前的索引页的一些记录迁移到新的索引页中。

NOTE

MySQL正常都是乐观插入，如果乐观插入失败了，一般都是空间不够所致，接着就进行悲观插入，在悲观插入中就会进行索引页的分裂。

索引页的分裂架构如图7-12所示，大致说明了索引页的分裂逻辑。

图7-12 索引页的分裂架构

图7-12示意：第1层有3号数据页（作为父节点），第0层有6号、7号、9号、8号数据页（从左到右）。分裂时，如果向7号页插入记录导致空间不足，则新建8号页，并将7号页中的部分记录迁移到8号页（迁移方向箭头指向8号页）。

从图7-12中可以总结出索引的分裂步骤：

  1. 由一条插入语句触发，前提条件是当前数据页空间不够了。
  2. 为该索引分配一个新的索引页。
  3. 找到split_record，也就是切分记录点。这里分两种情况：
    • 顺序插入：插入的记录位于索引页的最后一条记录后。这种情况该数据页中的记录不会迁移，只是分配一个新页，将新记录插入新页中即可。
    • 随机插入：插入的记录不在该索引页的最后一条记录后。这时候就需要计算索引页中间的记录，然后将索引页分裂50%出去。
  4. 将新建的索引页与之前的索引页用指针连接起来，这里是双向指针。如图7-13中的9号数据页所示。
  5. 将split_record后的记录迁移到新页中：
    • 如果是顺序插入，那么split_record后面就是supremum，不需要进行记录迁移。
    • 否则就需要进行迁移，一般情况下迁移50%的记录。
  6. 从之前的索引页中删除被迁移的记录。
  7. 完成索引页的分裂后，再将之前的记录插入合适的位置。

分裂过程中的锁

在索引分裂的过程中其实是会加锁的，这里主要有两个锁：

  • 保护整个索引树的读写锁，由dict_index_t结构体中的lock字段维护。
  • 保护单个索引页的读写锁，由buf_block_t结构体中的lock字段维护。

索引树会加SX模式的锁，单个索引页会加X模式的锁。这就意味着在索引页分裂的时候，与该索引树相关的记录是只读的，不能进行修改，而被分裂的索引页是不能进行读写的。SX模式的锁是MySQL 5.7版本引入的，在MySQL 5.6中，索引树也是直接加X模式的锁，在索引页分裂的时候，整个索引都不能进行读写。这里其实应该还有优化的空间，只涉及一个索引页的分裂，为什么整个索引树都变成只读了呢？能不能把锁粒度变小？答案是肯定的，但还需要考虑很多细节。

触发分裂的事务回滚处理

如果触发分裂的事务回滚怎么办？这里主要分如下两种情况：

  • 顺序插入时：索引页分裂其实就是新建一个索引页，将新的记录插入索引页中。如果这个时候进行回滚，会将新的数据删除，在数据删除的时候会主动调用索引页合并的流程，这个时候就会发现这个新的索引页没有数据，那么就会进行释放。
  • 随机插入时：索引页分裂是新建一个索引页并迁移之前索引页的记录到新的索引页上。如果这个时候进行回滚，会将新的数据删除，在数据删除的时候也会主动调用索引页合并的流程，这个时候就要区分情况了，主要看原有的索引页和新建的索引页谁的空间使用率小于50%，小于的那个会被合并，合并完成之后该索引页的记录会被清除，然后释放这个索引页。

至此，我们了解了整个索引分裂的流程。大家想想看上述逻辑有没有问题。每次迁移50%的话，如果应用造成频繁的索引分裂，有没有可能导致空间使用率变低？其实行业内已经有公司发现这个问题并且提供了相应的解决方案，读者若有兴趣可以自行了解。还有一个点需要强调，为什么大家都建议采用自增主键？因为自增主键插入的时候是按照顺序插入，在批量插入的时候不会引起大量的索引页分裂。

7.5.2 索引页合并

在本小节中，我们将深入探讨索引页合并的详细流程。索引页合并是指当某个索引页的使用率降至特定阈值以下时，系统会主动尝试将其与相邻的、符合条件的索引页合并。合并成功后，原索引页将被删除，从而提升存储空间的使用效率。接下来，让我们详细看看索引合并的具体步骤。

一般在purge线程完成记录的彻底删除后，会检查该索引页是否符合合并的条件。具体主要会判断索引的使用率是否低于一个阈值，该阈值由DICT_INDEX_MERGE_THRESHOLD_DEFAULT变量控制，默认为50%，低于该阈值即触发索引页合并。

合并的流程主要又分为向左合并和向右合并两种情况，这两种情况在合并记录时处理父节点的方式不太一样，下面进行详细介绍。

1. 向左合并

MySQL会优先选择向左合并，因为向左合并的代价会小于向右合并。图7-13所示为索引向左合并的流程。

图7-13 索引向左合并的流程

图7-13示意：第1层有3号数据页（父节点），第0层有6号、7号、8号数据页（从左到右）。向左合并是指将8号页（被合并页）的记录迁移到左边的7号页。步骤：第1步（迁移）将8号页的记录全部迁移到7号页；第2步（从链表移除）将8号页从双向链表中移除，修改7号页的next指针指向右边（原8号页右边）的页（即原右边不存在则指向NULL？图中显示8号页右边没有其他页，所以7号页的next指向NULL/Supremum？实际图中第2步修改左边页的页头指向右边页，右边页的页头指向左边页。这里被合并页是8号，右边没有页，所以只需修改7号页的next指向原来8号页的右边（可能为空），以及修改原8号页右边的页（如果有）的prev指向7号。图中右边无页，所以修改后7号页next指向NULL/Supremum）；第3步（删除父节点）删除8号页对应的父节点记录。

这个流程主要分为两个阶段：

  1. 判断左边的页是否符合条件：主要就是有没有足够的空间来存放被合并页的数据。

  2. 符合条件就开始合并，主要分为3个步骤：

    • 第1步：迁移数据（对应图7-13中的第1步）。向左合并迁移数据比较简单，遍历被合并页的所有记录并顺序插入左边的页中即可，因为被合并页的记录肯定比左边页最大的记录要大，所以直接在左边页最大用户记录后插入即可。然后删除被合并页对应的自适应哈希索引。
    • 第2步：将被合并页从数据页链表中移除（对应图7-13中的第2步），其实就是从双向链表中移除一个节点。这里主要是修改左边页的页头，将其指向下一个页的字段修改为右边的页。然后修改右边页的页头，将其指向上一个页的字段修改为左边的页。
    • 第3步：删除被合并页对应的父节点（对应图7-13中的第3步）。

至此，这个数据页就被彻底删除了，并且它里面的记录也迁移到左边的页中了。

2. 向右合并

向右合并的步骤与向左合并大体一致，只是有些细节不太一样。图7-14所示为索引向右合并的流程。

图7-14 索引向右合并的流程

图7-14示意：第1层有3号数据页，第0层有6号、7号、8号数据页。向右合并是指将7号页（被合并页）的记录迁移到右边的8号页。步骤：第1步（迁移）将7号页的记录逐条插入到8号页（需要比较大小）；第2步（从链表移除）将7号页从双向链表中移除，修改左边页（6号）的next指向8号，修改8号页的prev指向6号；第3步（修改父节点）：修改被合并页（7号）父节点中保存的叶子节点，改为指向右边的页（8号），然后将右边页（8号）对应的父节点删除。

这个流程主要也分为两个阶段：

  1. 如果左边的页不符合条件，就检查右边的页，也就是检查右边的页是否有足够的空间来存放被合并页的数据。

  2. 符合条件就开始合并，同样主要分为3个步骤：

    • 第1步：迁移数据（对应图7-14中的第1步）。这一步比向左合并要复杂一些。因为右边的页的记录比被合并的页要大，所以合并的页中的每条记录在插入前都需要进行一次对比。然后删除被合并页对应的自适应哈希索引。
    • 第2步：与向左合并一样（将被合并页从链表移除）。
    • 第3步（对应图7-14中的第3步）：修改被合并页父节点中保存的叶子节点，修改为指向右边的页。然后将右边页对应的父节点删除。

索引页的合并介绍完毕。可以看到，索引的合并会有一些代价，特别是向右合并的时候。这里其实应该也还有一些优化的空间，比如可以先把被合并的页中的记录从小到大依次插入右边的页，把它们链接起来。最后把这一段记录和右边页的记录链接起来，也就是Infimum指向这段记录的最小记录，这段记录的最大记录指向之前Infimum指向的记录。这其实相当于一个批量插入操作，这样就省去了每次插入都需要遍历记录对比大小的流程，性能会有所提升。当然，肯定还需要考虑其他的一些因素，这里只是抛砖引玉，希望感兴趣的读者可以推动实现。

7.5.3 索引页重组

在索引页合并的时候，其实有个步骤涉及索引的重组，就是在判断左边或者右边的页空间是否符合条件的时候。如果不符合条件会尝试进行索引页重组，重组后再进行判断。

简单来说，索引页重组就是将该索引页的记录重新组织一遍，这样能清理掉碎片，释放出一些空间。

索引重组的流程其实很简单，主要分为以下几步：

  1. 申请一个临时页。
  2. 将索引页的数据复制到临时页中。
  3. 将索引页的页头相关字段和索引页中的记录清空。
  4. 将临时页中的数据插入索引页中，插入完成就完成了索引页的重组。

7.6 总结

本章主要介绍了InnoDB索引的实现。首先解释了索引的作用是提高数据检索效率，常见的树状数据结构有二叉树、红黑树、B树和B+树，由于数据量大且需要存储于磁盘，二叉树和红黑树不适用，MySQL采用B+树作为索引。B树和B+树的主要区别在于B树的所有节点都存储数据，而B+树只有叶子节点存储数据；B树的叶子节点没有被链接起来，B+树的叶子节点都被链接起来了。

接着介绍了索引的实现，包括聚簇索引、二级索引和复合索引。聚簇索引的叶子节点存储具体的数据行，二级索引的叶子节点存储主键值。复合索引由多个字段组合而成，有向左优先原则。

然后介绍了索引的管理，包括在内存中的管理、加载和创建。索引在内存中由dict_index_t结构体管理，加载时从系统表中读取数据。创建索引部分按二级索引和聚簇索引的创建流程分别进行了介绍。

最后介绍了数据检索，包括聚簇索引和二级索引的数据检索方式，以及插入、删除和更新数据的流程。还介绍了索引页的分裂、合并和重组，分裂时会加锁，合并分为向左合并和向右合并，重组是为了清理碎片释放空间。