本身也想写点关于 MySQL 基础的东西，但是，网上一搜，各大论坛真的有好多，正好最近好多朋友在面试字节的时候，被问到底层算法的东西，然后被询问了一波，那我们就来看一下 mysql 底层所能涉及的算法，都研究明白了之后，是不是就不怕面试官扩展开来问 mysql 了呀

文章首发个人公众号：Java 架构师联盟，每日更新技术好文

运行流程

关于 mysql 的内部运行流程，这里不做过多的解释，通过下面这张图，我给大家讲解一下

注意：不同的存储引擎，数据文件和索引文件存放的位置是不同的，因此有了分类:

聚簇索引:数据和文件放在一起: innodb

.frm:存放的是表结构

.ibd:存放数据文件和索引文件

注意: mysql 的 innodb 存储引擎默认情况下会把所有的数据文件放到表空间中，不会为每一个单独的表保存一份数据文件，如果需要将每一个表单独使用文件保存，设置如下属性: set global innodb_file_per_table=on;

非聚簇索引:数据和索引单独一个文件:MylSAM

.frm:存放表结构

.MYI:存放索引数据.MYD:存放实际数据

那 mysql 的索引数据结构是什么呢？我们来看一下

哈希表可以完成索引的存储，每次在添加索引的时候需要计算指定列的 hash 值，取模运算后计算出下标，将元素插入下标位置即可，适合场景：等值查询

但是如果表中的数据是无序数据（范围查找的时候比较浪费时间，需要挨个进行遍历操作)，而在企业中多数的查询是范围查询，所以此时 hash 表不是特别合适，并且 hash 表在使用的时候，需要将全部的数据加载到内存，比较耗费内存的空间，也不是很合适

所以我们需要进行更换，首先想到的是什么----树

在树的结构中，左子树必须小于根节点，右子树必须大于根节点，如果是多叉树的话，从

左到右是有序，所以应该是可以的，我们来看一下（这也是在面试的过程中经常被询问的问题）

先看一下树都包含那些内容

排除前面几个，最适合的就是 AVL 树以及红黑树，我们分开查看一下

首先是 AVL 树

AVL 树是一颗严格意义上的平衡树，最高子树跟最低子树高度之差不能超过 1，因此在进行元素插入的时候，会进行 1 到 N 次的旋转，严重影响插入的性能，pass

其次是红黑树

之前的时候写过一篇红黑树的文章，有兴趣的朋友可以详细地看一下：快进收藏吃灰！字节跳动大佬用最通俗方法讲明白了红黑树算法

红黑树是基于 AVL 树的一个升级，损失了部分查询的性能，来提升插入的性能，在红黑树中最低子树跟最高子树之差小于 2 倍即可，在插入的时候，不需要进行 N 多次的旋转操作，而且还加入了变色的特性，来满足插入和查询性能的平衡

但是我还是要告诉你，pass，为什么？因为二叉树及其 N 多的变种都不能支撑索引，原因是树的深度无法控制或者插入数据的性能比较低

那既然寻常的二叉树不太好用，但是又想用树这个结构，那换个思路呢？B 树怎么样？看一下

B 树特点:

1、所有键值分布在整棵树中

2、搜索有可能在非叶子结点结束，在关键字全集内做一次查找,性能逼近二分查找

3、每个节点最多拥有 m 个子树

4、根节点至少有 2 棵树

5、分支节点至少拥有 m/2 颗子树(除根节点和叶子节点外都是分支节点)

6、所有叶子节点都在同一层、每个节点最多可以有 m-1 个 key，并且以升序排列

一张图展示一下

解释说明

每个节点占用一个磁盘块，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指十存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为 16 和 34，P1 指|指向的子树的数据范围为小于 16,P2 指针指向的子树的数据范围为 16~34，P3 指针指向的子树的数据范围为大于 34。

查找关键字过程:

1、根据根节点找到磁盘块 1，读入内存。【磁盘 V/О操作第 1 次】

2、比较关键字 28 在区间(16.34)，找到磁盘块 1 的指针 P2。

3、根据 P2 指针找到磁盘块 3，读入内存。【磁盘 I/O 操作第⒉次】

4、比较关键字 28 在区间(2531)，找到磁盘块 3 的指针 P2。

5、根据 P2 指针|找到脑盘块 8，读入内存。[磁盘|/O 操作第 3 次】

6、在磁盘块 8 中的关键字列表中找到关键字 28。

缺点:

1、每个节点都有 key，同时也包含 data，而每个页存储空间是有限的，如果 data 比较大的话会导致每个节点存储的 key 数量变小

2、当存储的数据量很大的时候会导致深度较大，增大查询时磁盘 io 次数，进而影响查询性能

那既然还是会影响 mysql 的查询性能，那 mysql 的索引数据结构是什么样子的呢？我们优化一下 B 树——B+Tree 是在 BTree 的基础之上做的—种优化，变化如下:

1、B+Tree 每个节点可以包含更多的节点，这个做的原因有两个，第一个原因是为了降低树的高度，第二个原因是将数据范围变为多个区间，区间越多，数据检索越快

2、非叶子节点存储 key ，叶子节点存储 key 和数据

3、叶子节点两两指针相互连接(符合磁盘的预读特性)，顺序查询性能更高

这么说可能有点抽象，那我给大家通过一张图展示一下

注意:在 B+Tree 上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点(即数据节点)之间是一种链式环结构。因此可以对 B+Tree 进行两种查找运算:一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

那 B+Tree 如何放置数据呢？

mysql InnoDB--B+Tree,叶子节点直接放置数据

注意:

1、InnoDB 是通过 B+Tree 结构对主键创建索引，然后叶子节点中存储记录，如果没有主键，那么会选择唯一键，如果没有唯一健，那么会生成一个 6 字节的 row_id 来作为主健

2、如果创建索引的键是其他字段，那么在叶子节点中存储的是该记录的主键，然后再通过主键索引找到对应的记录,叫做回表

mysql MylSAM--B+Tree

对于 MyISAM 的查找顺序，我从网上找到了这样的一张图，我个人感觉看起来是比较直观的

假设我们的数据不是按照之前的顺序插入的，而是按照图中的是顺序插入表，可以看到 MyISAM 引擎下，B+树叶子节点中包含的是数据记录的地址（可以简单理解为“行号”），而 MyISAM 的辅助索引在结构上和主索引没有本质的区别，同样其叶子节点也包含了数据记录的地址

到这里，基本对于数据库底层索引结构的内容就讲完了，其实看一下大多数也是算法和数据机构的问题，这里也是展示了数据结构对于你想往上走的重要性，计算机就是这样，相互之间结合是很重要的，所以学习一定要成体系的学习，融汇贯通才是最重要的

不知道今天的内容大家有没有什么收获呀？哈哈哈哈