mysql 检索分享上篇

B+树数据存储简图

这个是 B+树存储的一张简图，看这张图，我们可以从'增删改'和'查询'两种过程来分析，换句话就是数据保存在磁盘上的过程和数据从磁盘查询出来一个过程；

1.1 数据保存的过程

1.1 建表

下面的分析都是针对 B+树的分析，建表语句如下：

CREATE TABLE `mysql_index` (  `id` int NOT NULL AUTO_INCREMENT,  `age` int DEFAULT NULL,  `name` varchar(64) DEFAULT NULL,  PRIMARY KEY (`id`)) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci；

1.2 插入单条数据

mysql 的数据页默认是 16KB 大小，数据都是存在数据页中，我们往表中插入一条数据如下：

对应的也是往磁盘上申请一块存储空间，将数据存放进去。

1.3 页分裂或新增

这里面的 '最小记录' 和 '最大记录' 后面页结构里会讲到用途，这里我们只关注自己插入的数据；

随着插入的数据越来越多，16KB 的页迟早会被写满，比如下面这样：

数据页 page1 已经写满，当主键为 77 的记录要保存下来的时候怎么办的呢?

这个自然就是我们长听说的一个名词 '页分裂'：主键为 77 的这条记录保存到原页面，主键值在 77 之后的记录移动到一个新的页面内：

当然如果我们插入的不是主键值是 77 的记录，而是一个比 page 1 主键值 100 大的记录，那就不存在页分裂了，直接分配一个新的 16KB 的数据页保存即可；

1.4 为检索而考虑

现在有了两个数据页 page 1 和 page 2 ，现在我们想找主键为 100 的记录，怎么找呢?

我们知道数据页的有个属性叫 file header（页结构的分享会提到），而 file header 下有两个属性：fil_page_prev 和 fil_page_next ，这两个属性对应当前数据页，上一页和下一页的地址，所以页和页之间组成一个类似双向链表的结构；

我们知道链表的数据结构，查询的时间复杂度是 O(n)，如果只有两个页面，数据量不大，数据页全部读到内存中，遍历查询，这个时间还可以接受，但是如果页面比较多的话，比如有我们有 1000 万的数据，每条数据近似 160B, 每页存 100 条（当然数据页除了存记录还存有其他数据，只是为了方便计算），结果：

需要的数据页：10000000/100 = 10 万页；

占用内存：100,000 * 16KB = 1.6G;

所以，全放内存，不现实，一张表需要这么多内存，那要是有 100 张表，那得要多大内存的服务器可以运行这个 mysql 实例；但要是不放内存，边读磁盘，边把数据页加载到内存，然后再淘汰不用的数据，保证使用有限的内存，但是这样会有很多问题，最直观的一个问题就是 慢！且费力不讨好。

我只想查询主键为 100 的数据，为什么要把 100 之前的所有数据加载一遍，如果找的主键为 100000 的数据，还要把它之前的记录加载一遍吗？肯定不是，那有什么好的方式呢？

我们买一本书，想先看看这本书都讲了哪些内容，通常是先翻阅下它的目录，看看作者都列了哪些文章标题，通过文章标题里的关键字，按图索骥翻到指定页读文章。

所以,参照这种思路，我们来看下 mysql 的设计；

目录项记录（索引）：

我们把 page 1 的页面地址和最小的主键值提取出来放到一个单独的页，当做一个目录项，page 2 同样的处理，生成目录项 2；这样就构成一个索引页；

随着我们插入的数据越来越多，数据页自然越多，目录项页也是 16K，它也有被写满的时候，比如 page 10 ：

怎么办？和记录完整的数据页一样，记录目录项的页（非叶子节点页）也可以产生页的分裂、合并，我们可以新分配一个 page 12 的页，同时，为 page 12 生成一个目录项，记录到它的上层节点中；

直到遇到我们文章开始的那张图：

除了在叶子节点存储真实数据外，我们还在非叶子节点存储了部分便于检索的数据；比如我们知道的主键值 + 页号；

1.2 数据检索的过程

前面我们分析了，没有目录项的时候，想找到主键值为 100 的这条记录，我们只能顺序遍历所有数据，直到找到目标数据，现在我们有了目录项，好比一本书有了目录，我们就不用再一页一页的翻去找了；

我们可以直接在索引页中先定位我们查找的数据在哪个页内，再到数据内去遍历查找，这就比刚才把所有这条数据之前的记录都遍历一遍，高效多了。

我们算下这些索引页需要多少内存：

我们还是假设有 1000 万的数据，存放叶子节点的数据页每页存 100 条数据：

叶子节点总页数： 1000 万/100 = 10 万页；

每个索引页可以存放 1000 个目录项，索引页总页数： 10 万/1000 = 100 页；

索引页占用的内存：100 * 16K = 1.6M

索引页占用的内存很小一部分，我们可以把这 1.6M 数据全部加载到内存中，之后在内存中遍历查找，性能还是很理想的。

但是，这样就可以了吗？

虽然加载到内存里，我们依然还是在遍历查询，时间复杂度还是 O(n), 可不可以再优化下，让我们在查找指定数据的时候，再少遍历一点数据，比如运用下二分法的思想,有的，这个就要涉及到 INNODB 数据页结构了，这个我们下篇文章再交流分享！

总结：

这篇文章我们分析的是一个聚簇索引保存、检索数据的过程，这过程还比较宏观；还是有许多我们提及的细节；在有了宏观认识的时候再一点点深入细节，就好比使用显微镜，不断的调大显微镜的倍数，看到细节也会越来越多。

参考资料：

《MySQL 是怎样运行的：从根儿上理解 MySQL》