深入InnoDB焦点：揭秘B+树在数据库索引中的高效应用

目次
一、索引页与数据行的精密关联
（一）数据页的双向链表结构
（二）记载行的单向链表结构
二、未创建索引情况
（一）无索引下的单页查找过程
以主键为搜索条件
以非主键列为搜索条件
（二）无索引下的多页查找过程
三、InnoDB中的B+ 树索引方案初领会
（一）前置分析
行格式表示图
页内格式表示图
（二）目次项记载与用户记载的区别及其存储
目次项放到数据页
查找主键为20的记载
（三）分配新目次项记载页
更新后的数据页结构
查找主键值为20的记载的步调
确定目次项记载页
通过目次项记载页确定用户记载所在的页
在用户记载页中定位详细记载
（四）多级目次项记载页的先容
高级目次页分析
高级目次页（页33）
页30（目次项记载页）
页32（目次项记载页）
查找主键值为20的记载的步调（更新后的过程）
四、InnoDB中的B+ 树索引方案创建
（一）B+树的数据页结构
（二）B+树的条理结构
（三）B+树的查找服从
五、总结
 参考文献、册本及链接

---

干货分享，感谢您的阅读！
在当代数据库体系中，怎样高效地管理和查找海量数据是一个至关紧张的题目。InnoDB作为MySQL的存储引擎，通过引入B+树这种数据结构，办理了这一寻衅。B+树不光在索引性能方面表现精良，还在数据存储和检索上提供了极高的服从。我们探究下B+树在InnoDB中的实现和应用，更好地明确其工作原理和上风。
一、索引页与数据行的精密关联

在解读InnoDB数据库索引页与数据行的精密关联-CSDN博客中我们已经夸大过：在 InnoDB 中，数据页通过双向链表毗连，每个数据页内的记载行按照主键值从小到大的序次构成单向链表，而且每个数据页都有一个页目任命于快速定位记载。

查找记载时，先在页目次中使用二分法定位到特定槽，再在该槽对应的记载组中序次遍历找到目的记载。通过这种计划，InnoDB 可以大概高效地管理和查找数据，确保数据库体系的高性能和可靠性。
（一）数据页的双向链表结构

每个数据页被构造成一个双向链表，这意味着每个数据页都有指向前一个页和后一个页的指针（File Header 记载了页的根本信息和链表指针）。通过这种双向链表结构，InnoDB 可以方便地举行数据页的插入、删除和遍历利用。这种计划包管了数据页之间的高效毗连和管理。

（二）记载行的单向链表结构

 详细可见：数据库记载行在页内查询探索分析_查抄代码中循环依赖-CSDN博客
在每个数据页中，记载行按照主键值从小到大的序次构造成一个单向链表。这种有序的结构使得在数据页内查找记载变得更加高效。每条记载不光存储了自身的数据，还包罗指向下一条记载的指针，如许可以序次遍历记载。

每个数据页都有一个页目次，页目次可以看作是数据页内的索引结构。页目次将记载分成多个组，每个组在页目次中都有一个槽。通过页目次，InnoDB 可以快速定位到特定记载所在的组，从而淘汰遍历记载的时间。
当须要通过主键查找某条记载时，InnoDB 会先在页目次中使用二分法快速定位到对应的槽。页目次中的槽指向该槽对应的记载组，接着在该组中遍历记载，直到找到目的记载。这种查找过程团结了二分查找和序次遍历的优点，既高效又精确。
二、未创建索引情况

在数据库中，当没有针对特定列创建索引时，查询过程通常碰面临服从低下的题目。特别是对于非主键列的精确匹配查询，数据库引擎无法使用索引结构，从而导致须要全表扫描来探求符合条件的记载。
（一）无索引下的单页查找过程

在数据库中，当全部记载都可以大概存放在一个数据页中时，查找记载的过程可以根据查询条件的差别分为以下两种情况：
以主键为搜索条件

对于主键列的精确匹配查询：

• 页目次查找：数据页通常会维护一个页目次，用于存储每条记载的偏移位置。由于页目次是按照主键排序的，因此可以使用二分查找法快速定位到对应的记载槽。
  
• 记载遍历：找到对应槽后，只需遍历该槽中的记载，即可快速找到符合条件的记载。
  

这种方法由于使用了页目次的有序性，因此查找服从较高。这部门着实就是我们上文中讲到的抱负情况，但在开辟过程中我们不大概每次都是直接查主键id的情况。
以非主键列为搜索条件

对于非主键列的精确匹配查询：

• 全页扫描：由于非主键列没有对应的页目次，也没有任何排序信息，无法使用二分查找等高效查找算法。此时，数据库须要从数据页的最小记载开始，逐条遍历每条记载。
  
• 逐条比力：在遍历过程中，逐条对比记载是否符合搜索条件。假如记载数较多，这种方法的查找服从将会非常低。
  

显然，对于非主键列的查找，由于缺乏索引的支持，只能举行全页扫描，这在数据量较大时，性能会变得极为低下。
（二）无索引下的多页查找过程

在大部门现实应用中，表中的记载数量非常巨大，每每须要多个数据页来存储这些记载。当在多页中查找记载时，查找过程通常可以分为两个步调：

• 定位到记载所在的页。
  
• 从所在的页中查找相应的记载。
  

在没有索引的情况下，无论是根据主键列照旧其他列的值举行查找，由于无法快速定位到记载所在的页，只能沿着数据页的双向链表逐页查找。

这意味着：

• 遍历页链表：从第一个数据页开始，沿着双向链表依次访问每一个数据页。
  
• 逐页查找：在每个数据页中，使用前面先容的单页查找方式来查找指定的记载。
  

由于须要遍历全部数据页并在每个页中逐条比力记载，这种方式的服从非常低。
三、InnoDB中的B+ 树索引方案初领会

（一）前置分析

为了更好地明确 InnoDB 中 B+ 树索引的工作机制，我们从创建一个示例表index_demo开始，并通过详细的表示图展示记载在页中的存储结构及索引的作用。

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

复制代码

这个表中有两个 INT 范例的列 c1 和 c2，一个 CHAR(1) 范例的列 c3，而且 c1 列为主键。表的行格式为 Compact。
行格式表示图

为了更好地展示记载在页中的存储，简化 index_demo 表的行格式表示图：

每条记载由以下部门构成：
（配景：分析MYSQL行头信息数据详细和探究InnoDB Compact行格式背后）

• record_type：记载头信息的一项属性，表现记载的范例：0 表现平常记载；1 表现目次项记载；2 表现最小记载；3 表现最大记载
  
• next_record：记载头信息的一项属性，表现下一条记载所在相对于本记载的所在偏移量。
  
• 各个列的值：记载 index_demo 表中的三个列 c1、c2 和 c3 的值。
  
• 其他信息：除了上述三种信息以外的全部信息，包罗其他隐蔽列的值以及记载的额外信息。
  

为了节省篇幅，我们省略记载的其他信息部门并将记载竖着展示：

页内格式表示图

把一些记载放到页里边的表示图就是：

（二）目次项记载与用户记载的区别及其存储

在 InnoDB 中，为了机动管理 B+ 树索引的目次项，计划者们选择了复用存储用户记载的数据页来存储目次项记载。这种计划使得 InnoDB 可以大概高效地管理和查询数据。我们来详细分析并解说这一机制。
目次项放到数据页

有效地使用已有的数据结构和存储机制，通过记载头信息中的 record_type 属性，InnoDB 可以轻松区分目次项记载和用户记载。record_type 值为 1 表现目次项记载，值为 0 表现平常用户记载。

目次项记载仅包罗主键值和页号，这使得它们非常轻便高效。而平常用户记载则包罗用户界说的多个列。
min_rec_mask 属性资助 InnoDB 快速定位页中主键值最小的目次项记载，优化了索引的管理和查询性能。在存储目次项记载的页中，主键值最小的目次项记载的 min_rec_mask 值为 1，其他记载的 min_rec_mask 值为 0。
查找主键为20的记载

如今以查找主键为20的记载为例，根据某个主键值去查找记载的步调就可以大抵拆分成下面两步：

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

（三）分配新目次项记载页

只管目次项记载只存储主键值和对应的页号，相比于用户记载所需的存储空间要小得多，但由于每个数据页只有16KB的巨细，可以大概存放的目次项记载数量也是有限的。假如表中的数据非常多，以至于单个数据页无法存放全部的目次项记载，那么就须要分配更多的目次项记载页。
假设一个存储目次项记载的页最多只能存放4条目次项记载（请留意这只是个假设，现实情况可以存放更多）。当须要插入新的目次项记载时，比如主键值为320的记载，就会出现须要分配新目次项记载页的情况。

插入一条主键值为320的用户记载后，我们须要新增两个数据页：

• 页31：用于存储新的用户记载。
  
• 页32：用于存储新的目次项记载，由于原先存储目次项记载的页30已经满了（假设只能存储4条目次项记载）。
  

更新后的数据页结构

• 页30：存储目次项记载，主键值范围为 [1, 320)。
  
• 页32：存储目次项记载，主键值范围为 [320, ∞)。
  

查找主键值为20的记载的步调

如今由于存储目次项记载的页不止一个，以是假如我们想根据主键值查找一条用户记载，大抵须要三个步调。以查找主键值为20的记载为例：
确定目次项记载页

• 如今的存储目次项记载的页有两个：页30和页32。
  
• 页30存储的目次项的主键值范围是 [1, 320)，页32存储的目次项的主键值范围是不小于320。
  
• 因此，主键值为20的记载对应的目次项记载在页30中。
  

通过目次项记载页确定用户记载所在的页

在页30中，通过二分法快速定位到主键值为20的目次项记载，从而确定该用户记载存储在页9中。
在用户记载页中定位详细记载

在页9中，通过二分法快速定位到主键值为20的用户记载。
（四）多级目次项记载页的先容

在查询步调的第1步中，我们须要定位存储目次项记载的页。然而，这些页在存储空间中大概不一连分列。假如表中的数据量非常大，会产生很多存储目次项记载的页。那我们怎么根据主键值快速定位一个存储目次项记载的页呢？
为了办理这个题目，我们可以为这些存储目次项记载的页天生一个更高级的目次，形成多级目次结构。大目次中嵌套小目次，小目次中存储现实的数据。如今各个页的表示图如下：

高级目次页分析

高级目次页（页33）

页33存储更高级的目次项记载，用于指向存储目次项记载的页（比方页30和页32）。页33包罗两个目次项记载：

• 目次项记载1：指向页30，范围为[1, 320)
  
• 目次项记载2：指向页32，范围为[320, ∞)
  

页30（目次项记载页）

• 页30存储详细的目次项记载，指向用户记载页。
  
• 目次项记载指向主键值范围在[1, 320)内的用户记载页。
  

页32（目次项记载页）

• 页32存储详细的目次项记载，指向用户记载页。
  
• 目次项记载指向主键值范围在[320, ∞)内的用户记载页。
  

查找主键值为20的记载的步调（更新后的过程）

• 确定高级目次页：起首，根据主键值在高级目次页（页33）中举行查找。由于主键值20在范围[1, 320)内，以是对应的目次项记载在页30中。
  
• 确定详细的目次项记载页：在页30中，通过二分法快速定位到主键值为20的目次项记载，从而确定用户记载存储在页9中。
  
• 在用户记载页中定位详细记载：在页9中，通过二分法快速定位到主键值为20的用户记载。
  

这里留意我们之前的假设：假设一个存储目次项记载的页最多只能存放4条目次项记载（请留意这只是个假设，现实情况可以存放更多）
四、InnoDB中的B+ 树索引方案创建

在先容B+树之前，我们已经看到了怎样通过多级目次结构管理和查找数据。这种结构就像一棵倒过来的树，上头是树根，下头是树叶。着实，这是一种构造数据的情势，大概说是一种数据结构，它的名称是B+树。

（一）B+树的数据页结构

岂论是存放用户记载的数据页，照旧存放目次项记载的数据页，我们都把它们存放到B+树这个数据结构中，以是我们也称这些数据页为节点。
从图中可以看出来，我们的现实用户记载都存放在B+树的最底层的节点上，这些节点也被称为叶子节点或叶节点，别的用来存放目次项的节点称为非叶子节点大概内节点，此中B+树最上面的谁人节点也称为根节点。
（二）B+树的条理结构

计划InnoDB的大佬们为了讨论方便，规定最下面的那层，也就是存放我们用户记载的那层为第0层，之后依次往上加。为了简化，我们之前做了一个非常非常的假设：存放用户记载的页最多存放3条记载，存放目次项记载的页最多存放4条记载。着实在真实情况中，一个页存放的记载数量优劣常大的。
假设全部存放用户记载的叶子节点代表的数据页可以存放100条用户记载，全部存放目次项记载的内节点代表的数据页可以存放1000条目次项记载，那么：

• 假如B+树只有1层，也就是只有1个用于存放用户记载的节点，最多能存放100条记载。
  
• 假如B+树有2层，最多能存放1000×100=100,000条记载。
  
• 假如B+树有3层，最多能存放1000×1000×100=100,000,000条记载。
  
• 假如B+树有4层，最多能存放1000×1000×1000×100=100,000,000,000条记载。
  

哇咔咔～这么多的记载！！！
但现实上，可推演得出结论：当单行数据巨细为S字节，树高为H时，一个bigint范例的主键B+树索引中可以存放的数量行数N便是：

按公式盘算：当树高为4时，可以存放200百多亿行数据。如许的数据容量，可以满意绝大部门应用的需求，因此我们可以说在绝大部门应用中，B+树高度为3或4就可以满意数据存储的需求。B+树这种高扇出低树高的特性，也大大的进步了主键查询性能。详细推导可见：InnoDB存储引擎B+树的树高推导_b+树一样平常多少层-CSDN博客
（三）B+树的查找服从

你的表里能存放100,000,000,000条记载么？以是一样平常情况下，我们用到的B+树都不会凌驾4层，那我们通过主键值去查找某条记载最多只须要做4个页面内的查找（查找3个目次项页和一个用户记载页），又由于在每个页面内有所谓的Page Directory（页目次），以是在页面内也可以通过二分法实现快速定位记载，这不是很牛么！
通过引入B+树，InnoDB可以大概高效地管理和查找大量数据。B+树的结构包管了纵然在处置处罚大规模数据时，查找过程仍旧高效。每一层增长的节点数，使得数据的管理和查找变得更加敏捷和可靠。
B+树是数据库体系中广泛使用的索引结构，通过这种结构，InnoDB可以大概在巨大的数据会集快速、精确地找到所需的记载，为数据库性能提供了有力的保障。
五、总结

综上所述，B+树作为InnoDB的焦点索引结构，通过多级目次和高效的节点管理，实现了快速的数据查找和管理。其高扇出、低树高的特性，使得纵然在处置处罚大规模数据时，查找过程仍旧保持高效，通常不凌驾四层的树结构足以满意大部门应用需求。
通过B+树，InnoDB在巨大的数据会集可以大概快速、精确地找到所需记载，显着进步了数据库的性能和可靠性。其页目次、双向链表和单向链表等计划进一步优化了数据存储和查找过程，使得数据库体系在面临复杂查询时依然可以大概保持高效运作。
B+树不光在数据构造和存储方面显现了强盛的本事，更通过现实应用证实白其在数据库管理体系中的不可更换性。总之，B+树的引入和使用，使得InnoDB可以大概在当代数据库体系中脱颖而出，成为高性能、高可靠性的代名词。

 参考文献、册本及链接

• 《MySQL技能内幕：InnoDB存储引擎》（第2版）：MySQL技能内幕 (豆瓣)
  
• 《MySQL 是怎样运行的：从根儿上明确 MySQL》
  
• 《Inside InnoDB: The InnoDB Storage Engine》：MySQL :: MySQL 8.0 Reference Manual :: 15 The InnoDB Storage Engine
  
• 《InnoDB: The Ultimate Guide》：https://www.percona.com/blog/2018/06/05/innodb-the-ultimate-guide/
  
• 《InnoDB Storage Engine Internals》：https://mariadb.com/kb/en/innodb-storage-engine-internals/
  
• InnoDB的数据页结构