《数据库系统概念》12-文件的组织

一个数据库被映射到多个不同的文件,这些文件由底层的操作系统来维护。每个文件分成定长的存储单元,称为块(bolck),块是存储分配和数据传输的基本单元。数据库默认的块在4-8k之间。通常没有记录比块更大(图片音频等大文件先不考虑),此外还要求每条记录保存在单个块中。

一、定长记录

instructor表的属性有:ID char(5); name char(20)。假设每个字符占用1字节,则每条记录占用25字节,不能将这些记录顺序存储,否则会出现跨块的情况;而且删除记录时,将后面的记录依次向前移动开销很大。为了解决跨块的问题,每个块只存储整数条记录,多余的空间暂时不用。而在删除记录时,可以将最后一条记录移动到被删除记录的位置,而不是将所有后面的记录依次向前移动。此外考虑到插入操作往往比删除操作更为频繁,可以将删除记录后留出的空间给下次的插入数据占用。

但插入记录时,如何找到被删除记录的位置呢:可以在文件头部留出一定空间来存储第一条被删除记录的位置,第二条记录被删除后,其位置被记录在第一条删除记录的位置,这样依次进行,形成了图示的情况:

被删除的记录形成了一条链表(linked list),这儿也称为空闲列表(free list)。每次新插入数据时,都插入header指向的地址,同时header中的地址更新为下一条被删除记录的地址。

二、变长记录

A)存储方式

数据表中包含变长属性时就会涉及到变长记录的存储。不管何种变长存储技术,都需要解决这两个基本问题:如何描述一条记录,可以方便地获取其中的属性;如何在块中存储一条记录,可以使它被方便地获取到。

一条有变长属性的记录通常具有两部分:定长的初始部分,然后是紧随其后的变长部分。定长部分用(偏移量,长度)这样的格式来表示,偏移量指示了数据的起始位置,长度即为变长部分的长度。变长部分在定长部分之后连续存储。

上图示例为instructor(ID varchar(5);name varchar(20);dept_name varchar(20);salary numeric(8,2))的存储方式,ID name dept_name是变长的(假定偏移量、长度分别占用2个字节);salary是定长的,所以直接存储。

上图也演示了空位图(null bitmap)的使用,如果属性salary是空的,则空位图的第4位会被置为1,存储salary的12-19位会被忽略。1字节的空位图可以应对最多8个属性的表结构,如果有更多属性,则需要扩展空位图的长度。这种方式以额外的空位图读取为代价,节约了存储空间,在具有很多属性同时这些属性多为空的表中是很有效的。

B)在块中存储变长记录

在块中存储变长记录时一般使用分页的槽结构(slotted-page structure),如图所示,每个块(block)中都有header:

header中包含的信息有:块中条目的个数、空闲空间的结尾处、每条记录的入口(entry,包含记录位置和大小)。记录在块中连续存储,但是,是从块的尾部开始存起的。每次插入新的纪录时,就放置在空闲空间的末尾,同时在header中保存这条记录的入口信息;当删除一条记录时,被删除记录前的记录依次先后移动,以占据被删记录的空间。由于每个块的体积在4-8k之间,并不算太大,所以这种移动的开销相对较小。在分页的槽结构中,数据指针不是直接指向数据,而是指向数据的入口(entry),于是数据在块中可以任意被移动,这可以避免块中碎片的产生。

学习资料:Database System Concepts, by Abraham Silberschatz, Henry F.Korth, S.Sudarshan

欢迎关注公众号【菜鸟程序员成长记】

本文来自企鹅号 - 菜鸟程序员成长记媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Spark学习技巧

Java面试官最爱的volatile关键字

在Java相关的岗位面试中,很多面试官都喜欢考察面试者对Java并发的了解程度,而以volatile关键字作为一个小的切入点,往往可以一问到底,把Java内存模...

39060
来自专栏Java架构

面试官最爱的volatile关键字

14030
来自专栏Vamei实验室

纸上谈兵: 队列 (queue)

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢! 队列(queue)是一个简单而常见的数据结...

20560
来自专栏微信公众号:Java团长

Java面试官最爱的volatile关键字

在Java相关的岗位面试中,很多面试官都喜欢考察面试者对Java并发的了解程度,而以volatile关键字作为一个小的切入点,往往可以一问到底,把Java内存模...

8810
来自专栏JAVA技术zhai

并发编程的艺术

关于 Java 并发也算是写了好几篇文章了,本文将介绍一些比较基础的内容,注意,阅读本文需要一定的并发基础。

13920
来自专栏玄魂工作室

看代码学安全(8 )preg_replace函数之命令执行

--------------------------------------------------------------------------------...

25730
来自专栏技术博客

Asp.Net Web API 2第十四课——Content Negotiation(内容协商)

阅读本文之前,您也可以到Asp.Net Web API 2 系列导航进行查看 http://www.cnblogs.com/aehyok/p/3446289.h...

9510
来自专栏后端技术探索

PHP 使用协同程序实现合作多任务(二)

waitingForRead 及 waitingForWrite 属性是两个承载等待的socket 及等待它们的任务的数组。有趣的部分在于下面的方法,它将检查 ...

12410
来自专栏企鹅号快讯

Java后台编程初学者,这些常识你都知道吗?

Java编程中的一些常识,希望有心学习的可以多看一眼,如果你是高手欢迎指点文中小编的不足,感谢支持。以下这些编程常识均由小编结合个人水平以及搜寻相关资料整理编辑...

206100
来自专栏北京马哥教育

Python 函数库 APIs 编写指南

32740

扫码关注云+社区

领取腾讯云代金券