「AI投研邦」团体会员上线！75折解锁会员权益、PDF版研报、AI峰会....
06-18
简介相信每个后端开发工程师都被问过诸如“MySQL默认的存储引擎是什么？MySQL索引的数据结构是什么？”之类的问题。面试过程中。
相信每个有充分准备的人（熟悉八篇文章）都能轻松回答“MySQL默认存储引擎是InnoDB，MySQL索引使用B+树”这个答案。但是最初写MySQL的程序员大叔为什么要这样设计呢？概述 首先需要明确的是，MySQL 与 B+ 树没有直接关系。
与B+树真正相关的是MySQL的默认存储引擎InnoDB。 MySQL中存储引擎的主要作用是存储和提取数据。
除了InnoDB之外，MySQL还支持MyISAM等引擎作为表的底层存储引擎。但无论是InnoDB还是MyISAM，索引的数据结构实际上都是B+树。
只不过InnoDB使用聚集索引，实际数据在B+树叶子节点上；而MyISAM会为表的主键创建一个单独的索引，叶子节点保存指向实际数据的指针。那么接下来我们来讨论一下MySQL为什么使用B+树？ 1. 让我们从磁盘 I/O 开始 1. 磁盘的基本概念 让我们回到程序员叔叔设计 MySQL 的时代。
大叔设计数据库的时候肯定需要介质来存储数据。说到存储介质，我们可以想到两类：磁盘和SSD硬盘。
SSD硬盘肯定好，但是也贵，而且数据库必须支持T数据的存储。今年想想，这条路太贵了。
大叔们就用磁盘吧~ 磁盘结构 传统的硬盘结构如上图所示。它有一个或多个盘片，每个盘片可以有两侧，用于存储数据。
中间有一个主轴，所有盘片都围绕该主轴旋??转。组合臂上有多个磁头臂，每个磁头臂上都有一个磁头，负责读写数据。
磁盘表面如上图所示。每个盘的盘面被分成多个狭窄的同心环。
数据存储在同心环上，如上图所示。我们称这样的环为轨道。
根据硬盘驱动器的规格，磁道数量可以从几百到几千不等。每个磁道可以存储几千字节的数据，但计算机不必每次都读写那么多数据。
因此，每个磁道被划分为若干个弧段，每个弧段就是一个扇区。扇区是硬盘上的物理存储单元。
每个扇区可以存储字节数据已成为行业惯例。换句话说，即使计算机只需要某个字节的数据，也必须将这些字节的数据全部读入内存，然后选择所需的字节。
气缸 气缸是一个抽象的逻辑概念。简单地说，同一垂直区域内的轨道称为柱面。
如上图所示，每个盘片上相同位置的磁道集合属于同一个柱面。需要说明的是，磁盘读写数据都是以柱面为单位进行的。
磁头读写数据时，都是从磁盘的起始数据柱面??开始。读取完毕后，继续向下对同一柱面的不同盘面进行操作。
只有当同一柱面的所有磁头都完成读写操作后，磁头才会转移到下一个柱面。读写之所以这么设计，是因为选择磁头（从哪个磁头获取数据）只需要电子切换，而选择柱面则必须机械切换（移动磁头的位置） ）。
机械开关的速度肯定比电子开关慢得多。为了读写速度更快，数据是按柱面读写，而不是按磁盘读写。
因此，将数据存储在同一个柱面上是很有价值的。根据以上信息，我们可以得出磁盘容量的计算公式为： 代码语言：txt复制硬盘容量=磁盘数×柱面数×扇区数×字节 2、现代硬盘寻道用于磁盘阅读和写作。
CHS（气缸盖扇形）方法。我们可以将磁盘读写数据分为三个部分。
硬盘读取数据时，读写头呈放射状移动到要读取的扇区所在磁道的顶部。该机械切换时间称为寻道时间。
由于读写头起始位置与目标位置的距离不同，寻道时间也不同。磁头到达指定磁道后，通过磁盘的旋转将要读取的扇区移动到读写头下方。
这段时间称为旋转等待时间。读写数据也需要时间，称为传输时间。
通过介绍，大家很容易了解到寻道时间和旋转延迟时间需要花费很多时间。因为计算机的目标是更高、更快、更强。
数据库依赖于计算机存储，所以Mysql大叔在设计数据结构时也要考虑磁盘读写的特点，设计出让查询更快的数据结构。 3、连续I/O vs. 随机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的次数来提高查询效率呢？ 2.更快的搜索——树 作为一名程序员，大家一定对“树”这个词很熟悉（什么？不熟悉吗？面朝墙）。
树的数据结构经常涉及到算法问题。树的类型大致有： 二叉（搜索/排序）树：BST 平衡二叉搜索树：BBST 红黑树：BRTB-tree（也叫 B-tree） B+ 树 B* 树 R 树 本文就不列出各种了trees 的特性已经介绍过一次了，稍后会另开一篇新文章来详细介绍这些树及其特性。
因为我们是一篇老少皆宜的文章，所以我们先从树搜索的原理开始~ 1.搜索二叉（搜索/排序）树。每个人都听说过二叉树。
一般有一个根节点，根节点下挂有一个左子节点和一个右子节点。左子节点和右子节点可以作为子树的根节点。
如果在此基础上再加上一些要求，就变成了二叉搜索树（BST）。二叉搜索树的定义如下：如果它的左子树不为空，那么左子树上所有节点的值都小于它的根节点的值；如果它的右子树不为空，那么右子树上所有节点的值都不为空。
所有节点的值都大于其根节点的值；它的左子树和右子树也分别是二叉搜索树。二叉搜索树 从上图可以看出，根节点5的左子树中任意节点的值都小于5，而根节点5的右子树中所有节点的值都大于5，并且我们用2或者7作为根节点，仍然可以得出“左子树上所有节点的值都小于其根节点的值，且左子树上所有节点的值都小于它的根节点的值”的结论。
右子树大于其根节点的值。”这个结论。
因为二叉搜索树有这样的特性，假设我们搜索一个数据3，我们的算法路径是：3比根节点5小，比较左子树，临时根节点设置为左子树的根节点2 ; 3比根节点2大，比较右子树，将临时根节点确定为右子树的根节点3； 3等于根节点3，找到目标数据。从上面的查询路径可以发现，我们不需要遍历所有节点，通过二叉搜索树进行搜索也不会消耗额外的空间。
与遍历搜索相比，查找特定值的效率得到了极大的优化。每个人都需要知道，这不仅仅是比较数字。
因为Unicode、ASCII、UTF-8等计算机编码会让字符具有可比性。如果我们搜索一个字符或者数字，采用这种方法可以大大缩短查询时间。
2、B树（B-tree） 二叉搜索树虽然可以优化查询，但是有人发现有问题吗？数据库需要能够处理千万级数据。当数据量变得非常大的时候，如果我们仍然使用二叉搜索树来存储数据，那么二叉搜索树就会变得非常非常高。
而且，我们在存储数据时，一般都是顺序存储的，即一次写，进行顺序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个标识符）所有叶子节点都在同一级别，并且叶子节点只有关键字，指向孩子的指针为空。注：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是否为真，且结果为真，则认为子树D为树E；因为子树E是叶子节点，所以它的子节点为空。
判断叶子节点E中是否存在19，结果是存在，找到数据19。如果叶节点E中不存在19，则说明正在查找的数据不存在。
可以发现，通过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： 代码语言： txt copy SELECT * FROM class WHERE Teacher = 'yuann' ORDER BY id DESCSELECT * FROM class WHERE Student_number > 50 上面两条SQL涉及到排序和范围查询。我们知道Hash是通过Hash计算得到目标数据，而这种计算的结果往往是一个点。
显然，使用由哈希组成的索引是没有办法快速处理排序和范围查询的。查询会回退到全表扫描，依次判断条件是否满足。
显然，全表扫描是一种糟糕的情况，所以MySQL的人不使用Hash作为索引。 3、总结：为什么MySQL索引采用B+树计算机读写硬盘数据是通过磁头寻道和磁道上的旋转来找到数据对应的位置。
数据从硬盘读取到内存分三个阶段：磁头寻道、磁盘旋转和数据传输。步骤 1 和 2 特别耗时。
因此，通过在阅读和写入信息时尽量减少头部移动次数，可以节省大量时间。磁头的每次移动也对应于B型树中每次向下搜索子节点。
由于B型树具有同一节点下有多个关键字的结构，因此可以降低树的高度。当树的高度降低时，查询效率提高。
由于B+树的数据都存在叶子节点，因此查询效率比B树更稳定。对于数据库来说，范围查询和排序是非常频繁的。
与B树遍历相比，B+树只需要遍历叶子节点。范围查询减少随机 I/O。
同时Hash处理范围查询和排序会回落到全表扫描，效率会非常低。本文根据 Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License 获得许可。
转载时请注明原文链接。使用图片时，请保留图片中的所有内容。
您可以适当缩放它并附上该图像所在文章的链接。使用 Figma 绘制图像。
版权声明：本文内容由互联网用户自发贡献，本站不拥有所有权，不承担相关法律责任。如果发现本站有涉嫌抄袭的内容，欢迎发送邮件 举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。
标签：
相关文章
06-06
06-18
06-17
06-18
06-21
06-21
06-06
最新文章
【玩转GPU】ControlNet初学者生存指南
【实战】获取小程序中用户的城市信息（附源码）
包雪雪简单介绍Vue.js：开学
Go进阶：使用Gin框架简单实现服务端渲染
线程池介绍及实际案例分享
JMeter 注释 18 - JMeter 常用配置组件介绍
基于Sentry的大数据权限解决方案
【云+社区年度征文集】GPE监控介绍及使用