It's Design——为什么MySQL使用B+树？

引言

相信每一个后台开发工程师在面试过程中，都曾经被问到过“MySQL的默认存储引擎是什么？MySQL索引是什么数据结构？”这样的问题。相信准备充分（熟读八股文）的大家都能很容易的回答出“MySQL的默认存储引擎是InnoDB，MySQL索引使用的是B+树。”这样的答案。但是为什么当初写MySQL的程序员大叔要这样子来设计呢？

概述

首先需要明确一点，MySQL跟B+树没有直接的关系，真正与B+树有关系的是MySQL的默认存储引擎InnoDB，MySQL中存储引擎的主要作用是负责数据的存储和提取，除了InnoDB之外，MySQL中也支持MyISAM等引擎作为表的底层存储引擎。但是不管是InnoDB或是MyISAM，其实索引的数据结构都是B+树。只是InnoDB采用的是聚簇索引，实际数据就在B+树叶子节点上；而MyISAM会单独为表的主键创建一个索引，叶子节点保存指向实际数据的指针。

那么接下来，我们就来探讨一下，为什么MySQL使用B+树？

一、从磁盘I/O说起

1. 磁盘基本概念

让我们把时间回退到程序员大叔设计MySQL的年代。大叔们设计数据库那肯定是需要介质来存储数据的，说到存储介质，那我们能想到的就是两类：磁盘、SSD硬盘。SSD硬盘肯定香啊，但是也贵，而且数据库是要支持上T数据的存储，2021年想想这条路都太贵啦，大叔们还是乖乖用磁盘吧～

磁盘结构

传统的硬盘盘结构如上图所示。它有一个或多个盘片，每个盘片可以有两面，用于存储数据。中间有一个主轴，所有的盘片都绕着这个主轴转动。一个组合臂上面有多个磁头臂，每个磁头臂上面都有一个磁头，负责读写数据。

盘面

如上图所示，每个盘片的盘面被划分成多个狭窄的同心圆环，数据就存储在上图这样的同心圆环上面，我们将这样的圆环称为磁道 (Track)。根据硬盘的规格不同，磁道数可以从几百到成千上万不等。每个磁道可以存储数 Kb 的数据，但是计算机不必要每次都读写这么多数据。

因此，再把每个磁道划分为若干个弧段，每个弧段就是一个扇区 (Sector)。扇区是硬盘上存储的物理单位，现在每个扇区可存储 512 字节数据已经成了业界的约定。也就是说，即使计算机只需要某一个字节的数据，但是也得把这个 512 个字节的数据全部读入内存，再选择所需要的那个字节。

柱面

柱面是抽象出来的一个逻辑概念，简单来说就是处于同一个垂直区域的磁道称为柱面 。如上图所示，各盘面上相同位置磁道的集合属于同一柱面。

需要注意的是，磁盘读写数据是按柱面进行的。磁头读写数据时，从盘片的起始数据柱面开始，读取完后，依次向下在同一柱面的不同盘面上进行操作。只有在同一柱面所有的磁头全部读写完毕后磁头才转移到下一柱面。之所以读写这么设计是因为选取磁头（数据从哪个磁头获取）只需通过电子切换即可，而选取柱面则必须通过机械切换（移动磁头位置）。而机械切换的速度肯定远远不如电子切换。为了读写的更快，数据的读写是按柱面进行的，而不是按盘面进行。正因为如此，数据存到同一个柱面是很有价值的。

根据上文的信息，我们可以得出磁盘容量的计算公式为：

硬盘容量 = 盘面数 × 柱面数 × 扇区数 × 512字节

2. 磁盘读写

现代硬盘寻道都是采用CHS(Cylinder Head Sector)的方式。我们可以把磁盘读写数据分3个部分来看。

• 硬盘读取数据时，读写磁头沿径向移动，移到要读取的扇区所在磁道的上方，这段机械切换的时间称为寻道时间(seek time)。因读写磁头的起始位置与目标位置之间的距离不同，寻道时间也不同。
• 磁头到达指定磁道后，通过盘片的旋转，使得要读取的扇区转到读写磁头的下方，这段时间称为旋转延迟时间(rotational latencytime)。
• 读写数据也需要时间，这段时间称为传输时间（transfer time）。

通过介绍，大家能很容易的理解寻道时间和旋转延迟时间耗时特别多。因为计算机的目标是更高、更快、更强。数据库依赖于计算机存储，那么Mysql大叔设计数据结构式肯定也得考虑磁盘读写的特点，去设计一个让查询更快的数据结构。

3. 连续I/O于随机I/O

大家都知道，MySQL这类数据库软件，功能其实就分为存数据和查询数据。查询数据依赖于存数据，存数据的方式肯定也影响着查询的快慢。因为数据是存储在磁盘上的，那么计算机内存肯定是要和磁盘打交道的，而这个打交道的过程，就伴随着磁盘I/O。我们可以根据查询磁盘的方式，将磁盘I/O分为以下两种：

• 连续I/O ：本次 I/O 给出的初始扇区地址和上一次 I/O 的结束扇区地址是完全连续或者相隔不多的。
• 随机I/O：本次 I/O 给出的初始扇区地址和上一次 I/O 的结束扇区相差很大，则算作一次随机 I/O。

因为在做连续 I/O 的时候，磁头几乎不用换道，或者换道的时间很短；而对于随机 I/O，如果这个 I/O 很多的话，会导致磁头不停地换道，造成效率的极大降低。这也就是连续 I/O 比随机 I/O 效率高的原因。

因为读写是依赖于存储的，并且查询往往带有条件，导致查询的数据不连续。所以MySQL大叔们就想，能不能设计一个存储方式，避免随机I/O或者减少随机I/O的次数，来提高查询效率呢？

二、更快的查找——树

作为一名程序员，“树”这个名词大家一定是熟知的（啥？你竟然不熟？面壁去）。树的数据结构常常在算法题中涉及到。树的种类大致有：

• 二叉（搜索/排序）树：BST
• 平衡二叉查找树：BBST
• 红黑树：BRT
• B-树（也叫B树）
• B+树
• B*树
• R树

本文不会把各种树的特性介绍一遍啦，后续会重新开一篇文章去详细介绍这些树及其特性。因为咱们是一篇老少皆宜的文章，所以我们先从树查找的原理开始～

1. 二叉（搜索/排序）树的查找

二叉树大家都听过，一般就是一个根结点，根结点下挂一个左子节点，一个右子节点。而左子节点和右子节点又能作为子树的根结点。如果在这个基础上稍微加一点点要求，就变成了二叉搜索树（BST）。二叉搜索树定义如下：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉搜索树。

二叉搜索树

从上图中我们可以看到，根结点5左子树的任何节点的值都小于5，根结点5右子树上面的所有节点值都大于5，并且我们以2或者7来作为根结点，依然可以得出“左子树上所有结点的值均小于它的根结点的值，右子树上所有结点的值均大于它的根结点的值”这一结论。

因为二叉搜索树具有这样的特性，假设我们查找一个数据3。我们的算法路径为：

• 3比根结点5小，比较左子树，临时根结点定为左子树根结点2；
• 3比根结点2大，比较右子树，临时根结点定为右子树根结点3；
• 3与根结点3相等，找到目标数据。

从上面的查询路径中我们可以发现，我们并不需要遍历所有的节点，而且通过二叉搜索树查找也没有消耗额外的空间。相较于遍历查找，这样子找一个具体的值，效率是大大优化了的。而且大家要知道，这不仅仅只可以比较数字哦。因为Unicode,ASCII,UTF-8等等这些计算机编码会将字符变得可以比较。如果我们查找一个字符或数字，按照这样子的方法，便可以大大的缩短查询时间啦。

2. B树（B-树）

虽然二叉查找树能优化查询，但是大家有没有发现一个问题。数据库是需要能处理上千万上亿条数据的，当数据量变得特别大时，如果我们还是用二叉查找树去存储数据，那么二叉查找树就会变得非常非常的高。并且，因为存储数据时，我们一般都是顺序存储，也就是执行一次写的顺序I/O。但是要查询时，寻找的数据可不一定有序，那么就会伴随着随机I/O，将数据读取到内存中进行计算比较。因为二叉树的一次向下查找往往就是一次随机I/O，如果树太高，那么随机I/O就会特别多，查询效率又降低了。

这时候聪明的小伙伴就在想啦，如果把这个树变成“矮胖矮胖”的，减少它的随机I/O，是不是就能加速查询啦！

因此，我们的B树闪亮的出现啦，同时B树也称为B-树（还没讲到B+树啊，摔），对于一个m阶的B树（其中某颗子树最多有m个子节点），相较于二叉查找树，其定义如下：

• 每个节点最多只有m个子节点。
• 每个非叶子节点（除了根）具有至少ceil(m/2)子节点。（3阶则至少有2个子节点，5阶至少3个...）
• 如果根不是叶节点，则根至少有两个子节点。（2阶则至少有2个子节点）
• 具有k个子节点的非叶节点包含k -1个关键码。（如果他有k个儿子，那么他这个节点，里面有k-1个标识）
• 所有叶子节点都在同一层，并且叶子节点只有关键字，指向孩子的指针为 null

注：ceil是除法的进一，就比如7/6结果是1余1，那么我们输出结果为2。

B树

如上图所示，这是一个4阶B树。如果我们要查找数据19，具有如下路径：

• 19<24，因为根结点只有一个关键码24，所以直接比较左子树A；
• 判断19<5是否成立，结果不成立，不考虑子树B；
• 判断5<19<13是否成立，结果不成立，则不考虑子树C；
• 判断13<19<17是否成立，结果不成立，则不考虑子树D；
• 判断17<19是否成立，结果成立，则考虑子树E；
• 因为子树E为叶子节点，其子节点为null。判断19是否存在与叶子节点E中，结果为存在，找到数据19。如果19不存在于叶子节点E里，那么说明查找的数据不存在。

大家可以发现通过B树，MySQL就可以在树“矮胖”的前提下，将更多的数据塞到树里，并且能够享受二叉树查询效率提高的优点。如果我们使用B树作为索引，目的关键码对应的实际数据存储在每个节点中。

3. B+树

既然B树都能让MySQL更快查询啦，为什么MySQL不采用B树作为索引的数据结构呢？这是因为我们的B+树是B树的进阶版啊～（加量不加价，用了都说好）B+树相较于B树，其定义如下：

• 叶子节点中包含了全部关键字信息，和这些关键字所对应的真实数据信息。叶子节点的关键字也是递增链接的。左边结尾数据都会保存右边节点开始数据的指针。
• 所有的非叶子节点可以看成是索引部分。非叶子节点仅含有其子树中最大或最小的关键字。且不指向具体信息。
• 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
• 根节点的最大元素，也就等同于整个B+树的最大元素。以后无论插入删除多少元素，始终保持最大元素在根节点当中。

B+树

如上图所示，这是一棵B+树。通过这样子的设计，我们可以发现：

• 单一节点存储更多的元素，这样子我们就可以把树变得更加矮胖，使得查询的IO次数更少；
• 因为整棵树中出现过的数据，都在最下层叶子节点中出现，且只有在叶子节点里才会存储目标数据信息，所以查询性能更稳定；
• 叶子节点中，左边叶子节点通过指针指向右边叶子节点。那么所有叶子节点形成了有序链表，便于范围查询。

4. 为什么不使用Hash

通过上面的介绍可知，如果以B+树作为MySQL的数据存储，那么时间复杂度将是O(log n)，也就是树的高度。但是如果我们以Hash的方式查询一个具体数据，时间复杂度却有可能达到 O(1) 。那么为什么MySQL大叔们不考虑这样的设计呢？我们可以看下面的SQL：

SELECT * FROM class WHERE teacher = 'yuann' ORDER BY id DESC
SELECT * FROM class WHERE student_number > 50

上面2个SQL涉及到排序及范围查询。我们知道Hash是通过Hash计算获取目标数据的，而这个计算结果往往也是一个点。那么很明显，使用哈希构成的索引是没有办法快速处理排序及范围查询的，查询会回退到全表扫描，并依次判断是否满足条件。显然，全表扫描是一个糟糕的状况，因此MySQL大叔们不使用Hash作为索引。

三、总结：为什么MySQL索引采用B+树

• 计算机读写硬盘数据是经过磁头寻道、在磁道通过旋转找到数据对应位置、数据从硬盘读取到内存有3个阶段：磁头寻道、盘片旋转以及数据传输。其中步骤1和2耗时特别多。所以，在读写信息时尽量减少磁头的移动次数，就能减少很多时间。而每次磁头的移动，也对应着B类树的每次向下找子节点。因为B类树有着同一节点下有多关键字的结构，就可以降低树的高度，树的高度降低了，这样查询效率就提高了。
• 因为B+树的数据都存在叶子节点，所以查询效率比B树更加稳定。
• 对于数据库来说，范围查询和排序非常频繁，B+树相比B树遍历只需要遍历叶子节点即可,范围查询减少了随机I/O。同时Hash处理范围查询和排序会回退到全表扫描，效率会很低下。

本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载时请注明原文链接，图片在使用时请保留图片中的全部内容，可适当缩放并在引用处附上图片所在的文章链接，图片使用 Figma 进行绘制。

原作者： yuann

原文链接：It's Design——为什么MySQL索引用B+树？

发布日期：2021-04-15