引言

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