深入浅出——深入分析MySQL索引和B+树（基于InnoDB和MyISAM引擎分析），看完直呼：妙哉！

MySQL, 中间件, 后端开发 Karos

B+树和索引

浅析索引和B+树（初步了解，深入请从正言开始看）

索引是数据库提供的利于快速查询的机制，索引类似于书籍目录，当查询条件那一列建立了索引之后，那么数据库会去硬盘索引文件中找到满足查询条件的（数据的）物理位置， 根据位置就可以定位并获取到数据。

种类

2.2 索引的种类有哪些？(重点)

  1. 主键索引
  2. 唯一索引
  3. 单列索引
  4. 外键索引
    以上四种索引的命中规则，只要查询条件中包含索引列即可 where 列名=列值
  5. 组合索引: 命中规则是最左原则，比如对 a b c 三列创建组合索引，一旦使用到 a
    这列就会命中组合索引；
    Select from user where a=? 命中索引
    Select     from user where a=? and b=? 命中索引
    Select from user where a=? and b=? and c=? 命中索引
    Select     from user where b=? and c=? 没有命

sql调优，索引命中如何知晓

会开启 MySQL 慢查询，设置一个时间阈值，对耗时较长（超过设计阈 值）的 sql 语句进行优化，SQL 优化，其实就是从查询效率和消耗资源入手，核心原理就一 个，别让索引失效，避免全表扫描。

对查询进行优化，应尽量避免全表扫描，首先应考虑在 where 及 order by 涉及的列上建立索引。

优化后通过 explain 查看 SQL 优化后的效果。可以看到该 sql 的索引命中情况 (type 字段值类型为 “ALL”表明没有命中索引，进行的全表扫描；值为”where”命中索引 )

数据结构

Hash索引

哈希索引是基于哈希表实现，哈希表是一种key-value的数据结构，能够通过key以近乎O(1)的时间复杂度获取到value的值，因此，对于等值查询(=,in)的性能非常高。

索引的原理：Hash索引的底层原理是什么？ - 掘金 (juejin.cn)

B树

B 树（B-Tree）是一种多路平衡查找树，它的每个节点最多可以存储 m 个关键字（m ≥ 2），并且有 m + 1 个指向子树的指针，每个节点的关键字从小到大排列，且各个关键字之间相互独立，不重复。B 树具有如下特性：

  • 根节点至少有两个子女。
  • 每个中间节点都包含 k-1 个元素和 k 个孩子，其中 m/2 <= k <= m。
  • 每一个叶子节点都包含 k-1 个元素，其中 m/2 <= k <= m。
  • 所有的叶子节点都位于同一层。

image-20230617082647836

图解：什么是B树？（心中有 B 树，做人要虚心）一文读懂B-树 - 知乎 (zhihu.com)

B+树

img

img

(88条消息) 什么是B+树？（详细图解）_初念初恋的博客-CSDN博客

B*树

img

其他资料

一文详解 B-树，B+树，B*树 - 知乎 (zhihu.com)

正言

在前面我们只是简单的提了一下B+树，相信大家对B+树都有了一些了解，现在，让我们来深入探讨一下B+树。

好了，回归正题，前面我们讲了InnoDB数据页的结构，知道了在各个页之间会形成双向链表，而在页内，会以单链表的形式链接每一行

好了，说到链表，鼠鼠来打个广告，hhh

这是之前我写的关于链表的文章，感兴趣的同学可以看一看：【数据结构】异或双链表–拥有单链表的空间，效率如双链表 – Karos (wzl1.top)

要学一个东西，我们得先知道这个东西拿来干嘛的，对吧

而B+数我们主要就是用于快速查询，好了，下面我们来说一说 快速查询

没有索引的查找

在没有索引的条件下，我们使用条件对列进行精确匹配

select [列名] from 表名 where 列名 = xxx;

在一个页中查找

当表中的数据量较小的时候，我们只有一页，那么下面的查找分两种情况

  • 搜索主键
    根据row_id来找，我们相对熟悉了，不熟悉的可以看下我的这篇文章
    深入浅出——InnoDB页结构详解，慎入！ – Karos (wzl1.top)
    在页内对slot进行二分查找，找到对应的slot后再遍历

  • 搜索其他列
    由于没有像row_id那样建立页目录，所以对于非主键来说是无序的，不能用二分，所以这里只能遍历

    哎，要是这里能够将其他列和主键更直接的建立联系就好辣

在很多页中查找

在这种情况下我们要查找得分两个步骤，如下：

  • 定位到记录所在页
  • 在所在页中查找响应的记录

在没有索引的情况下，我们得先找到所在页，所以外层暴力循环，内层二分查找加暴力，$O(n^2logn)$，

wc，太慢了，好了，马上讲讲索引优化

索引

老规矩，先来提前说一下啊，建表

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)

下面是简化后的行格式示意图，其中record_type和next_record是记录头信息，c1列也是row_id，其他信息里面包含了事务ID和回滚指针和记录的其他信息，具体的可以看我之前的文章深入浅出——InnoDB记录结构详解，菜鸡看了直呼：能懂！ – Karos (wzl1.top)

image-20230616132400061

record_type：0 表示普通记录、 2 表示最小记录、 3 表示最大记录

next_record：到下一个记录的地址偏移量

为了节省点篇幅，在后面的内容中，我们把其他信息去掉

那么我们把多个记录放在页中的时候，结构图如下：

image-20230616133059791

索引方案的简单实现

由于按照某个搜索条件来查找记录，而页中的记录又没有对于对应字段的普遍规律，所以我们不得不遍历所有数据页。

那么如何快速定位呢？

其实我们可以联想一下页目录，靠主键值快速定位，那么我们这里可以按照之前页目录来实现一下，实现一个建议目录，这个目录满足下面的条件

  • 数据页中，用户记录中最大的主键值（注意，不包括最大记录和最小记录哦）必须小于下一个数据也中用户记录主键的最小值

那么我们先来insert一组数据（之前在讲页结构的时候，我们提过，一页的大小最大为16kb，但是这里我们为了后面方便描述，==假设一页最多只有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

那么，此时的内存结构是这样：

image-20230616152109008

可以看到，我们放到了10号页中（为什么是10号，而不是1号？呃呃呃，这个地方，其实页的编号是随机的，在内存中，页的地址也不是连续的，后面也是这样）

在此时如果我们要加入一条row_id为4的数据的话，就像这样

image-20230616152233602

这里也好是随机的，刚才已经说过了，这里反复强调一下，hhh

但是，这里为了我们方便查找，我们还得再插入之前其实还有个步骤，所以说上面的方式是错误的。

先把row_id=5的记录放到Page28中

image-20230616152543598

再将row_id=4的记录放到Page10中

image-20230616152612244

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

当我们插入多条数据后，就是这样的效果：

image-20230616152713066

但是这样仍然不方便管理，不知道大家有没有学过静态链表，其实这里可以用类似静态链表的方式来管理

没错，就是把记录每一个页的地址，下面说一说吧，其实你也可以认为是建了个hash

key是页的最小记录row_id，value是poage_no

image-20230616165815326

然后这里怎么做呢，还是二分，哈哈哈

对目录进行按key排序

比如你要找row_id=20的数据

第一步，20和5比较，往右划分

第二步，20比12大，选择12

通过Key=12找到page_no=9，再依次遍历（实际上是对page中的slot进行二分后再遍历，具体的过程之前讲页结构的时候已经讲过）

到这里，页的建议目录就做好了，没错，它就是==索引==

InnoDB中的实现方案

woc，这就是索引？也不难嘛！

轻轻松松拿捏！

image-20230616203833741

先别急，其实这个只是简单方案，存在一些问题

简单方案问题分析

  • 在写简单方案的时候，我们假定的是一个页面最多3条数据，但是在我们实际运用的情况下，一个页面其实是16k，数据很多，而且实际的页面也可能比较少，在这种情况下使用二分，比较鸡肋，查询效率也没有更好的优化
  • 如果我们把Page28中的记录全部删除，那么后面的目录项（注意，不是页面）都要往前移动，因为目录项2没有了存在的必要，牵一发而动全身不太可行（其实我想的是，你用链表实现不就解决了吗，不过事实确实如此，往下看！）

那么为了解决这类问题，InnoDB的开发者选择了这样一种设计方式：

  • 他们发现目录项和用户记录差不多，但是只有主键和页号，所以他们复用数据页来存储目录项
  • 为了和用户目录进行区分，他们把目录项的记录成为目录项记录

呃呃呃，说了句废话，其实就是记录头信息中record_type=1

那么这时候就变成了这个样子

image-20230616212645938

当然，目录项记录和用户记录除了结构上面的区别和记录类型的区别之外，还有一点，就算这个

image-20230617000057713

只有存储在目录项记录的最小记录才会有这个标记。

这个图似曾相识？（可以和B+树甚至于B*树联想一下）

当数据多的时候就变成了这样

image-20230617011557508

wc，那么当数据再多的时候，我们又会发现一个问题，我们有需要去记录 目录项记录的记录，或者说是索引，那么，程序员最喜欢的路子来了，套娃，没错按照之前的思想，在对目录项记录进行一个套娃

image-20230617011847640

比如我们要找220，那么首先会在Page33里面进行二分，然后进入1，在里面再次二分，进入209，然后再二分找到220所在的slot，最后再遍历，找到220.

B+树

细心的话可以发现，这里是我们之前讲过的B*树，我们可以简化一下，节点中的内容直接省略，然后第二层的前驱后继有点碍眼，我们去掉，最后简化，就成为了一颗B+树

image-20230617012858025

从上面可以看出，其实实际的用户记录全部存储在底层节点上，为了方便讨论，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 条记录。

但是，你的表里能存放 100000000000 条记录么？所以一般情况下，我们用到的 B+ 树都不会超过4层，那我们通过主键 值去查找某条记录最多只需要做4个页面内的查找（查找3个目录项页和一个用户记录页），又因为在每个页面内有所谓的 Page Directory （页目录），所以在页面内也可以通过二分法实现快速定位记录，这不是很牛么，哈哈！

聚簇索引

在上面我们讲到，B+树，现在我们针对B+树的特点来进行分析

  • 使用记录主键值大小进行记录和页的排序
    • 页内的记录是按照主键的大小顺序排成一个单向链表。
    • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
    • 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成 一个双向链表。
  • B+树叶子节点存储的是完整的用户记录

我们把具有这两种特性的 B+ 树称为 聚簇索引 ，所有完整的用户记录都存放在这个 聚簇索引 的叶子节点处。这 种 聚簇索引 并不需要我们在 MySQL 语句中显式的使用 INDEX 语句去创建（后边会介绍索引相关的语句）。

InnoDB 存储引擎会自动的为我们创建聚簇索引。另外有趣的一点是，在 InnoDB 存储引擎中， 聚簇索引 就是数 据的存储方式（所有的用户记录都存储在了 叶子节点 ），也就是所谓的索引即数据，数据即索引。

二级索引

通过上面的解释，不难发现，聚簇索引只有在搜索条件是主键的时候才能够使用，因为B+树是按照主键进行排序的

那么，如果我们要用其他键来查找呢，暴力遍历？

nonono！这里大不了再建几颗二叉树就可以了

image-20230617040627769

但是这颗二叉树，是非聚簇索引，来看看具体的区别吧（假设这里我们是以c2列进行查询的）：

  • 没有以主键大小进行记录排序和页排序
    • 页内记录按照c2字段进行排序，使用单链表链接
    • 存放c2记录的页也是按照c2列的大小进行排序形成双链表
    • 目录项记录，使用c2+page_no进行搭配，并且在同一层次中也是通过c2进行排序，使用双链表进行连接
  • 0层存储的并不是完整的用户记录，而是c2+row_id这两个列的值

为什么这里不直接存储用户数据？

答：您的空间真的大image-20230617043153032

具体的二分和聚簇索引差不多，这里就不再讲了，每次都要讲一遍浪费时间，这里其实拿到c2列和row_id以后，会根据row_id再到聚簇索引里面去找到完整的用户记录，这个过程叫做 回表

联合索引

顾名思义，就是联合查找的时候会用到的索引。

这里按照c2、c3的大小进行排序，对了，注意最左原则，所以应该先按照c2的大小进行排序

具体的步骤如下：

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

image-20230617044225191

这里其实也是个二级索引，只不过在记录、目录项中都加了c3字段，需要注意的是和分别对c2、c3两列进行二级索引是不同的

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

根节点不会移动

在之前介绍B+树的时候，我们先建立的叶子节点，在建立内节点，主要是为了方便大家理解，现在，我们来说一下，InnoDB实际建立B+树的过程：

  • 为某个表创建B+树索引的时候（聚簇索引是默认就有的），首席按都会为改索引创建一个根节点页面，这时候根节点中没有任何用户记录，也没有任何目录项记录
  • 随后插入用户记录是，先把用户记录存储的到根节点中
  • 当根节点中可用空间用完的时候再继续插入，那么会发生拷贝，将所有内容拷贝到PageA中，PageA在进行也分裂，生成PageB，根节点变为存储目录项记录的页，当要出现信的页分裂的时候，再按照如此流程

这里其实要提一下，一个B+树的根节点在被创建之后，是不会发生移动的，这样是为了保证在以后InnoDB在用到该表的同一个索引时，不用重复创建，直接通过重复的地方取出根节点的页号，从而访问这个索引

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

目录项记录由c2:page_no组成，但是c2并不是主键，可能出现相同情况

image-20230617064227410

如该表，为c2列建立B+树后是这样的

image-20230617064311189

小蝌蚪经历二分后，来到岔路口，我到底该进Page4还是Page5呢，进不了巢啊！

为了避上述懵逼问题发生，让新插入记录能够找到自己所在页，前提是需要保证B+树同一层节点目录项记录除了页号这个字段以外是唯一的，所以二级索引内节点其实有3部分组成：

  • 索引列的值
  • 主键值（没错，这里将主键值从0层拉上来了）
  • 页号

添加后也就是个这样

image-20230617065509902

这时候如果还需要继续插入c2=1的值的时候，由于索引相同，那么就可以通过比较主键大小来确定最后走向。

一个页面最少由两条记录

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

那如果一个大的目录中只存放一个子目录是个啥效果呢？那就是目录层级非常非常非常多，而且最后的那个
存放真实数据的目录中只能存放一条记录。费了半天劲只能存放一条真实的用户记录？逗我呢？所以 InnoDB 的
一个数据页至少可以存放两条记录，这也是我们之前唠叨记录行格式的时候说过一个结论（我们当时依据这个结
论推导了表中只有一个列时该列在不发生行溢出的情况下最多能存储多少字节，忘了的话回去看看吧）。

image-20230617070309391

MyISAM索引实现方案简介

MyISAM虽然也是采用的树形结构来存储，但实际，他是把索引和数据分开存储。

  • 将表中记录按照插入顺序单独存储与一个文件之中（称为数据文件）。该文件也没有数据页的划分，有多少记录塞多少记录就行，然后我们可以通过行号找到记录

MyISAM记录也需要记录头信息来存储一些额外数据，以前文为例，如图

image-20230617073003390

可惜的是，在我们插入数据是并没有可以按照主键大小排序，所以啊，这次不能使用二分法来进行查找辣

image-20230617073931623

那么MyISAM是如何实现快速查找的呢，总不可能暴力吧。

下面我们来说一说：

  • 使用MyISAM存储引擎的表会把所以i你信息你单独存储到另外一个文件中（索引文件）。

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

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

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

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

    MyISAM数据文件和索引文件：image-20230617080003602

导致SQL索引失效的情况

  1. where 子句中对字段进行 null 值判断。

  2. where 子句中使用!=或<>操作符。

  3. where 子句中使用 or 来连接条件。

  4. in 和 not in 也要慎用,尽可能用 between 取代

  5. 使用like进行模糊查询

    like要详细说一下，

    %x 索引失效

    %x% 索引失效

    x% 索引下推

    索引下推的下推其实就是指将部分上层（服务层）负责的事情，交给了下层（引擎层）去处理。

    MySQL大概架构

    • 在5.6之前，server层获取获取所有索引，再交给引擎层进行where判断，如图（回表这个词在后面会讲）

      未使用ICP

    • 在5.6之后，MySQL推出了 索引下推来对sql进行优化

      当存在索引的列做为判断条件时，MySQL server将这一部分判断条件传递给存储引擎，然后存储引擎会筛选出符合MySQL server传递条件的索引项，即在存储引擎层根据索引条件过滤掉不符合条件的索引项，然后回表查询得到结果，将结果返回给MySQL server。

      使用ICP的示意图

      索引下推使用条件

      • 只能用于range、 ref、 eq_ref、ref_or_null访问方法；
      • 只能用于InnoDB和 MyISAM存储引擎及其分区表；
      • 对InnoDB存储引擎来说，索引下推只适用于二级索引（也叫辅助索引）;

      索引下推的目的是为了减少回表次数，也就是要减少IO操作。对于InnoDB的聚簇索引来说，数据和索引是在一起的，不存在回表这一说。

      • 引用了子查询的条件不能下推；
      • 引用了存储函数的条件不能下推，因为存储引擎无法调用存储函数。

      相关系统参数

      索引条件下推默认是开启的，可以使用系统参数optimizer_switch来控制器是否开启。

      查看默认状态：

      mysql> select @@optimizer_switch\G;
*************************** 1. row ***************************
@@optimizer_switch: index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on,index_condition_pushdown=on,mrr=on,mrr_cost_based=on,block_nested_loop=on,batched_key_access=off,materialization=on,semijoin=on,loosescan=on,firstmatch=on,duplicateweedout=on,subquery_materialization_cost_based=on,use_index_extensions=on,condition_fanout_filter=on,derived_merge=on
1 row in set (0.00 sec)

      切换状态：

      set optimizer_switch="index_condition_pushdown=off";
set optimizer_switch="index_condition_pushdown=on";

部分内容参考于《MySQL是怎样运行的：从根儿上理解MySQL》、五分钟搞懂MySQL索引下推 - 掘金 (juejin.cn)

  • 微信或QQ扫一扫

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

→ 目录