數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)

兩階段多路歸并排序Two-PhaseMultiwayMerge-Sort實(shí)驗(yàn)報(bào)告TOC\o"1-5"\h\z\o"CurrentDocument"實(shí)驗(yàn)?zāi)康?\o"CurrentDocument"實(shí)驗(yàn)內(nèi)容3\o"CurrentDocument"實(shí)驗(yàn)環(huán)境3\o"CurrentDocument"實(shí)驗(yàn)的設(shè)計(jì)和實(shí)現(xiàn)3算法描述3設(shè)計(jì)思路4數(shù)據(jù)結(jié)構(gòu)5具體實(shí)現(xiàn)6\o"CurrentDocument"實(shí)驗(yàn)結(jié)果950MB內(nèi)存TPMMS實(shí)驗(yàn)結(jié)果910MB內(nèi)存TPMMS實(shí)驗(yàn)結(jié)果9100MB內(nèi)存TPMMS實(shí)驗(yàn)結(jié)果10三者的比較11\o"CurrentDocument"實(shí)驗(yàn)遇到的問(wèn)題和解決方法11Phase2階段遇到的問(wèn)題和解決方法11生成子記錄文件名的方法13\o"CurrentDocument"代碼附錄131實(shí)驗(yàn)?zāi)康耐℉merge-sor算法的實(shí)現(xiàn)，掌握外存算法所基于的I/O模型與內(nèi)存算法基于的RAM模型的區(qū)別；理解不同的磁盤訪問(wèn)優(yōu)化方法是如何提高數(shù)據(jù)訪問(wèn)性能的。2實(shí)驗(yàn)內(nèi)容生成一個(gè)具有10,000,00（個(gè)記錄的文本文件，其中每個(gè)記錄由100個(gè)字節(jié)組成。實(shí)驗(yàn)只考慮記錄的一個(gè)屬，性A,假定A為整數(shù)類型。記錄在block上封裝時(shí)，采用non-spanned方式，即塊上小于一個(gè)記錄的空間不使用。Block的大小可在自己的操作系統(tǒng)上查看，xp一般為4096bytes在內(nèi)存分配50M字節(jié)的空間用于外部merge-sort要求設(shè)計(jì)和實(shí)現(xiàn)程序完成下列功能：1）生成文本文件，其中屬性入的值隨機(jī)產(chǎn)生。2）按照ppt中的方法對(duì)文本文件中的記錄，按照屬性A進(jìn)行排序，其中在第二階段的排序中每個(gè)子列表使用一個(gè)block大小的緩沖區(qū)緩沖數(shù)據(jù)。3）按照教材cylinder-basedbuffers（1Mb（的方法，修改第二階段的算法。4）比較兩種方法的時(shí)間性能，如果有更大的內(nèi)存空間，算法性能還能提高多少？3實(shí)驗(yàn)環(huán)境1）VisualC++6.02）Windows7操作系統(tǒng)4實(shí)驗(yàn)的設(shè)計(jì)和實(shí)現(xiàn)4.1算法描述Two-PhaseMultiwayMerge-So]|t法的具體描述分為2個(gè)階段，如下所示：?Phase1Fillmainmemorywithrecords.Sortwithfavoritemainmemorysortingalgorithms.Writesortedlisttodisk.Repeatuntilallrecordshavebeenputintooneofthesortedlists.?Phase2Initiallyloadinputbufferswiththefirstblockoftheirrespectivesortedlists.Repeatedrunacompetitionamongthefirstunchosenrecordsofeachofthebufferedblocks.Ifaninputblockisexhausted,getthenextblockfromthesamefile.Iftheoutputblockisfull,writeittodisk.4.2設(shè)計(jì)思路從上述的算法描述中，我們知道，系統(tǒng)主要由2大模塊組成:Phasel和Phase2。Phasel階段主要將生成的記錄文件按內(nèi)存塊大小(本實(shí)驗(yàn)中是50MB)分成多個(gè)(本實(shí)驗(yàn)中是20個(gè))相應(yīng)的子記錄文件，把這些文件中的記錄讀進(jìn)內(nèi)存進(jìn)行排序，再寫(xiě)回磁盤上。Phase2階段利用多路歸并排序算法，將Phasel階段已經(jīng)排好序的子記錄文件重新歸并為1個(gè)有序的記錄文件，寫(xiě)回到磁盤上。由于我們?cè)赑hasel和Phase2階段之前必須先生成1個(gè)含有10000000個(gè)100B記錄的文件，所以系統(tǒng)必須再加上1個(gè)生成記錄文件的GenerateRecordFile模塊。終上所述，系統(tǒng)由3大模塊組成，分別為：GenerateRecordFile、Phase1、Phase2oPhase1模塊可以細(xì)分為內(nèi)存塊排序模塊MainMemorySort和寫(xiě)回磁盤模塊WriteToDisk。Phase2模塊可以細(xì)分為多路歸并排序模塊Merge-Sort和寫(xiě)回磁盤模塊WriteToDisko詳細(xì)的系統(tǒng)邏輯結(jié)構(gòu)圖如圖3-1所示：

圖3-1TPMMS系統(tǒng)邏輯結(jié)構(gòu)圖4.3數(shù)據(jù)結(jié)構(gòu)我們討論單個(gè)記錄的數(shù)據(jù)結(jié)構(gòu)。由于1個(gè)記錄有100個(gè)字節(jié)，其中4字節(jié)是由隨機(jī)整數(shù)組成的主鍵屬性PrimaryKey，另外96個(gè)字節(jié)是隨意填充的數(shù)據(jù)content，而且本系統(tǒng)又是由C語(yǔ)言進(jìn)行實(shí)現(xiàn)的，所以我們可以采取結(jié)構(gòu)體來(lái)作為記錄的數(shù)據(jù)結(jié)構(gòu)。其中整形字段key記錄4字節(jié)的主鍵屬性，以便進(jìn)行排序工作。數(shù)組字段contents用來(lái)填充剩余的96個(gè)字節(jié)，內(nèi)容可以隨意（本實(shí)驗(yàn)中均為0）。具體的數(shù)據(jù)結(jié)構(gòu)如圖4-1所示：/*thedatastructrueofarecord*/pedefstructrecordintkey;//primaryI{叩charcontents[ROW_NUMBER+1];//content}Record;

4.4具體實(shí)現(xiàn)GenerateRecordFile階段GenerateRecordFile階段比較簡(jiǎn)單，首先打開(kāi)一個(gè)文件，然后生成隨機(jī)數(shù)key并將其寫(xiě)入文件中，再填充96個(gè)任意內(nèi)容的字節(jié)（本實(shí)驗(yàn)中均為0），即能生成1條完整的記錄。重復(fù)10000000次，生成我們所需的記錄文件。核心代碼實(shí)現(xiàn)如圖4-2所示，其中MAX_RECORD_NUMBER大小為10000000，ROW_NUMBER大小為95。//openfiloFILEHp-PopcnfrileHamc.c_str(l,"w");iFt!fp)"openfailedprintI("Iilccouldnotbecr?atca!\n"J:lprintl(stderr,"Iiiecouldnotbecrcatcd?\n"):cxit(1】；/fqcncrati?randnnintegersardrecordssrandiced++)//generateNAX_RECOAD_NUkEERrecordsrandominteger,srandiced++)//generateNAX_RECOAD_NUkEERrecordsrandominteger,Wtiytesfor(inti-u：i<nnxreluednumber：iIF(i>3)fprintFffpp"\n');IntKey-randt);//primarykey,//writerecordtodislt,cucryrecardl-printu//writerecordtodislt,cucryrecardl-printuf-p,F",HJ;for(inti=0；1<RUUNUNEfLH；1*+hprintufp,W,1U'):?fFp);//uuLpuLFilehasmabytes//uritcmstheFirmt"bytesJ，/urite'LI'1-orcontentastheother9t>Phase1階段Phase1階段重點(diǎn)在于如何進(jìn)行內(nèi)存排序，并寫(xiě)回到磁盤上。這里我們采用了STL的sort函數(shù)幫助我們進(jìn)行排序。首先讀入50MB記錄，利用sort函數(shù)進(jìn)行排序后，寫(xiě)到磁盤上生成1個(gè)有序的子記錄文件。重復(fù)進(jìn)行20次，生成20個(gè)相應(yīng)的子記錄文件。核心代碼實(shí)現(xiàn)如圖4-3所示，其中BLOCK_SIZE大小為50M，SUB_LIST_NUMBER大小為20。//readallrecordstomainnenorijfor(intk=3;L<SUBLISTHUMEER;k)<一一//rpsrlrprnrfl^n+smnrk^ijprnnnpmnr||forfi=9;1<BLDGK_SIZE;i十十)<rgets(str,ROWMUMBER■16,infp);sicanftctr,"^dML'LcutiFccDrdfi],5ubRccard[i].contents);//ii^pSilaIgrrirnmznrrrnrpnni-rt^btrLfbutiReuijrd,bubReLurd?BLOCKSIZE,Linp，temp-generateTileflanefksortedlistnameFILE*Dutfp-fapcn(temp.cctr(),"w");//DpenoutputFileif(*Dutfp)//openbailedprinfF["HipnnuIdnnrhpnppnpuwmnp-jtyfpriiiLffilderr,"FilrluuUiiuLLtu^jentfJr\u",Ltni|j.u5tr()eKitf1//writethesortedrecardstcsubListfilefor(i=B;i<R|[)DKJ；T7F;i++)Iffi?6Jfpriulf(uuLFp,"\n");Fprint^toutFp,''^d,subRccordfi].l<cij,sutjRecord[i].contents);}printF("Thp<^(irtp(11igpnprabprt<jiicrpq<;Fiil1yl\n",tpmp.r_<;tr());i-rin<ip(niirrpj-nr.in^pnurpiir^rrp^m圖4-3Phasel階段的實(shí)現(xiàn)Phase2階段Phase2階段是本系統(tǒng)實(shí)現(xiàn)的難點(diǎn)所在。主要的實(shí)現(xiàn)大致可以分為以下幾部分進(jìn)行討論：1）輸入緩沖的實(shí)現(xiàn)將Phasel階段中得到的20個(gè)子記錄文件的首字符分別讀入長(zhǎng)度為20的輸入緩沖數(shù)組inputBuffer，核心代碼實(shí)現(xiàn)如圖4-4所示：//readallofthesublist'sFirstrecordtoinputbufferfor(intk=0;k<SUBLISTNUMEER;k++)temp=generateFileName(k);infp[k]=fopen(temp.c_str(),"r");//opensortedlistFileif(tinfp[k])//upenfailedprintF("Filecouldnotbecreated!\n",temp.cstr());l-printi-(stderr,"Hile%scouldnotbecreatedT\n",temp.cstr(});exit(1);//readrecordtoinputbufferFgetsfstr,ROU_NUMBER+18,inFp[k]):sscanf(str,"^d%s'',ftinputBuFFer[k]-key,inputBuFFer[k].contents)}圖4-4輸入緩沖的實(shí)現(xiàn)輸出緩沖的實(shí)現(xiàn)選取輸入緩沖數(shù)組inputBuffer中主鍵屬性key最小的那個(gè)緩沖區(qū)，輸入到輸出緩沖數(shù)組outputBuffer中，然后循環(huán)執(zhí)行，核心代碼實(shí)現(xiàn)如圖4-5所示：//selectthesmallestrecordintindex=selpetMinRpcor(l(SUB_LI￡T_NUMBERintneulndex=indPK://writerecordtooutputbuffercop^Record(QutputBuFFer[count]9inputBuffer[inde?]);count++;圖4-5輸出緩沖的實(shí)現(xiàn)多路歸并排序的實(shí)現(xiàn)如果輸出緩沖數(shù)組outputBuffer已經(jīng)填滿，此時(shí)可知輸出緩沖是有序的，且之后的主鍵屬性key的值都不會(huì)小于該輸出緩沖區(qū)，這時(shí)我們即可將其輸出到最后想要得到的結(jié)果文件上，核心代碼實(shí)現(xiàn)如圖4-6所示：//outputbufferisfull,writetodiskif(count>=BLUCK_SHE)count=0;//resetcountwriteToDisl<(outfp);4)Phase2階段的其他實(shí)現(xiàn)我們將在“實(shí)驗(yàn)中遇到的問(wèn)題和解決辦法”這一章詳細(xì)討論P(yáng)hase2階段剩下來(lái)的難點(diǎn)實(shí)現(xiàn)。5實(shí)驗(yàn)結(jié)果5.150MB內(nèi)存TPMMS實(shí)驗(yàn)結(jié)果采用50MB內(nèi)存塊大小進(jìn)行TPMMS實(shí)驗(yàn)的結(jié)果如圖5-1所示:圖5-150MB內(nèi)存TPMMS實(shí)驗(yàn)結(jié)果圖從上圖可以看出，生成1GB大小10000000條記錄的文件需要152秒，phasel階段需要136秒，phase2階段需要150秒。所以整個(gè)排序過(guò)程需要286秒，即4分46秒的時(shí)間才能完成。5.210MB內(nèi)存TPMMS實(shí)驗(yàn)結(jié)果我們將50MB內(nèi)存縮減5倍，進(jìn)行10MB內(nèi)存塊大小的TPMMS實(shí)驗(yàn)。這將

產(chǎn)生100個(gè)子記錄文件。實(shí)驗(yàn)結(jié)果如圖5-2所示:圖5-210MB內(nèi)存TPMMS實(shí)驗(yàn)結(jié)果圖生成1GB大小10000000條記錄的文件所需時(shí)間不變，仍為152秒左右。我們注重于phase1階段和phase2階段的所需時(shí)間。從圖中可以看出，phase1階段需要147秒，phase2階段需要152秒。整個(gè)排序過(guò)程需要300秒，即5分鐘的時(shí)間才能完成。5.3100MB內(nèi)存TPMMS實(shí)驗(yàn)結(jié)果我們?cè)賹?0MB內(nèi)存增加2倍，進(jìn)行100MB內(nèi)存塊大小的TPMMS實(shí)驗(yàn)。這將產(chǎn)生10個(gè)子記錄文件。實(shí)驗(yàn)結(jié)果如圖5-3所示:圖5-3100MB內(nèi)存TPMMS實(shí)驗(yàn)結(jié)果圖生成1GB大小10000000條記錄的文件所需時(shí)間不變，仍為152秒左右。我們注重于phasel階段和phase2階段的所需時(shí)間。從圖中可以看出，phasel階段需要124秒，phase2階段需要130秒。整個(gè)排序過(guò)程需要254秒，即4分14秒的時(shí)間才能完成。5.4三者的比較從上面的實(shí)驗(yàn)結(jié)果，我們可以很明顯地看出，內(nèi)存塊大小越大，算法所需時(shí)間越少。這是因?yàn)閮?nèi)存塊越小，生成的子記錄文件個(gè)數(shù)就越多，這樣phase1階段生成子記錄文件的時(shí)間就增加了。并且這還使得phase2階段的輸出緩沖區(qū)變小，導(dǎo)致多路歸并時(shí)程序讀寫(xiě)磁盤的次數(shù)增多，所以phase2階段時(shí)間也增加了。這樣整個(gè)排序過(guò)程時(shí)間當(dāng)然增加。終上所述，當(dāng)在理想條件下，我們應(yīng)使用內(nèi)存塊大小較大的方法來(lái)進(jìn)行TPMMS算法的實(shí)現(xiàn)。在本章中TPMMS算法的性能為：100MB優(yōu)于50MB優(yōu)于10MB。所以在可能的情況下，應(yīng)該考慮采納100MB的TPMMS算法。6實(shí)驗(yàn)遇到的問(wèn)題和解決方法6.1Phase2階段遇到的問(wèn)題和解決方法前文已經(jīng)詳細(xì)描述了Phase2階段的3個(gè)主要的實(shí)現(xiàn)階段，但是僅僅依靠這3個(gè)階段還不能完全實(shí)現(xiàn)Phase2階段，必須解決以下幾個(gè)關(guān)鍵問(wèn)題才能完成Phase2階段的所有任務(wù)。6.1.1讀完某個(gè)子記錄文件后，輸入緩沖的填充方法當(dāng)某個(gè)輸入緩沖數(shù)組inputBuffer[i]相對(duì)應(yīng)的子記錄文件infp[i]已經(jīng)讀完時(shí)，我們就必須重新查找其余可用的子記錄文件，按數(shù)組下標(biāo)i搜索到第一個(gè)可用的文件infp[k]后，將它的第一個(gè)字節(jié)繼續(xù)填充到輸入緩沖數(shù)組inputBuffer[i]中。特別的，當(dāng)數(shù)組下標(biāo)i超過(guò)子記錄文件總數(shù)SUB_LIST_NUMBER(本實(shí)驗(yàn)中為20)時(shí)，我們就認(rèn)為所有子記錄文件已經(jīng)讀取完畢，這時(shí)可以設(shè)置一個(gè)bool型變量flag=true，進(jìn)行標(biāo)識(shí)。核心代碼實(shí)現(xiàn)如圖6-1所示：iF(feof(in1:p[index]))//theuholesubFilehastbeenresd//selectaFilethathasmorerecordtobereadFor(i=n；i<SURITSTNIIMRFR;i++)iF(?FeoF(inFp[i]))neulndex=i;break;//dllburLedfilehduebeenreddif(i>=SUB_LIST_NUMBER)Flag=true;圖6-1讀完某個(gè)子記錄文件后，輸入緩沖的填充方法6.1.2讀完所有子記錄文件后，處理最后一組輸入緩沖數(shù)據(jù)的方法利用在6.1.1中設(shè)置的bool型變量flag，當(dāng)flag=true時(shí)，我們知道子記錄文件已經(jīng)全部讀取完畢。這時(shí)在輸入緩沖數(shù)組inputBuffer中只剩下最后一組數(shù)據(jù)，并且根據(jù)Phase2階段的定義，它們肯定比之前輸入緩沖中的數(shù)據(jù)要大。所以我們只需利用STL提供的sort函數(shù)對(duì)它們進(jìn)行排序后，直接輸出到最終結(jié)果文件即可。核心代碼實(shí)現(xiàn)如圖6-2所示：//handlethelastnumberoFsizeretordssort(inputDufFer,inputDufFer+SUBLISTHUHBER,cmp);far(i=0；1<SI|JF_LISr_NLJI1EER；1Ti-)//copytooutputhuFfercap^RecardfoutputBuFfer[BLOCK_SIZE-SUB_LIST_HUMDERi]BinputBi?ffer[i]);counttotalwriteToEii￡k(nutfp);//mrltetodisk圖6-1讀完所有子記錄文件后，處理最后一組輸入緩沖數(shù)據(jù)的方法6.2生成子記錄文件名的方法當(dāng)我們生成子記錄文件時(shí)，想要賦予文件類似于record_k.txt(k=i+1,0<=i<=19)的文件名。由于在C語(yǔ)言中，不支持字符串和整數(shù)的直接連接。在這里我們需要一個(gè)generateFileName函數(shù)，采用itoa函數(shù)將整數(shù)k=i+1轉(zhuǎn)換成字符串，再連接到“record_”后面，從而得到想要的文件名。核心代碼實(shí)現(xiàn)如圖6-3所示：/-*giveaninteger,togenerateafilename*/stringgenerateFileName(inti)charstr[29];//temporarych-araterarraystringtemp=//temporarystringitoa(i+1,str,18);//storeintegerk+1toarratjstrtemp=str;//conuertarraystrtotemporarystringtemp="D:/record_"+temp+".txt";//formtheFilenamereturntemp;//returnthetemporarystringoFfilename圖6-3生成子記錄文件名的方法7代碼附錄//forsortfunction//forstrcpy//forfscanf,fprintf,fopen//forclock#include<algorithm>#include<string>#include<cstdio>#include<ctime>usingnamespacestd;/*definetheconstantsusedinthisprogram*/constintMAX_RECORD_NUMBER=10000000;//maxrecordnumberconstintBLOCK_SIZE=500000;//mainmemoryblocksizeconstintROW_NUMBER=95;//forsortfunction//forstrcpy//forfscanf,fprintf,fopen//forclockbytesconstintSUB_LIST_NUMBER=(MAX_RECORD_NUMBER/BLOCK_SIZE);//sublistnumberconstintMAX=99999999;//forfunctionselectMinRecordtoinitialithevariablemin/*thedatastructrueofarecord*/typedefstructrecord(intkey;//primarykeycharcontents[ROW_NUMBER+1];//content}Record;RecordsubRecord[BLOCK_SIZE];//mainmemorybufferRecordinputBuffer[BLOCK_SIZE+1];//inputbufferRecordoutputBuffer[BLOCK_SIZE+1];//outputbuffer/*generateafileofMAX_RECORD_NUMBER(=10000000)records,everyrecordis100bytes*/voidgenerateFile(stringfileName)(//calculatetimeprintf("Therecordsisnowundergenerating...\n〃)；clock_tstart,finish;doubleduration;start=clock();//starttime//openfileFILE*fp=fopen(fileName.c_str(),"w");if(!fp)//openfailed{printf("Filecouldnotbecreated!\n");fprintf(stderr,"Filecouldnotbecreated!\n");exit(1);}//generaterandomintegersandrecordssrand((unsigned)time(NULL));//srandseedfor(inti=0;i<MAX_RECORD_NUMBER;i++)//generateMAX_RECORD_NUMBERrecords{if(i>0)fprintf(fp,"\n");intkey=rand();//primarykey,randominteger,4bytes//writerecordtodisk,everyrecordhas100bytesfprintf(fp,"%d",key);//writekeyasthefirst4bytesfor(intj=0;j<ROW_NUMBER;j++)//write'0'forcontentastheother96bytesfprintf(fp,"%c",'0');}fclose(fp);//closeoutputfile//calculatetimefinish=clock();//finishtimeduration=(double)(finish-start)/CLOCKS_PER_SEC;//runtimeprintf("Ittakes%fsecondstogenetatethewholerecords.\n",duration);

/*useforphase1oftwophasemultiwaymergesortcomparetworecordbyprimarykey,withascendingorder*/boolcmp(constRecord&r1,constRecord&r2){returnr1.key<r2.key;}/*giveaninteger,togenerateafilename*/stringgenerateFileName(inti)charstr[20];//temporarycharatercharstr[20];stringtemp="";//temporarystringitoa(i+1,str,10);temp=str;//storeintegerk+1toarraystr//itoa(i+1,str,10);temp=str;temp="D:/record_"+temp+".txt";//formthefilenamereturntemp;//returnthetemporarystringoffilename/*phase1oftwophasemultiwaymergesortreadrecordwithmaximumblocksizetomainmemoryandsortthembyprimarykey*/voidphase1(stringfileName){//openfileFILE*infp=fopen(fileName.c_str(),"r");if(!infp)//openfailed{printf("File%scouldnotbeopened!\n",fileName.c_str());fprintf(stderr,"File%scouldnotbeopened!\n",fileName.c_str());exit(1);}stringtemp="";//temporarystringinti=0,j=0;//calculatetimeprintf("Thesortedlistofrecordsisnowundergenerating...\n");clock_tstart,finish;doubleduration;start=clock();//starttimecharstr[ROW_NUMBER+10];//readallrecordstomainmemoryfor(intk=0;k<SUB_LIST_NUMBER;k++){//readrecordsofablocksizetomainmemoryfor(i=0;i<BLOCK_SIZE;i++){fgets(str,ROW_NUMBER+10,infp);sscanf(str,"%d%s",&subRecord[i].key,subRecord[i].contents);}//useSTLalgorithmsorttosortrecordssort(subRecord,subRecord+BLOCK_SIZE,cmp);temp=generateFileName(k);//sortedlistnameFILE*outfp=fopen(temp.c_str(),"w");//openoutputfileif(!outfp)//openfailed{printf("File%scouldnotbeopened!\n",temp.c_str());fprintf(stderr,"File%scouldnotbeopened!\n",temp.c_str());exit(1);}//writethesortedrecordstosublistfilefor(i=0;i<BLOCK_SIZE;i++){if(i>0)fprintf(outfp,"\n");fprintf(outfp,"%d%s",subRecord[i].key,subRecord[i].contents);}printf("Thesortedlist%sgeneratedsuccessfully!\n",temp.c_str());fclose(outfp);//closeoutputstream}fclose(infp);//closeinputfile//calculatetimefinish=clock();//finishtimeduration=(double)(finish-start)/CLOCKS_PER_SEC;//runtimeprintf("Ittakes%fsecondstogenetatethesortedlistofrecords.\n",duration);}/*copyrecordr2torecordr1*/voidcopyRecord(Record&r1,Record&r2)rl.key=r2.key;strcpy(rl.contents,r2.contents);}/*copyarecordtoinputbuffer*/voidcopyToInputBuffer(FILE*fp,intindex){charstr[ROW_NUMBER+10];fgets(str,ROW_NUMBER+10,fp);sscanf(str,"%d%s”,&inputBuffer[index].key,inputBuffer[index].contents);}/*writetherecordsinoutputbuffertodiskwhentheoutputbufferisfull*/voidwriteToDisk(FILE*fp){//flushoutputbuffertodiskfor(intj=0;j<BLOCK_SIZE;j++){fprintf(fp,"%d%s\n”,outputBuffer[j].key,outputBuffer[j].contents);}}/*selecttheminimumrecordininputbufferbyprimarykey*/intselectMinRecord(intsize){intmin=MAX;intindex=0;

for(inti=0;i<size;i++){if(inputBuffer[i].key<min){min=inputBuffer[i].key;index=i;}}returnindex;}/*phase2oftwophasemultiwaymergesortmergethesortedsublisttoasortedresultfileofascendingorder*/voidphase2(){//openoutputfiletostorethesortedrecordsFILE*outfp=fopen("D:/result.txt”,"w");if(!outfp)//openfailed{printf("Outputfilecouldnotbecreated!\n");fprintf(stderr,"Outputfilecouldnotbecreated!\n");exit(1);}stringtemp=""intcount=0;inttotal=0;inti=0,j=stringtemp=""intcount=0;inttotal=0;inti=0,j=0;//arrayofinputstreamobject,toopensublistofsortedrecordsFILE**infp=newFILE*[SUB_LIST_NUMBER];//calculatetimeprintf("Mergeallofthesortedlistsofrecords...\n");clock_tstart,finish;doubleduration;start=clock();//starttimecharstr[ROW_NUMBER+10];//readallofthesublist'sfirstrecordtoinputbufferfor(intk=0;k<SUB_LIST_NUMBER;k++){temp=generateFileName(k);infp[k]=fopen(temp.c_str(),"r");//opensortedlistfileif(!infp[k])//openfailed{printf("File%scouldnotbecreated!\n",temp.c_str());fprintf(stderr,"File%scouldnotbecreated!\n",temp.c_str());exit(1);}//readrecordtoinputbufferfgets(str,ROW_NUMBER+10,infp[k]);sscanf(str,"%d%s",&inputBuffer[k].key,inputBuffer[k].contents);}//markwhetherallthesoredlisthavebeenreadboolflag=false;//mergethesortedlistwhile(total<MAX_RECORD_NUMBER){//selectthesmallestrecordintindex=select