数据库系统实现

《数据库系统实现》由会员分享，可在线阅读，更多相关《数据库系统实现（23页珍藏版）》请在装配图网上搜索。

1、两阶段多路归并排序Two-Phase Multiway Merge-Sort实验报告目录1实验目的 32实验内容 33实验环境 34实验的设计和实现 34.1算法描述34.2设计思路44.3数据结构54.4具体实现65实验结果 95.1 50MB内存TPMMS实验结果95.2 10MB内存TPMMS实验结果95.3 100MB内存TPMMS实验结果105.4 三者的比较116 实验遇到的问题和解决方法 116.1 Phase2 阶段遇到的问题和解决方法 116.2 生成子记录文件名的方法137 代码附录 131 实验目的通过 merge-sort 算法的实现，掌握外存算法所基于的 I/O 模型

2、与内存算法基 于的 RAM 模型的区别；理解不同的磁盘访问优化方法是如何提高数据访问性能 的。2 实验内容生成一个具有 10,000,000 个记录的文本文件，其中每个记录由 100 个字节组 成。实验只考虑记录的一个属性A,假定A为整数类型。记录在block上圭寸装时， 采用non-spanned方式，即块上小于一个记录的空间不使用。Block的大小可在 自己的操作系统上查看，xp 一般为4096 bytes。在内存分配50M字节的空间用 于外部merge-sort。要求设计和实现程序完成下列功能：1) 生成文本文件，其中属性 A 的值随机产生。2) 按照 ppt 中的方法对文本文件中的记录

3、，按照属性 A 进行排序，其中在 第二阶段的排序中每个子列表使用一个 block 大小的缓冲区缓冲数据。3) 按照教材cylinder-based buffers(lM bytes)的方法，修改第二阶段的算法。4) 比较两种方法的时间性能，如果有更大的内存空间，算法性能还能提高 多少？3 实验环境1) Visual C+ 6.02) Windows 7 操作系统4 实验的设计和实现4.l 算法描述Two-Phase Multiway Merge-Sort算法的具体描述分为2个阶段，如下所示: Phase 11) Fill main memory with records.2) Sort wit

4、h favorite main memory sorting algorithms.3) Write sorted list to disk.4) Repeat until all records have been put into one of the sorted lists. Phase 21) Initially load input buffers with the first block of their respective sorted lists.2) Repeated run a competition among the first unchosen records o

5、f each of the buffered blocks.3) If an input block is exhausted, get the next block from the same file.4) If the output block is full, write it to disk.4.2 设计思路从上述的算法描述中，我们知道，系统主要由2大模块组成:Phasel和Phase2。 Phasel阶段主要将生成的记录文件按内存块大小(本实验中是50MB)分成多个 (本实验中是 20个)相应的子记录文件，把这些文件中的记录读进内存进行排 序，再写回磁盘上。 Phase2 阶段利用

6、多路归并排序算法，将 Phasel 阶段已经排 好序的子记录文件重新归并为1个有序的记录文件，写回到磁盘上。由于我们在 Phasel和Phase2阶段之前必须先生成1个含有10000000个100B记录的文件， 所以系统必须再加上1个生成记录文件的Generate Record File模块。终上所述, 系统由 3 大模块组成，分别为：Generate Record File、Phase1、Phase2。Phase1 模块可以细分为内存块排序模块 Main Memory Sort 和写回磁盘模块 Write To Disk。Phase2模块可以细分为多路归并排序模块Merge-Sort和写回磁

7、盘模块Write To Disk。详细的系统逻辑结构图如图3-1 所示：4.3 数据结构我们讨论单个记录的数据结构。由于1 个记录有 100 个字节，其中4 字节是 由随机整数组成的主键属性Primary Key,另外96个字节是随意填充的数据 content，而且本系统又是由C语言进行实现的，所以我们可以采取结构体来作 为记录的数据结构。其中整形字段key记录4字节的主键属性，以便进行排序工 作。数组字段 contents 用来填充剩余的 96 个字节，内容可以随意（本实验中均 为 0）。具体的数据结构如图 4-1 所示：/* the data structrue of a record *

8、/pedef struct recordint key;/ primary kcpchar contentsROW_NUMBER + 1;/ contentRecord;图 4-1 单个记录的数据结构4.4 具体实现4.4.1 Generate Record File 阶段Generate Record File 阶段比较简单，首先打开一个文件，然后生成随机 数 key 并将其写入文件中，再填充 96 个任意内容的字节（本实验中均为 0 ）， 即能生成 1 条完整的记录。重复 10000000 次，生成我们所需的记录文件。 核心代码实现如图 4-2 所示，其中 MAX_RECORD_NUMBE

9、R 大小为 10000000，ROW_NUMBER 大小为 95。open fileFILE p - fopen( FilcNaTie-c_5ttat)fl wB,iF t !fp J / open failedpintF(BBFilc could not be created!nfiB): fpijintF( stderr p File could not be created?nBi ); esit( 1 、;/ generate random intogers and ecordsHftX_RECOR&HUI10EH recordssrandj (un；ignod)tinQi( NULL

10、 ) );/ srand sedlfor ( int i - 6; i 3 )fprintF( fpp An B );Int they - rand );/ prlnry May, randlom integer,期/ write recordi to disbEn every record fprintf( Fp, f key J；fw ( int j = 0； j RUU HUHEfER； j + + fprintF( fpp c B0B );fclo( fp );/ close uotput Filehis 1(J btes/ write as tne First a bytes)/ w

11、rite Oi for conteinit as the other 9&bytes图 4-2 Generate Record File 阶段的实现4.4.2 Phase1 阶段Phase1 阶段重点在于如何进行内存排序，并写回到磁盘上。这里我们采 用了 STL 的 sort 函数帮助我们进行排序。首先读入 50MB 记录，利用 sort 函数进行排序后，写到磁盘上生成 1 个有序的子记录文件。重复进行 20 次， 生成 20 个相应的 子记 录文件。 核心 代码实 现如图 4-3 所示， 其中 BLOCK_SIZE 大小为 50M，SUB_LIST_NUMBER 大小为 20。/ read

12、all for int kJrecords to main nenorij=3; L SUBLISTHUMEER; k “ / readfor ( 1rprnrfi ni- s rn nrk ijp rnn npmnr|=0; i BLOCK SIZE; i 十十)rgets( str, ROW MUMBER 16, infp );sicanft ctr , d 先 u, LcutiFccDrdfi , subR0cordi .contc ntu );/ iip ll a I grrirnm nrt rn firr rpnni-rt btrLf butiFteuijrd, buliFteLur

13、d * BLOCK SIZE, cmp );temp.cctr(), w );/ upen output File/ open bailedtemp - generateTileflanef k ) j / sorted list name FILE HDutFp - fapcn( if ( *Dutfp )卩rinrf. H ip 弹w fpriiiLff ilderr, eKitf 1 )；nnu I d nnr hp n 卩 pipfifyn , rpm 卩_;什()；Filr 怎、luuU nut Lt ujentf Jru, Ltni|j .u 5tr();/ write the s

14、orted recards tc sub List filefor ( i = B; 1 rimk ef； i + ) _If f i ? 6 Jfpriulf( uuLFp , n);Fprintt outFp, 宪 d , subRccordfi .lcij, subRecordi .cd nt entc ); printF( Thp (irtp(1 1 i算w gpnprabprt jiicrpq;Fiil 1 yln , tpm卩_r?_qt广O );tr iniP( niirfi J -n r.inp nur卩iir Trpm图 4-3 Phase1 阶段的实现4.4.3 Phase

15、2 阶段Phase2 阶段是本系统实现的难点所在。主要的实现大致可以分为以下几 部分进行讨论：1) 输入缓冲的实现将 Phase1 阶段中得到的 20 个子记录文件的首字符分别读入长度为20的输入缓冲数组inputBuffer，核心代码实现如图4-4所示：/ read all of the sublists First record tD input buffer for ( int k = 0; k = BLOCK SI2E )count = 0; writeToDisl( outfp );图 4-6 多路归并排序的实现4) Phase2 阶段的其他实现 我们将在“实验中遇到的问题和解决办法

16、”这一章详细讨论 Phase2 阶段剩下来的难点实现。5 实验结果5.1 50MB内存TPMMS实验结果采用50MB内存块大小进行TPMMS实验的结果如图5-1所示:图 5-1 50MB 内存 TPMMS 实验结果图从上图可以看出，生成1GB大小10000000条记录的文件需要152秒，phasel 阶段需要136 秒, phase2阶段需要150秒。所以整个排序过程需要286秒，即4 分 46 秒的时间才能完成。5.2 10MB内存TPMMS实验结果我们将50MB内存缩减5 倍,进行10MB内存块大小的TPMMS实验。这将产生100 个子记录文件。实验结果如图 5-2所示：B D：F orS

17、tu Tyt3radLiatEi早程谈j据奉垂诫宜现1宜捡1214前_邑干慝一宜验1瞠验1涼代码_De b.HiesortedlisLThesortedlistHiesortedlisLThesortedlistHiesortedlisLThesortedlistHiesortedlisLThesortedlistHiesortedlisLThesortedlistThesortedlisLThesortedlistHiesortedlisLThesortedlistHiesortedlisLThesortedlistHiesortedlisLThesortedlistHiesortedlis

18、LThesortedlistHiesortedlisLThesortedlistHiesortedlisLThesortedlistHiesortedlisLThesortedlistZecoFd_75 .txtZecord_76 .txtZtec oFd_77 t MtZecord_78 .txtZecoFd_79 .txtZecord_8B.txtZecoFd_81 .txtZecord_82 .txtZecoFd_83 .txtZecord_84.txtZecoFd_85 .txtZecord_86 .txtZecoFd_87 .txtZecord_88 .txtZecoFd_89 .t

19、xtZecord_90.txtZecoFd_?l.txtZecord_92 .txtZecoFd_93 .txtZecord_94.txtZecoFd_95 .txtZecord_96 .txtZecoFd_97 .txtZecord_98 .txtZecoFd_99 .txtgenerated successfullj/? generated successfull?/! generated successfullj/? generated successfull?/! generated successfullj/? generated successfull?/! generated s

20、uccessfullj/? generated successfull?/! generated successfullj/? generated successfull?/! generated successfullj/? generated successfull?/! generated successfullj/? generated successfull?/! generated successfullj/? generated successfull?/! generated successfullj/? generated successfull?/! generated s

21、uccessfullj/? generated successfull?/! generated successfullj/? generated successfull?/! generated successfullj/? generated successfull?/! generated successfullj/?Zecord_i06 txt generated successflilly!It takes 147.65000 seconds to genetate the sorted list of records.Merge all of the sorted lists of

22、 records 11 takes 152.204090 seconds to merge the sorted list of records 11 takes 300.93509S seconds to sort the original re coatis.Fpess any key to continue區|图 5-2 10MB 内存 TPMMS 实验结果图生成1GB大小10000000条记录的文件所需时间不变，仍为152秒左右。我 们注重于 phase1 阶段和 phase2 阶段的所需时间。从图中可以看出， phase1 阶段 需要147 秒, phase2阶段需要152秒。整个排

23、序过程需要300秒，即5分钟的时 间才能完成。5.3100MB内存TPMMS实验结果我们再将50MB内存增加2倍，进行100MB内存块大小的TPMMS实验。 这将产生10个子记录文件。实验结果如图5-3所示：图 5-3 100MB 内存 TPMMS 实验结果图生成1GB大小10000000条记录的文件所需时间不变，仍为152秒左右。我 们注重于 phase1 阶段和 phase2 阶段的所需时间。从图中可以看出， phase1 阶段 需要124秒，phase2阶段需要130秒。整个排序过程需要254秒，即4分14秒 的时间才能完成。5.4 三者的比较从上面的实验结果，我们可以很明显地看出，内存

24、块大小越大，算法所需时 间越少。这是因为内存块越小，生成的子记录文件个数就越多，这样 phase1 阶 段生成子记录文件的时间就增加了。并且这还使得phase2阶段的输出缓冲区变 小,导致多路归并时程序读写磁盘的次数增多，所以phase2阶段时间也增加了。 这样整个排序过程时间当然增加。终上所述，当在理想条件下，我们应使用内存块大小较大的方法来进行TPMMS算法的实现。在本章中TPMMS算法的性能为：100MB优于50MB优 于10MB。所以在可能的情况下，应该考虑采纳100MB的TPMMS算法。6 实验遇到的问题和解决方法6.1 Phase2 阶段遇到的问题和解决方法前文已经详细描述了 Ph

25、ase2阶段的3个主要的实现阶段，但是仅仅依靠这3 个阶段还不能完全实现Phase2阶段，必须解决以下几个关键问题才能完成Phase2 阶段的所有任务。6.1.1 读完某个子记录文件后，输入缓冲的填充方法当某个输入缓冲数组inputBufferi相对应的子记录文件infpi已经读完 时，我们就必须重新查找其余可用的子记录文件，按数组下标 i 搜索到第一 个可用的文件infpk后，将它的第一个字节继续填充到输入缓冲数组 inputBufferi中。特别的，当数组下标i超过子记录文件总数SUB_LIST_NUMBER (本实 验中为 20)时，我们就认为所有子记录文件已经读取完毕，这时可以设置一

26、个bool型变量flag = true，进行标识。核心代码实现如图6-1所示：iF ( feof( in1=pindex ) )/ the uhole sub File base been resd/ select a File that has more record to be readFor ( i = n； i = SUB_LIST_NUMBER )Flag = true;图 6-1 读完某个子记录文件后，输入缓冲的填充方法6.1.2 读完所有子记录文件后，处理最后一组输入缓冲数据的方法利用在6.1.1中设置的bool型变量flag，当flag=true时，我们知道子记 录文件已经全部

27、读取完毕。这时在输入缓冲数组inputBuffer中只剩下最后一 组数据，并且根据Phase2阶段的定义，它们肯定比之前输入缓冲中的数据要 大。所以我们只需利用STL提供的sort函数对它们进行排序后，直接输出到 最终结果文件即可。核心代码实现如图 6-2所示：/ handle the last number of size irecori(j5sort( inputDufFer, inputDufFer + SUB LIST HUHBER, cmp ); far ( i = 0； 1 SI|JF_LISr_NLJI1EER； 1 Ti-) copy to output huFfercapRe

28、cardf outputBuFferBLOCK_SIZE - SUB_LIST_HUMDER + i B inputBifferi); counttotalwriteToEiik( nutf p );/ mrlte to disk图 6-1 读完所有子记录文件后，处理最后一组输入缓冲数据的方法6.2 生成子记录文件名的方法当我们生成子记录文件时，想要赋予文件类似于 record_k.txt (k = i+1, 0 = i = 19) 的文件名。由于在 C 语言中，不支持字符串和整数的直接连接。在这里 我们需要一个 generateFileName 函数，采用 itoa 函数将整数 k = i+

29、1 转换成字符 串，再连接到“record_”后面，从而得到想要的文件名。核心代码实现如图6-3 所示：/-* give an integer, to generate a file name */ string generateFileName( int i )charstr 29;/temporary ch-arater arraystringtemp =Htemporary stringitoa( i+1, str, 18 );/ store integer k+1 to array strtemp=str;/conuert array str totemporary stringtem

30、p=D:/record_ + temp + .txt; / form theFilenamereturn temp;/ return the temporary string oF file name图 6-3 生成子记录文件名的方法7 代码附录/ for sort function/ for strcpy/ for fscanf, fprintf, fopen/ for clock#include #include #include #include using namespace std;/* define the constants used in this program */cons

31、t int MAX_RECORD_NUMBER = 10000000;/ max record numberconst int BLOCK_SIZE = 500000; / main memory block sizeconst int ROW_NUMBER = 95;/ for record to fill the other 96bytes const int SUB_LIST_NUMBER = ( MAX_RECORD_NUMBER / BLOCK_SIZE );/ sub list numberconst int MAX = 99999999; / for function selec

32、tMinRecord to initialize the variable min/* the data structrue of a record */typedef struct recordint key;/ primary keychar contentsROW_NUMBER + 1; / content Record;/ main memory bufferRecord subRecordBLOCK_SIZE;Record inputBufferBLOCK_SIZE + 1; / input buffer/ output bufferRecord outputBufferBLOCK_

33、SIZE + 1;/* generate a file of MAX_RECORD_NUMBER (= 10000000) records, every record is 100 bytes */void generateFile( string fileName )/ calculate timeprintf(The records is now under generating .n);clock_t start, finish;double duration;start = clock(); / start time/ open fileFILE *fp = fopen( fileNa

34、me.c_str(), w );if ( !fp ) / open failedprintf(File could not be created!n);fprintf( stderr, File could not be created!n );exit( 1 );/ generate random integers and recordssrand( (unsigned)time( NULL ) );/ srand seedfor ( int i = 0; i 0 )fprintf( fp, n );int key = rand();/ primary key, random integer

35、, 4 bytes/ write record to disk, every record has 100 bytesfprintf( fp, %d , key );/ write key as the first 4 bytesfor ( int j = 0; j ROW_NUMBER; j + ) / write 0 for content as the other 96 bytesfprintf( fp, %c, 0 );fclose( fp ); / close output file/ calculate timefinish = clock(); / finish timedura

36、tion = (double)( finish - start ) / CLOCKS_PER_SEC; / run time printf ( It takes %f seconds to genetate the whole records.n, duration );/* use for phase 1 of two phase multiway merge sortcompare two record by primary key, with ascending order */ bool cmp( const Record &r1, const Record &r2 ) return

37、r1.key r2.key; /* give an integer, to generate a file name */ string generateFileName( int i )char str20;/ temporary charater arraystring temp = / temporary stringitoa( i+1, str, 10 );/ store integer k+1 to array strtemp = str;/ convert array str to temporary stringtemp = D:/record_ + temp + .txt; /

38、 form the file namereturn temp; / return the temporary string of file name/* phase 1 of two phase multiway merge sortread record with maximum block size to main memoryand sort them by primary key */void phase1( string fileName )/ open fileFILE *infp = fopen( fileName.c_str(), r );if ( !infp ) / open

39、 failedprintf( File %s could not be opened!n, fileName.c_str() ); fprintf( stderr, File %s could not be opened!n, fileName.c_str() ); exit( 1 );string temp = ;/ temporary stringint i = 0, j = 0;/ calculate timeprintf( The sorted list of records is now under generating .n ); clock_t start, finish;dou

40、ble duration;start = clock();/ start timechar strROW_NUMBER + 10;/ read all records to main memoryfor ( int k = 0; k SUB_LIST_NUMBER; k + )/ read records of a block size to main memoryfor ( i = 0; i BLOCK_SIZE; i + )fgets( str, ROW_NUMBER + 10, infp );sscanf( str, %d %s, &subRecordi.key, subRecordi.

41、contents ); / use STL algorithm sort to sort records sort( subRecord, subRecord + BLOCK_SIZE, cmp );temp = generateFileName( k ); / sorted list nameFILE *outfp = fopen( temp.c_str(), w ); / open output file if ( !outfp )/ open failedprintf( File %s could not be opened!n, temp.c_str();fprintf( stderr

42、, File %s could not be opened!n, temp.c_str() ); exit( 1 );/ write the sorted records to sub list file for ( i = 0; i 0 )fprintf( outfp, n );fprintf( outfp, %d %s, subRecordi.key, subRecordi.contents );printf( The sorted list %s generated successfully!n, temp.c_str() );/ close output stream/ close i

43、nput filefclose( outfp );fclose( infp );/ calculate timefinish = clock();/ finish timeduration = (double)( finish - start ) / CLOCKS_PER_SEC; / run time printf( It takes %f seconds to genetate the sorted list of records.n, duration );/* copy record r2 to record r1 */void copyRecord( Record &r1, Reco

44、rd &r2 )r1.key = r2.key;strcpy( r1.contents, r2.contents ); /* copy a record to input buffer */void copyToInputBuffer( FILE *fp, int index ) char strROW_NUMBER + 10;fgets( str, ROW_NUMBER + 10, fp );sscanf( str, %d %s, &inputBufferindex.key, inputBufferindex.contents ); /* write the records in outpu

45、t buffer to diskwhen the output buffer is full */void writeToDisk( FILE *fp )/ flush output buffer to diskfor ( int j = 0; j BLOCK_SIZE; j + )fprintf( fp, %d %sn, outputBufferj.key, outputBufferj.contents );/* select the minimum record in input bufferby primary key */int selectMinRecord( int size )i

46、nt min = MAX;int index = 0;for ( int i = 0; i size; i + )if ( inputBufferi.key min ) min = inputBufferi.key; index = i;return index;/* phase 2 of two phase multiway merge sort merge the sorted sub list to a sorted result file of ascending order */void phase2()/ open output file to store the sorted r

47、ecords FILE *outfp = fopen( D:/result.txt, w );if ( !outfp ) / open failedprintf( Output file could not be created!n );fprintf( stderr, Output file could not be created!n ); exit( 1 );string temp = ;/ temporary stringint count = 0;/ the used output buffer sizeint total = 0;/ the record number writte

48、n to diskint i = 0, j = 0;/ array of input stream object, to open sub list of sorted records FILE * *infp = new FILE* SUB_LIST_NUMBER ;/ calculate timeprintf( Merge all of the sorted lists of records .n ); clock_t start, finish;double duration;start = clock(); / start timechar strROW_NUMBER + 10;/ r

49、ead all of the sublists first record to input bufferfor ( int k = 0; k SUB_LIST_NUMBER; k + )temp = generateFileName( k );infpk = fopen( temp.c_str(), r );/ open sorted list fileif ( !infpk )/ open failedprintf( File %s could not be created!n, temp.c_str() );fprintf( stderr, File %s could not be cre

50、ated!n, temp.c_str() ); exit( 1 );/ read record to input bufferfgets( str, ROW_NUMBER + 10, infpk );sscanf( str, %d %s, &inputBufferk.key, inputBufferk.contents ); / mark whether all the sored list have been readbool flag = false;/ merge the sorted listwhile ( total = BLOCK_SIZE )count = 0; / reset

51、count writeToDisk( outfp );if ( feof( infpindex ) )/ the whole sub file hase been resd/ select a file that has more record to be read for ( i = 0; i = SUB_LIST_NUMBER ) flag = true;if ( !flag )/ not all sublist have been readcopyToInputBuffer( infpnewIndex, index );else/ all sublist have been read/

52、handle the last number of size records sort( inputBuffer, inputBuffer + SUB_LIST_NUMBER, cmp );for ( i = 1; i SUB_LIST_NUMBER; i + )/ copy to output buffercopyRecord( outputBufferBLOCK_SIZE - SUB_LIST_NUMBER + i, inputBufferi );count +;total +; writeToDisk( outfp );/ write to diskbreak;/ close all i

53、nput filefor ( i = 0; i SUB_LIST_NUMBER; i + ) fclose( infpi );fclose( outfp );/ close output file/ calculate timefinish = clock();/ finish timeduration = (double)( finish - start ) / CLOCKS_PER_SEC; / run time printf( It takes %f seconds to merge the sorted list of records.n, duration );/* the entr

54、ance of the program */int main()/ generate record filestring fileName = D:/record.txt;generateFile( fileName );/ calculate timeclock_t start, finish;double duration;start = clock();/ phase1 and phase2phase1( fileName );phase2();/ calculate timefinish = clock();/ finish timeduration = (double)( finish - start ) / CLOCKS_PER_SEC; / run time printf( It takes %f seconds to sort the original records.n, duration );return 0;