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

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叉树，其树的高度为$log_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数据。而非叶子结点里则放了用来加速查询的索引数据。

同样一个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=1280，y=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》