9.2.3.1 【MySQL】XDES Entry链表

本文涉及的产品
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
云数据库 RDS MySQL,高可用系列 2核4GB
简介: 9.2.3.1 【MySQL】XDES Entry链表

当段中数据较少的时候,首先会查看表空间中是否有状态为 FREE_FRAG 的区,也就是找还有空闲空间的碎片区,如果找到了,那么从该区中取一些零碎的页把数据插进去;否则到表空间下申请一个状态为 FREE 的区,也就是空闲的区,把该区的状态变为 FREE_FRAG ,然后从该新申请的区中取一些零碎的页把数据插进去。之后不同的段使用零碎页的时候都会从该区中取,直到该区中没有空闲空间,然后该区的状态就变成了FULL_FRAG 。


现在的问题是你怎么知道表空间里的哪些区是 FREE 的,哪些区的状态是 FREE_FRAG 的,哪些区是FULL_FRAG 的?要知道表空间的大小是可以不断增大的,当增长到GB级别的时候,区的数量也就上千了,我们总不能每次都遍历这些区对应的 XDES Entry 结构吧?这时候就是 XDES Entry 中的 List Node 部分发挥奇效的时候了,我们可以通过 List Node 中的指针,做这么三件事:


把状态为 FREE 的区对应的 XDES Entry 结构通过 List Node 来连接成一个链表,这个链表我们就称之为 FREE 链表。

把状态为 FREE_FRAG 的区对应的 XDES Entry 结构通过 List Node 来连接成一个链表,这个链表我们就称之为 FREE_FRAG 链表。

把状态为 FULL_FRAG 的区对应的 XDES Entry 结构通过 List Node 来连接成一个链表,这个链表我们就称之为 FULL_FRAG 链表。

这样每当我们想找一个 FREE_FRAG 状态的区时,就直接把 FREE_FRAG 链表的头节点拿出来,从这个节点中取一些零碎的页来插入数据,当这个节点对应的区用完时,就修改一下这个节点的 State 字段的值,然后从 FREE_FRAG 链表中移到 FULL_FRAG 链表中。同理,如果 FREE_FRAG 链表中一个节点都没有,那么就直接从 FREE 链表中取一个节点移动到 FREE_FRAG 链表的状态,并修改该节点的 STATE 字段值为FREE_FRAG ,然后从这个节点对应的区中获取零碎的页就好了。


当段中数据已经占满了32个零散的页后,就直接申请完整的区来插入数据了。

9.2.3.2 链表基节点

如何找到这些链表,怎么找到某个链表的头节点或者尾节点在表空间中的位置,这就需要List Base Node的结构。这个结构中包含了链表的头节点和尾节点的指针以及这个链表中包含了多少节点的信息,我们画图看一下这个结构的示意图:

我们上边介绍的每个链表都对应这么一个 List Base Node 结构,其中:


List Length 表明该链表一共有多少节点。

First Node Page Number 和 First Node Offset 表明该链表的头节点在表空间中的位置。

Last Node Page Number 和 Last Node Offset 表明该链表的尾节点在表空间中的位置。

一般我们把某个链表对应的 List Base Node 结构放置在表空间中固定的位置,这样想找定位某个链表就容易多了。

9.2.3.3 链表小结

综上所述,表空间是由若干个区组成的,每个区都对应一个 XDES Entry 的结构,直属于表空间的区对应的 XDESEntry 结构可以分成 FREE 、 FREE_FRAG 和 FULL_FRAG 这3个链表;每个段可以附属若干个区,每个段中的区对应的 XDES Entry 结构可以分成 FREE 、 NOT_FULL 和 FULL 这3个链表。每个链表都对应一个 List Base Node 的结构,这个结构里记录了链表的头、尾节点的位置以及该链表中包含的节点数。正是因为这些链表的存在,管理这些区才容易不少。


相关实践学习
如何快速连接云数据库RDS MySQL
本场景介绍如何通过阿里云数据管理服务DMS快速连接云数据库RDS MySQL,然后进行数据表的CRUD操作。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助     相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
相关文章
|
存储 缓存 关系型数据库
MySQL的双向链表是干什么的?底层原理是什么?
MySQL的双向链表是干什么的?底层原理是什么?
520 0
|
10月前
|
存储 关系型数据库 MySQL
9.2.5.2 【MySQL】XDES 类型
9.2.5.2 【MySQL】XDES 类型
64 0
9.2.5.2 【MySQL】XDES 类型
|
存储 缓存 关系型数据库
图解MySQL系列(4)-Buffer Pool中的free链表
Buffer Pool中有N多缓存页,每个缓存页还有个描述信息。DB启动后,按BP大小向os申请一块内存区域,作为BP的内存区域。 当内存区域申请完后,DB按默认缓存页及对应描述信息快,在BP中划出一块块内存,当DB把BP划分完后
116 0
|
存储 缓存 监控
你知道MySQL的LRU链表吗?
相信大家对LRU链表是不陌生的,算是一种基础的数据结构! LRU:Least Recently Used
256 0
|
关系型数据库 MySQL
MYSQL INNODB 中通用双向链表的实现
原创:如果有误请支持 源码在Ut0lst.h中 注意:这里我将链表中的实际的串联的数据叫做数据类比如:lock_t、mem_block_t 链表作为一种的非常重要的数据结构,在任何地方都会用到,这里简单解释一下innodb双向 链表的实现,让我们来看看inno...
1250 0
|
存储 MySQL 关系型数据库
MySQL · 引擎特性 · InnoDB 软链表随手记
之前一直没去了解这快,这两天正好工作中碰到,这里简单记录下data directory的相关代码,InnoDB不支持INDEX_DIRECTORY,不在本文的讨论范围内. 以下涉及代码部分基于MySQL5.7.12 创建表 在建表时指定DATA DIRECTORY,如下所示: mysql>
2909 0
|
9月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
9月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
9月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
76 2
|
10月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
94 1