前言

本文记录MySQL底层的存储数据结构和存储引擎。

MySQL存储结构

从需求的角度出发来考虑可以用的数据结构。对于数据库来说，最重要的功能就是要快速找到需要的数据。因此，线性的存储结构比如数组，链表等都不做考虑，用遍历的方式找到数据太过缓慢。可用的数据结构有哈希表，搜索二叉树，红黑树，b树，b+树等。下面逐一分析优劣来理解为什么MySQL选择了b+树作为存储结构。

哈希表

哈希表的特点是能够在O(1)的时间复杂度内找到所需的元素。其原理是将键值对的键利用哈希函数转换，变成等长的形式，之后存在相应的内存地址上，之后查询的时候就对键做同样操作，然后去内存上找到对应位置即可。

优点：查找快速

缺点：

数据量过大时哈希冲突会很多，此时每个地址下存入的都是一个红黑树，查找也会变慢。
只能做精确查找，无法完成范围查找

二叉树

搜索二叉树是一种特殊的二叉树，对每一个节点，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

优点：可以做范围查找，查询速度为O(logn)

缺点：

如果维护的字段是递增的，则生成的二叉树很不平衡（只有右子），此时查找仍是O(n)
大量数据会造成深度过深，此时搜索仍旧很慢

对于第一点的优化可以使用红黑树，但仍旧无法解决第二个缺点

B树

B树是一种平衡树，即每个叶结点的深度相同，以此来防止非平衡树带来的查询复杂度不同的问题，同时每个节点可以存储多个数据，解决深度过深的问题。具体定义以下概念：

度：指节点存储的数据个数
阶：指节点最多能存储的数据个数

对于一颗m阶的B树，其满足：

每个结点最多有m-1个关键字。
根结点最少可以只有1个关键字。
非根结点至少有Math.ceil(m/2)-1个关键字。
每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

具体的插入删除操作参考：https://www.cnblogs.com/nullzx/p/8729425.html

具体的动画演示：https://www.cs.usfca.edu/~galles/visualization/BTree.html

优点：解决了大量数据的存储和查询问题

缺点：每个节点能够存储的元素有限。MySQL需要将节点读入内存来进行查找工作，由于每个节点包含关键字（key）和所有值（value），因此内存限制了一次无法读入很多节点，降低搜索效率。

B+树

和B树类似，有两点不同

所有的值都存在叶子节点，非叶子节点只存储关键字
叶子节点之间用指针连接，方便范围查找

m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录。

内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。

动画演示：https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

优点：满足大量数据快速查询，由于非叶子节点只存索引，可以一次尽可能多的加载索引进入内存，加快查找。同时叶子节点之间的指针加快范围查找。

mysql底层bigint类的索引占8字节，指针占6字节，默认每个索引字段的大小为16kb（每个节点就是一个索引字段），由此得出，每个索引字段可以存大概1000个元素（索引）

MySQL 的搜素引擎

先明确一点，MySQL的存储引擎是用来形容表的，不是数据库。它决定了一张表是如何存储在硬盘上的。

常见的存储引擎有MYISAM和InnoDB。

MYISAM

对于每张表，MYISAM有三个文件：.MYD , .MYI, .frm

frm 是表结构定义的文件

MYD是数据的存储

MYI是索引的存储，主键是自带索引的。

拿到需要的索引，进入MYI文件通过b+树定位，找到对应的指针（myiSAM），在用这个指针去MYD文件里定位到对应的位置。

是非聚集索引（数据和索引分开存储）

InnoDB

INNODB的存储只有两个文件.frm和.ibd

其中ibd保存索引和数据，不用指针来定位，直接把索引和数据存在一起

表数据本身就是按照b+树结构来存储的

聚集索引：叶子节点包含了完整的数据记录

innoDB必须要建立主键来组织b+树，并且推荐用自增整形来做主键，因为1.节约存储空间2.搜素过程需要比大小

3.自增是因为b+树必须维护元素有序，当插入的元素不是结尾元素时，b+树已经生成的结构可能需要重构（之前的一个索引字段已经满了，又要插入一个，则这个字段必须分裂）

叶子节点之间的指针（双向指针）：用来进行范围查找，找到边界的节点，之后利用这个指针找到左右需要的范围