侧边栏壁纸
博主头像
Ysfun博主等级

一名热爱技术、喜欢折腾的小小程序猿

  • 累计撰写 42 篇文章
  • 累计创建 14 个标签
  • 累计收到 21 条评论

目 录CONTENT

文章目录

MySQL:总算把B+树搞明白了

Ysfun
2022-06-17 / 0 评论 / 1 点赞 / 66 阅读 / 4,178 字

1. MySQL索引为何使用B+树

MySQL索引是提升数据库查询效率的最强武器,那么为何索引能够提升数据库查询速度?为何MySQL采用B+树来实现索引?

1. 为何索引能提升查询性能?

第一个问题可以用一个比较通俗的说法来回答,数据库索引相当于给一本书加了一个目录。

问题来了,为什么有了”目录“就能提升数据库查询效率呢?

比较简单的解释,通过目录查找的过程可以近似理解为二分查找查找的过程,我们知道二分查找可以将遍历查询的时间复杂度从o(n)降为o(log n)

数据库利用索引查询数据的具体过程,后文会进行详细描述。

2. 为何MySQL不用二叉树来实现索引?

我们知道通过排序二叉树(也叫二分查找树)可以实现o(log n)的时间复杂度进行查询,相比于o(n)的时间复杂度已经有了极大的提升。

MySQL为何没有采用二分查找树作为索引呢?

要解答这个问题,就必须介绍那些因素对数据库查询过程中起到了制约作用。我们都知道CPU的数据处理性能远远比磁盘I/O的速度快,因此要提升查询性能,较少I/O次数就至关重要了。通过查找的过程,树的层数基本就等于磁盘I/O的次数,因此要尽可能降低树的高度。

我们知道,对于一颗满二叉树,假设树的高度为n,那么这棵树的节点个数为2^n-1个,即对于一个含有n个节点的二叉树,其高度至少为log n,对于数据库百万千万的数据,如果要经历log n次的I/O,其查询耗时则可想而知。

至此,我们知道,之所以不采用二叉树来实现数据库索引,是因为二叉树的高度太大,而每次查询经历的磁盘I/O的次数和树的高度相等,导致查询速度过慢。

3. 为何使用B+树?

前面提到,为了减少磁盘I/O的次数,就必须降低树的高度,比较容易想到降低树的高度的方法:增加树的分叉!不难计算,对于一颗具有n个节点的k叉树,其树的高度为logknlog_k n

多叉树里有两种较为常见的,分别为B-树(又称为B树)和B+树。这二者的区别可参考B+树和B树的区别,我们这里主要提三点:

  • B+树的data数据只存放在叶子节点,非叶子节点只存储树的索引信息;而B-树的叶子节点和非叶子节点都存放实际的数据。
  • B+树的叶子节点增加了前后指针,分别指向前一个叶子节点和后一个叶子结点,可以理解为维护了一个双向链表。
  • 由于B+树的实际数据都保存在叶子结点,且所有叶子节点都在同一层,所以使用B+树进行查询所经历的I/O次数固定为树的高度;而由于B-树非叶子节点也存放数据,则其查询时间是不固定的。

B+树和B-树中,为何选择B+树?

我们知道要提升数据库查询效率,就要尽可能降低树的高度,即对应相同的数据量,应尽可能使树变得”胖“一些。由于B+树非叶子节点不存储实际数据,对于一个非叶子节点(MySQL数据是分页保存,每页默认16kB,即树的每个节点的大小为16kB),能够有更多的”分叉“,因此可以让树变得更”宽矮“一些,即相比于B-树,同样高度的B+树能保存更多的数据页,因此MySQL采用B+树来实现索引。

2. InnoDB是如何存储数据的?

MySQL 支持多种存储引擎,不同的存储引擎,存储数据的方式也是不同的,我们最常使用的是 InnoDB 存储引擎,下面介绍下InnoDB 是如何存储数据的。

磁盘读写的最小单位是扇区,扇区的大小只有 512B 大小,操作系统一次会读写多个扇区,所以操作系统的最小读写单位是块(Block)。Linux 中的块大小为 4KB,也就是一次磁盘 I/O 操作会直接读写 8 个扇区。同样的,MySQL保存的记录是以「行」为单位的,但是数据库的读取并不以「行」为单位,否则一次读取(也就是一次 I/O 操作)只能处理一行数据,效率会非常低。InnoDB 的数据是按「数据页」为单位来读写的,也就是说,当需要读一条记录的时候,并不是将这个记录本身从磁盘读出来,而是以页为单位,将其整体读入内存。

InnoDB保存的数据文件是后缀为.ibd的文件,其含义是InnoDB data文件,又叫表空间。虽然在数据表里,它们看起来是挨在一起的。但实际上在xx.ibd里他们被分成很多小份的数据页,每份默认大小为16kB。类似如下结构:

数据库I/O操作的最小单位是InnoDB 数据页的默认大小是 16KB,意味着数据库每次读写都是以 16KB 为单位的,一次最少从磁盘中读取 16K 的内容到内存中,一次最少把内存中的 16K 内容刷新到磁盘中。

数据页主要包括七个部分,数据页结构图如下:

各部分的作用:

在 File Header 中有两个指针,分别指向上一个数据页和下一个数据页,连接起来的页相当于一个双向的链表,如下图所示:

采用链表的结构是让数据页之间不需要是物理上的连续的,而是逻辑上的连续。

数据页中的记录按照「主键」顺序组成单向链表,单向链表的特点就是插入、删除非常方便,但是检索效率不高,最差的情况下需要遍历链表上的所有节点才能完成检索。

因此,数据页中有一个页目录,起到记录的索引作用,就像我们书那样,针对书中内容的每个章节设立了一个目录,想看某个章节的时候,可以查看目录,快速找到对应的章节的页数,而数据页中的页目录就是为了能快速找到记录。通过页目录可以使数据页内查询记录的时间复杂度从o(n)变为o(log n),提升页内查询效率。

3. B+树是如何进行查询的?

InnoDB中一个数据页默认的大小为16 kB,当面对大数据量时,需要多个数据页共同存放数据,如何建立合适的索引,才能快速的定位到记录所在的页。因此,MySQL采用B+树作为索引。

InnoDB 里的 B+ 树中的每个节点都是一个数据页,结构示意图如下:

通过上图,我们看出 B+ 树的特点:

  • 只有叶子节点(最底层的节点)才存放了数据,非叶子节点(其他上层节)仅用来存放目录项作为索引。
  • 非叶子节点分为不同层次,通过分层来降低每一层的搜索量;
  • 所有节点按照索引键大小排序,构成一个双向链表,便于范围查询;

我们再看看 B+ 树如何实现快速查找主键为 6 的记录,以上图为例子:

  • 从根节点开始,通过二分法快速定位到符合页内范围包含查询值的页,因为查询的主键值为 6,在[1, 7)范围之间,所以到页 30 中查找更详细的目录项;
  • 在非叶子节点(页30)中,继续通过二分法快速定位到符合页内范围包含查询值的页,主键值大于 5,所以就到叶子节点(页16)查找记录;
  • 接着,在叶子节点(页16)中,通过槽查找记录时,使用二分法快速定位要查询的记录在哪个槽(哪个记录分组),定位到槽后,再遍历槽内的所有记录,找到主键为 6 的记录。

4. 聚集索引和二级索引

索引又可以分为聚集索引和二级索引,其区别在于叶子节点存放了什么数据。

  • 聚集索引叶子节点存放了实际数据,所有完整的数据记录都保存在聚集索引的叶子节点;
  • 二级索引叶子节点存放了主键值,而不是实际数据

因为表的数据都是存放在聚集索引的叶子节点里,所以 InnoDB 存储引擎一定会为表创建一个聚集索引,且由于数据在物理上只会保存一份,所以聚簇索引只能有一个。

InnoDB 在创建聚簇索引时,会根据不同的场景选择不同的列作为索引:

  • 如果有主键,默认会使用主键作为聚簇索引的索引键;
  • 如果没有主键,就选择第一个不包含 NULL 值的唯一列作为聚簇索引的索引键;
  • 在上面两个都没有的情况下,InnoDB 将自动生成一个隐式自增 id 列作为聚簇索引的索引键;

一张表只能有一个聚簇索引,那为了实现非主键字段的快速搜索,就引出了二级索引(非聚簇索引/辅助索引),它也是利用了 B+ 树的数据结构,但是二级索引的叶子节点存放的是主键值,不是实际数据。

如果某个查询语句使用了二级索引,但是查询的数据不是主键值,这时在二级索引找到主键值后,需要去聚簇索引中获得数据行,这个过程就叫作「回表」,也就是说要查两个 B+ 树才能查到数据。不过,当查询的数据是主键值时,因为只在二级索引就能查询到,不用再去聚簇索引查,这个过程就叫作「索引覆盖」,也就是只需要查一个 B+ 树就能找到数据。

5. 一颗B+树可以存放多少行数据?

前面提到,B+树的每个节点是一个数据页,默认大小16kB。前面 数据页结构图已经介绍了每个数据页的结构,除去页头页尾及其它描述信息,真正存放用户记录的User Records部分还不足16kB

1. 叶子节点和非叶子节点分别存放多少数据?

B+树的最末级叶子结点里放了record数据。而非叶子结点里则放了用来加速查询的索引数据。

三层B+树

同样一个16kB的页,非叶子节点里每一条数据都指向一个新的页,而新的页有两种可能。

  • 如果是末级叶子节点的话,那么里面放的就是一行行record数据。
  • 如果是非叶子节点,那么就会循环继续指向新的数据页。

2. B+树总行数的计算公式

假设

  • 非叶子结点内指向其他内存页的指针数量为x
  • 叶子节点内能容纳的record数量为y
  • B+树的层数为z

那这棵B+树放的行数据总量等于 (x ^ (z-1)) * y

x怎么算?

数据页的结构

非叶子节点里主要放索引查询相关的数据,放的是主键和指向页号。

主键假设是bigint(8Byte),而页号在源码里叫FIL_PAGE_OFFSET(4Byte),那么非叶子节点里的一条数据是12Byte左右。

整个数据页16k, 页头页尾那部分数据全加起来大概128Byte,加上页目录毛估占1k吧。那剩下的15kB除以12Byte,等于1280,也就是可以指向x=1280页

我们常说的二叉树指的是一个结点可以发散出两个新的结点。m叉树一个节点能指向m个新的结点。这个指向新节点的操作就叫扇出(fanout)

而上面的B+树,它能指向1280个新的节点,恐怖如斯,可以说扇出非常高了。

y怎么算?

叶子节点和非叶子节点的数据结构是一样的,所以也假设剩下15kB可以发挥。

叶子节点里放的是真正的行数据。假设一条行数据1kB,所以一页里能放y=15行

行总数计算

回到 (x ^ (z-1)) * y 这个公式。

已知x=1280y=15

假设B+树是两层,那z=2。则是(1280 ^ (2-1)) * 15 ≈ 2w

假设B+树是三层,那z=3。则是(1280 ^ (3-1)) * 15 ≈ 2.5kw

**这个2.5kw,就是我们常说的单表建议最大行数2kw的由来。**毕竟再加一层,数据就大得有点离谱了。三层数据页对应最多三次磁盘IO,也比较合理。

3. 行数超过1亿查询速度就慢吗?

上面假设单行数据用了1kb,所以一个数据页能放个15行数据。

如果我单行数据用不了这么多,比如只用了250byte。那么单个数据页能放60行数据。

那同样是三层B+树,单表支持的行数就是 (1280 ^ (3-1)) * 60 ≈ 1个亿

你看我一个亿的数据,其实也就三层B+树,在这个B+树里要查到某行数据,最多也是三次磁盘IO。所以并不慢。

4. B树存放多少行数据

B树将行数据都存在非叶子节点上,假设每个数据页还是16kB,掐头去尾每页剩15kB,并且一条数据表行数据还是占1kb,就算不考虑各种页指针的情况下,也只能放个15条数据。数据页扇出明显变少了。

B树可承载的总行数的公式也变成了一个等比数列

15 + 15^2 +15^3 + ... + 15^z

其中z还是层数的意思。

为了能放2kw左右的数据,需要z>=6。也就是树需要有6层,查一次要访问6个页。假设这6个页并不连续,为了查询其中一条数据,最坏情况需要进行6次磁盘IO

而B+树同样情况下放2kw数据左右,查一次最多是3次磁盘IO。

磁盘IO越多则越慢,这两者在性能上差距略大。

为此,我们可以更明确地回答B+树和B-树中,为何选择B+树?B+树比B树更适合成为mysql的索引。

参考资料:

《MYSQL内核:INNODB存储引擎 卷1》

1

评论区