Mysql 为什么要选取 b+ 树作为索引的底层数据结构

在讨论这个问题之前我们先看一个例子,假设有一张 user 表,表里面有 5 个字段,分别是 id、name、age、height、gender,其中 id 为主键

在没有索引的情况下,如果要执行 select * from user where height = 175 这样的一条 SQL,Mysql 底层是怎么做的呢?

首先需要从表的第一行开始,然后一行一行的遍历比对,查看是否存在 height 的值等于 175 的行记录,当比对到第三行的时候终于找到了 height = 175 的数据

找到了 height = 175 的行记录之后整个执行流程就结束了吗?

答案是否定的,因为你不能确定这张表里面还有没有其它的行记录中存在 height = 175 的情况,所以你还得继续一行一行的遍历,直到把整张表全部遍历完为止,找出所有符合 height = 175 的数据,这整个过程就称为 全表扫描,幸运的是现在表里面只有 10 行数据,等你遍历完 10 行记录拿到你想要的结果并返回的时候,耗费的时间并不会很长,可是如果你的表里面有几百万的数据,你这样做全表扫描性能是不是会很差呢?

那么有没有什么比较好的方法解决呢?

学过数据结构的同学应该知道,利用数据结构的特性可以帮助我们大大减少查找遍历次数,索引就是使用比较巧妙的数据结构来帮助我们进行快速查找的

先看一下索引的定义

索引是帮助 Mysql 高效获取数据的一种有序的数据结构(索引是一种数据结构,并且这种数据结构还是按照某种规则排好了序的)

既然索引是一种数据结构,那么 Mysql 索引选取的到底是哪种数据结构呢?

索引可选的数据结构有

• 二叉树
• 红黑树
• 哈希表
• B 树
• B+ 树

1、二叉树

假设我们以 height 作为索引,使用二叉树作为索引的底层数据结构,看看需要多少次才能获取到需要的数据

下面的图是通过国外的一个模拟数据结构的网站生成出来的二叉树结构(https://www.cs.usfca.edu/~galles/visualization/Algorithms.html)

通过上图可以得知,二叉树这种数据结构确实可以减少查询的次数,根据图示最极端的情况就是查询 height = 171 和 height = 185 的数据,会进行 5 次遍历查找,虽然遍历的次数很多,但是想比于全表扫描的 10 次来说还是快上不少的,那么 Mysql 底层的数据结构就是二叉树吗?

答案是否定的,因为二叉树作为索引的底层数据结构会存在如下弊端

• 大数据量的情况下,树的高度会很高,需要遍历的次数依旧很多
• 某一些极端的情况下二叉树会退化成单向链表

假设以 id 作为索引,二叉树就退化成了单向链表了,如果想查询的数据在链表的尾部,那么就又回到了全表扫描的这种情况了

2、红黑树

为了避免二叉树出现单边增长的情况,这个时候你又想起来一种自平衡的二叉树(红黑树),那么我们继续看看索引如果选择红黑树作为底层数据结构又是一个什么情况

依旧以 height 作为索引,利用红黑树这种数据结构来构建索引

使用红黑树之后看起来确实清爽一些,最差的情况都只需要遍历 4 次就可以拿到自己想要的数据了,比起全表扫描、普通二叉树来说遍历的次数都减少了,那么 Mysql 是不是使用的红黑树呢?

很不幸也不是红黑树,虽然红黑树的查找性能相比于全表扫描、普通二叉树来说确实提高了,但还是会面临大数据量的情况下查找性能低下的问题,虽然红黑树可以通过旋转自平衡来降低树的高度,但是能力也是有限的,试想一下一颗完美的平衡二叉树,类似于下图这个样子的

如果我有 一百万 的数据,那么树的层高是多少?

假设树的层高为 n ,由 2^n - 1 = 1000000,可以得出 19 < n < 20 ,也就是说存放 1000000 的数据红黑树高度为 20,万一要查找的数据就在最底层的子节点上,那么你就需要遍历 20 次,也就是需要进行 20 次磁盘 IO 才能获取到你想要数据,想想都觉得恐怖!

3、哈希表

哈希表就是采用一定的 Hash 算法,将 key 换算成新的 Hash 值,映射到对应的槽位上,然后存储在 Hash 表中;如果两个(或多个) key 映射到一个相同的槽位上,他们就产生了 Hash 冲突(也称为 Hash 碰撞),可以通过链表来解决

Hash 是一种非常快的查找方法,一般在不发生 Hash 碰撞的情况下查找的时间复杂度为 O(1),查询效率极高,但是由于不支持范围查询(>、<、between)、不支持利用索引排序等条件的限制,InnoDB 并没有采用 Hash 表作为索引的底层数据结构,在 MySQL 中支持 Hash 索引的是 Memory 存储引擎,虽然 InnoDB 存储引擎没有选用 Hash 表作为索引的底层数据结构,但是在某些场景下 InnoDB 具有自适应 Hash 功能,具体的,InnoDB 会监控对表上索引的查找,如果观察到某些索引被频繁访问,索引成为热数据,建立哈希索引可以带来性能的提升,那么就建立哈希索引,这就是所谓的自适应(adaptive).自适应哈希索引通过缓冲池的 B+ 树构造而来,因此建立的速度很快.而且不需要将整个表都建立哈希索引,InnoDB 会自动根据访问的频率和模式来为某些页建立哈希索引,从而提升查询效率.

4、B 树

B-Tree: B 树是一种多叉路平衡查找树,相对于二叉树,B 树每个节点可以有多个分支,即多叉,以一颗最大度数 (max-degree) 为 4 (4阶) 的 B 树为例它有以下特点

• 4 阶的 B 树,每一个节点最多存储 4 个 key,对应 5 个 指针

• 一旦节点存储的 key 数量到达 4 就会裂变,中间元素向上分裂

• 在 B 树的叶子节点和非叶子节点都会存放数据

5、B+ 树

Mysql 索引底层数据结构使用的是 B+ 树,不过它与经典的 B+ 树有略微的区别,经典的 B+ 树叶子节点通过一个单向的指针进行连接,节点之间形成一个单向链表,而 Mysql 索引的 B+ 树叶子节点是通过双向的指针进行连接,从而叶子节点形成的一个双向链表,虽然结构相较于经典 B+ 树发生了变化,但是它还是称为 B+ 树(可以这么理解,把 B 树看做是接口,经典的 B+ 树和 Mysql 改造后的 B+ 树看做是具体的实现类,虽然实现方式不同,但是都是在原来的 B 树上进行的改造,所以它们都统称为 B+ 树)

那么问题来了,为什么 Mysql 要使用 B+ 树来作为索引的底层数据结构呢?

相比于 二叉树、红黑树、B 树来说,B+ 树能存储更多的数据,在讨论 B+ 树能存储多少数据之前,我们先看一下 Innodb 的逻辑存储结构

表空间(tableSpace)对应的就是 innodb 的 .ibd 文件,一个表空间包含若干个数据段(segment),一个段中包含若干个区(extent),一个区的大小默认为 1 M,而一个区中又有多个页(page),一个 page 的大小是 16 KB,也就是一个 extent 里面包含了 64 个 page,而一个 page 又有多条行记录,行记录里面就是我们表里面的字段,一条行记录里面除了包含我们建立的字段,还有 3 个隐藏的字段(row_id、trx_id、roll_pointer)

page 是 Mysql 与磁盘交互的最小单位,可以通过如下命令进行查看

SHOW GLOBAL STATUS LIKE 'Innodb_page_size';

16384 B = 16 * 1024 B

Mysql 为什么把 page_size 设置为 16 KB 呢?

1、16 KB 可以满足存储的数据量要求

Mysql 非叶子节点、叶子节点的数据都是通过 page 来存储的,假设索引字段的类型为 Bigint(8 个字节),一个指针的大小为 6 个字节,对于 B+ 树来说,一个 page 能存储的 key 和指针的数量为 16384 / 14 = 1170,指针的数量为 1170 + 1 = 1171

以上图两层的 B+ 树为例:第一层有 1171 个指针指向第二层,那么第二层就会有 1171 个节点,每个节点同样是以 page 来存储的,假设一行数据的大小是 1KB,那么一个节点大致可以存储 16 行记录,所以两层的 B+ 树可以存储的数据行为 1171 * 16 = 18736,同理一个 3 层的 B+ 树可以存储 1171 * 1171 * 16 = 21939856 行数据

2、内存和磁盘交互是有规则的

磁盘 IO 跟内存交互的单位是 4KB,即一次可能读取 4KB 的数据,可能有时候有一些局部读取的原理可能会取几十 KB(4的整数倍)取个16KB，24KB 也是可以的,假设 page 设置的过大,那么一次性从磁盘加载到内存中的数据量就会很大,首先内存是有大小的,其次加载这么多的数据,一次磁盘 IO 耗时是相当恐怖的,这还仅仅只是一张表的情况,如果数据库中所有的表都加载进内存,你的内存早就被撑爆了

B+ 树和 B 树有什么区别?

1、非叶子节点没有数据,数据都挪到叶子节点

2、叶子节点之间通过指针连接形成双向链表

为啥 data 元素都挪到叶子节点?

可以参考上图,非叶子节点的数据挪走了之后,非叶子节点就可以存储更多的 key 和指针,指针越多,树的分叉就越多,那么同等树高的情况下可以存储更多的行记录

为啥要在叶子节点上使用双向指针?

是为了提升范围查询的性能和方便排序.例如查询 height > 175 的数据,可以通过索引的 root 节点定位到 175 这个元素,然后根据指针从前往后找,如果想查询 height < 175 的数据,就可以定位到 175 这个节点,然后从后往前找,同时也可以根据双向指针正序、倒序排序