5 mysql底层解析——b+ tree和每个page存储结构,包括连接、解析、缓存、引擎、存储等

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/tianyaleixiaowu/article/details/100533628

上一篇,我们学习了innodb文件系统内部大的存储结构,包括段(segment),簇(extent),页(page)各自的含义。

简单回顾一下,段是组成表空间的最大结构,当创建一个表时,会同时创建两个段(内节点段,叶子段),分别管理非叶子节点数据和叶子节点数据。其实还有一个段(回滚段),是存放回滚数据的,只不过回滚段不是放在每个表的表空间,而是放在共享表空间的,希望还能记得共享表空间是什么。

簇,是段的下一级,每个簇固定大小是64个page,共64*16K=1M。为了保证数据存储时,页能尽量保持物理磁盘上的连续性,innodb会一次性申请4-5个簇。

页,最小的存储单位。常见的页类型有数据页、undo页、系统页、事务数据页、插入缓冲位图页、插入缓冲空闲列表页、未压缩的二进制大对象页、压缩的二进制大对象页。

OK,回到B+ tree这里。

B+ tree是如何构成的,里面的数据是怎么存放的呢。

以一个简单的2层b+ tree为例

这个树只有2层,首先每个page都有自己的唯一编号,将来就要通过编号来找对应的page。根页做为一个第一层的索引页,里面是不存在叶子数据(行数据)的,只存放Key,同时还包含了pageNo信息,用来将来去找对应的页。

所有的记录节点都是按键值的大小顺序存放在同一层的叶子节点上,由各叶子节点指针进行连接(双向指针)。所以查询时,无论正序倒序,其实是一样的扫描速度。

每一层的最左边节点页面的最左边位置,会有一个Min记录,该记录由2部分组成,第一部分就是一个Min标记,代表这就是 最小值;第二部分是一个pageNo指针,指向下一层中最左边的记录。注意看根页的Min记录,就是这样的。而33号page的Min记录由于没有下一层了,所以没有pageNo指针。

可以看到,上一层的Key,在下一层对应的page中,也会重复存在,譬如Key=10的记录。但是,每个page,只有第一条数据会和上层有重复,其他的不会有重复。

每一个page还会有一个最大记录和最小记录,用来标记该page的边界,便于查询。

由此结构可以看到,做一次查询的耗时,每一层只需要一次内存级的二分查找,定位后就进入下一层,再一次二分查找。

譬如查询Key=11,那么可以定位到56号page,因为11小于78号page的最小值,之后找到56号page,在做一次二分查询。就能找到11。2层只需要2次IO,就能找到一条数据。3层3次,之前已经说过,3层和4层分别能存多少数据,这个查询效率其实是非常高的。

通过这样的方式,我们就知道了一颗树是怎么构成的了。下面来看看具体到每个page内部是怎么存放的。

每个Page内详细结构

这就是一个page内的存储,共16K的空间,要放的所有东西。

分为几个大部分,文件管理头信息、页面头信息、页面尾信息、最小记录最大记录、用户记录、可重用空间、未使用空间、页面槽信息。

从名字就能看出来,用户记录就是行数据,可重用就是曾经被分配过数据后来被删了,未使用就是没分配过的空间。

文件管理头信息

它占用38个字节,里面存储的东西主要有——

该页面的checkSum信息,校验文件是否被损坏的;

该页面在当前表空间的页面号(pageNo);

当前页面的上一个页面的pageNo;

下一个页面的pageNo;

当前页面最后一次被修改时,对应日志的LSN值,与后面的日志系统有关;

当前页面的类型;

只有第0号页面会存一个LSN值,用来存储当前Innodb引擎最大的被flush的LSN值,将来做checkPoint时用;

标记属于哪个表空间的(避免多个表空间,有相同的pageNo的页)

页面头信息:

这里面存的东西也巨多,挑几个重要的——

槽的个数;

未使用空间的指针;

存储的记录数,包括最大最小记录的管理;

已被删除的记录的链表的首指针;

已被标记删除的记录数;

最后被插入的记录的位置;

当前节点在b+ tree处于第几层,叶子就是0,往上就加1;

页面尾部:

这8个字节还是用来做完整性校验的。

页面重组

一个页面会频繁的插入删除,在插入过程中,都会去已经删除的可重用链表去找合适的空间,如果放得下,就会放进去,放不下,另寻空间。时间一长,就会有空间碎片产出,譬如累计的空闲空间还有很多呢,但就是找不到能放下一条新数据的合适空间。

那么带来的问题很明显,page增加,每个page存储数据量下降,磁盘占用很大,但存的数据并不多,IO数增加,性能下降。

如果是一张表的话,如果大量数据被删,就需要及时处理回收空间,可以通过一个空的alter命令,如alter table tablename engine innodb,就可以将表的空间给回收重组了。

对于页面也一样,在数据库向某一个页面插入时,如果找不到大小合适的空间,就会做一次页面重组操作。重组的方式是,新建一个buffer pool页面,然后将老页面的数据一条一条插入到新页面,插入完成后,将老页面空间释放掉,再修改指针位置,指向新页面。

Innodb索引插入和删除

这个有点复杂,主要是树的节点分裂、迁移,扩容等操作。好比Hashmap一样,空间不够时,就扩容,但b+ tree是有序的,每次插入都要保持严格的顺序,就会比普通的扩容多一些排序查找的操作。

细节我就不想写了,可以去网上搜一搜。

删除相对简单一些,只有当一个page里完全没有数据了,才会将整个page从b+ tree里删掉。细节不谈。

下一篇就要进入缓存层,对性能起决定性影响的因素,和增删改查时,Innodb所做的内存处理。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序通事

SPI 机制-插件化扩展功能

SPI(Service Provider Interfaces),中文直译服务提供者接口,一种服务发现机制。可能很多人都不太熟悉这个机制,但是平常或多或少都用到...

6810
来自专栏AustinDatabases

MYSQL MVCC 实现机理 与 知识漏洞要补

说来惭愧,被友人问了一些关于MYSQL 的问题,虽然算不上对答如流,但也算是沉稳应对。唯独折在 MVCC 中MYSQL INNODB 是如何实现的问题上,回答错...

11330
来自专栏用户3029758的专栏

Linux环境搭建:CentOs + Apache + MySQL + PHP

声明:本文为原创,作者为 对弈,转载时请保留本声明及附带文章链接:http://www.duiyi.xyz/c%e5%ae%9e%e7%8e%b0%e9%9b%...

31910
来自专栏杨建荣的学习笔记

MySQL在Consul服务中的健康检查逻辑

MySQL的Consul方向开始要大规模推广的时候,一直感觉健康检查的部分还是不够严谨,虽然感觉是,但是总体逻辑上看也没什么硬伤,就暂时搁置了下来,最近业务...

10210
来自专栏AustinDatabases

SQL SERVER 锁升级的 investigation 与 别吃黄连

前些日子在分析SQL SERVER 死锁的过程中,检查有一些莫名其妙的死锁,两个根本不搭噶的事务,锁在了一起,WHY,其实SQL SERVER 在数据库界,算是...

8240
来自专栏WriteOnRead

MySQL笔记-基本架构

本文以及接下来的几篇 MySQL 笔记是本人在「极客时间」的专栏『MySQL实战45讲』和掘金小册「MySQL 是怎样运行的:从根儿上理解 MySQL」的学习笔...

7030
来自专栏IT大咖说

相见恨晚的15个 Linux 神器,你可能一个都没见过

mycli:mysql客户端,支持语法高亮和命令补全,效果类似ipython,可以替代mysql命令。

11520
来自专栏web秀

Todo List: Node + Express 搭建服务端连接Mysql – 第五章(第一节)

万丈高楼平地起,我们的Todo List项目也是越来越健壮了。Todo List的前面4章内容都是在为Client端开发,现在架构基本ok,接下来我们搭建Ser...

13040
来自专栏Python 学习

数据库-part1-MySQL安装

datadir=D:\MySQL\MySQL Server 5.7.22\data

11140
来自专栏用户3029758的专栏

Windows10下安装解压版MySQL

这里有一个坑点,配置字段的等号左右两边不能有空格,否则等一下MySQL初始化的时候可能会报如下错误:

13120

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励