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

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

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

4.4具體實現(xiàn)GenerateRecordFile階段GenerateRecordFile階段比較簡單，首先打開一個文件，然后生成隨機數(shù)key并將其寫入文件中，再填充96個任意內(nèi)容的字節(jié)（本實驗中均為0），即能生成1條完整的記錄。重復(fù)10000000次，生成我們所需的記錄文件。核心代碼實現(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階段重點在于如何進行內(nèi)存排序，并寫回到磁盤上。這里我們采用了STL的sort函數(shù)幫助我們進行排序。首先讀入50MB記錄，利用sort函數(shù)進行排序后，寫到磁盤上生成1個有序的子記錄文件。重復(fù)進行20次，生成20個相應(yīng)的子記錄文件。核心代碼實現(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階段的實現(xiàn)Phase2階段Phase2階段是本系統(tǒng)實現(xiàn)的難點所在。主要的實現(xiàn)大致可以分為以下幾部分進行討論：1）輸入緩沖的實現(xiàn)將Phasel階段中得到的20個子記錄文件的首字符分別讀入長度為20的輸入緩沖數(shù)組inputBuffer，核心代碼實現(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輸入緩沖的實現(xiàn)輸出緩沖的實現(xiàn)選取輸入緩沖數(shù)組inputBuffer中主鍵屬性key最小的那個緩沖區(qū)，輸入到輸出緩沖數(shù)組outputBuffer中，然后循環(huán)執(zhí)行，核心代碼實現(xiàn)如圖4-5所示：//selectthesmallestrecordintindex=selpetMinRpcor(l(SUB_LI￡T_NUMBERintneulndex=indPK://writerecordtooutputbuffercop^Record(QutputBuFFer[count]9inputBuffer[inde?]);count++;圖4-5輸出緩沖的實現(xiàn)多路歸并排序的實現(xiàn)如果輸出緩沖數(shù)組outputBuffer已經(jīng)填滿，此時可知輸出緩沖是有序的，且之后的主鍵屬性key的值都不會小于該輸出緩沖區(qū)，這時我們即可將其輸出到最后想要得到的結(jié)果文件上，核心代碼實現(xiàn)如圖4-6所示：//outputbufferisfull,writetodiskif(count>=BLUCK_SHE)count=0;//resetcountwriteToDisl<(outfp);4)Phase2階段的其他實現(xiàn)我們將在“實驗中遇到的問題和解決辦法”這一章詳細(xì)討論Phase2階段剩下來的難點實現(xiàn)。5實驗結(jié)果5.150MB內(nèi)存TPMMS實驗結(jié)果采用50MB內(nèi)存塊大小進行TPMMS實驗的結(jié)果如圖5-1所示:圖5-150MB內(nèi)存TPMMS實驗結(jié)果圖從上圖可以看出，生成1GB大小10000000條記錄的文件需要152秒，phasel階段需要136秒，phase2階段需要150秒。所以整個排序過程需要286秒，即4分46秒的時間才能完成。5.210MB內(nèi)存TPMMS實驗結(jié)果我們將50MB內(nèi)存縮減5倍，進行10MB內(nèi)存塊大小的TPMMS實驗。這將

產(chǎn)生100個子記錄文件。實驗結(jié)果如圖5-2所示:圖5-210MB內(nèi)存TPMMS實驗結(jié)果圖生成1GB大小10000000條記錄的文件所需時間不變，仍為152秒左右。我們注重于phase1階段和phase2階段的所需時間。從圖中可以看出，phase1階段需要147秒，phase2階段需要152秒。整個排序過程需要300秒，即5分鐘的時間才能完成。5.3100MB內(nèi)存TPMMS實驗結(jié)果我們再將50MB內(nèi)存增加2倍，進行100MB內(nèi)存塊大小的TPMMS實驗。這將產(chǎn)生10個子記錄文件。實驗結(jié)果如圖5-3所示:圖5-3100MB內(nèi)存TPMMS實驗結(jié)果圖生成1GB大小10000000條記錄的文件所需時間不變，仍為152秒左右。我們注重于phasel階段和phase2階段的所需時間。從圖中可以看出，phasel階段需要124秒，phase2階段需要130秒。整個排序過程需要254秒，即4分14秒的時間才能完成。5.4三者的比較從上面的實驗結(jié)果，我們可以很明顯地看出，內(nèi)存塊大小越大，算法所需時間越少。這是因為內(nèi)存塊越小，生成的子記錄文件個數(shù)就越多，這樣phase1階段生成子記錄文件的時間就增加了。并且這還使得phase2階段的輸出緩沖區(qū)變小，導(dǎo)致多路歸并時程序讀寫磁盤的次數(shù)增多，所以phase2階段時間也增加了。這樣整個排序過程時間當(dāng)然增加。終上所述，當(dāng)在理想條件下，我們應(yīng)使用內(nèi)存塊大小較大的方法來進行TPMMS算法的實現(xiàn)。在本章中TPMMS算法的性能為：100MB優(yōu)于50MB優(yōu)于10MB。所以在可能的情況下，應(yīng)該考慮采納100MB的TPMMS算法。6實驗遇到的問題和解決方法6.1Phase2階段遇到的問題和解決方法前文已經(jīng)詳細(xì)描述了Phase2階段的3個主要的實現(xiàn)階段，但是僅僅依靠這3個階段還不能完全實現(xiàn)Phase2階段，必須解決以下幾個關(guān)鍵問題才能完成Phase2階段的所有任務(wù)。6.1.1讀完某個子記錄文件后，輸入緩沖的填充方法當(dāng)某個輸入緩沖數(shù)組inputBuffer[i]相對應(yīng)的子記錄文件infp[i]已經(jīng)讀完時，我們就必須重新查找其余可用的子記錄文件，按數(shù)組下標(biāo)i搜索到第一個可用的文件infp[k]后，將它的第一個字節(jié)繼續(xù)填充到輸入緩沖數(shù)組inputBuffer[i]中。特別的，當(dāng)數(shù)組下標(biāo)i超過子記錄文件總數(shù)SUB_LIST_NUMBER(本實驗中為20)時，我們就認(rèn)為所有子記錄文件已經(jīng)讀取完畢，這時可以設(shè)置一個bool型變量flag=true，進行標(biāo)識。核心代碼實現(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讀完某個子記錄文件后，輸入緩沖的填充方法6.1.2讀完所有子記錄文件后，處理最后一組輸入緩沖數(shù)據(jù)的方法利用在6.1.1中設(shè)置的bool型變量flag，當(dāng)flag=true時，我們知道子記錄文件已經(jīng)全部讀取完畢。這時在輸入緩沖數(shù)組inputBuffer中只剩下最后一組數(shù)據(jù)，并且根據(jù)Phase2階段的定義，它們肯定比之前輸入緩沖中的數(shù)據(jù)要大。所以我們只需利用STL提供的sort函數(shù)對它們進行排序后，直接輸出到最終結(jié)果文件即可。核心代碼實現(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)我們生成子記錄文件時，想要賦予文件類似于record_k.txt(k=i+1,0<=i<=19)的文件名。由于在C語言中，不支持字符串和整數(shù)的直接連接。在這里我們需要一個generateFileName函數(shù)，采用itoa函數(shù)將整數(shù)k=i+1轉(zhuǎn)換成字符串，再連接到“record_”后面，從而得到想要的文件名。核心代碼實現(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