引言

置信每一个后盾开发工程师在面试过程中，都已经被问到过“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。

如上图所示，这是一个 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 + 树。通过这样子的设计，咱们能够发现：

• 繁多节点存储更多的元素，这样子咱们就能够把树变得更加矮胖，使得查问的 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