-
数据库系统——关系型数据在磁盘上的存储布局
2013-05-04 19:22:41关系型数据在磁盘上的存储布局 1.基于page的heap file Heap file是保存page数据的一种数据结构。从功能上来说,Heap file类似于内存数据结构中的链表。它可以作为通用数据项的一种无序容器。 Heap file和链表...关系型数据在磁盘上的存储布局
1.基于page的heap file
Heap file是保存page数据的一种数据结构。从功能上来说,Heap file类似于内存数据结构中的链表。它可以作为通用数据项的一种无序容器。
Heap file和链表结构类似的地方:
--高效的增加(append)功能
--支持大规模顺序扫描
--不支持随机访问
下面是Heap file自有的一些特性:
--数据保存在二级存储体(disk)中:Heapfile主要被设计用来高效存储大数据量,数据量的大小只受存储体容量限制;
--Heapfile可以跨越多个磁盘空间或机器:heapfile可以用大地址结构去标识多个磁盘,甚至于多个网络;
--数据被组织成页;
--页可以部分为空(并不要求每个page必须装满);
页面可以被分割在某个存储体的不同的物理区域,也可以分布在不同的存储体上,甚至是不同的网络节点中。我们可以简单假设每一个page都有一个唯一的地址标识符PageAddress,并且操作系统可以根据PageAddress为我们定位该Page。
下面是heap file的一些主要的接口:
class HeapFile
{
PageIterator scan();
PageAddress allocate();
void deallocate(PageAddress);
Page read(PageAddress);
void write(PageAddress, Page);
PageAddress find_free(int minsize);
};
class PageIterator
{
Page first();
boolean hasNext();
Page next();
};
1.1 基于链表的heap file实现
一种简单的基于链表的heap file实现方案的磁盘结构布局:
但是这种方案存在这样的问题:HeapFile::find_free(int minsize)的开销比较大。如上图,我们要定位存在剩余空间的page(page3),那么我们必须从开始遍历很多page(page1和page2)。我们发现,这时的遍历I/O开销是这个数据存储区,显然这样I/O开销就太高。
1.2 基于索引的heap file实现
一个简单的,但是比较高效的heap file的实现是:用少量的block去存放所有page的地址索引和它们剩余的空间大小。
从page1到page2都是满的,它们的剩余空间大小n1和n2都为零。我们寻找一个存在剩余空间的page仍然需要遍历索引,但是这时我们的开销仅仅是一个磁盘的I/O。
如果索引page是多个的话,那么我们可以采用链表的形式存储page索引,如下图所示
我们假设有如下参数:
Page size:16K
Page address size:32bits
那么,每个索引项(即是索引Page的记录项)的大小:
Bits for free space+Bits for page addresslog2(16 KB)+32=17+32 bits=49 bits
则,每个索引page能索引的数据大小为:
16 KB/49 bits=2674 pages=42 MB
2.数据的序列化
我们稍稍从磁盘整体布局离题讨论一下如何从tuple record转化成字节数组。
2.1定长record的序列化
对于一些关系型数据,所有的record必须具有相同的长度。例如,思考一下用下面的SQL定义的关系型schema:
CREATE TABLE Person1 (
name CHAR(100) NOT NULL,
age INTEGER NOT NULL,
birthdate DATETIME NOT NULL
)
所有的记录都具有一样的字节数:
100 * sizeof(CHAR) + sizeof(INTEGER) + sizeof(DATETIME)
那么定长record可以采用如下的序列化方式:
从schema上来说,我们可以检查每个字段的大小,从而将字节数组解码成不同的字段。
2.2变长record的序列化
假设我们改变上面Person1表的schema定义,使name可以是不超过1024个字符。Schema如下:
CREATE TABLE Person2 (
name VARCHAR(1024) NOT NULL,
age INTEGER NOT NULL,
birthdate DATETIME
)
上面table的record是边长的是由于:
--name字段是一个变长的字符串;
--birthdate可以为NULL;
变长record的序列化的关键是字段边界的界定。一种比较流行的方法是在record的首部保存字段边界的offset。
Person2的record的编排方式如下:
Note:我们在首部设置4个整型去存储三个字段的四个边界offset。
上面的编排方式很自然的提供一种NULL字段的编排方式--可以标识该字段的值为NULL,如下图:
第三个offset和第四个offset指向同一个位置,那么就表明第三个字段的大小是零,即是一个NULL值。
3 Page Format
现在我们要具体的描述一下数据在page中是如何编排的。
我们做一个简单化的设想:每个page中的tuple record具有相同的schema。
这种简单化的设想有两个重要的结果:
1. 每个关系表至少占用一个page;
2. 每个page中保存的要么是定长的数据,要么是变长数据;
在Page编排格式中有两个变量:一个是为了定长数据,一个是为了变长数据。对于DMS(Database Management System)来说,Page Format必须具有如下的特性:
1.高效利用磁盘空间;
2.支持scan、insert、delete和modify record的功能,并且要求高效和尽量少的I/O;
3.有一个高效的为每一个record分配唯一ID的方式。并且某个record的ID不会由于数据库的modify、insert、delete而改变;
4.每个record的大小不能超过一个Page的有效存储大小,这个特性在以后的章节将会被放宽。
3.1基于定长record的page format
在Page中组织编排定长record相对来说是比较容易的。常用的方法是将一个Page的初始数据段分割成大小相等的M个slot,每个slot装载一个record。Page的最后一段存储着一个整数M和标识对应的slot是否为空的M bit。
定长record的Page的维护也非常简单。
Record ID
record r的Record ID可以是这种结构<pid(P), offset(r)>。
Record ID的一个重要的特性是它的分配是持久的——它不因数据库的改变而受到影响。甚至,Record ID作为数据库定位该record在物理磁盘上位置的依据,是完全能胜任的。
创建一个新的Record
将record r插入到page P中,
1.将page P中的最后sizeof(int)个字节读出来作为M,
2.然后在倒着遍历M bits,
3.如果所有M bit都是1,那就表明page P没有多余的空间存储record r,
4.如果K-th bit是0(当然这个K是离结尾最近的那个为0的),那么,record r可以存储在P[nk:n(k+1)]的位置,其中n=sizeof(r),最后将K-th bit置为1.
修改record
修改一个record,我们可以很简单的用该record的新值去覆盖旧的值。这是由于都是定长数据,它的边界不会因为record的值而受到影响。
删除record
删除一个record,就将对应的那个bit从1改变成0即可。
3.2.变长record的Page Format
在一个Page中保存变长数据以及对该数据的维护相对来说都是比较困难的,因为:
1.record的边界以及字段的边界都依赖于数据内容(即是record的值);
2.Record被修改时,record的大小可能会改变,这就造成物理上对该record的重新定位。这就需要一个非常高效的在一个Page内的或是多个Page的record迁移方法;
3.如果Record ID需要持久,那么尽管该record已经被迁移,那么该record被分配到的Record ID也不能改变。
一个有效的设计方法是维护一个Page首部去跟踪free空间和record的索引。
Record ID的分配
Record ID是由page ID和目录索引组成的。
创建一个新的record
将record r插入到page P中,
1.确保page P中的剩余空间能存放sizeof(r)的数据和(sizeof(offset)+sizeof(int))的目录索引;
2.将r从剩余空间的开始写入;
3.修改目录索引信息:offset和record size;
4.修改空余空间指针的指向。
删除record
将record i从page P中删除:
1.如果i是最后一个record,我们只需将最后一个目录索引删除,在修改空余空间的指向即可;
2.如果i不是最后一个,我们只需将该record对应的目录索引的offset设置为-1即可。
修改record
假设r是一个旧的值,r’是一个新的值。i是r的索引。
如果|r’|<=|r|,那么就将新的值写的offset(i),修改对应的目录索引的size:sizeof(r’)。
如果|r|<=|r’|:
--如果该record所在的page P还有空余的空间能够存放r’,那么
1.将r’写入page P;
2.修改offset(i),更新到r’存储的位置;
3.更新空余空间的指针。
--如果剩余空间不足以存放r’,那么我们就尝试压缩page P(由于删除操作使得page中有很多空洞,所以可以压缩)。压缩后,如果存在足够的空间存放r’,那么就按上面的顺序增加r’;如果还是没有足够的空间存放r’,那么:
1.申请一个新page,将r’写入到新page中。由于r’在不同的page中,所以它有一个不同的Record ID;
2.将r’的Record ID写入到r中去。
4.处理比较大的record
在这个部分,我们专注讨论一下一个record保存在多个page中的方法。
4.1.record跨page保存的动因
一个明显的动因是当一个record的大小超出了page size。record域被设计用来承载一个大的对象,比如:文件,多媒体数据等等。几乎可以肯定的是,BLOB记录必须跨越多个page。
另一个动因是避免空间的浪费。思考一下,在上面介绍的定长record的存储中,如果record的大小略大于1/2page size,那么我们的一个page只能存放一个record,我们浪费几乎浪费了一半的存储空间。在这种情况下,我们采用record跨page存储将获益匪浅。
4.2.Spanned records(跨page的record)
--如果一个record存储在多个page中,那么我们就说它spanned。否则,unspanned。
--Spanned record分别保存在不同的record fragment中。每个片段在一个page中。
--每个record必须用1 bit去标识该record是否spanned。
--每一个record fragment都需要保存下一个record fragment的地址,使得众多的record fragment能够串联起来。
-
数据库在磁盘上的存储
2018-11-02 22:09:40关系型数据在磁盘上的存储布局: https://blog.csdn.net/cjfeii/article/details/8884658#t10 基于page的heap file 深入理解数据库磁盘存储(Disk Storage): ... ...关系型数据在磁盘上的存储布局:
https://blog.csdn.net/cjfeii/article/details/8884658#t10基于page的heap file
深入理解数据库磁盘存储(Disk Storage):
https://blog.csdn.net/u011537073/article/details/49157903 -
高并发瓶颈在IO磁盘上,不在CPU上
2020-06-01 22:44:57互联网应用在高并发情况下,瓶颈在 IO 上(网络 IO 和磁盘 IO 上),并不在 CPU 上,这时采用传统的多线程技术基本上无济于事。 减少数据库磁盘 IO 时间最有效的办法是使用缓存(如redis非关系型数据库一些场合替换...互联网应用在高并发情况下,瓶颈在 IO 上(网络 IO 和磁盘 IO 上),并不在 CPU 上,这时采用传统的多线程技术基本上无济于事。
减少数据库磁盘 IO 时间最有效的办法是使用缓存(如redis非关系型数据库一些场合替换mysql关系型数据库),还可以将数据库弄成 master/slave 的读写分离,分表分库等等。
减少网络 IO、静态资源磁盘 IO 有效的办法:响应使用 GZIP 压缩(Web 服务器都能支持)、设置静态资源(图片、JS 文件、CSS 文件、HTML 文件的过期时间),应用在多 IDC 进行部署、使用 DNS 分发至不同的节点,若要加速用户的访问速度,可以使用 CDN 等等。
-
简述磁盘和文件系统的关系
2013-01-05 16:11:58文件系统是在磁盘上的,是在磁盘上组织文件的方法。磁盘的一个分区可以是一个文件系统 当然也可以所有分区文件系统一样文件系统是在磁盘上的,是在磁盘上组织文件的方法。磁盘的一个分区可以是一个文件系统 当然也可以所有分区文件系统一样
-
计算机内存和磁盘的关系
2020-09-04 20:42:56计算机内存和磁盘的关系 前言 上篇文章详细讲了计算机内存的物理结构,逻辑结构以及在内存的基础上理解几种常见的数据结构。但是,计算机系统出了内存之外,还有一个非常重要的硬件,那就是磁盘。他们都是用于计算机... -
mysql 上一行数据_MySql数据是如何存储在磁盘上存储的?
2021-01-29 12:21:41关于MySql数据库,相信很多人都不陌生,这是当今最常用的一种关系型数据库,关于MySql的知识也是很丰富的。...Innodb的存储格式我们知道,关于Mysql这种关系型数据库,里面保存的数据最终都是要持久化到磁盘... -
mysql数据保存在哪个盘_MySql数据是如何存储在磁盘上存储的?
2021-02-07 15:24:57关于MySql数据库,相信很多人都不陌生,这是当今最常用的一种关系型数据库,关于MySql的知识也是很丰富的。...**Innodb的存储格式**我们知道,关于Mysql这种关系型数据库,里面保存的数据最终都是要持久化到磁盘文... -
MySql数据在磁盘上到底是怎么存储的?被存储的数据怎么查找?
2021-02-19 19:45:28本文来自作者投稿,原作者:zyz1992 关于MySql数据库,相信很多人都不陌生...我们知道,关于Mysql这种关系型数据库,里面保存的数据最终都是要持久化到磁盘文件上面的。磁盘文件里存放的物理格式就是数据页(关于数. -
2、磁盘管理、进程管理、在CentOS上安装JDK、安装Tomcat
2020-09-12 23:41:45Linux磁盘管理好坏直接关系到整个系统的性能问题。 Linux磁盘管理常用命令为 df、du。 df :列出文件系统的整体磁盘使用量 du:检查磁盘空间使用量 df du 查看当前目录下的磁盘空间使用情况。 与df命令不同的... -
inode、block和磁盘性能的关系
2019-09-18 08:38:02inode、block和磁盘性能的关系 什么是inode和block? 理解inode,要从文件储存说起。 文件储存在硬盘上,硬盘的最小存储单位叫做"扇区"(即:Sector)。每个扇区储存512字节(相当于0.5KB)。 操作系统读取硬盘的... -
mysql 上一行数据_下次面试我一定问:MySql数据是如何存储在磁盘上存储的?
2021-01-26 04:37:33本文来自作者投稿,原作者:zyz1992关于MySql数据库,相信很多人都不陌生,这是当今最常用的一种关系型数据库,关于MySql的知识也是很丰富的。那么,不知道大家有没有想过这样的问题:MySql中的数据是存在哪的?又是... -
mysql怎么存储评论_上次面试被问到的:MySql数据是如何存储在磁盘上的?
2021-01-26 03:42:31关于MySql数据库,相信很多人都不陌生,这是当今最常用的一种关系型数据库,关于MySql的知识也是很丰富的...Innodb的存储格式我们知道,关于Mysql这种关系型数据库,里面保存的数据最终都是要持久化到磁盘文件上面的... -
Linux下磁盘分区和目录的关系
2017-05-26 10:20:353、磁盘Linux分区都必须挂载到目录树中某个具体的目录上才能进行读写操作(这点在安装Linux系统的时候,需要你手动选择挂载,这也是和安装Windows系统不同的地方); 4、根目录是所有Linux的文件和目录所在的地方... -
磁盘分区
2018-04-24 20:10:26一、BIOS/MBRUEFI/GPT他们之间的关系1、传统的主板就是传统 BIOS,可在使用 MBR 分区表的硬盘(俗称 MBR磁盘,就是传统常用的模式)上安装32或64位操作系统。同时也支持使用 GUID 分区表的硬盘(俗称GPT磁盘),但该... -
zz :inode、block和磁盘性能的关系
2019-08-17 20:30:29inode、block和磁盘性能的关系 什么是inode和block? 理解inode,要从文件储存说起。 文件储存在硬盘上,硬盘的最小存储单位叫做"扇区"(即:Sector)。每个扇区储存512字节(相当于0.5KB)。 操作系统读取硬盘的... -
mysql 的数据存放在_下次面试我一定问:MySql数据是如何存储在磁盘上存储的?...
2021-01-26 23:06:58本文来自作者投稿,原作者:zyz1992关于MySql数据库,相信很多人都不陌生,这是当今最常用的一种关系型数据库,关于MySql的知识也是很丰富的。那么,不知道大家有没有想过这样的问题:MySql中的数据是存在哪的?又是... -
mysql中字段存储1_2_3这样数据的读取_MySql数据是如何存储在磁盘上存储的?
2021-02-08 00:33:51关于MySql数据库,相信很多人都不陌生,这是当今最常用的一种关系型数据库,关于MySql的知识也是很丰富的...Innodb的存储格式我们知道,关于Mysql这种关系型数据库,里面保存的数据最终都是要持久化到磁盘文件上面的... -
CPU、内存、磁盘IO之间的关系
2019-04-29 10:08:14CPU和内存的关系: CPU是负责运算和处理的,内存是交换数据的。 当程序或者操作者对CPU发出指令,这些指令和数据暂存在内存里,在CPU空闲时传送给CPU,CPU处理后把... -
RedhatVM虚拟机挂载磁盘出现问题:无法用yum安装包关系
2020-04-03 17:03:39可能只会在VM虚拟机上出现这样的问题 无法用yum安装包关系 反复报:Unable to read consumer identity 一、问题描述 挂载磁盘后执行yum clean all [root@qiuhua ~]# yum clean all Loaded plugins: katello, ... -
缓存和内存,磁盘的关系
2015-11-25 17:48:18缓存严格来说就是一种临时存储,和内存原理上没有什么区别。 因为在大数据交换中,存储器不能及时和运算器、控制器交换数据的话,就会出现问题,所以人们发明了缓存。 说白了假设运算器和控制器是工厂,存储器... -
论文研究-GEP在磁盘负载均衡方面的应用研究.pdf
2019-07-22 23:23:32如何提高存储子系统的 I/O性能一直以来都是计算机领域的一个研究热点 ,而目前提高存储子系统的 I/O性能的一个最大障碍就是负载不均衡。提出了一种采用基因...在操作上 ,采用选择复制、倒置和交换等特殊的搜索算子。 -
python磁盘io_python2.0_s12_day9_协程&多线程和cpu,磁盘io之间的关系
2020-12-29 02:57:07事件驱动和异步io有什么直接关系。当我们访问一个网页,不考虑网络问题。我们人类不觉得网页慢。但是实际中对计算机来说还是慢。那慢在哪里。ioio操作是整个网络操作中最慢的。比如你打开网页要是有2秒。cpu去请求... -
文件系统逻辑块与磁盘物理扇区的关系
2018-01-22 14:42:00文件系统逻辑块是文件系统中最小的操作单位,windowsNTFS中叫做文件系统分配单元。它由一个或多个扇区组成,;OS的虚拟文件系统从硬件设备上读取一个...不同的文件系统文件块可使用不同的大小,操作系统会在内存中开... -
inode、block块、superblock和磁盘性能的关系
2020-04-29 10:18:14文件储存在硬盘上,硬盘的最小存储单位叫做"扇区"(即:Sector)。每个扇区储存512字节(相当于0.5KB)。 操作系统读取硬盘的时候,不会一个个扇区地读取,这样效率太低,而是一次性连续读取多个扇区,即一次性... -
linux下查询asm磁盘和linux的分区的对应关系确认的方法
2013-01-03 14:09:16在通过EM进行ASM磁盘管理实验过程中 ,卸载了磁盘ASMDISK11,查看有多块磁盘,不知道对应于linux上哪块分区了,且必须先进行磁盘删除才能重用这个分区通过如下命令可以查看asm磁盘对应linux分区[root... -
VMWare下的CentOs的磁盘扩容以及与windows文件系统的关系对比
2017-06-09 01:16:49在物理磁盘的基础上,我们划分了主分区和扩展分区。然后扩展分区又会划分一块到几块的逻辑分区 然后我们的c盘、d盘等每一个盘符一般会与一个分区对应。比如c盘一般是主分区,d、e这些是逻辑分区 然后在每个盘符中... -
分区 分区函数 文件组 分区方案 文件 磁盘之间的关系
2020-04-29 22:08:41**图片文字解说:**在创建分区方案时需要根据分区函数的参数定义映射分区的文件组。需要文件组来容纳分区数,文件组课由单个或多个...2、有分区函数创建分区方案,定义分区函数在文件组上的位置。3、使用分区方案。 ...
-
目标检测中的先验框详解(原作者以yolov2,yolov3为例写得非常详细)
-
PPT大神之路高清教程
-
2018O奖论文-How to achieve the full adoption of all-electric vehicles.PDF
-
干货丨时序数据库DolphinDB集群如何扩展节点和存储?
-
ApacheSpark大数据分析入门(一)
-
CCS(硬件基础)播放器.txt
-
为什么 Nginx 比 Apache 更牛叉?
-
防复制防破解小区门禁梯控升级非联网CPU卡脱机写卡门禁梯控一卡通系统92HID623CPU V5.00操作说明之软件的安装卸载说明
-
一天学完MySQL数据库
-
MySQL 管理利器 mysql-utilities
-
跨境电商ERP中的自动化 4.平台订单自动取运单号
-
培训师职业形象.ppt
-
企业内训师培训技巧2.ppt
-
半股票调和:我只提出了几个主题,外加一些摘要和其他调整-源码
-
【Python-随到随学】FLask第二周
-
培训培训师.pptx
-
五星内训师团队管理.pdf
-
ubuntu18.04安装后再安装所需插件遇见的问题(自用)
-
第九十五题:编写程序求出 1000-2000 年之间的所有闰年,并统计个数。
-
尼尔森十大交互原则实用总结