侧边栏壁纸
博主头像
一定会去到彩虹海的麦当

说什么呢?约定好的事就一定要做到啊!

  • 累计撰写 63 篇文章
  • 累计创建 16 个标签
  • 累计收到 3 条评论

目 录CONTENT

文章目录

[MySQL进阶]——InnoDB数据结构

一定会去到彩虹海的麦当
2022-02-11 / 0 评论 / 0 点赞 / 68 阅读 / 7,425 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-02-11,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

📚 笔记整理自 【宋红康】MySQL数据库(mysql安装/基础/高级/优化),还参考网上的其他技术文章作为补充,具体参考链接在文末

@[TOC]

🗄️数据库的存储结构:页

磁盘与内存交互基本单位:页

作为磁盘和内存之间交互的 基本单位 ,也就是一次最少从磁盘中读取16KB的内容到内存中,一次 最少把内存中的16KB内容刷新到磁盘中。也就是说,**在数据库中,不论读一行,还是读多行,都是将这 些行所在的页进行加载。也就是说,数据库管理存储空间的基本单位是页(Page),数据库 I/O 操作的 最小单位是页。**一个页中可以存储多个行记录。

💡记录是按照行来存储的,但是数据库的读取并不以行为单位,否则一次读取(也就是一次 I/O 操 作)只能处理一行数据,效率会非常低。

image-20220119085112650

页结构概述

页a、页b、页c ... 页n 这些页可以 不在物理结构上相连 ,只要通过 双向链表🔗 相关联即可。每个数据页中 的记录会按照主键值从小到大的顺序组成一个 单向链表 ,每个数据页都会为存储在它里边的记录生成一 个 页目录 ,在通过主键查找某条记录的时候可以在页目录中 使用二分法 快速定位到对应的槽,然后再遍 历该槽对应分组中的记录即可快速找到指定的记录。

image-20220119085248320

MySQL 的 InnoDB 存储引擎中,默认页的 大小是 16KB

页的上层结构

另外在数据库中,还存在着区(Extent)、段(Segment)和表空间(Tablespace)的概念。行、页、 区、段、表空间的关系如下图所示:

image-20220119085421771

📄页的内部结构

页如果按类型划分的话,常见的有 数据页(保存 B+ 树节点) 、 系统页 、 Undo 页 和 事务数据页 等。 数据页是我们最常使用的页。

数据页的 16KB 大小的存储空间被划分为七个部分,分别是文件头(File Header)、页头(Page Header)、最大最小记录(Infimum+supremum)、用户记录(User Records)、空闲空间(Free Space)、页目录(Page Directory)和文件尾(File Tailer)。

页结构的示意图如下所示:

image-20220119085526084

这 7 个部分作用分别如下,我们简单梳理如下表所示:

image-20220119085545145

File Header(文件头部)

构成:

img

在 File Header 中有两个指针,分别指向上一个数据页和下一个数据页,连接起来的页相当于一个双向的链表,如下图所示:

图片

采用链表的结构是让数据页之间不需要是物理上的连续的,而是逻辑上的连续。

File Trailer(文件尾部)

  • 前4个字节代表页的校验和:

    这个部分是和File Header中的校验和相对应的。

  • 后4个字节代表页面被最后修改时对应的日志序列位置(LSN):

    这个部分也是为了校验页的完整性的,如果首部和尾部的LSN值校验不成功的话,就说明同步过程出现了问题。

Free Space(空闲空间)

  • 我们自己存储的记录会按照指定的行格式存储到User Records部分。

  • 但是在一开始生成页的时候,其实并没有User Records这个部分,每当我们插入一条记录,都会从Free Space部分,也就是尚未使用的存储空间中申请一个记录大小的空间划分到User Records部分

  • 当Free Space部分的空间全部被User Records部分替代掉之后,也就意味着这个页使用完了,如果还有新的记录插入的话,就需要去申请新的页了。

img

User Records (用户记录)

数据页中的记录按照「主键」顺序组成单向链表,单向链表的特点就是插入、删除非常方便,但是检索效率不高,最差的情况下需要遍历链表上的所有节点才能完成检索。

lnfimum+Suupremum(最小最大记录)

💡记录可以比较大小吗?

是的,记录可以比大小,对于一条完整的记录来说,比较记录的大小就是比较主键的大小。比方说我们插入的4行记录的主键值分别是:1、2、3、4,这也就意味着这4条记录是从小到大依次递增。

InnoDB规定的最小记录与最大记录这两条记录的构造十分简单,都是由5字节大小的记录头信息和8字节大小的一个固定的部分组成的,如图所示:

img

这两条记录不是我们自己定义的记录,所以它们并不存放在页的User Records部分,他们被单独放在一个称为Infimum + Supremum的部分,如图所示:

img

Page Directory(页目录)

💡为什么需要页目录?

在页中,记录是以单向链表的形式进行存储的。单向链表的特点就是插入、删除非常方便,但是检索效率不高,最差的情况下需要遍历链表上的所有节点才能完成检索。因此在页结构中专门设计了页目录这个模块,专门给记录做一个目录,通过二分查找法的方式进行检索,提升效率。

需求:根据主键值查找页中的某条记录,如何实现快速查找呢?

SELECT * FROM page_demo WHERE c1 = 3;

1️⃣方式1:顺序查找

从Infimum记录(最小记录)开始,沿着链表一直往后找,总有一天会找到(或者找不到),当链表的某个节点代表的记录的主键值大于你想要查找的主键值时,就停止查找

如果一个页中存储了非常多的记录,这么查找性能很差。

2️⃣方式2:使用页目录,二分法查找

  1. 将所有的记录分成几个组,这些记录包括最小记录和最大记录,但不包括标记为“已删除”的记录。

  2. 第 1 组,也就是最小记录所在的分组只有 1 个记录;

    最后一组,就是最大记录所在的分组,会有 1-8 条记录;

    其余的组记录数量在 4-8 条之间。

这样做的好处是,除了第 1 组(最小记录所在组)以外,其余组的记录数会尽量平分。

  1. 在每个组中最后一条记录的头信息中会存储该组一共有多少条记录,作为 n_owned 字段。

  2. 页目录用来存储每组最后一条记录的地址偏移量,这些地址偏移量会按照先后顺序存储起来,每组的地址偏移量也被称之为槽(slot),每个槽相当于指针指向了不同组的最后一个记录。

👌举例1:

img

👌举例2:

现在的page_demo表中正常的记录共有6条,InnoDB会把它们分成两组,第一组中只有一个最小记录,第二组中是剩余的5条记录。如下图:

img

⚠️从这个图中我们需要注意这么几点:

  • 现在页目录部分中有两个槽,也就意味着我们的记录被分成了两个组,槽1中的值是112,代表最大记录的地址偏移量(就是从页面的0字节开始数,数112个字节);槽0中的值是99,代表最小记录的地址偏移量。

  • 注意最小和最大记录的头信息中的n_owned属性

  • 最小记录的n_owned值为1,这就代表着以最小记录结尾的这个分组中只有1条记录,也就是最小记录本身。

  • 最大记录的n_owned值为5,这就代表着以最大记录结尾的这个分组中只有5条记录,包括最大记录本身还有我们自己插入的4条记录。

用箭头指向的方式替代数字,这样更易于我们理解,修改后如下:

img

再换个角度看一下:(单纯从逻辑上看一下这些记录和页目录的关系)

img

💡总结:

页目录就是由多个槽组成的,槽相当于分组记录的索引。然后,因为记录是按照「主键值」从小到大排序的,所以我们通过槽查找记录时,可以使用二分法快速定位要查询的记录在哪个槽(哪个记录分组),定位到槽后,再遍历槽内的所有记录,找到对应的记录,无需从最小记录开始遍历整个页中的记录链表

Page Header(页面头部)

为了能得到一个数据页中存储的记录的状态信息,比如本页中已经存储了多少条记录,第一条记录的地址是什么,页目录中存储了多少个槽等等,特意在页中定义了一个叫Page Header的部分,这个部分占用固定的56个字节,专门存储各种状态信息。

img

🏷️InnoDB行格式(或记录格式)

💡我们平时的数据以行为单位来向表中插入数据,这些记录在磁盘上的存放方式也被称为 行格式 或者 记录格式

InnoDB存储引擎设计了4种不同类型的 行格式 ,分别是 Compact 、 Redundant 、 Dynamic 和 Compressed 行格式。

指定行格式的语法

在创建或修改表的语句中指定行格式:

CREATE TABLE 表名 (列的信息) ROW_FORMAT=行格式名称

ALTER TABLE 表名 ROW_FORMAT=行格式名称

举例:

mysql> CREATE TABLE record_test_table (

  ->   col1 VARCHAR(8),

  ->   col2 VARCHAR(8) NOT NULL,

  ->   col3 CHAR(8),

  ->   col4 VARCHAR(8)

  -> ) CHARSET=ascii ROW_FORMAT=COMPACT;

Query OK, 0 rows affected (0.03 sec)

向表中插入两条记录:

INSERT INTO record_test_table(col1, col2, col3, col4) 

VALUES

('zhangsan', 'lisi', 'wangwu', 'songhk'), 

('tong', 'chen', NULL, NULL);


COMPACT行格式

我们先介绍这个格式,因为其他格式基本跟它差不多

image-20220120081131623

1、变长字段长度列表

MySQL支持一些变长的数据类型,比如VARCHAR(M)、VARBINARY(M)、TEXT类型,BLOB类型,这些数据类型修饰列称为变长字段**,变长字段中存储多少字节的数据不是固定的**,所以我们在存储真实数据的时候需要顺便把这些数据占用的字节数也存起来。

在Compact行格式中,把所有变长字段的真实数据占用的字节长度都存放在记录的开头部位,从而形成一个变长字段长度列表

💡注意:这里面存储的变长长度和字段顺序是反过来的。比如两个varchar字段在表结构的顺序是a(10),b(15)。那么在变长字段长度列表中存储的长度顺序就是15,10,是反过来的。

👌以record_test_table表中的第一条记录举例:

因为record_test_table表的col1、col2、col4列都是VARCHAR(8)类型的,所以这三个列的值的长度都需要保存在记录开头处

⚠️注意record_test_table表中的各个列都使用的是ascii字符集(每个字符只需要1个字节来进行编码)。

img

又因为这些长度值需要按照列的逆序存放,所以最后变长字段长度列表的字节串用十六进制表示的效果就是(各个字节之间实际上没有空格,用空格隔开只是方便理解):

06 04 08 

把这个字节串组成的变长字段长度列表填入上边的示意图中的效果就是:

img

2、NULL值列表

Compact行格式会把可以为NULL的列统一管理起来,存在一个标记为NULL值列表中。如果表中没有允许存储 NULL 的列,则 NULL值列表也不存在了。

💡为什么定义NULL值列表?

之所以要存储NULL是因为数据都是需要对齐的,如果没有标注出来NULL值的位置,就有可能在查询数据的时候出现混乱。

如果使用一个特定的符号放到相应的数据位表示空置的话,虽然能达到效果,但是这样很浪费空间,所以直接就在行数据得头部开辟出一块空间专门用来记录该行数据哪些是非空数据,哪些是空数据

格式如下:

  1. 二进制位的值为1时,代表该列的值为NULL。

  2. 二进制位的值为0时,代表该列的值不为NULL。

👌例如:

字段 a、b、c,其中a是主键,在某一行中存储的数依次是 a=1、b=null、c=2。

那么Compact行格式中的NULL值列表中存储:01。

第一个0表示c不为null,第二个1表示b是null。

这里之所以没有a是因为数据库会自动跳过主键,因为主键肯定是非NULL且唯一的,在NULL值列表的数据中就会自动跳过主键。

record_test_table的两条记录的NULL值列表就如下:

第一条记录:

img

第二条记录:

img

3、记录头信息(5字节)

mysql> CREATE TABLE page_demo(

  ->   c1 INT,

  ->   c2 INT,

  ->   c3 VARCHAR(10000),

  ->   PRIMARY KEY (c1)

  -> ) CHARSET=ascii ROW_FORMAT=Compact;

Query OK, 0 rows affected (0.03 sec)

这个表中记录的行格式示意图:

img

这些记录头信息中各个属性如下:

img

简化后的行格式示意图:

img

插入数据:

INSERT INTO page_demo 

VALUES

(1, 100, 'song'), 

(2, 200, 'tong'), 

(3, 300, 'zhan'), 

(4, 400, 'lisi');

图示如下:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LlOJtLjf-1642639439601)(C:/Users/wcl/AppData/Local/Temp/mindmaster/1616362b5174/bin/FFE4E988-DF30-4F6E-A25E-DE1B0EA227B8.png)]

4、记录的真实数据

记录的真实数据除了我们自己定义的列的数据以外,还会有三个隐藏列:

img

实际上这几个列的真正名称其实是:DB_ROW_ID、DB_TRX_ID、DB_ROLL_PTR。

  • 一个表没有手动定义主键,则会选取一个Unique键作为主键,如果连Unique键都没有定义的话,则会为表默认添加一个名为row_id的隐藏列作为主键。所以row_id是在没有自定义主键以及Unique键的情况下才会存在的。

  • 事务ID和回滚指针我会在后面的文章介绍

Dynamic和Compressed行格式

💡行溢出:

InnoDB存储引擎可以将一条记录中的某些数据存储在真正的数据页面之外。

但我们知道一个页的大小一般是16KB,也就是16384字节,而一个VARCHAR(M)类型的列就最多可以存储65533个字节,这样就可能出现一个页存放不了一条记录,这种现象称为行溢出。

各个格式对行溢出处理的区别

  • 在Compact和Reduntant行格式中,对于占用存储空间非常大的列,在记录的真实数据处只会存储该列的一部分数据,把剩余的数据分散存储在几个其他的页中进行分页存储,然后记录的真实数据处用20个字节存储指向这些页的地址

    这称为页的扩展,举例如下:

    img

  • 在MySQL 8.0中,默认行格式就是Dynamic,Dynamic

    • Compressed和Dynamic两种记录格式对于存放在BLOB中的数据采用了完全的行溢出的方式。在数据页中只存放20个字节的指针(溢出页的地址),实际的数据都存放在Off Page(溢出页)中。

    • Compact和Redundant两种格式会在记录的真实数据处存储一部分数据(存放768个前缀字节)。

    Compressed行记录格式的另一个功能就是,存储在其中的行数据会以zlib的算法进行压缩,因此对于BLOB、TEXT、VARCHAR这类大长度类型的数据能够进行非常有效的存储。

    img

Redundant行格式

注意Compact行格式的开头是变长字段长度列表,而Redundant行格式的开头是字段长度偏移列表,与变长字段长度列表有两处不同:

  • 少了“变长”两个字:Redundant行格式会把该条记录中所有列(包括隐藏列)的长度信息都按照逆序存储到字段长度偏移列表。

  • 多了“偏移”两个字:这意味着计算列值长度的方式不像Compact行格式那么直观,它是采用两个相邻数值的差值来计算各个列值的长度。

🗂️区、段与碎片区

image-20220120083136502

为什么要有区?

B+ 树的每一层中的页都会形成一个双向链表,如果是以 页为单位 来分配存储空间的话,双向链表相邻 的两个页之间的 物理位置可能离得非常远 。

引入 的概念,一个区就是在物理位置上连续的 64个页 。因为 InnoDB 中的页大小默认是 16KB,所以 一个区的大小是 64*16KB= 1MB

在表中 数据量大 的时候,为某个索引分配空间的时候就不再按照页为 单位分配了,而是按照 区为单位分配 ,甚至在表中的数据特别多的时候,可以一次性分配多个连续的 区。

虽然可能造成 一点点空间的浪费 (数据不足以填充满整个区),但是从性能角度看,可以消除很多 的随机I/O, 功大于过 !

为什么要有段?

对于范围查询,其实是对B+树叶子节点中的记录进行顺序扫描,而如果不区分叶子节点和非叶子节点, 统统把节点代表的页面放到申请到的区中的话,进行范围扫描的效果就大打折扣了。

所以 InnoDB 对 B+ 树的 叶子节点非叶子节点 进行了区别对待,也就是说叶子节点有自己独有的区,非叶子节点也有自己 独有的区。

存放叶子节点的区的集合就算是一个 ( segment ),存放非叶子节点的区的集合也算是 一个段。也就是说一个索引会生成2个段,一个 叶子节点段 ,一个 非叶子节点段

💡段其实不对应表空间中某一个连续的物理区域,而是一个逻辑上的概念,由若干个零散的页面以及一些 完整的区组成。

为什么要有碎片区?

为了考虑以完整的区为单位分配给某个段对于 数据量较小 的表太浪费存储空间的这种情况,InnoDB提出 了一个 碎片(fragment)区 的概念。

在一个碎片区中,并不是所有的页都是为了存储同一个段的数据 而存在的,而是碎片区中的页可以用于不同的目的,比如有些页用于段A,有些页用于段B,有些页甚至 哪个段都不属于。 碎片区直属于表空间 ,并不属于任何一个段。

区的分类

区大体上可以分为4种类型:

  • 空闲的区(FREE) :现在还没有用到这个区中的任何页面。
  • 有剩余空间的碎片区(FREE_FRAG) :表示碎片区中还有可用的页面。
  • 没有剩余空间的碎片区(FULL_FRAG) :表示碎片区中的所有页面都被使用,没有空闲页面。
  • 附属于某个段的区(FSEG) :每一个索引都可以分为叶子节点段和非叶子节点段。

处于 FREE 、 FREE_FRAG 以及 FULL_FRAG 这三种状态的区都是独立的,直属于表空间。而处于 FSEG 状态的区是附属于某个段的

如果把表空间比作是一个集团军,段就相当于师,区就相当于团。一般的团都是隶属于某个师的, 就像是处于 FSEG 的区全都隶属于某个段,而处于 FREE 、 FREE_FRAG 以及 FULL_FRAG 这三种状 态的区却直接隶属于表空间,就像独立团直接听命于军部一样。

📚表空间

表空间可以看做是InnoDB存储引擎逻辑结构的最高层,所有的数据都存放在表空间中

表空间是一个 逻辑容器 ,表空间存储的对象是段,在一个表空间中可以有一个或多个段,但是一个段只 能属于一个表空间。

表空间数据库由一个或多个表空间组成,表空间从管理上可以划分为

  • 系统表空间 (System tablespace)
  • 独立表空间 (File-per-table tablespace)
  • 撤销表空间 (Undo Tablespace)和
  • 临时表空间 (Temporary Tablespace)等。

🔗参考链接:

换一个角度看 B+ 树

0

评论区