MySQL索引剖析【了解背后的数据结构】

MySQL官方对索引的定义为：索引是帮助MySQL高效获取数据的数据结构。

即索引是数据结构，可以简单的理解为“排好序的快速查找数据结构”，满足特定查找算法，这些数据结构以某种方式指向数据。索引的作用相当于图书的目录，可以根据目录中的页码快速查找到所需的内容。

在MySQL中，索引是在存储引擎中实现的，先在索引中找到对应值，然后根据匹配的索引记录找到对应的行。首先，我们需要花5分钟搞懂MySQL存储引擎

常用索引概念

聚簇索引 和 非聚簇索引（二级索引）是数据库中的两种索引类型，他们在组织和存储数据时有不同的方式。

聚簇索引 🎉

聚簇索引，简单点理解就是将数据与索引放到了一起，找到索引也就是找到了数据。对于聚簇索引来说，它的非叶子节点上存储的是索引字段的值，而它的叶子节点上存储的是这条记录的数据。

在InnoDB中，聚簇索引指的是按照每张表的主键构建的一种索引方式，它是将表数据按照主键的顺序存储在磁盘上的一种方式。这种索引方式保证了行的物理存储顺序与主键的逻辑顺序相同，因此查找聚簇索引的速度非常快。

如果我们在表结构中没有定义主键，那怎么办呢？

其实，数据库中的每行记录中，除了保存了我们自己定义的一些字段以外，还有一些重要的 db_row_id字段，其实他就是一个数据库帮我添加的隐藏主键，如果我们没有给这个表创建主键，会选择一个不为空的唯一索引来作为聚簇索引，但是如果没有合适的唯一索引，那么会以这个隐藏主键来创建聚簇索引。

非聚簇索引（二级索引）

非聚簇索引，就是将数据与索引分开存储，叶子节点存储着指向数据页数据行的逻辑指针。

在Innodb中，非聚簇索引（Non-clustered Index）是指根据非主键字段创建的索引，也就是通常所说的二级索引。它不影响表中数据的物理存储顺序，而是单独创建一张索引表，用于存储索引列和对应行的指针。

在InnoDB中，主键索引就是聚簇索引，而非主键索引，就是非聚簇索引，所以在InnoDB中：

• 对于聚簇索引来说，他的非叶子节点上存储的是索引值，而它的叶子节点上存储的是整行记录。
• 对于非聚簇索引来说，他的非叶子节点上存储的都是索引值，而它的叶子节点上存储的是主键的值+索引值。

所以，通过非聚簇索引的查询，需要进行一次回表，就是先查到主键ID，在通过ID查询所需字段。

数据结构选择

从MySQL的角度讲，不得不考虑一个现实问题那就是 磁盘IO，也就是数据页从磁盘加载至内存。如果我们能让索引的数据结构尽少的减少IO次数，那对于查询的时间消耗也是最小的。

首先说明下MySQL的索引主要是基于Hash表或者B+树～

Hash结构 ⭐️

Hash 本身是一个算法，相同的输入永远可以得到相同的输出。

数据结构定义为：给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。具有以下特点：

• Key-Value存储结构，查询的复杂度为O(1)
• 无法用于范围查询、模糊、排序情景
• 当数据量过大时，容易发生Hash冲突

Hash索引适用存储引擎如表所示：

索引/存储引擎	MyISAM	InnoDB	Memory
Hash索引	不支持	不支持	支持

Hash结构效率高，那为什么索引结构要设计成树型呢？

• 首先，Hash 索引仅能满足等值查找（=、!=、in）。如果进行范围查询，时间复杂度会退化至O(n)，而树型的“有序”特性，依然能够保持O(log2N)的高效率。
• 其次，hash表中数据是无序的，在进行 order by 时，需要对数据重新排序。
• 最后，当数据量过大时，Hash冲突较多，需要遍历桶中行指针来进行一一比较，消耗了大量性能。

上图中，hash函数有可能将两个不同的关键字映射到相同的位置，这叫做 hash冲突（hash碰撞） ，在数据库中一般采用 链接法 来解决。在链接法中，将散列到同一槽位的元素放在一个链表中。

InnoDB支持 自适应Hash索引

另外，InnoDB本身虽然不支持Hash索引，但是提供 自适应Hash索引。在InnoDB中，如果某个数据经常被访问，当满足一定条件的时候，就会将这个数据页的地址存放到Hash表中。在下次同样查询条件的时候，就可以直接找到这个页所在位置，这样B+树也具备了Hash索引的优点。

我们可以通过 innodb_adaptive_hash_index 变量来查看是否开启了自适应 Hash，比如：

mysql> show variables like '%innodb_adaptive_hash_index';
+----------------------------+-------+
| Variable_name              | Value |
+----------------------------+-------+
| innodb_adaptive_hash_index | ON    |
+----------------------------+-------+
1 row in set (0.06 sec)

有序数组

数组中的数据是按关键字 升序（或降序）排列的，具有以下特征：

• 更新代价大，插入和删除操作需要移动大量数据。当数据个数不确定时，难以确定存储空间的容量
• 无须为表示线性表中数据之间的逻辑关系而增加额外的存储空间。通过二分法，时间复杂度为（O(logN)）查找，适用于等值，范围查找

class Solution {public int search(int[] nums, int target) {int l = 0;int r = nums.length;while(l <= r) {int i = (r-l)/2;if(nums[i] == target) {return i;} else if (nums[i] > target) {r = i;} else if (nums[i] < target) {l = i ;}}return -1;}
}

二叉搜索树

如果我们利用二叉树作为索引结构，那么磁盘的IO次数和索引树的高度是相关的。为什么这样说呢，我们先来看看二叉树的特征：

• 一个节点只能有两个子节点，并且子节点也为二叉树；
• 若它的左子树不空，则左子树上所有节点的值均小于它根节点的值；
• 若它的右子树不空，则右子树上所有节点的值均大于它根节点的值。

搜索某个节点和插入节点的规则一样，我们假设插入的数值为key

1. 如果 key 大于 当前节点，则在右子树中进行查找；
2. 如果 key 小于 当前节点，则在左子树中进行查找；
3. 如果 key 等于 当前节点，返回当前节点即可。

举个例子，我们以数列（34, 22, 89, 5, 23, 77, 91）构造一棵二叉搜索树如下图，此时查询某个值，我们仅需io 3次即可

但是在深度比较大时，比如我们给出的数据顺序是（5, 22, 23, 34, 77, 89, 91）,如下图。此时性能已经退化成链表一致，时间复杂度为O(n)

为了提高查询效率，就需要 减少磁盘IO数 。为了减少磁盘IO的次数，就需要尽量 降低树的高度 ，需要把原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好。

AVL树（平衡二叉搜索树）

为了防止二叉树像一个「链表」一样存在，于是在 1962 年，一个姓 AV 的大佬（G. M. Adelson-Velsky） 和一个姓 L 的大佬（ Evgenii Landis）提出「平衡二叉树」（AVL） 。奇特性为：任何一个节点的左子树或者右子树都是「平衡二叉树」（左右高度差小于等于 1）

我们发现如上图五层仅能存储31节点，如果使用平衡三叉树仅需四层即可，那M叉呢？我们需要把树再变的"矮胖"些！

B-Tree（多路平衡查找树）

B树中所有节点的孩子个数的最大值称为B树的阶，用m表示。一颗m阶B树是一颗空树或者是符合一系列条件的m叉树。具有以下特征：

• m阶B树，每个节点最多有m棵子树，那么该节点最多有m-1个关键字(元素)；（m阶是代表每个节点最多有m个分支/子树）
• 根节点要么没有子树，要么至少有两个子树；
• 除根节点外，其它非叶子节点至少有m/2(向上取整)棵子树，也就是至少有 【m/2(向上取整）-1 】个关键字；
• 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它；
• 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同；
• 在 B 树中，节点存储的是键值和对应的数据
  • 内部节点包含一组键值和指向子节点的指针
  • 叶子节点包含键值和对应的数据

如图是一棵 3 阶的 B 树。我们可以看下磁盘块 2，里面的关键字为（8，12），它有 3 个孩子 (3，5)，(9，10) 和 (13，15)。我们发现(3，5) 小于 8，(9，10) 在 8 和 12 之间，而 (13，15) 大于 12，完全符合刚才我们给出的特征。

然后我们来看下如何用 B 树进行查找。假设我们想要 查找的关键字是 9 ，那么步骤可以分为以下几步：

1. 我们与根节点的关键字 (26，35）进行比较，9 小于 26 那么得到指针 P1；

2. 按照指针 P1 找到磁盘块 2，关键字为（8，12）。因为 9 在 8 和 12 之间，所以我们得到指针 P2；

3. 按照指针 P2 找到磁盘块 6，关键字为（9，10），然后我们找到了关键字 9。

B 树相比于平衡二叉树来说磁盘 I/O 操作要少 ，在数据查询中比平衡二叉树效率要高。所以只要树的高度足够低，IO次数足够少，就可以提高查询性能 。

但是我们发现B 树的非叶子节点和叶子节点都存储数据，导致每个磁盘块能够容纳的键值对数量较少。除此之外，由于数据分布在内部节点和叶子节点上，执行范围查询时需要在多个层级上进行搜索和遍历。在执行顺序访问操作时需要进行多次随机磁盘访问。

B+Tree ⭐️

B+树是B树的一些变形，它具有以下特点：

• m阶B+树，每个分支节点最多有m叉(与B树相同)；
• 根节点要么没有子树，要么至少有两个子树(与B树相同)；
• 除根节点外，其它每个分支节点至少有m/2(向上取整)棵子树；
• 有n棵子树的节点恰好有n个关键字(B树是有n-1个关键字才有n个节点)；
• 所有内部节点中仅包含它的各个子节点中最大关键字和指向子节点的指针。
• 所有叶子节点包含全部关键字和记录数据，而且叶子节点按关键字大小顺序排列。并将所有叶子节点链接起来⭐️；

MySQL中索引的实现

InnoDB 索引实现

接下来通过推演的方式讲解 InnoDB中的索引实现

页和记录的关系

CREATE TABLE index_demo(c1 INT,c2 INT,c3 CHAR(1),PRIMARY KEY(c1)
) ROW_FORMAT = C

我们新建了 index_demo 表，表中有2个INT类型的列，1个CHAR(1)类型的列，并且设定c1列为主键。指定 compact 行格式来实际存储记录的。为了便于理解，简化了index_demo表的行格式示意图：

• record_type ：记录头信息的一项属性，表示记录的类型。

  • 0表示普通记录
  • 1表示B+树非叶节点记录
  • 2表示最小记录
  • 3表示最大记录。

• next_record：它表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量。（下面示意图中我们用

  箭头来表明下一条记录是谁）

• 各个列的值 ：这里只记录在 index_demo 表中的三个列，分别是 c1 、 c2 和 c3 。

• 其他信息 ：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息

那将记录格式示意图的其他信息项暂时去掉并把它竖起来的效果就是这样

它们在页中是这样（为了便于理解，我们示意图中每页仅3条记录）：

我们知道的，数据页是InnoDB存储引擎中用于存储数据的基本单位。它是磁盘上的一个连续区域，通常大小为16KB（可以通过配置修改）。意味着每次读写都是以16KB为单位的，一次磁盘到内存的读取是16KB，一次从内存到磁盘的持久化也是16KB。

首先，一个简单的索引

在不设置索引之前根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？因为各个页中的记录并没有规律，我们并不知道我们的搜索条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。

现在我们建立一个目录用于快速定位数据页，如同下图

以 页28 为例，它对应 目录项2 ，这个目录项中包含着该页的页号 28 以及该页中用户记录的最小主键值 5 。我们只需要把几个目录项在物理存储器上连续存储（比如：数组），就可以实现根据主键值快速查找某条记录的功能了。比如：查找主键值为 20 的记录，具体查找过程分两步：

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

2. 再根据前边说的在页中查找记录的方式去 页9 中定位具体的记录。

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

那我们把前边使用到的目录项放到数据页中的样子就是这样（假设只能存储4条目录项记录）

我们新分配了一个编号为30的页来专门存储目录项记录。目录项记录 和 普通的用户记录 是有些不同的

• 两者的record_type 不同，目录项记录的 record_type 值是1，而 普通用户记录 的 record_type 值是0。
• 目录项记录只有 主键值和页的编号 两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列 ，另外还有InnoDB自己添加的隐藏列。

除此之外，记录头信息里还有一个叫 min_rec_mask 的属性，当前记录是目录项页中主键值最小时值是为1，其他记录该值都是 0 。

迭代两次：多个目录项纪录的页

如上图，我们插入了一条主键值为320的新记录，此时前三个用于存储记录的页容量已满（前边假设只能存储3条数据记录），需要新生成页31用于存储该用户记录。此时，原先存储目录项记录的 页30的容量已满 （前边假设只能存储4条目录项记录），所以不得不需要一个新的 页32 来存放 页31 对应的目录项。

此时我们再查找主键值为20的用户记录大致需要3个步骤

1. 首先需要确定目录项记录页，根据 二分法 快速确定出在 主键值为20的记录页的目录项页30（因为 1 < 20 < 320 ）
2. 再通过目录项页 确定用户记录真实所在的页 9（因为 12 < 20 < 209 ）
3. 在真实存储用户记录的页中定位到具体的记录

迭代三次：目录项记录页的目录页

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

嗯哼，有没有人发现类似于某种数据结构了嘛？

没错，那就是 B+ 树。B+树的每个节点都对应着一个数据页，包括根节点、非叶子节点和叶子节点。B+树通过节点之间的指针连接了不同层级的数据页，从而构建了一个有序的索引结构。

• B+树的非叶子节点对应着数据页，其中存储着主键+指向子节点（即其他数据页）的指针。

• B+树的叶子节点包含实际的数据行，每个数据行存储在一个数据页中。

通过B+树的搜索过程，可以从根节点开始逐层遍历，最终到达叶子节点，找到所需的数据行所在的数据页。而数据页是存储数据行的实际物理空间，以页为单位进行磁盘读写操作。

一般情况下，我们用到的B+树都不会超过4层 ，因为以上为了便于理解我设定了非常极端的假设：存放用户记录的页 最多存放3条记录 ，存放目录项记录的页 最多存放4条记录 。其实真实环境中一个页存放的记录数量是非常大的，假设所有存放用户记录的叶子节点代表的数据页可以存放 100条用户记录 ，所有存放目录项记录的内节点代表的数据页可以存放 1000条目录项记录 ，那么：

• 如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放 100 条记录；
• 如果B+树有2层，最多能存放 1000×100=10,0000 条记录；
• 如果B+树有3层，最多能存放 1000×1000×100=1,0000,0000 条记录。
• 如果B+树有4层，最多能存放 1000×1000×1000×100=1000,0000,0000 条记录。请问，咱们的表里能存放10亿条记录嘛？

通过这种方式，InnoDB利用B+树和数据页的组合，实现了高效的数据存储和检索。B+树提供了快速的索引查找能力，而数据页提供了实际存储和管理数据行的机制。它们相互配合，使得InnoDB能够处理大规模数据的高效访问。

MyISAM 索引实现

MyISAM是采用了一种索引和数据分离的存储方式，也就是说，MyISAM中索引文件和数据文件是独立的。

因为文件独立，所以在MyISAM的索引树中，叶子节点上存储的并不是数据，而是数据所在的地址。所以，MyISAM 存储引擎实际上不支持聚簇索引的概念。在 MyISAM 中，所有索引都是非聚簇索引。

也就是说，在MyISAM中，根据索引查询的过程中，必然需要先查到数据所在的地址，然后再查询真正的数据，那么就需要有两次查询的过程。而在InnoDB中，如果基于聚簇索引查询，则不需要回表，因为叶子节点上就已经包含数据的内容了。

因为MyISAM是先出的，正式因为存在这个问题，所以后来的InnoDB 引入了聚簇索引的概念提高了数据检索的效率，特别是对于主键检索。

InnoDB 和 MyISAM 对比

首先，MyISAM的索引方式都是非聚簇的，与InnoDB包含1个主键聚簇索引。

1. InnoDB存储引擎中，我们只需要根据主键值对 聚簇索引 进行一次查找就能找到对应的记录，而在MyISAM 中却需要进行一次 回表 操作 。
2. InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是 分离的 ，索引文件仅保存数据记录的地址。
3. InnoDB的非聚簇索引data域存储相应记录 主键的值 ，而MyISAM索引记录的是 地址 。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域。
4. MyISAM的回表操作是十分 快速 的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。
5. InnoDB要求表 必须有主键 （ MyISAM可以没有 ）。如果没有显式指定，则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。