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

数据库系统实现实验报告一、实验名称：TwoPhase,MultiwayMerge-Sort二、实验环境：Linux操作系统 标准c89、c99都可运行三、实验目的：通过merge-sort算法的实现，掌握外存算法所基于的I/O模型与内存算法基于的RAM模型的区别；理解不同的磁盘访问优化方法是如何提高数据访问性能的。四、实验内容：生成一个具有10,000,000个记录的文本文件，其中每个记录由100个字节组成。实验只考虑记录的一个属性A，假定A为整数类型。记录在block上封装时，采用non-spanned方式，即块上小于一个记录的空间不使用。Block的大小可在自己的操作系统上查看，xp一般为4096bytes。在内存分配50M字节的空间用于外部merge-sort。要求设计和实现程序完成下列功能：1生成文本文件，其中属性A的值随机产生。2按照ppt中的方法对文本文件中的记录，按照属性A进行排序，其中在第二阶段的排序中每个子列表使用一个block大小的缓冲区缓冲数据。3按照教材cylinder-basedbuffers(825280bytes)的方法，修改第二阶段的算法。4比较两种方法的时间性能，如果有更大的内存空间，算法性能还能提高多少？五、实验分析：一个具有10,000,000个记录的文本文件共计10,000,000*100B=1000MB,而内存只有50MB，50MB/4KB=50*1024KB/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个记录的文本文件f0.txt，其中每个记录由100个字节组成，其中有一个整数类型属性A。程序生成一个int型随机整数作为每条记录的属性A。记录写入f0.txt文件中。2.根据实验分析，将f0.txt文件分为20个子文件，并且按照文件中每个记录的属性对各个子文件进行内部排序（使用快速排序加快时间），最终形成20个有序的子文件3.对20个有序的子文件进行归并排序（在比较20个数大小的时候使用堆排序算法），最终形成一个有序的结果文件f0.txt,同时删除20个中间生成的小文件。七、实验流程图：Step2:开始(nr=read(f0,tr,LS)0 N Y关闭文件f0快速排序结束创建新文件fi写入新文件拍好的数据关闭文件Step3:开始i0 N Ytrti=fi1.tffi1.lesk;ti+;结束ti=Lwrite(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个小文件并排序在37秒左右，但是其算法复杂度为o(nlog2n20)o(n)(n=512000比较小所以可以)在考虑到cup的运算速度和第一阶段生成随即数花费的时间，第二阶段的时间应该和第一阶段的时间差不多。第三阶段的时间为80秒左右，但是其算法复杂度按理来说是是三个阶段中最少的，平均次数为12log220n3n（n=1000000000）但是它的io次数太多为250020次，即增加了程序中断开销，又增加了磁盘读取和写入的开销。第二阶段的解决办法，减少递归的次数在数据量小于16时用插入排序。第三阶段用题目要求的cylinder-basedbuffers(8255280bytes)的方法3.改进后的结果（cylinder-basedbuffers(825280bytes)的方法）考虑到一个记录100个字节所以去每个子列表的缓冲区为825200bytes图6图7九、实验总结改进后的算法明显要好于第一次运行的结果。第三阶段表现最明显，Io次数减少后时间减少了60秒。如果每个子列表的缓冲区为cylinder的整数倍或略小于他的整数倍的话效果都会非常的好，如果有更大的内存空间它将与第二阶段的时间一样甚至还要少。十、实验代码/* = Name : dbt.c Author : sunbo Version : Copyright : Your copyright notice Description : Hello World in C, Ansi-style = */#include#include#include#include#include#include #include #include #define R 10000000/总记录数#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(const 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(str,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,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_WRONLY|O_CREAT|O_TRUNC,S_IRUSR|S_IWUSR); int i=0,j=0,m=L; while(jD) i=0; while(irecordA=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, 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,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-low115) int l1=trlow1.recordA-trhigh1.recordA; int l2=trlow1.recordA-tr(low1+high1)/2.recordA; struct btr prvotkey; if(l10&l20) if(l1l2) prvotkey =tr(low1+high1)/2; else prvotkey=trhigh1; else if(l10&l2l1) prvotkey =tr(low1+high1)/2; else prvotkey=trhigh1; else prvotkey=trlow1; int low=low1; int high=high1; while (lowhigh) while (low=prvotkey.recordA) -high; trlow=trhigh; while (lowhigh&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=low1&(sor.recordAtrj.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(i0&fidt.tf0.recordA1; i+; /printf(%dn,fi1.tf0.recordA); int dr=D,ti=0; int fg= open(f1.txt,O_WRONLY|O_CREAT|O_TRUNC,S_IRUSR|S_IWUSR); while(dr0) trti=fi1.tffi1.lesk; /printf(%dn,fi1.tf0.recordA); ti+; if(ti=L) /*int j=0; while(jrecordA); j+; */ write(fg,tr,LS); ti=0; fi1.lesk+; if(fi1.lesk=fi1.nr) fi1.nr=(read(fi1.flg,fi1.tf,SB)/S; if(fi1.nr=0) free(fi1.tf); close(fi1