数据库系统实现实验报告1

1、数据库系统实现实验报告 一、实验名称：Two Phase, Multiway Merge-Sort 二、实验环境：Linux操作系统 标准c89、c99都可运行三、 实验目的： 通过merge-sort算法的实现，掌握外存算法所基于的I/O模型与内存算法基于的RAM模型的区别；理解不同的磁盘访问优化方法是如何提高数据访问性能的。 四、 实验内容： 生成一个具有10,000,000个记录的文本文件，其中每个记录由100个字节组成。实验只考虑记录的一个属性A，假定A为整数类型。记录在block上封装

2、时，采用non-spanned方式，即块上小于一个记录的空间不使用。Block的大小可在自己的操作系统上查看，xp一般为4096 bytes。在内存分配50M字节的空间用于外部merge-sort。要求设计和实现程序完成下列功能： 1生成文本文件，其中属性A的值随机产生。 2按照ppt中的方法对文本文件中的记录，按照属性A进行排序，其中在第二阶段的排序中每个子列表使用一个block大小的缓冲区缓冲数据。 3按照教材cylinder-based buffers(825280 bytes)的方法，修改第二阶段的算法。 4比较两种

3、方法的时间性能，如果有更大的内存空间，算法性能还能提高多少？ 五、 实验分析： 一个具有10,000,000个记录的文本文件共计10,000,000*100B=1000MB,而内存只有50MB，50MB/4KB=50*1024 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个记录。

4、60;因此此次实验需要将文本文件分成20个子文件。分别对子文件分别进行内部排序。最后对20个排好序的子文件进行归并排序，完成排序。 六、 实验步骤： 1. 生成一个具有10,000,000个记录的文本文件f0.txt，其中每个记录由100个字节组成，其中有一个整数类型属性A。程序生成一个int型随机整数作为每条记录的属性A。记录写入f0.txt文件中。 2. 根据实验分析，将f0.txt文件分为20个子文件，并且按照文件中每个记录的属性对各个子文件进行内部排序（使用快速排序加快时间），最终形成20个有序的子文件 3.

5、0;对20个有序的子文件进行归并排序（在比较20个数大小的时候使用堆排序算法），最终形成一个有序的结果文件f0.txt,同时删除20个中间生成的小文件。 七、 实验流程图：Step2:开始(nr=read(f0,tr,LS)>0 N Y关闭文件f0快速排序结束创建新文件fi写入新文件拍好的数据关闭文件Step3:开始i<=20 N打开目标文件 Y打开i文件进行基于堆排序的归并算法读取BS个字节删除20个小文件进行堆排序上调算法关闭文件f1结束基于堆排序的归并算法：开始判断子文件个数dr>0 N Ytrti=fi1.tffi1.lesk;ti+;结束ti=L

6、write(fg,tr,LS); ti=0;fi1.lesk=fi1.nr Yfi1.nr=(read(fi1.flg,fi1.tf,SB)/S;装入内存是否成功功 N Y关闭文件fi; dr- -文件fi偏移量置零进行堆排序下调算法八、 实验截图及分析： 1. 在第二阶段的排序中每个子列表使用一个block大小的缓冲区缓冲数据总体运行结果图图 1生成20个小文件的图图 2第19个小文件的结果图 3文件f0.txt在排序前后的结果（看其中的修改时间）图4 图 52.结果分析从图上可以看出第一阶段生成一个10000000个记录的文件在13秒左右，第二阶段生成20个小文件并排序

7、在37秒左右，但是其算法复杂度为o(n×log2n20)o(n)(n=512000比较小所以可以)在考虑到cup的运算速度和第一阶段生成随即数花费的时间，第二阶段的时间应该和第一阶段的时间差不多。第三阶段的时间为80秒左右，但是其算法复杂度按理来说是是三个阶段中最少的，平均次数为12×log220×n3×n（n=1000000000）但是它的io次数太多为250020次，即增加了程序中断开销，又增加了磁盘读取和写入的开销。第二阶段的解决办法，减少递归的次数在数据量小于16时用插入排序。第三阶段用题目要求的cylinder-based buffe

8、rs(8255280 bytes)的方法3.改进后的结果（cylinder-based buffers(825280 bytes)的方法）考虑到一个记录100个字节所以去每个子列表的缓冲区为825200bytes图6图7九、实验总结改进后的算法明显要好于第一次运行的结果。第三阶段表现最明显，Io次数减少后时间减少了60秒。如果每个子列表的缓冲区为cylinder的整数倍或略小于他的整数倍的话效果都会非常的好，如果有更大的内存空间它将与第二阶段的时间一样甚至还要少。 十、实验代码/* = Name : dbt.c Author : sunbo Versio

9、n : Copyright : Your copyright notice Description : Hello World in C, Ansi-style = */#include<stdio.h>#include<stdlib.h>#include<time.h>#include<malloc.h>#include<unistd.h>#include <sys/types.h>#include <sys/stat.h>#include <fcntl.h>#define R 10000000/

10、总记录数#define L 512000/内存最大记录数#define S 100/单个记录的长度#define D 20/R/L+1#define A 0/记录中属性A的位置#define B 82252/一个子文件的内存中的记录数#define SB 8225200/S*B#define LS 51200000/L*S/表示一个记录 struct btr int record25; ; /表示子文件的路径struct pstr char ptD30; ; int main() time_t startT,sdT,sfT, endT; clock_t a,b,c,d; int step1(c

11、onst char*, struct btr *);/生成一个10，000，000个随机记录的文件 struct pstr step2(const char*, struct btr *);/将上面的文件分成20个小文件并排序 void step3(struct pstr,struct btr *);/用归并算法将上面的20个小文件排好续重新放入源文件 startT=time(NULL); a=clock(); char * str="f0.txt"/原始文件的目录 struct btr *tr; tr = (struct btr *)malloc(LS); step1(s

12、tr,tr); sdT=time(NULL); b=clock();printf("第一阶段的运行时间为%fn",difftime( sdT, startT); printf("%fn",(double)(b-a)/1000); struct pstr ps= step2(str,tr); sfT=time(NULL); c=clock(); printf("第二阶段的运行时间为%fn",difftime( sfT, sdT); printf("%fn",(double)(c-b)/1000); step3(ps,

13、tr); endT=time(NULL); d=clock(); printf("%fn",(double)(d-c)/1000); printf("第三阶段的运行时间为%fn",difftime( endT, sfT); printf("总运行时间为%fn",difftime( endT, startT); free(tr); return 0; int step1(const char*str,struct btr *tr) int f0; srand(unsigned)time(NULL); f0 = open(str,O_WR

14、ONLY|O_CREAT|O_TRUNC,S_IRUSR|S_IWUSR); int i=0,j=0,m=L; while(j<D) i=0; while(i<m) (tr+i)->recordA=rand();/printf("%dn",(tr+i)->recordA); i+; write(f0,tr,i*sizeof(struct btr); j+; if(j=(D-1) m= R-(D-1)*L; close(f0); return 0; /将上面的文件分成20个小文件并排序 struct pstr step2(const char*str,

15、 struct btr *tr) /快速排序 void kuip(struct btr *,int,int); /int cmp(struct btr* a, struct btr* b) / return (a->recordA-b->recordA); / struct pstr nps; int f0 = open(str,O_RDONLY); int nr,h=0; while(nr=read(f0,tr,LS)>0) /qsort(tr,L,S,cmp); kuip(tr,0,nr/S-1); sprintf(nps.pth,"%s%d",&qu

16、ot;file",h); / printf("%sn",nps.pth); int fi=open(nps.pth,O_WRONLY|O_CREAT|O_TRUNC,S_IRUSR|S_IWUSR); write(fi,tr,nr); close(fi); h+; close(f0); return nps; /快速排序 void kuip(struct btr* tr,int low1,int high1) if(high1-low1>15) int l1=trlow1.recordA-trhigh1.recordA; int l2=trlow1.reco

17、rdA-tr(low1+high1)/2.recordA; struct btr prvotkey; if(l1>0&&l2>0) if(l1>l2) prvotkey =tr(low1+high1)/2; else prvotkey=trhigh1; else if(l1<0&&l2<0) if(l2>l1) prvotkey =tr(low1+high1)/2; else prvotkey=trhigh1; else prvotkey=trlow1; int low=low1; int high=high1; while

18、(low<high) while (low<high&&trhigh.recordA>=prvotkey.recordA) -high; trlow=trhigh; while (low<high&&trlow.recordA<=prvotkey.recordA) +low; trhigh=trlow; trlow=prvotkey; kuip(tr,low1,low-1); kuip(tr,low+1,high1); else struct btr sor; int i=low1+1; while(i<=high1) sor

19、=tri; int j=i-1; while(j>=low1&&(sor.recordA<trj.recordA) trj+1=trj; j-; trj+1=sor; i+; /用归并算法将上面的20个小文件排好续重新放入源文件 void step3(struct pstr ps,struct btr * tr) struct fil struct btr *tf; int flg; int lesk; int nr; fiD+1; int i=1; /printf("%dn",1); while(i<=D) /fii=(struct fi

20、l *)malloc(sizeof(struct fil); fii.tf=(struct btr *)malloc(SB); fii.flg=open(ps.pti-1,O_RDONLY); fii.lesk=0; fii.nr=read(fii.flg,fii.tf,SB)/S; int di=i/2,dt=i; /printf("%dn",fi1.tf0.recordA); while(di>0&&fidt.tf0.recordA<fidi.tf0.recordA) struct fil fd=fidt; fidt=fidi; fidi=fd; dt=di; di=di>>1; i+; /printf("%dn",fi1.tf0.recordA); int dr=D,ti=0; int fg= open("f1.txt&qu