小型数据库管理系统中页的设计与实现

开篇：润墨网以专业的文秘视角，为您筛选了一篇小型数据库管理系统中页的设计与实现范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要:Ubase是自主开发的小型教学用数据库管理系统。页是该系统中的重要内容之一。它是磁盘存储的基本单位,也是内存缓冲区的基本单位。在整个系统中,页起了贯穿全局的重要作用。该文将详细介绍Ubase中页的设计与实现。

关键词:Ubase;数据库管理系统;页

中图分类号:TP311文献标识码:A 文章编号:1009-3044(2010)19-5134-03

The Design and Implementation of Page in Mini Database Management System

CHEN Yan-hong, ZHANG Tai-hong, FENG Xiang-ping

(Computer and Information Engineering Institute of Xinjiang Agricultural University, Ulumuqi 830052, China)

Abstract: Ubase is a mini,teaching database management system that is independently developed by us. The page is one of the important contents in Ubase. It is a basic unit of disk, and also is a basic unit of buffer in memory. In system, the page forms through the whole system. This article will detailedly introduce the design and implementation of page in Ubase.

Key words: Ubase; database management system; page

在信息产业飞速发展的今天,数据库技术仍然是IT技术创新乃至企业业务创新的源动力。面对日趋复杂的业务需求和爆炸式的数据增长,数据库产品的销售额以每年12%的速度在增长(已超过200亿美元)。但我国的数据库产品相对落后,市场占有率极低。而全球范围内的数据库市场被美国的几家大型企业所垄断。在我国大力发展拥有独立自主知识产权产品的背景下,作为计算机业的基础性软件,数据库系统的开发越显重要。鉴于此现状,我们开发了小型教学用数据库管理系统Ubase(以下简称为Ubase),以帮助学生在清晰掌握DBMS的结构的同时,逐步实现一个小型DBMS。这将为培养优秀的数据库人才打下良好的基础。Ubase主要实现了磁盘I/O模块、缓存管理模块、页管理、堆文件管理器、数据字典及前端工具和关系操作符及DML等功能模块。在这些模块中,页起到了贯穿整个系统的作用。页是存储的最基本单位。系统无论是在保存数据还是在读取数据的时候,都是以页为单位来进行操作的。可见页在整个DBMS的实现中占有重要的地位。下面将详细介绍在Ubase中页的设计与实现。

1 页的设计

在Ubase中实现了一个page(页)类,页在数据库中用来存放记录,同时也是磁盘和缓存池交换数据的单位,一页可以存放多条变长记录,记录是按插槽结构存储的。页(Page)在各种情况下的结构如图1~图6所示。

由图1可以清楚地看出页由两部分构成:存放数据部分和头部。其中,使用字符型数组data来存放数据,头部则包含多个存放页基本信息的域。这些域分别是:1)由包含元素offset(记录起始位置的偏移量)和length(记录长度)的slot(插槽)结构体构成的插槽数组。该数组为反向增长,即下标依次为0、-1、-2……。2)表示已使用的插槽数(其绝对值表示当前页存放的记录数)的slotCnt。指示插槽数组的下一个可用下标,其初始值为0,每插入一条记录,其值减1。3)空闲空间(即data数组中第一个可用字节)相对于页头的偏移量freePtr。4)可用空间的字节数。5)用于字对齐的域dumy。6)当前页所链接的下一页的页号nextPage。7)当前页的页号curPage。这所有的域中,需要注意的也是最重要的是插槽数组在各种情况下的变化。同时,需要补充说明一下rid是包含元素pageNo(所在页号)和slotNo(插槽号)的结构体RID的对象。

图2和图3清楚地展示了向页增加记录时data数组以及各信息域的变化。图4说明了当删除插槽元素位于插槽数组中间的记录时,其占用的存放数据的空间释放了,后面的记录向前移动,不上了空缺。但被删除记录占用的插槽数组元素只是将偏移量和记录长度值变成了-1,而并未释放。这样的设计其目的是为了提高系统的效率,避免频繁压缩或扩大所占空间并不大的插槽数组。图5说明了新插入的记录重新利用了空闲着的插槽元素。图6显示了当删除的记录的插槽为最后一个元素时,将在释放数据空间的同时也释放该插槽元素。

通过以上的图示以及详细说明,我们对于页的设计及各种情况中的变化,有了较清晰的理解。下面将详细介绍页的实现。

2 页的实现

页在实现过程中涉及到Record、slot_t、RID结构体和Page类。下面将详细介绍这些结构体和类的实现。

2.1 主要结构体的定义

页以插槽方式组装变长记录,记录按以下形式存放在内存时将有利于上层模块处理:

struct Record{

void* data;

int length;

};

在一个页上,记录的存储方式可以采用不同的方式。在Ubase中,记录的数据(data)和长度(length)是分开存储的,记录的数据(data)从一页的开头(0字节)起一个接一个存储,而包含记录偏移量(记录的开始位置)和长度的插槽数组从该页的尾部反向增长。

每个插槽数组元素的结构为:

struct slot_t {

short offset;

short length;

};

offset代表记录从data[]的开头算起的起始位置,而length与记录的长度相等。当删除一条记录时,造成的空穴应当压缩,但是,由于记录是用(pageNo, slotNo)对编址的,我们称之为RID,我们不能随意压缩插槽数组(最后一个插槽元素例外)。RID的结构如下:

struct RID{

intpageNo;

intslotNo;

};

pageNo为文件中页的物理页号( 缓存管理器和I/O层使用的页号)。slotNo为插槽号,他其实指定了插槽数组的具体元素。容易让人困惑的是,RID的slotNo域总是正数,而插槽数组的下标为负数,因此在他们之间转换时需加上一个负号。

2.2 Page类主要成员函数

Page类的成员变量在前面已详细说明,在此只详细介绍主要成员函数:

//初始化页的结构,pageNo参数用来设置curPage属性。

void init(const int pageNo);

//通过pageNo返回下一页。注意,下一页的页号不一定和当前页号( curPage)连续,这是因为堆文件中页的次序是由页的链表决定的,而不是由页号决定的,I/O层的File类在分配新页时可能返回任何页号,页号只是起到指针的作用。如果没有发生任何错误则返回OK。

const Status getNextPage(int& pageNo) const;

//将nextPage值设置为pageNo,如果没有发生任何错误则返回OK。

const Status setNextPage(const int pageNo);

//在页中插入记录rec,记录的数据和长度要分别拷贝到合适的位置,通过rid返回记录的RID,如果没有发生任何错误则返回OK,如果页没有足够的空间存储记录则返回NOSPACE。

const Status insertRecord(const Record & rec, RID& rid);

//修改RID为rid的记录,用rec替代记录的内容。如果没有发生任何错误则返回OK,如果rid无效(即页中没有该记录)则返回 INVALIDSLOTNO。

const Status updateRecord(const Record & rec, const RID& rid);

//删除RID为rid的记录,压缩删除记录后留下的空穴,在压缩空穴时,空穴后面的所有记录的offsets(在插槽数组中)都要前移空穴大小的位置,只有删除最后一个插槽对应的记录时,插槽数组方可压缩。如果没有发生任何错误则返回OK,如果rid无效(即页中没有该记录)则返回 INVALIDSLOTNO。

const Status deleteRecord(const RID & rid);

//通过firstRid参数返回本页第一条的RID,请注意slot[0]( 也许slot[-1], ...)可能因为记录删除而为空,因此,你应当从0开始,向后扫描插槽数组找寻非空插槽(空插槽的length域为-1)。如果没有发生任何错误则返回OK,如果页为空则返回NORECORDS。

const Status firstRecord(RID& firstRid) const;

//通过nextRid参数返回当前记录(curRid)的下一条记录的RID,再提醒以下,插槽数组可以为空,插槽数组的下标为 0, -1, -2, -3, ... 而不是0, 1, 2, 3 ... ,因此将slotNo转换为时curRid要加上一个负号,而且在你按slotCnt的值停止搜索(循环)时,记着slotCnt总是比最后一个有效的插槽下标小1,例如,若某页有四条记录,且没有记录被删除过,使用的插槽将为0, -1, -2, -3,而slotCnt将为-4。

如果没有发生任何错误则返回OK,如果curRid已经是该页的最后一条记录则返回ENDOFPAGE。

const Status nextRecord (const RID& curRid, RID& nextRid) const;

//通过rec参数返回RID为rid的记录(包含指向记录数据的指针和记录的长度)。你可以直接通过合适的插槽元素得到记录长度(recLen)但是recPtr应该是一个指向记录数据的指针而不是从data[]开头算起的偏移量,这意味着UBase上层可以直接修改包含该记录的页的部分内容。如果没有发生任何错误则返回OK,如果rid无效(即页中没有该记录)则返回 INVALIDSLOTNO。

const Status getRecord(const RID& rid, Record& rec);

3 页的测试

任何软件的性能都必须经过详尽而严格的测试后,才能证明其可推广。但是一个软件整体的测试,是建立在每一个模块都经过了缜密的测试的基础上的。在完成了页这部分之后,也要进行详细的测试。我们的测试主要是从以下几个方面进行的:

1)插入不同长度(当前页可能存不下)、不同类型的数据、插入批量数据、插入空数据,以测试其插入功能是否完备。

2)获取当前记录、下一条记录(个能不在当前页)、指定的记录,以测试其获取记录的功能。

3)删除所有记录、当前记录、下一条记录、指定的记录、空页中的记录等情况,以测试其删除记录的功能。

4)获取页的空闲空间大小、当前记录的偏移量、指定记录的RID等信息,以测试程序获取相关信息的功能。

4 结束语

小型教学用数据库管理系统Ubase的研制和开发,填补了新疆教学用数据库管理系统的空白,解决了开放源代码数据库管理系统过于复杂而难于让教师和学生从代码级掌握等问题。本文主要详细介绍了Ubase系统中贯穿整个系统的重要对象页及其设计和实现,以期能对数据库技术爱好者深入理解DBMS内部结构有所帮助。

参考文献:

[1] 陈民峰.国产数据库管理系统应用的研究与探讨[J].计算机应用.2003(23):39-42.

[2] 唐常杰,相利民,熊岚,等.数据库管理系统设计与实现[M].北京:电子工业出版社,1993.

[3] 刘云生.现代数据库技术[M].北京:国防工业出版社,2001.

[4] Meng X F, Hu D, Li C. Schema-Guided wrapper maintenance for web-data extraction[C]//Chiang RHL, Laender A H F, Lim E P.Proc. of the 5th ACM CIKM Int’l Workshop on Web Information and Data Management (WIDM). ACM Press, 2003:1-8.