敞开成长之旅！这是我参加「日新计划 12 月更文应战」的第14天，点击检查活动概况

【MySQL进阶】深化了解B+树索引底层原理

【MySQL进阶】深化了解B+树索引底层原理一、前语——没有索引的查找1、在一个页中的查找2、在许多页中查找3、总结二、索引1、一个简略的索引计划2、InnoDB中的索引计划3、B+ 树4、聚簇索引5、二级索引6、回表7、联合索引三、InnoDB的B+树索引的注意事项1、根页面万年不动窝2、内节点中目录项记载的仅有性四、总结1、B+ Tree 原理2、详细查找流程

参考资料：《MySQL是怎样运行的：从根儿上了解MySQL》。

一、前语——没有索引的查找

在正式介绍 索引 之前，咱们需求了解一下没有索引的时分是怎样查找记载的。咱们下边先只啰嗦查找条件为对某个列准确匹配的状况，所谓准确匹配，便是查找条件中用等于 = 连接起的表达式，比如这样：

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

1、在一个页中的查找

假定目前表中的记载比较少，一切的记载都能够被寄存到一个页中，在查找记载的时分能够依据查找条件的不同分为两种状况：

  • 以主键为查找条件

    这个查找进程咱们现已很熟悉了，能够在 页目录 中运用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记载即可快速找到指定的记载

  • 以其他列作为查找条件

    对非主键列的查找的进程可就不这么走运了，由于在数据页中并没有对非主键列树立所谓的 页目录 ，所以咱们无法经过二分法快速定位相应的 槽 。这种状况下只能从 最小记载 开端依次遍历单链表中的每条记载，然后对比每条记载是不是符合查找条件。很显然，这种查找的功率是十分低的。

2、在许多页中查找

大部分状况下咱们表中寄存的记载都是十分多的，需求许多的数据页来存储这些记载。在许多页中查找记载的话能够分为两个进程：

  • 定位到记载地点的页
  • 从地点的页内里查找相应的记载

3、总结

在没有索引的状况下，不论是依据主键列或许其他列的值进行查找，由于咱们并不能快速的定位到记载地点的页，所以只能从第一个页沿着双向链表一向往下找，在每一个页中依据咱们刚刚啰嗦过的查找方法去查找指定的记载。由于要遍历一切的数据页，所以这种方法显然是超级耗时的，假如一个表有一亿条记载，运用这种方法去查找记载那要等到猴年马月才干等到查找成果。

二、索引

咱们先建一个表：

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 表的行格式示意图：

【MySQL进阶】深入理解B+树索引底层原理

把一些记载放到页里边的示意图便是：

【MySQL进阶】深入理解B+树索引底层原理

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

那么这些记载现已依照主键值的巨细串联成一个单向链表了，如图所示：

【MySQL进阶】深入理解B+树索引底层原理

从图中能够看出来， index_demo 表中的3条记载都被刺进到了编号为 10 的数据页中了。此刻咱们再来刺进一条记载：

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

由于 页10 最多只能放3条记载，所以咱们不得不再分配一个新页：

【MySQL进阶】深入理解B+树索引底层原理

页10 中用户记载最大的主键值是 5 ，而 页28 中有一条记载的主键值是 4 ，由于 5> 4 ，所以这就不符合下一个数据页中用户记载的主键值有必要大于上一个页中用户记载的主键值的要求，所以在刺进主键值为 4 的记载的时分需求伴跟着一次记载移动，也便是把主键值为 5 的记载移动到 页28 中，然后再把主键值为 4 的记载刺进到 页10 中，这个进程的示意图如下：

【MySQL进阶】深入理解B+树索引底层原理

这个进程表明了在对页中的记载进行增删改操作的进程中，咱们有必要经过一些诸如记载移动的操作来一向确保这个状态一向成立：下一个数据页中用户记载的主键值有必要大于上一个页中用户记载的主键值。这个进程咱们也能够称为 页割裂 。

  • 给一切的页树立一个目录项

由于数据页的编号或许并不是接连的，所以在向 index_demo 表中刺进许多条记载后，或许是这样的作用：

【MySQL进阶】深入理解B+树索引底层原理

目录项：

由于这些 16KB 的页在物理存储上或许并不挨着，所以假如想从这么多页中依据主键值快速定位某些记载地点的页，咱们需求给它们做个目录，每个页对应一个目录项，每个目录项包括下边两个部分：

  • 页的用户记载中最小的主键值，咱们用 key 来表明
  • 页号，咱们用 page_no 表明

【MySQL进阶】深入理解B+树索引底层原理

至此，针对数据页做的简易目录就搞定了。不过忘了说了，这个 目录 有一个别号，称为 索引 。

2、InnoDB中的索引计划

上边之所以称为一个简易的索引计划，是由于咱们为了在依据主键值进行查找时运用二分法快速定位详细的目录项而假定一切目录项都能够在物理存储器上接连存储，可是这样做有几个问题：

  • InnoDB 是运用页来作为办理存储空间的基本单位，也便是最多能确保 16KB 的接连存储空间，而跟着表中记载数量的增多，需求十分大的接连的存储空间才干把一切的目录项都放下，这对记载数量十分多的表是不现实的。
  • 咱们经常会对记载进行增删，假定咱们把 页28 中的记载都删除了， 页28 也就没有存在的必要了，那意味着 目录项2 也就没有存在的必要了，这就需求把 目录项2 后的目录项都向前移动一下，这种牵一发而动全身的设计不是什么好主意。

所以，设计 InnoDB 的大叔们设计了一种能够灵活办理一切 目录项 的方法。

目录项其实长得跟咱们的用户记载差不多，只不过 目录项 中的两个列是 主键 和 页号 罢了。为了和用户记载做一下区别，咱们把这些用来表明目录项的记载称为 目录项记载 。那 InnoDB 怎样区别一条记载是一般的 用户记载 仍是 目录项记载 呢？别忘了记载头信息里的record_type 属性，它的各个取值代表的意思如下：

  • 0 ：一般的用户记载
  • 1 ：目录项记载
  • 2 ：最小记载
  • 3 ：最大记载

咱们把前边运用到的目录项放到数据页中的姿态便是这样：

【MySQL进阶】深入理解B+树索引底层原理

从图中能够看出来，咱们新分配了一个编号为 30 的页来专门存储 目录项记载 。这儿再次强调一遍 目录项记载和一般的 用户记载 的不同点：

  • 目录项记载 的 record_type 值是1，而一般用户记载的 record_type 值是0。
  • 目录项记载 只需主键值和页的编号两个列，而一般的用户记载的列是用户自己界说的，或许包括许多列，另外还有 InnoDB 自己增加的躲藏列。

现在以查找主键为 20 的记载为例，依据某个主键值去查找记载的进程就能够大致拆分红下边两步：

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

那假如表中的数据太多，以至于一个数据页不足以寄存一切的 目录项记载 ，该咋办呢？

  • 当然是再多整一个存储 目录项记载 的页喽

咱们假定一个存储 目录项记载 的页最多只能寄存4条 目录项记载，所以假如此刻咱们再向上图中刺进一条主键值为 320 的用户记载的话，那就需求分配一个新的存储 目录项记载的页：

【MySQL进阶】深入理解B+树索引底层原理

现在由于存储 目录项记载 的页不止一个，所以假如咱们想依据主键值查找一条用户记载大致需求3个进程，以查找主键值为 20 的记载为例：

  • 确认 目录项记载 页

    咱们现在的存储 目录项记载 的页有两个，即 页30 和 页32 ，又由于 页30 表明的目录项的主键值的规模是[1, 320) ， 页32 表明的目录项的主键值不小于 320 ，所以主键值为 20 的记载对应的目录项记载在 页30中。

  • 经过 目录项记载 页确认用户记载实在地点的页

  • 在实在存储用户记载的页中定位到详细的记载。

那么问题来了，在这个查询进程的第1步中咱们需求定位存储 目录项记载 的页，可是这些页在存储空间中也或许不挨着，假如咱们表中的数据十分多则会产生许多存储 目录项记载 的页，那咱们怎样依据主键值快速定位一个存储 目录项记载 的页呢？其实也简略，为这些存储 目录项记载 的页再生成一个更高档的目录，就像是一个多级目录相同，大目录里嵌套小目录，小目录里才是实践的数据，所以现在各个页的示意图便是这姿态：

【MySQL进阶】深入理解B+树索引底层原理

这玩意儿像不像一个倒过来的 树 呀，上头是树根，下头是树叶！其实这是一种组织数据的形式，或许说是一种数据结构，它的名称是 B+ 树。

【MySQL进阶】深入理解B+树索引底层原理

3、B+ 树

MySQL 中最常用的索引的数据结构是 B+ 树，他有以下特色：

  1. 在 B+ 树中，一切数据记载节点都是依照键值的巨细寄存在同一层的叶子节点上，而非叶子结点只存储key的信息，这样能够大大削减每个节点的存储的key的数量，下降B+ 树的高度
  2. B+ 树叶子节点的关键字从小到大有序排列，左边结束数据都会保存右边节点开端数据的指针。
  3. B+ 树的层级更少：相较于 B 树 B+ 每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快
  4. B+ 树查询速度更安稳：B+ 一切关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更安稳;
  5. B+ 树天然具有排序功能：B+ 树一切的叶子节点数据构成了一个有序链表，在查询巨细区间的数据时分更便利，数据紧密性很高，缓存的命中率也会比B树高。
  6. B+ 树全节点遍历更快：B+ 树遍历整棵树只需求遍历一切的叶子节点即可，，而不需求像 B 树相同需求对每一层进行遍历，这有利于数据库做全表扫描。

【MySQL进阶】深入理解B+树索引底层原理

假定一切寄存用户记载的叶子节点代表的数据页能够寄存100条用户记载，一切寄存目录项记载的内节点代表的数据页能够寄存1000条目录项记载，那么：

  • 假如 B+ 树只需1层，也便是只需1个用于寄存用户记载的节点，最多能寄存 100 条记载
  • 假如 B+ 树有2层，最多能寄存 1000100=100000 条记载
  • 假如 B+ 树有3层，最多能寄存 10001000100=100000000 条记载
  • 假如 B+ 树有4层，最多能寄存 100010001000100=100000000000 条记载

你的表里能寄存 100000000000 条记载么？所以一般状况下，咱们用到的 B+ 树都不会超过4层，那咱们经过主键值去查找某条记载最多只需求做4个页面内的查找（查找3个目录项页和一个用户记载页），又由于在每个页面内有所谓的 Page Directory （页目录），所以在页面内也能够经过二分法完结快速定位记载，这不是很牛么，哈哈！

4、聚簇索引

咱们上边介绍的 B+ 树本身便是一个目录，或许说本身便是一个索引。它有两个特色：

  • 运用记载主键值的巨细进行记载和页的排序，这包括三个方面的意义：

    • 页内的记载是依照主键的巨细次序排成一个单向链表
    • 各个寄存用户记载的页也是依据页中用户记载的主键巨细次序排成一个双向链表
    • 寄存目录项记载的页分为不同的层次，在同一层次中的页也是依据页中目录项记载的主键巨细次序排成一个双向链表

  • B+ 树的叶子节点存储的是完好的用户记载

    • 所谓完好的用户记载，便是指这个记载中存储了一切列的值（包括躲藏列）

咱们把具有这两种特性的 B+ 树称为 聚簇索引 ，一切完好的用户记载都寄存在这个 聚簇索引 的叶子节点处。

在 InnoDB 存储引擎中， 聚簇索引 便是数据的存储方法（一切的用户记载都存储在了 叶子节点 ），也便是所谓的索引即数据，数据即索引。

5、二级索引

上边介绍的 聚簇索引 只能在查找条件是主键值时才干发挥作用，由于 B+ 树中的数据都是依照主键进行排序的。那假如咱们想以其他列作为查找条件该咋办呢？难道只能从头到尾沿着链表依次遍历记载么？

不，咱们能够多建几棵 B+ 树，不同的 B+ 树中的数据选用不同的排序规矩。比方说咱们用 c2 列的巨细作为数据页、页中记载的排序规矩，再建一棵 B+ 树，作用如下图所示：

【MySQL进阶】深入理解B+树索引底层原理

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

  • 运用记载 c2 列的巨细进行记载和页的排序，这包括三个方面的意义：

    • 页内的记载是依照 c2 列的巨细次序排成一个单向链表。
    • 各个寄存用户记载的页也是依据页中记载的 c2 列巨细次序排成一个双向链表。
    • 寄存目录项记载的页分为不同的层次，在同一层次中的页也是依据页中目录项记载的 c2 列巨细次序排成一个双向链表。

  • B+ 树的叶子节点存储的并不是完好的用户记载，而仅仅 c2列+主键 这两个列的值。

  • 目录项记载中不再是 主键+页号 的搭配，而变成了 c2列+页号 的搭配。

所以假如咱们现在想经过 c2 列的值查找某些记载的话就能够运用咱们刚刚建好的这个 B+ 树了。以查找 c2 列的值为 4 的记载为例，查找进程如下：

  • 确认 目录项记载 页

    依据 根页面 ，也便是 页44 ，能够快速定位到 目录项记载 地点的页为 页42 （由于 2 < 4 < 9 ）。

  • 经过 目录项记载 页确认用户记载实在地点的页

    在 页42 中能够快速定位到实践存储用户记载的页，可是由于 c2 列并没有仅有性束缚，所以 c2 列值为 4 的记载或许散布在多个数据页中，又由于 2 < 4 ≤ 4 ，所以确认实践存储用户记载的页在 页34 和 页35 中。

  • 在实在存储用户记载的页中定位到详细的记载

    到 页34 和 页35 中定位到详细的记载。

  • 可是这个 B+ 树的叶子节点中的记载只存储了 c2 和 c1 （也便是 主键 ）两个列，所以咱们有必要再依据主键值去聚簇索引中再查找一遍完好的用户记载。

6、回表

咱们依据这个以 c2 列巨细排序的 B+ 树只能确认咱们要查找记载的主键值，所以假如咱们想依据 c2 列的值查找到完好的用户记载的话，仍然需求到 聚簇索引 中再查一遍，这个进程也被称为 回表 。也便是依据 c2 列的值查询一条完好的用户记载需求运用到 2 棵 B+ 树！！！

那现在假定查询的 SQL 是这姿态的（咱们假定 student 中还有除了name，age，id 其他的字段 ）

SELECT * FROM student WHERE name='wx'

这种状况下，MySQL 就需求进行回表查询了。此刻 MySQL 就会依据定位到的某条记载中的 id 再次进行聚簇索引查找，也便是说会依据 id 去保护 id 的那么 B+ 树中查找。由于聚簇索引中数据页记载的是一条记载的完好的记载，这个进程就叫回表。

再强调下回表的意义：依据非主键索引查询到的成果并没有查找的字段值，此刻就需求再次依据主键从聚簇索引的根节点开端查找，这样再次查找到的记载才是完结的。

由于这种依照 非主键列 树立的 B+ 树需求一次 回表 操作才干够定位到完好的用户记载，所以这种 B+ 树也被称为 二级索引 （英文名 secondary index ），或许 辅佐索引 。

由于咱们运用的是 c2 列的巨细作为 B+ 树的排序规矩，所以咱们也称这个 B+ 树为为c2列树立的索引。

7、联合索引

咱们也能够同时以多个列的巨细作为排序规矩，也便是同时为多个列树立索引，比方说咱们想让 B+ 树依照 c2和 c3 列的巨细进行排序，这个包括两层意义：

  • 先把各个记载和页依照 c2 列进行排序。
  • 在记载的 c2 列相同的状况下，选用 c3 列进行排序

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

【MySQL进阶】深入理解B+树索引底层原理

如图所示，咱们需求注意一下几点：

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

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

  • 树立 联合索引 只会树立如上图相同的1棵 B+ 树。
  • 为c2和c3列别离树立索引会别离以 c2 和 c3 列的巨细为排序规矩树立2棵 B+ 树

三、InnoDB的B+树索引的注意事项

1、根页面万年不动窝

咱们前边介绍 B+ 树索引的时分，为了咱们了解上的便利，先把存储用户记载的叶子节点都画出来，然后接着画存储目录项记载的内节点，实践上 B+ 树的构成进程是这样的：

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

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

2、内节点中目录项记载的仅有性

咱们知道 B+ 树索引的内节点中目录项记载的内容是 索引列 + 页号 的搭配，可是这个搭配关于二级索引来说有点儿不谨慎。还拿 index_demo 表为例，假定这个表中的数据是这样的：

【MySQL进阶】深入理解B+树索引底层原理

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

【MySQL进阶】深入理解B+树索引底层原理

假如咱们想新刺进一行记载，其中 c1 、 c2 、 c3 的值别离是： 9 、 1 、 ‘c’ ，那么在修正这个为 c2 列树立的二级索引对应的 B+ 树时便碰到了个大问题：

咱们新刺进的这条记载的 c2 列的值也是 1 ，那咱们这条新刺进的记载到底应该放到 页4 中，仍是应该放到 页5 中啊？

为了让新刺进记载能找到自己在那个页里，咱们需求确保在B+树的同一层内节点的目录项记载除 页号 这个字段以外是仅有的。 所以关于二级索引的内节点的目录项记载的内容实践上是由三个部分构成的：

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

也便是咱们把 主键值 也增加到二级索引内节点中的目录项记载了，这样就能确保 B+ 树每一层节点中各条目录项记载除 页号 这个字段外是仅有的，所以咱们为 c2 列树立二级索引后的示意图实践上应该是这姿态的：

【MySQL进阶】深入理解B+树索引底层原理

这样咱们再刺进记载 (9, 1, ‘c’) 时，由于 页3 中存储的目录项记载是由 c2列 + 主键 + 页号 的值构成的，能够先把新记载的 c2 列的值和 页3 中各目录项记载的 c2 列的值作比较，假如 c2 列的值相同的话，能够接着比较主键值，由于 B+ 树同一层中不同目录项记载的 c2列 + 主键 的值肯定是不相同的，所以最终肯定能定位仅有的一条目录项记载，在本例中最终确认新记载应该被刺进到 页5 中。

四、总结

1、B+ Tree 原理

【MySQL进阶】深入理解B+树索引底层原理

2、详细查找流程

【MySQL进阶】深入理解B+树索引底层原理

【MySQL进阶】深入理解B+树索引底层原理