东华大学计算机学院 研究生 数据库实验1

数据库系统实现

数据库系统实现

实验报告

实验名称：实验1：Two Phase, Multiway Merge-Sort

姓名：王国林（2131524） 指导老师：王洪亚 日期：2013年10月20日

一、 实验目的：

通过merge-sort算法的实现，掌握外存算法所基于的I/O模型与内存

数据库系统实现

算法基于的RAM模型的区别；理解不同的磁盘访问优化方法是如何提高数据访问性能的。

二、 实验内容：

生成一个具有10,000,000个记录的文本文件，其中每个记录由100个字节组成。实验只考虑记录的一个属性A，假定A为整数类型。记录在block上封装时，采用non-spanned方式，即块上小于一个记录的空间不使用。Block的大小可在自己的操作系统上查看，xp一般为4096 bytes。在内存分配50M字节的空间用于外部merge-sort。要求设计和实现程序完成下列功能：

1．生成文本文件，其中属性A的值随机产生。

2．按照ppt中的方法对文本文件中的记录，按照属性A进行排序，其中在第二阶段的排序中每个子列表使用一个block大小的缓冲区缓冲数据。

3．按照教材cylinder-based buffers(1M bytes)的方法，修改第二阶段的算法。

4．比较两种方法的时间性能，如果有更大的内存空间，算法性能还能提高多少？

三、 实验分析：

一个具有

10,000,000

个记录的文本文件共计

50MB，50MB/4KB=50*1024

10,000,000*100B=1000MB,而内存只有

KB/4KB=12800块，每块可以存放4*1024B/100B=40个记录，每块剩余96KB，内存一共可以存放12800*40=512000个记录，一共有10,000,000个记录。所以要进行10,000,000/512000=19.53次，即20次排序，每次排序的记录数为10,000,000/20=500,000个记录。

因此此次实验需要将文本文件分成20个子文件。分别对子文件分别进行内部排序。最后对20个排好序的子文件进行归并排序，完成排序。

四、 程序的设计思路：

数据库系统实现

1. 生成一个具有10,000,000个记录的文本文件data.txt，其中每个记

录由100个字节组成，其中只有一个整数类型属性A，剩余字节用0填充。程序生成一个4个字节之内随机整数作为每条记录的属性，剩余字节用0填充。记录写入data.txt文件中。

2. 根据实验分析，将data.txt文件分为20个子文件，并且按照文件

中每个记录的属性对各个子文件进行内部排序，最终形成20个有序的子文件data1.txt,data2,txt,…data20.txt。

3. 对20个有序的子文件进行归并排序，最终形成一个有序的结果文件

result.txt。

五、 程序流程图：

FileGenerate：

开始否记录数小于10,000,000？是生成一个随机数结束随机数写入记录中为该记录填充0直到达到100字节记录数+1

数据库系统实现

开始data.txt已经读完？是结束否子文件个数+1从data.txt中读一个记录到recordTemp对该子文件数组进行内部排序记录放入一个子文件数组中把该子文件数组写入到子文件中子文件数组中记录数等于500000？是新建一个子文件数组否

数据库系统实现

开始每个文件读1个记录进入归并数组中结果文件中的记录条数小于10000000条记录否结束是在当前归并数组中选出最小元素写入结果文件result.txt中结果文件中的记录条数+1结果文件中的记录条数小于500000条否该文件在归并数组中的相应位置置为最大值是从对应的子文件中再选出一条记录放入归并数组中

六、 实验结果及分析：

1. 生成一个具有10,000,000个记录的文本文件data.txt。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库东华大学计算机学院 研究生 数据库实验1在线全文阅读。