數(shù)據(jù)結(jié)構(gòu)與算法-文件與外部排序

教學(xué)要求掌握文件的相關(guān)概念；文件的各種組織方法及特點(diǎn)；查詢、更新操作及其算法；掌握外部排序的一般過程，熟練掌握適合外存特點(diǎn)的歸并排序的相關(guān)技術(shù)。主要內(nèi)容7.1文件及文件操作7.2文件組織7.3磁盤文件的歸并排序7.4磁帶文件的歸并排序7.1文件及文件操作1、相關(guān)概念文件是用于表示駐留在外存儲(chǔ)器中的數(shù)據(jù)，是同性質(zhì)記錄的有序集合。記錄學(xué)號(hào)姓名性別年齡數(shù)學(xué)語文物理其它A003孫喆B008陳益C009史碩剛D010許藝洪E011張爽F(xiàn)012沈鍵關(guān)鍵字：主關(guān)鍵字and次關(guān)鍵字文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)：邏輯結(jié)構(gòu)：呈現(xiàn)給用戶，描述記錄間的邏輯關(guān)系物理結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)，記錄在存儲(chǔ)器中的組織，連續(xù)，鏈?zhǔn)降?、文件操作操作：

●INSERT，在文件中插入記錄

●DELETE，從文件中刪除記錄

●MODIFY，修改滿足條件的記錄

●

RETRIEVE，檢索滿足條件的記錄檢索方式：實(shí)時(shí)or成批更新方式：實(shí)時(shí)or成批文件更新文件檢索3、查詢方式

Q1簡(jiǎn)單查詢：查詢單個(gè)關(guān)鍵字值等于給定值的記錄

如：性別=男

Q2范圍查詢：查詢單個(gè)關(guān)鍵字值滿足指定范圍的記錄

如：數(shù)學(xué)>80

Q3函數(shù)查詢：對(duì)于某個(gè)關(guān)鍵字的函數(shù)，查詢滿足指定函數(shù)

值的記錄

如：物理>平均分

Q4布爾查詢：對(duì)Q1Q2Q3進(jìn)行組合的查詢，查詢滿足布爾

表達(dá)式的記錄如：(性別=男)and(年齡=18)

布爾運(yùn)算：andornotMain(){FILE*fp;……}Sourcefile.c輸入數(shù)據(jù)原始數(shù)據(jù)磁盤/帶文件處理結(jié)果輸出數(shù)據(jù)文件指針文件結(jié)構(gòu)體——FILEtypedefstruct{int_fd;//文件號(hào)

int_cleft;//緩沖區(qū)中剩下的字符數(shù)

int_mode;//文件操作方式

char*_next;//文件當(dāng)前讀寫位置

char*_buff;//文件緩沖區(qū)位置}FILE;Stdio.hFILE*變量名；文件信息用系統(tǒng)定義的名為FILE的結(jié)構(gòu)體描述Intfclose(FILE*fp)FILE*fopen(char*name,char*mode)

fread(buffer,size,count,fp);

fwrite(buffer,size,count,fp);

標(biāo)準(zhǔn)輸入：鍵

盤-------stdin

標(biāo)準(zhǔn)輸出：顯示器-------stdout標(biāo)準(zhǔn)出錯(cuò)輸出：顯示器-------stderr#include"stdio.h"

main(intargc,char*argv[]){FILE*in,*out;if(argc!=3){printf("Youforgottoenterafilename\n");exit(0);}if((in=fopen(argv[1],"r"))==NULL){printf("Cannotopeninfile!\n");exit(0);}if((out=fopen(argv[2],"w"))==NULL){printf("Cannotopenoutfile!\n");exit(0);}

while(!feof(in))fputc(fgetc(in),out);fclose(in);fclose(out);}？按用途

系統(tǒng)文件、庫(kù)文件、用戶文件

按保護(hù)級(jí)別

可執(zhí)行文件、只讀文件、讀寫文件按信息流向

輸入文件、輸出文件、輸入輸出文件按存放時(shí)限

臨時(shí)文件、永久文件、檔案文件按設(shè)備類型

磁盤文件、磁帶文件、卡片文件、打印文件

按文件組織結(jié)構(gòu)邏輯文件(流式文件、記錄式文件)、物理文件（順序文件、鏈接文件、索引文件）4、文件分類FAT：FileAllocationTableNTFS：NewTechnologyFilesSyatemWinFS：WindowsFutureStorage操作系統(tǒng)FAT12Fat16Fat32NTFSNTFS5.0WinFSDOS3.0以下是支

持

末

來

的

操

作

系

統(tǒng)Dos3.0是DOS4.0是Windows3.X是Windows95是Windows95OSR2是是Windows98是是Windows98SE是WindowsMe是是WindowsNT是是Windows2000是是是是WindowsXP是是是是Windows2003是是是是Unix

是

Linux

是是(軟盤引導(dǎo))

文件大小限制最大支持8M最大支持2G不能大于4G單文件最大64GB單文件最大2TBWindows不同版本操作系統(tǒng)

的文件格式7.2文件組織常用的文件組織方式：順序方式索引方式散列方式鏈接方式另外還有……

ISAMVSAMUNIX問題：文件駐留外存，數(shù)據(jù)量大

每次讀入一個(gè)物理快文件操作復(fù)雜為使操作方便，要研究設(shè)計(jì)有效的存儲(chǔ)機(jī)制7.2.1順序方式文件的各個(gè)記錄按邏輯順序存放在外存的連續(xù)區(qū)內(nèi)記錄的順序往往是按主關(guān)鍵字的大小排列的適合于Q1型查詢，且檢索與更新是成批進(jìn)行的適合磁帶或磁盤1、基本術(shù)語【順序文件（SequentialFile）】是記錄按其在文件中的邏輯順序依次進(jìn)入存儲(chǔ)介質(zhì)而建立的，即順序文件中物理記錄的順序和邏輯記錄的順序是一致的?！敬?lián)文件】物理記錄之間的次序由指針相鏈接表示的順序文件。【連續(xù)文件】次序相繼的兩個(gè)物理記錄在存儲(chǔ)介質(zhì)上的存儲(chǔ)位置是相鄰的順序文件。2、特點(diǎn)順序文件是根據(jù)記錄的序號(hào)或記錄的相對(duì)位置來進(jìn)行存取的文件組織方式。特點(diǎn)是：①存取第i個(gè)記錄，必須先搜索在它之前的i-1個(gè)記錄。②插入記錄時(shí)要批量移動(dòng)記錄，或加在文件末尾的溢出區(qū)。

③刪除記錄時(shí)要批量移動(dòng)記錄，或標(biāo)記記錄④若要更新文件中某個(gè)記錄，則必須將整個(gè)文件進(jìn)行復(fù)制。3、磁帶上順序文件的批處理主文件：待修改的原始文件。事務(wù)文件：所有的修改請(qǐng)求集中構(gòu)成的一個(gè)文件。磁帶文件的批處理過程：首先對(duì)事務(wù)文件進(jìn)行排序，然后將主文件和事務(wù)文件歸并成一個(gè)新的主文件。

其中，主文件、事務(wù)文件和新的主文件分別存放在一臺(tái)磁帶上。主文件按關(guān)鍵字自小至大（或自大至?。╉樞蛴行?，事務(wù)文件必須和主文件有相同的有序關(guān)系。事務(wù)文件舉例：新調(diào)來35人調(diào)走28人漲工資343人事務(wù)總數(shù)406件文件修改程序事務(wù)文件職工老文件職工新文件

終端事務(wù)文件排序有序的事務(wù)文件主文件新主文件

在歸并的過程中，順序讀出主文件與事務(wù)文件中的記錄，比較它們的關(guān)鍵字并分別進(jìn)行處理。對(duì)于關(guān)鍵字不匹配的主文件中的記錄，則直接將其寫入新主文件中?！案摹焙汀皠h除”記錄時(shí)，要求其關(guān)鍵字相匹配?！皠h去”不用寫入，而“更改”則要將更改后的新記錄寫入新主文?！安迦搿睍r(shí)不要求關(guān)鍵字相匹配，可直接將事務(wù)文件上要插入的記錄寫到新主文件的適當(dāng)位置。算法實(shí)現(xiàn)：f—主文件；g—事務(wù)文件；h—新主文件。它們都按關(guān)鍵字遞增排序。事務(wù)文件的每個(gè)記錄中，增設(shè)一個(gè)代碼以示修改要求，其中：“I”表示插入；“D”表示刪去；“U”表示更改。voidMergeFile(FILE*f,FILE*g,FILE*h){

fread(*fr,sizeof(RcdType),1,f); fread(*gr,sizeof(RcdType),1,g);while(!feof(f)||!feof(g)){switch{ casefr.key<gr.key: //復(fù)制“舊”主文件中記錄

fwrite(*fr,sizeof(RcdType),1,h); if(!feof(f)) fread(*fr,sizeof(RcdType),1,f); break; casegr.code==‘D’&&fr.key==gr.key: //刪除”舊”主文件中記錄,不復(fù)制

if(!feof(f)) fread(*fr,sizeof(RcdType),1,f); if(!feof(g)) fread(*gr,sizeof(RcdType),1,g); break; casegr.code==‘I’&&fr.key>gr.key: //插入,函數(shù)P把gr加工為h的結(jié)構(gòu)

fwrite(P(gr),sizeof(RcdType),1,h); if(!feof(g)) fread(*gr,sizeof(RcdType),1,g); break; casegr.code==‘U’&&fr.key==gr.key: //更改”舊”主文件中記錄

fwrite(Q(fr,gr),sizeof(RcdType),1,h); //函數(shù)Q將fr和gr歸并成一個(gè)h結(jié)構(gòu)的記錄

if(!feof(f)) fread(*fr,sizeof(RcdType),1,f); if(!feof(g)) fread(*gr,sizeof(RcdType),1,g); break; defaultERROR(); //其他均為出錯(cuò)情況

}//switch}//while}//MergeFile分析批處理算法的時(shí)間：假設(shè)主文件包含n個(gè)記錄，事務(wù)文件包含m個(gè)記錄。一般情況下，事務(wù)文件較小，可以進(jìn)行內(nèi)部排序，則時(shí)間復(fù)雜度為O(m*logm)。內(nèi)部歸并的時(shí)間復(fù)雜度為O(n+m)，則總的內(nèi)部處理時(shí)間為O(m*logm+n)。4、磁盤上順序文件的批處理磁盤上順序文件的批處理和磁帶文件類似，只是當(dāng)修改項(xiàng)中沒有插入，且更新時(shí)不增加記錄的長(zhǎng)度時(shí)，可以不建立新的主文件，而直接修改原來的主文件即可。顯然，磁盤文件的批處理可以在一個(gè)磁盤上進(jìn)行。

假設(shè)所有的輸入/輸出都是通過緩沖區(qū)進(jìn)行的，并假設(shè)緩沖區(qū)大小為s（個(gè)記錄），則整個(gè)批處理過程中讀/寫外存的次數(shù)為：n：主文件包含的記錄數(shù)，m：事務(wù)文件包含記錄數(shù)7.2.2索引方式【定義】索引指的是記錄的關(guān)鍵字值與記錄駐留在外存的地址組成數(shù)對(duì)的集合。每個(gè)數(shù)對(duì)稱為一個(gè)索引項(xiàng)。索引文件在存儲(chǔ)器上分兩區(qū)：索引區(qū)和數(shù)據(jù)區(qū)查找記錄：分兩步進(jìn)行刪除記錄：只刪除索引插入記錄：先存數(shù)據(jù)，然后登記索引并重新排序建立文件：按數(shù)據(jù)存入的先后順序建立索引，最后索引排序示例：序號(hào)姓名記錄內(nèi)容記錄位置柱面號(hào)盤面號(hào)1AnCai…11人事檔案示意文件柱面的最大關(guān)鍵字柱面號(hào)CaiLong1柱面索引盤面的最大關(guān)鍵字盤面號(hào)PiHong1盤面索引1、基本術(shù)語

索引表：除了文件本身（稱做數(shù)據(jù)區(qū)）之外，另建立的一張指示邏輯記錄和物理記錄之間一一對(duì)應(yīng)關(guān)系的表。

索引項(xiàng)：索引表中的每一項(xiàng)。總是按關(guān)鍵字（或邏輯記錄號(hào)）順序排列。索引文件：包括文件數(shù)據(jù)區(qū)和索引表兩大部分的文件。索引順序文件：數(shù)據(jù)區(qū)中的記錄也按關(guān)鍵字順序排列的

文件。通常為索引順序文件建立“溢出區(qū)”索引非順序文件：數(shù)據(jù)區(qū)中的記錄不按關(guān)鍵字順序排列。

在記錄輸入建立數(shù)據(jù)區(qū)的同時(shí)建立一個(gè)索引表，表中的索引項(xiàng)按記錄輸入的先后次序排列，待全部記錄輸入完畢后再對(duì)索引表進(jìn)行排序。2、索引表的生成索引表是由系統(tǒng)程序自動(dòng)生成的。

非稠密索引：數(shù)據(jù)文件中的記錄按關(guān)鍵字順序有序，則可對(duì)一組記錄建立一個(gè)索引項(xiàng)，這種索引表稱為非稠密索引。

稠密索引：由于數(shù)據(jù)文件中記錄不按關(guān)鍵字順序排列，則必須對(duì)每個(gè)記錄都建立一個(gè)索引項(xiàng)，如此建立的索引表稱為稠密索引。

由于索引項(xiàng)的長(zhǎng)度比記錄小得多，則通?？蓪⑺饕硪淮巫x入內(nèi)存，由此在索引文件中進(jìn)行檢索只訪問外存兩次，即一次讀索引，一次讀記錄。并且由于索引表是有序的，則查找索引表時(shí)可用折半查找法。3、索引文件的檢索檢索方式：直接存取或按關(guān)鍵字（進(jìn)行簡(jiǎn)單詢問）存取。

檢索過程：首先，查找索引表，若索引表上存在該記錄，則根據(jù)索引項(xiàng)的指示讀取外存上該記錄;否則說明外存上不存在該記錄，也就不需要訪問外存。

上述的多級(jí)索引是一種靜態(tài)索引，索引均為順序表結(jié)構(gòu)。其結(jié)構(gòu)簡(jiǎn)單，但修改很不方便，每次修改都要重組索引。當(dāng)記錄變動(dòng)較多時(shí)，應(yīng)采用動(dòng)態(tài)索引。

【如】二叉排序樹（或二叉平衡樹）、B-樹以及鍵樹。5、多級(jí)索引查找表：對(duì)索引表建立的索引。通常最高可有四級(jí)索引：4、索引文件的修改刪除操作：刪除一個(gè)記錄時(shí)，僅需刪去相應(yīng)的索引項(xiàng)；插入操作：插入一個(gè)記錄時(shí)，應(yīng)將記錄置于數(shù)據(jù)區(qū)的末尾，同時(shí)再索引表中插入索引項(xiàng)；更新操作：更新記錄時(shí)，應(yīng)將更新后的記錄置于數(shù)據(jù)區(qū)末尾，同時(shí)修改索引表中相應(yīng)的索引項(xiàng)。多級(jí)索引結(jié)構(gòu)形成m路搜索樹數(shù)據(jù)區(qū)一級(jí)索引二級(jí)索引三級(jí)索引四級(jí)索引多級(jí)索引結(jié)構(gòu)形成m叉樹每個(gè)分支結(jié)點(diǎn)表示一個(gè)索引塊，最多存放m個(gè)索引項(xiàng)每個(gè)索引項(xiàng)給出各子樹結(jié)點(diǎn)(較低一級(jí)索引塊)的最大關(guān)鍵碼和結(jié)點(diǎn)地址。葉結(jié)點(diǎn)中各索引項(xiàng)給出在數(shù)據(jù)表中存放的記錄的關(guān)鍵碼和存放地址。這種m叉樹用來作為多級(jí)索引，就是m路搜索樹7.2.3散列方式用散列（HASH）法組織的文件。特點(diǎn)是用一個(gè)散列函數(shù)H(key)，將關(guān)鍵字key映射為記錄的地址，即:

記錄地址=HASH(key)基本步驟:確定記錄數(shù)存儲(chǔ)單位（桶）記錄數(shù)確定桶數(shù)設(shè)計(jì)HASH(key)函數(shù)1、基本術(shù)語直接存取文件指的是利用哈希（Hash）法進(jìn)行組織的文件。它類似于哈希表，既根據(jù)文件中關(guān)鍵字的特點(diǎn)設(shè)計(jì)一種哈希函數(shù)和處理沖突的方法將記錄散列到存儲(chǔ)設(shè)備上，故又稱散列文件。與哈希表不同，磁盤上的文件記錄通常是成組存放的。又稱直接存取文件2、溢出處理若干個(gè)記錄組成一個(gè)存儲(chǔ)單位，在散列文件中，這個(gè)存儲(chǔ)單位叫做桶（Bucket）。假若一個(gè)桶能存放m個(gè)記錄，m個(gè)同義詞的記錄可以存放在同一地址的桶中，當(dāng)?shù)趍＋1個(gè)同義詞出現(xiàn)時(shí)才發(fā)生“溢出”。解決溢出：鏈地址法當(dāng)發(fā)生“溢出”時(shí)，需要將第m＋1個(gè)同義詞存放到另一個(gè)桶中，通常稱此桶為“溢出桶”；相對(duì)地，稱前m個(gè)同義詞存放的桶為“基桶”。溢出桶和基桶大小相同，相互之間用指針相鏈接。當(dāng)在基桶中沒有待查記錄時(shí)，就順指針?biāo)傅揭绯鐾爸羞M(jìn)行查找。因此，希望同一散列地址的溢出桶和基桶在磁盤上的物理位置不要相距太遠(yuǎn)，最好在同一柱面上。3、圖形表示例如，某一文件有18個(gè)記錄，其關(guān)鍵字分別為278，109，063，930，589，184，505，269，008，083，164，215，330，810，620，110，384，355。桶的容量為m＝3，桶數(shù)b＝7。用除留余數(shù)法作哈希函數(shù)H(key)＝keyMOD7。由此得到的直接存取文件如圖所示。桶編號(hào) 基桶 溢出桶00631841589505008 33023269164410962052782158101103556930083384直接存取文件示例a為存取桶數(shù)的期望值（相當(dāng)于哈希表中的平均查找長(zhǎng)度），對(duì)鏈地址處理溢出來說，a=1+α/2；te為存取一個(gè)桶所需的時(shí)間；ti為在內(nèi)存中順序查找一個(gè)記錄所需的時(shí)間。4、查找操作查找過程：首先根據(jù)給定值求得哈希地址（即基桶號(hào)），將基桶的記錄讀入內(nèi)存進(jìn)行順序查找，若找到關(guān)鍵字等于給定值的記錄，則檢索成功；否則，若基桶內(nèi)沒有填滿記錄或其指針域?yàn)榭?，則文件內(nèi)不含有待查記錄；否則根據(jù)指針域的值的指示將溢出桶的記錄讀入內(nèi)存繼續(xù)進(jìn)行順序查找，直至檢索成功或不成功。因此，總的查找時(shí)間為T=a(te+ti)，其中：α為裝載因子，在散列文件中：其中：n為文件的記錄數(shù)，b為桶數(shù)，m為桶的容量。5、刪除操作在直接存取文件中刪除記錄時(shí)，僅需對(duì)被刪記錄作一標(biāo)記即可。6、直接存取文件的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：文件隨機(jī)存放，記錄不需進(jìn)行排序；插入、刪除方便，存取速度快，不需要索引區(qū)，節(jié)省存儲(chǔ)空間。

缺點(diǎn)：不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取，且詢問方式限于簡(jiǎn)單詢問，并且在經(jīng)過多次的插入、刪除之后，也可能造成文件結(jié)構(gòu)不合理，即溢出桶滿而基桶內(nèi)多數(shù)為被刪除的記錄。此時(shí)亦需重組文件。最大學(xué)號(hào)204060改進(jìn)方法：索引鏈接文件，將鏈表分拆成多個(gè)較多的小鏈表7.2.4鏈接方式文件和多重鏈表文字把文件中的關(guān)鍵字按照主關(guān)鍵字的某種次序用鏈接字連接起來，整個(gè)文件對(duì)應(yīng)一個(gè)鏈表。在記錄中保存鏈接。特點(diǎn)：順序查找，速度較慢。記錄B記錄A記錄E記錄C記錄F記錄D多關(guān)鍵字文件

特點(diǎn)：在對(duì)文件進(jìn)行檢索操作時(shí)，不僅對(duì)主關(guān)鍵字進(jìn)行簡(jiǎn)單詢問，還經(jīng)常需要對(duì)關(guān)鍵字進(jìn)行其他類型的詢問檢索。1、多重表文件多重表文件（MultilistFile）的特點(diǎn)是：記錄按主關(guān)鍵字的順序構(gòu)成一個(gè)串聯(lián)文件，建立主關(guān)鍵字的索引（主索引）；對(duì)每一個(gè)次關(guān)鍵字項(xiàng)建立次關(guān)鍵字索引（次索引），所有具有同一次關(guān)鍵字的記錄構(gòu)成一個(gè)鏈表。主索引為非稠密索引，次索引為稠密索引。每個(gè)索引項(xiàng)包括次關(guān)鍵字、頭指針和鏈表長(zhǎng)度。數(shù)據(jù)文件：一個(gè)多重表其中，學(xué)號(hào)為主關(guān)鍵字，記錄按學(xué)號(hào)順序鏈接，為了查找方便，分成3個(gè)子鏈表，其索引如圖(b)所示，索引項(xiàng)中的主關(guān)鍵字為各子表中的最大值。(b)主關(guān)鍵字索引紀(jì)錄號(hào)姓名學(xué)號(hào)專業(yè)已修學(xué)分選修課程01王雯135002軟件0241203丙02丁0302馬小雁135103軟件0739807甲04丙0303阮森135204計(jì)算機(jī)05436^乙05丙04丁0504蘇明明1353^應(yīng)用0640208甲06丙0805田永135406計(jì)算機(jī)^38402乙07丁0906楊青135507應(yīng)用0935610甲0707薛平平135608軟件08398^甲08乙^08崔子健1357^軟件^40801甲09丙^09王洪135810應(yīng)用1037005甲10丁^10劉倩1359^應(yīng)用^36409甲^主關(guān)鍵字頭指針135301135705135909(d)“已修學(xué)分”索引(e)“選修課目”索引多重表文件示例(c)“專業(yè)”索引專業(yè)、已修學(xué)分和選修課目為3個(gè)次關(guān)鍵字項(xiàng)，具有相同次關(guān)鍵字的記錄鏈接在同一鏈表中。它們的索引如圖(c)～(e)所示。次關(guān)鍵字頭指針長(zhǎng)度軟件014計(jì)算機(jī)032應(yīng)用044次關(guān)鍵字頭指針長(zhǎng)度甲027乙033丙015丁014次關(guān)鍵字頭指針長(zhǎng)度350-399066400-449044記錄職工號(hào)姓名職務(wù)指針性別指針婚否指針工資A29丁一程序員^男E婚E898B05王二維修員E男G婚A456C02趙忠程序員G女D婚B1200D38張三工程師H女F否H2400E31王五維修員F男^婚F456F43劉玉維修員^女H婚^456G17李芳程序員A男A否D1200H46張洪工程師^女^否^3000次關(guān)鍵字長(zhǎng)度指針程序員3C維修員3B工程師2D次關(guān)鍵字長(zhǎng)度指針男4B女4C次關(guān)鍵字長(zhǎng)度指針婚5C否3G職務(wù)索引性別索引婚否索引【例7-1】多重鏈表文件結(jié)構(gòu)2、倒排文件——在索引中保存鏈接倒排文件和多重表文件的區(qū)別在于次關(guān)鍵字索引的結(jié)構(gòu)不同。通常稱倒排文件中的次關(guān)鍵字索引為倒排表，具有相同次關(guān)鍵字的記錄之間不設(shè)指針鏈接，而在倒排表中該次關(guān)鍵字的一項(xiàng)中存放這些記錄的物理記錄號(hào)。

倒排表作索引的好處在于檢索記錄較快。特別是對(duì)某些詢問，不用讀取記錄，就可得到解答，如詢問“軟件”專業(yè)的學(xué)生中有否選課程“乙”的，則只要將“軟件”索引中的記錄號(hào)和“乙”索引中的記錄號(hào)作求“交集”的運(yùn)算即可。

在插入和刪除記錄時(shí)，倒排表也要作相應(yīng)的修改，值得注意的是倒排表中具有同一次關(guān)鍵字的記錄號(hào)是有序排列的，則修改時(shí)要作相應(yīng)移動(dòng)。(a)專業(yè)倒排表(b)已修學(xué)分倒排表(c)選修課目倒排表【例7-2】上例文件的倒排表紀(jì)錄號(hào)姓名學(xué)號(hào)專業(yè)已修學(xué)分選修課程01王雯135002軟件0241203丙02丁0302馬小雁135103軟件0739807甲04丙0303阮森135204計(jì)算機(jī)05436^乙05丙04丁0504蘇明明1353^應(yīng)用0640208甲06丙0805田永135406計(jì)算機(jī)^38402乙07丁0906楊青135507應(yīng)用0935610甲0707薛平平135608軟件08398^甲08乙^08崔子健1357^軟件^40801甲09丙^09王洪135810應(yīng)用1037005甲10丁^10劉倩1359^應(yīng)用^36409甲^軟件01,02,07,08計(jì)算機(jī)03,05應(yīng)用04,06,09,10350-39902,05,06,07,09,10400-44901,03,04,08甲

02,04,06,07,08,09,10乙

03,05,07丙

01,02,03,04,08丁01,03,05,09

若數(shù)據(jù)文件非串鏈文件，而是索引順序文件（如ISAM文件），則倒排表中應(yīng)存放記錄的主關(guān)鍵字而不是物理記錄號(hào)。倒排文件的缺點(diǎn)：維護(hù)困難在同一索引表中，不同的關(guān)鍵字其記錄數(shù)不同，各倒排表的長(zhǎng)度不等，同一倒排表中各項(xiàng)長(zhǎng)度也不等。記錄職工號(hào)姓名職務(wù)性別婚否工資A29丁一程序員男婚898B05王二維修員男婚456C02趙忠程序員女婚1200D38張三工程師女否2400E31王五維修員男婚456F43劉玉維修員女婚456G17李芳程序員男否1200H46張洪工程師女否3000次關(guān)鍵字指針程序員CGA維修員BEF工程師DH次關(guān)鍵字指針男BGAE女CDFH次關(guān)鍵字指針婚CBAEF否GDH職務(wù)索引性別索引婚否索引【例7-3】倒排文件結(jié)構(gòu)參考7-1：ISAM文件1、基本屬于索引順序存取方法ISAM(IndexedSequentialAccessMethod)：是一種專為磁盤存取設(shè)計(jì)的文件組織方式，采用靜態(tài)索引結(jié)構(gòu)。

由于磁盤是以盤組、柱面和磁道三級(jí)地址存取的設(shè)備，則可對(duì)磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道三級(jí)索引。①磁道索引項(xiàng)基本索引項(xiàng)關(guān)鍵字：表示該磁道中最末一個(gè)記錄的關(guān)鍵字（在此為最大關(guān)鍵字）指針：指示該磁道中第一個(gè)記錄的位置。溢出索引項(xiàng)關(guān)鍵字：表示該磁道溢出的記錄的最大關(guān)鍵字。指針：指示在溢出區(qū)中的第一個(gè)記錄。②柱面索引項(xiàng)關(guān)鍵字：表示該柱面中最末一個(gè)記錄的關(guān)鍵字（最大關(guān)鍵字）。指針：指示該柱面上的磁道索引位置。主索引柱面索引磁道索引基本數(shù)據(jù)區(qū)ISAM文件結(jié)構(gòu)示意圖圖為存放一個(gè)磁盤組上的ISAM文件。每個(gè)柱面建立一個(gè)磁道索引，每個(gè)磁道索引項(xiàng)由基本索引項(xiàng)和溢出索引項(xiàng)兩部分組成。ISAM文件結(jié)構(gòu)示例

柱面索引存放在某個(gè)柱面上，若柱面索引較大，占多個(gè)磁道時(shí)，則可建立柱面索引的索引——主索引。2、ISAM文件的檢索在ISAM文件上檢索記錄的過程：先從主索引出發(fā)找到相應(yīng)的柱面索引，再?gòu)闹嫠饕业接涗浰谥娴拇诺浪饕?，最后從磁道索引找到記錄所在磁道的第一個(gè)記錄的位置，由此出發(fā)在該磁道上進(jìn)行順序查找直至找到為止；反之，若找遍該磁道而不存在此記錄，則表明該文件中無此記錄。3、溢出區(qū)和插入操作溢出區(qū)是為插入記錄所設(shè)置的。每個(gè)柱面的基本區(qū)是順序存儲(chǔ)結(jié)構(gòu)，而溢出區(qū)是鏈表結(jié)構(gòu)。同一磁道溢出的記錄由指針相鏈。溢出區(qū)的設(shè)置方法：①集中存放：整個(gè)文件設(shè)一個(gè)大的單一的溢出區(qū)。②分散存放：每個(gè)柱面設(shè)一個(gè)溢出區(qū)。③集中與分散相結(jié)合：溢出時(shí)記錄先移至每個(gè)柱面各自的溢出區(qū)，待滿之后再使用公共溢出區(qū)。當(dāng)插人新記錄時(shí)，首先找到它應(yīng)插入的磁道,若該磁道不滿，則將新記錄插入該磁道的適當(dāng)位置上即可；若該磁道已滿，則新記錄或者插在該磁道上，或者直接插入到該磁道的溢出鏈表上。插入后，可能要修改磁道索引中的基本索引項(xiàng)和溢出索引項(xiàng)。

(3)插入R83，因?yàn)?0<83<90，則83直接插入溢出區(qū)T11’2中，其指針指向T11’0，并修改磁道1的溢出鏈表，使得表頭指向T11’2。(2)插入R95，使得T2中的R145溢出至溢出區(qū)T11’1，修改相應(yīng)磁道索引。

(1)插入R65，首先將1柱面1磁道中大于65的記錄順次后移，導(dǎo)致R90溢出至溢出區(qū)T11’0(11磁道0塊中)，造成磁道T1中最大關(guān)鍵字成為R80，修改磁道索引，將基本項(xiàng)中最大關(guān)鍵字90修改為80，將溢出項(xiàng)中最大關(guān)鍵字改為90，指針指向T11’0（溢出鏈表頭在11磁道0塊中），然后在相應(yīng)位置插入R65。T11,05、柱面索引的位置假設(shè)文件占有n個(gè)柱面，柱面索引在第x柱面上，則磁頭移動(dòng)距離的平均值為： 令，得到。這就是說，柱面索引應(yīng)放在數(shù)據(jù)文件的中間位置的柱面上。4、刪除操作

ISAM文件中刪除記錄，只需找到待刪除的記錄，在其存儲(chǔ)位置上做刪除標(biāo)記即可，而不需要移動(dòng)記錄或改變指針。但在經(jīng)過多次的增刪后，文件的結(jié)構(gòu)可能變得很不合理。此時(shí)，大量的記錄進(jìn)入溢出區(qū)，而基本區(qū)中又浪費(fèi)很大空間。由此，通常需要周期地整理ISAM文件。把記錄讀入內(nèi)存，重新排列，復(fù)制成一個(gè)新的ISAM文件，填滿基本區(qū)而空出溢出區(qū)。參考7-2：VSAM文件控制區(qū)域（ControlRange）：順序集中一個(gè)結(jié)點(diǎn)連同對(duì)應(yīng)所有控制區(qū)間形成的一個(gè)整體。1、基本術(shù)語

虛擬存儲(chǔ)存取方法VSAM（VirtualStorageAccessMethed）.它也是一種索引順序文件的組方式，采用B+樹作為動(dòng)態(tài)索引結(jié)構(gòu)。該方法利用了操作系統(tǒng)的虛擬存儲(chǔ)器的功能，給用戶提供方便。對(duì)用戶來說，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲(chǔ)單位，與外存儲(chǔ)器中柱面、磁道等具體存儲(chǔ)單位沒有必然的聯(lián)系?？刂茀^(qū)間（ControlInterval）：它是一個(gè)I/O操作的基本單位，由一組連續(xù)的存儲(chǔ)單元組成。同一文件上控制區(qū)間的大小相同。每個(gè)控制區(qū)間可視為一個(gè)邏輯磁道，而每個(gè)控制區(qū)域可視為一個(gè)邏輯柱面。

在VSAM文件中，記錄可以是不定長(zhǎng)的，則在控制區(qū)間中除了存放記錄本身以外，還有每個(gè)記錄的控制信息和整個(gè)區(qū)間的控制信息，控制區(qū)間的結(jié)構(gòu)如圖所示。

在控制區(qū)間上存取一個(gè)記錄時(shí)需從控制區(qū)間的兩端出發(fā)同時(shí)向中間掃描。

記 記 未利用記錄n記錄1控制空錄錄 的的的控制間的控

1n 空閑空間控制信息信息制信息

控制區(qū)間的結(jié)構(gòu)示意圖2、刪除操作在VSAM文件中刪除記錄時(shí)，需將同一控制區(qū)間中較刪除記錄關(guān)鍵字大的記錄向前移動(dòng)，把空間留給以后插入的新記錄。若整個(gè)控制區(qū)間變空，則需修改順序集中相應(yīng)的索引項(xiàng)。3、插入操作

VSAM文件中沒有溢出區(qū)，解決插入的辦法是在初建文件時(shí)留有空間。每個(gè)控制區(qū)間內(nèi)不填滿記錄，在最末一個(gè)記錄和控制信息之間留有孔隙；在每個(gè)控制區(qū)域中有一些完全空的控制區(qū)間，并在順序集的索引中指明這些空區(qū)間。當(dāng)插入記錄時(shí)，大多數(shù)的新記錄能插入到相應(yīng)的控制區(qū)間內(nèi)，但要注意為了保持區(qū)間內(nèi)記錄的關(guān)鍵字自小至大有序，則需將區(qū)間內(nèi)關(guān)鍵字大于插入記錄關(guān)鍵字的記錄向控制信息的方向移動(dòng)。若在若干記錄插入之后控制區(qū)間已滿，則在下一個(gè)記錄插入時(shí)要進(jìn)行控制區(qū)間的分裂，既將近乎一半的記錄移到同一控制區(qū)域中全空的控制區(qū)間中，并修改順序集中相應(yīng)索引。若控制區(qū)域中已經(jīng)沒有全空的控制區(qū)間，則要進(jìn)行控制區(qū)域的分裂，此時(shí)順序集中的結(jié)點(diǎn)亦要分裂，由此尚需修改索引集中的結(jié)點(diǎn)信息。4、VASM文件的特點(diǎn)優(yōu)點(diǎn)：動(dòng)態(tài)地分配和釋放存儲(chǔ)空間，不需要對(duì)文件進(jìn)行重組，并能較快地對(duì)插入的記錄進(jìn)行查找，查找一個(gè)后插入記錄的時(shí)間與查找一個(gè)原有記錄的時(shí)間是相同的。缺點(diǎn)：占有較多的存儲(chǔ)空間，一般只能保持約75％的存儲(chǔ)空間利用率。1、UNIX的多重索引

規(guī)定每個(gè)文件的索引表使用13個(gè)登記項(xiàng)（每個(gè)登記項(xiàng)有4個(gè)字節(jié)），前10個(gè)登記項(xiàng)直接指出存放文件信息的磁盤塊號(hào)。如果10個(gè)磁盤塊不夠容納該文件信息，則利用第11個(gè)登記項(xiàng)指向一個(gè)磁盤塊，該磁盤塊作為文件的一級(jí)間接索引共有128個(gè)登記項(xiàng)（每個(gè)登記項(xiàng)為4個(gè)字節(jié)），可分別指向128個(gè)磁盤塊。于是，文件的長(zhǎng)度可達(dá)到138個(gè)磁盤塊的容量。對(duì)于大型文件還可利用第12和第13兩個(gè)登記項(xiàng)作為二級(jí)和三級(jí)間接索引參考7-3：了解UNIX文件結(jié)構(gòu)利用主存緩沖區(qū)可以把多個(gè)邏輯記錄一次性保存到磁盤塊上。也就是當(dāng)記錄要求存盤時(shí)，先存入主存緩沖區(qū)，緩沖區(qū)的大小等于最大邏輯長(zhǎng)度乘以成組的塊因子，就是塊的大小。在緩沖區(qū)未存滿時(shí)，不啟動(dòng)磁盤寫，這樣就提高了存儲(chǔ)空間的利用率，減少啟動(dòng)外設(shè)的次數(shù)，提高了系統(tǒng)的工作效率。2、記錄的成組：把若干個(gè)邏輯記錄合成一組存入一塊的工作稱為“記錄的成組”。每塊中邏輯記錄的個(gè)數(shù)稱“塊因子”3、記錄的分解：記錄成組的一個(gè)逆過程。先從磁盤中找到記錄所在的塊，并將本塊讀入主存緩沖區(qū)，再?gòu)木彌_區(qū)取出所需要的記錄送到用戶工作區(qū)。如果用戶所需的記錄已經(jīng)在緩沖區(qū)中，則不需要啟動(dòng)外設(shè)讀塊信息，這也可以提高系統(tǒng)工作效率。歸并方法：首先將文件中的數(shù)據(jù)輸入到內(nèi)存，采用內(nèi)部分類方法進(jìn)行分類（歸并段），然后將有序段寫回外存；對(duì)多歸并段進(jìn)行多遍歸并，最后形成一個(gè)有序序列。7.3磁盤文件的歸并分類磁盤信息的存取

磁盤：是一個(gè)扁平的圓盤，盤面上有許多稱為磁道的圓圈，信息就記載在磁道上。它是一種直接存取的存儲(chǔ)設(shè)備（DASD）。

磁盤的工作原理：盤片裝在一個(gè)主軸上，并繞主軸高速旋轉(zhuǎn)，當(dāng)磁道在讀/寫頭下通過時(shí)，便可進(jìn)行信息的讀/寫。讀/寫信息的功能由磁盤驅(qū)動(dòng)器執(zhí)行。

固定頭盤：固定頭盤的每一磁道上都有獨(dú)立的磁頭，這些磁頭固定不動(dòng)，專負(fù)責(zé)讀/寫某一磁道上的信息。

活動(dòng)頭盤：活動(dòng)頭盤的磁頭是可以移動(dòng)的。一個(gè)盤面上只有一個(gè)磁頭，磁頭裝在一個(gè)動(dòng)臂上，可以從該面上的一道移動(dòng)到另一道。

在磁盤上表明一個(gè)具體信息必須用一個(gè)三維地址：柱面號(hào)（確定讀/寫頭的徑向運(yùn)動(dòng))、盤面號(hào)、塊號(hào)(確定信息在盤片圓圈上的位置）。磁盤結(jié)構(gòu)：由磁盤驅(qū)動(dòng)器、讀、寫磁頭、活動(dòng)臂、盤片（磁道、扇區(qū)）、旋轉(zhuǎn)主軸構(gòu)成。速度快、容量大、直接存取設(shè)備。訪問一塊信息：（1）找柱面,移動(dòng)臂使磁頭移動(dòng)到所需柱面上(稱為定位或?qū)げ?；（2）等待要訪問的信息轉(zhuǎn)動(dòng)磁頭之下；（3）讀/寫所需信息。磁盤上讀寫一塊信息所需的時(shí)間為：TI/O=tseek+tla+n*twm其中：tseek為尋查時(shí)間（seektime）：讀/寫頭定位的時(shí)間；

tla為等待時(shí)間（latencytime）：

等待信息塊的初始位置旋到讀/寫頭下的時(shí)間；

twm為傳輸時(shí)間（transmissiontime）?！纠?-4】假設(shè)一個(gè)磁盤文件，由4500個(gè)記錄組成，分別記為A1,A2,……,A4500設(shè)系統(tǒng)提供容納750個(gè)記錄的內(nèi)存共分類使用，每次磁盤讀寫250個(gè)記錄的數(shù)據(jù)塊，則可設(shè)計(jì)分類過程如下：(1)每次從文件中輸入三個(gè)數(shù)據(jù)塊（750個(gè)記錄）到工作空間，進(jìn)行內(nèi)部分類。分類結(jié)果寫回磁盤，構(gòu)成6個(gè)初始?xì)w并段：R1,R2,R3,R4,R5,R6R1R2R3R4R5R61-750751-15001501-22502251-30003001-37503751-4500（2）將內(nèi)存空間三等分，每塊250個(gè)記錄，其中2塊為輸入緩沖區(qū)，1塊為輸出緩沖區(qū)。歸并R1和R2，輸出到輸出緩沖區(qū)，若輸出緩沖區(qū)滿，則寫盤。同樣，若R1和R2的緩沖區(qū)出現(xiàn)空，則繼續(xù)讀盤，直到歸并結(jié)束為止。R12=R1+R2；同樣得到：R34=R3+R4,R56=R5+R6；R12、R34、R56分別都包含1500個(gè)記錄。（3）類似（2）的方法，可將R12和R34歸并成R1234,，再將R1234和R56進(jìn)行歸并。得到最后的排序結(jié)果。R1R2R3R4R5R6R12R34R56R1234R12346×750記錄3×1500記錄12×250記錄18×250記錄K路歸并……...遍數(shù)[log2m]層數(shù)[log2m]+1M個(gè)歸并段的歸并過程R1R2Rm-1Rm2…KK+1…2K……m...logkm+1levers(1)多路歸并——減少歸并遍數(shù)并行操作的緩沖區(qū)處理——使輸入、輸出和CPU處理盡可能重疊(3)初始?xì)w并段的生成討論問題：logkm遍比較次數(shù)：擴(kuò)大初始?xì)w并段長(zhǎng)度，從而減少初始?xì)w并段個(gè)數(shù)m進(jìn)行多路(k路)歸并減少合并趟數(shù)s，以減少I/O次數(shù)

s=logkm提高外排序效率的途徑：(1)多路歸并——減少歸并遍數(shù)m個(gè)初始段進(jìn)行2路歸并，需要log2m遍歸并;m個(gè)初始段，采用k路歸并，需要logkm遍歸并。顯然，k越大，歸并遍數(shù)越少，可提高歸并的效率。

在k路歸并時(shí)，從k個(gè)關(guān)鍵字中選擇最小記錄時(shí)，要比較K-1次。若記錄總數(shù)為n，每遍要比較的次數(shù)為：

n*(k-1)[log2m/log2k]可以看出，隨著k增大，(k-1)/log2k也增大，當(dāng)歸并路數(shù)多時(shí)，CPU處理的時(shí)間也隨之增多。為此要選擇好的分類方法，以減少分類中比較次數(shù)。610920689901796817681516203820301525155011161001101820

選擇樹(Selectiontree)或敗者樹(treeofloser)分析：第一次建立選擇樹的比較所花時(shí)間為:O(k-1)=O(k)而后每次重新建造選擇樹所需時(shí)間為：

O(log2k)n個(gè)記錄處理時(shí)間為初始建立選擇樹的時(shí)間加上n-1次重新選擇樹的時(shí)間：

O((n-1)·

log2k)+O(k)=O(n·

log2k)這就是k路歸并一遍所需的CPU處理時(shí)間。歸并遍數(shù)為logkm，總時(shí)間為：

O(n·

log2k·

logkm)=O(n·

log2m)(k路歸并CPU時(shí)間與k無關(guān))最佳歸并樹

將哈夫曼樹進(jìn)行拓展，不僅對(duì)2叉樹，同樣可形成3叉、4叉、…、k叉樹，亦稱為哈夫曼樹，同樣可求得帶權(quán)路徑長(zhǎng)度最小。對(duì)長(zhǎng)度不等的m個(gè)初始?xì)w并段，構(gòu)造哈夫曼樹作為歸并樹，可使在進(jìn)行外部歸并時(shí)所需要對(duì)外存進(jìn)行的讀寫次數(shù)達(dá)到最小。

最佳歸并樹中，并不只是只有度為k和0的結(jié)點(diǎn)，會(huì)有缺額。當(dāng)初始?xì)w并段的數(shù)目不足時(shí)，需附加長(zhǎng)度為0的虛段，按照哈夫曼樹的構(gòu)造原則，權(quán)為0的葉子結(jié)點(diǎn)應(yīng)離樹根最遠(yuǎn)。問題：起因：由于初始?xì)w并段通常不等長(zhǎng),進(jìn)行歸并時(shí),長(zhǎng)度不同的初始?xì)w并段歸并的順序不同,讀寫外存的總次數(shù)也不同。目的：減少讀寫外存的次數(shù)。【例7-5】9個(gè)初始?xì)w并段，記錄數(shù)分別為9、30、12、18、3、17、2、6、24。如果進(jìn)行3-路歸并，請(qǐng)討論在各種情況下的對(duì)外存的讀寫次數(shù)。從外存讀121個(gè)記錄寫入外存121個(gè)記錄從外存讀121個(gè)記錄寫入外存121個(gè)記錄30129317186242513832121總共讀寫外存484個(gè)記錄讀寫磁盤次數(shù)=∑wj·

lj=(9+30+12+18+3+17+2+6+24)*2=242從外存讀11個(gè)記錄寫入外存11個(gè)記錄從外存讀91個(gè)記錄寫入外存121個(gè)記錄寫入外存91個(gè)記錄從外存讀121個(gè)記錄62392417183011325912112總共讀寫外存446個(gè)記錄讀寫磁盤次數(shù)=∑wj·

lj=(2+3+6)*3+(9+12+17+18+24)*2+30*1=223按照hafuman樹的思想，記錄少的段最先合并。不夠時(shí)增加虛段【例7-6】8個(gè)初始?xì)w并段，記錄數(shù)分別為2、3、6、9、12、17、18、24。如果進(jìn)行3-路歸并，請(qǐng)討論在各種情況下的對(duì)外存的讀寫次數(shù)。從外存讀5個(gè)記錄寫入外存5個(gè)記錄從外存讀67個(gè)記錄寫入外存91個(gè)記錄寫入外存67個(gè)記錄從外存讀91個(gè)記錄共讀寫326個(gè)記錄讀寫磁盤次數(shù)=∑wj·

lj=(2+3)*3+(6+9+12+17+18)*2+24*1=163

虛段的補(bǔ)法:

在K路平衡歸并時(shí)，它的歸并樹的模型是一棵度為K的樹。在這棵樹上的結(jié)點(diǎn)要么是葉子，要么是具有K個(gè)孩子的內(nèi)部結(jié)點(diǎn)。設(shè)具有K個(gè)孩子的內(nèi)部結(jié)點(diǎn)共有nk

個(gè)。初始?xì)w并段的個(gè)數(shù)為m個(gè)。設(shè)n=nk+m，故：從結(jié)點(diǎn)出發(fā)的分枝，共計(jì)有K*nk

個(gè)。若從進(jìn)入結(jié)點(diǎn)的角度進(jìn)行考慮，則共有：nk+m-1注意：沒有分枝進(jìn)入根結(jié)點(diǎn)。所以，K*nk＝nk+m-1

于是：nk=(m-1)/(K-1)

這就意味著，若(m-1)MOD(K-1)＝0，無需增加虛段。否則，要增加虛段，其數(shù)目為：（K-1)-(m-1)MOD(K-1)限制：由于磁帶尋找具有最少記錄的初始?xì)w并段，必須反復(fù)倒帶。所以，實(shí)用性不強(qiáng)；在磁盤的情況下，需要有段包含的記錄數(shù)信息、段的位置信息等；文件如集中放置在幾個(gè)相鄰的柱面上的情況比較合適。并行操作的緩沖區(qū)處理----1324ou(1)ou(2)iu(1)iu(2)----iu(3)iu(4)12---3-457--34----57615歸并到ou(1)輸入到in(3)歸并到ou(2)輸入到in(4)輸出ou(1)(a)(b)(c)56

89---7-15

78-92025---159-

--2025

-15歸并到ou(1)輸入到in(1)歸并到ou(1)輸入到in(3)輸出ou(2)(d)(e)(f)歸并到ou(2)輸入到in(2)輸出ou(1)輸出ou(2)

對(duì)k個(gè)歸并段進(jìn)行k路歸并至少需要k個(gè)輸入和1個(gè)輸出緩沖區(qū)，要使輸入、輸出和歸并同時(shí)進(jìn)行，k+1個(gè)緩沖區(qū)是不夠的，需要2k個(gè)輸入緩沖區(qū)實(shí)現(xiàn)并行操作。135789246152025(3)初始?xì)w并段的生成步12345678910111213…緩沖區(qū)內(nèi)容151515(11)(11)(11)(11)(11)(11)1111(06)……1919191925(16)(16)(16)(16)161616……04122727272734(26)(26)262626……8383838383838383(07)109090……輸出結(jié)果0412151925273483

07101116…R1R2(a)初始?xì)w并段的長(zhǎng)度≥緩沖區(qū)的長(zhǎng)度(b)任何內(nèi)部分類算法都可作為生成初始?xì)w并段的算法(c)例如：緩沖區(qū)的長(zhǎng)度為4，輸入序列為：

151904831227112516342607109006…新輸入記錄.key小于當(dāng)前記錄.key，等待下一個(gè)歸并段采用置換-選擇法生成初始?xì)w并段的長(zhǎng)度平均是緩沖區(qū)長(zhǎng)度的兩倍。磁盤文件的歸并分類小結(jié)：1、磁盤文件的特點(diǎn)2、要解決的問題

（1）多路歸并—減少歸并遍數(shù)k路歸并，選擇樹，最佳歸并樹（k-叉哈夫曼樹）

（2）并行操作的緩沖區(qū)處理—使輸入、輸出和CPU處理盡可能重疊

2k個(gè)輸入緩沖區(qū)，2個(gè)輸出緩沖區(qū)

（3）初始?xì)w并段的生成

置換-選擇法，生成初始?xì)w并段長(zhǎng)度平均是緩沖區(qū)長(zhǎng)度的兩倍7.4磁帶文件的歸并分類（外部）存儲(chǔ)設(shè)備——紙帶、磁鼓、磁帶、磁盤等磁帶信息的表示：一種磁化方向、代表1另一種磁化方向，代表00100100110101111參考資料：關(guān)于磁帶

磁帶：一條薄薄涂上一層磁性材料的窄帶（現(xiàn)在使用的磁帶大多數(shù)有1/2英寸寬，最長(zhǎng)可達(dá)3600英尺，繞在一個(gè)卷盤上）。它是一種順序存取的存儲(chǔ)設(shè)備。

磁帶的工作原理：使用時(shí)，將磁帶放在磁帶機(jī)上，驅(qū)動(dòng)器控制磁帶盤轉(zhuǎn)動(dòng)，帶動(dòng)磁帶向前移動(dòng)。通過讀/寫頭就可以讀出磁帶上的信息或者把信息寫入磁帶中。

7道帶：在1/2英寸寬的帶面上記錄7位二進(jìn)制信息的磁帶。

9道帶：在1/2英寸寬的帶面上記錄9位二進(jìn)制信息的磁帶。每一橫排可表示一個(gè)字符（8位表示一個(gè)字符，剩下的一位作奇偶校驗(yàn)位）。

信息密度：每英寸的二進(jìn)制字符數(shù)。通常為每英寸800位或1600位或6250位。移動(dòng)速度：每秒200英寸。

間隙IRG（InterRecordGap）：磁帶上相鄰兩組字符組（記錄）之間的空白區(qū)。根據(jù)啟停時(shí)間的需要，這個(gè)間隙通常為1/4~3/4英寸。

例如，若每個(gè)字符組的長(zhǎng)度是80個(gè)字符，IRG為3/4英寸，則對(duì)密度為每英寸1600個(gè)字符的磁帶，其利用率僅為1/16，有15/16的帶用于IRG。如圖11.1(a)所示。

塊間間隙IBG（InterBlockGap）：將若干個(gè)字符組合并成塊，每個(gè)字符組間沒有IRG，而變成塊間的間隙。

例如，圖(b)表示將20個(gè)長(zhǎng)度為80字符的字符組存放在磁帶上的一個(gè)物理塊中的情況。IRGIRGIRG記錄(a)字符組長(zhǎng)80字符的磁帶IBGIBGIBG20個(gè)記錄20個(gè)記錄20個(gè)記錄(b)成塊存放的磁帶磁帶上信息存放示意圖磁帶上讀寫一塊信息所需的時(shí)間為： TI/O=ta+n*tw其中：ta為延遲時(shí)間，讀/寫頭到達(dá)傳輸信息所在物理塊起始位置所需時(shí)間（顯然，延遲時(shí)間和信息在磁帶上的位置、當(dāng)前讀/寫頭所在位置有關(guān)）；tw為傳輸一個(gè)字符的時(shí)間。成塊的優(yōu)點(diǎn)：（1）可以減少IRG的數(shù)目，從而提高磁帶的利用率，塊的長(zhǎng)度大于IBG的長(zhǎng)度。（2）可以減少I/O操作。因?yàn)橐淮蜪/O操作可把整個(gè)物理塊都讀到內(nèi)存緩沖區(qū)中，然后再?gòu)木彌_區(qū)中取出所需要的信息（一個(gè)字符組）。每當(dāng)要讀一個(gè)字符組時(shí)，首先要查緩沖區(qū)中是否已有，若有，則不必執(zhí)行I/O操作，直接從緩沖區(qū)讀取即可。

與磁盤不同，磁帶是順序存儲(chǔ)設(shè)備，讀取信息塊的時(shí)間與信息塊的位置有關(guān)。研究磁帶分類，需要了解信息塊的分布。K路平衡歸并分類磁帶機(jī)數(shù)量：2k輸入：T1,T2,……,Tk

輸出輸出：Tk+1,Tk+2,……,T2k

輸入磁帶機(jī)T1T2…Tk歸并段R1R2…RkRk+1Rk+2…R2k…………Rmk+1………T1:R1(1000),R3(1000),R5(1000)T2:R2(1000),R4(1000),R6(1000)T3:?T4:?T1:?T2:?T3:

R1(2000),R3(2000)T4:R2(2000)T1:R1(4000)T2:

R2(2000)T3:?T4:?T1:?T2:?T3:R1(6000)

T4:?i遍后t1t2t3開始13(1L)21(L)空1空8(1L)13(2L)28(3L)空5(2L)33(3L)5(5L)空4空2(5L)3(8L)52(13L)空1(8L)61(13L)1(21L)空7空空1(34L)步t1t2t3總段數(shù)n0011n-11102n-22013n-30235n-43508n-580513n-6081321n-71321034以k=2為例，用三臺(tái)磁帶機(jī)T1，T2，T3，假設(shè)初始?xì)w并段長(zhǎng)度為L(zhǎng)。初始?xì)w并段的段數(shù)為34。過程如表1所示。將上例遞歸過程從最后一步逆推，如表2所示。每一步歸并段總數(shù)排列成序列為：1，2，3，5，8，13，21，34,…剛好組成Fibonacci數(shù)列，F(xiàn)k=Fk-1+Fk-2K路多階段歸并，可從2路歸并擴(kuò)充，對(duì)應(yīng)k階Fibonacci數(shù)列。0≤n≤K-2n=K-1n≥K……結(jié)論：K+1臺(tái)磁帶機(jī)k路多階段歸并，在n-j步歸并段的分布規(guī)則=〉第j步歸并斷總數(shù)：其中第j步中邏輯磁帶機(jī)上第i臺(tái)磁帶機(jī)。表示：空磁帶機(jī)臺(tái)號(hào)=K+1當(dāng)j=0或k+1的整數(shù)倍j%(k+1)j不為上述值注意：在多路歸并中，若要求歸并的文件其初始?xì)w并段總數(shù)不是K階Fibonacci數(shù)，則需附加一些虛的歸并段數(shù)，以湊成k階Fibonacci數(shù)，同時(shí)還應(yīng)該將虛歸并段適當(dāng)?shù)胤植荚趉路歸并的k臺(tái)磁帶上。每一步都有一臺(tái)磁帶機(jī)是空的。【例7-7】設(shè)有磁盤文件中記錄的關(guān)鍵字分別為：

10,20,15,25,12,13,21,30,8,16,10

用置換-選擇排序法產(chǎn)生初始?xì)w并段，問可產(chǎn)生幾個(gè)初始?xì)w并段？每個(gè)初始?xì)w并段包含哪些記錄（設(shè)工作區(qū)能容納4個(gè)記錄）。解：內(nèi)存緩沖區(qū)可容納4個(gè)記錄，采用4路歸并的置換-選擇排序方法生成初始