數(shù)據(jù)結構與算法-文件與外部排序

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

●INSERT，在文件中插入記錄

●DELETE，從文件中刪除記錄

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

●

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

Q1簡單查詢：查詢單個關鍵字值等于給定值的記錄

如：性別=男

Q2范圍查詢：查詢單個關鍵字值滿足指定范圍的記錄

如：數(shù)學>80

Q3函數(shù)查詢：對于某個關鍵字的函數(shù)，查詢滿足指定函數(shù)

值的記錄

如：物理>平均分

Q4布爾查詢：對Q1Q2Q3進行組合的查詢，查詢滿足布爾

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

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

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

int_mode;//文件操作方式

char*_next;//文件當前讀寫位置

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

fread(buffer,size,count,fp);

fwrite(buffer,size,count,fp);

標準輸入：鍵

盤-------stdin

標準輸出：顯示器-------stdout標準出錯輸出：顯示器-------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)文件、庫文件、用戶文件

按保護級別

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

輸入文件、輸出文件、輸入輸出文件按存放時限

臨時文件、永久文件、檔案文件按設備類型

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

按文件組織結構邏輯文件(流式文件、記錄式文件)、物理文件（順序文件、鏈接文件、索引文件）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

是是(軟盤引導)

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

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

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

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

③刪除記錄時要批量移動記錄，或標記記錄④若要更新文件中某個記錄，則必須將整個文件進行復制。3、磁帶上順序文件的批處理主文件：待修改的原始文件。事務文件：所有的修改請求集中構成的一個文件。磁帶文件的批處理過程：首先對事務文件進行排序，然后將主文件和事務文件歸并成一個新的主文件。

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

終端事務文件排序有序的事務文件主文件新主文件

在歸并的過程中，順序讀出主文件與事務文件中的記錄，比較它們的關鍵字并分別進行處理。對于關鍵字不匹配的主文件中的記錄，則直接將其寫入新主文件中?！案摹焙汀皠h除”記錄時，要求其關鍵字相匹配。“刪去”不用寫入，而“更改”則要將更改后的新記錄寫入新主文?！安迦搿睍r不要求關鍵字相匹配，可直接將事務文件上要插入的記錄寫到新主文件的適當位置。算法實現(xiàn)：f—主文件；g—事務文件；h—新主文件。它們都按關鍵字遞增排序。事務文件的每個記錄中，增設一個代碼以示修改要求，其中：“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: //復制“舊”主文件中記錄

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

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的結構

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歸并成一個h結構的記錄

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

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

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

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

索引項：索引表中的每一項?？偸前搓P鍵字（或邏輯記錄號）順序排列。索引文件：包括文件數(shù)據(jù)區(qū)和索引表兩大部分的文件。索引順序文件：數(shù)據(jù)區(qū)中的記錄也按關鍵字順序排列的

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

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

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

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

由于索引項的長度比記錄小得多，則通常可將索引表一次讀入內(nèi)存，由此在索引文件中進行檢索只訪問外存兩次，即一次讀索引，一次讀記錄。并且由于索引表是有序的，則查找索引表時可用折半查找法。3、索引文件的檢索檢索方式：直接存取或按關鍵字（進行簡單詢問）存取。

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

上述的多級索引是一種靜態(tài)索引，索引均為順序表結構。其結構簡單，但修改很不方便，每次修改都要重組索引。當記錄變動較多時，應采用動態(tài)索引。

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

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

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

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

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

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

在插入和刪除記錄時，倒排表也要作相應的修改，值得注意的是倒排表中具有同一次關鍵字的記錄號是有序排列的，則修改時要作相應移動。(a)專業(yè)倒排表(b)已修學分倒排表(c)選修課目倒排表【例7-2】上例文件的倒排表紀錄號姓名學號專業(yè)已修學分選修課程01王雯135002軟件0241203丙02丁0302馬小雁135103軟件0739807甲04丙0303阮森135204計算機05436^乙05丙04丁0504蘇明明1353^應用0640208甲06丙0805田永135406計算機^38402乙07丁0906楊青135507應用0935610甲0707薛平平135608軟件08398^甲08乙^08崔子健1357^軟件^40801甲09丙^09王洪135810應用1037005甲10丁^10劉倩1359^應用^36409甲^軟件01,02,07,08計算機03,05應用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文件），則倒排表中應存放記錄的主關鍵字而不是物理記錄號。倒排文件的缺點：維護困難在同一索引表中，不同的關鍵字其記錄數(shù)不同，各倒排表的長度不等，同一倒排表中各項長度也不等。記錄職工號姓名職務性別婚否工資A29丁一程序員男婚898B05王二維修員男婚456C02趙忠程序員女婚1200D38張三工程師女否2400E31王五維修員男婚456F43劉玉維修員女婚456G17李芳程序員男否1200H46張洪工程師女否3000次關鍵字指針程序員CGA維修員BEF工程師DH次關鍵字指針男BGAE女CDFH次關鍵字指針婚CBAEF否GDH職務索引性別索引婚否索引【例7-3】倒排文件結構參考7-1：ISAM文件1、基本屬于索引順序存取方法ISAM(IndexedSequentialAccessMethod)：是一種專為磁盤存取設計的文件組織方式，采用靜態(tài)索引結構。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

磁盤的工作原理：盤片裝在一個主軸上，并繞主軸高速旋轉，當磁道在讀/寫頭下通過時，便可進行信息的讀/寫。讀/寫信息的功能由磁盤驅動器執(zhí)行。

固定頭盤：固定頭盤的每一磁道上都有獨立的磁頭，這些磁頭固定不動，專負責讀/寫某一磁道上的信息。

活動頭盤：活動頭盤的磁頭是可以移動的。一個盤面上只有一個磁頭，磁頭裝在一個動臂上，可以從該面上的一道移動到另一道。

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

tla為等待時間（latencytime）：

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

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

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

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

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

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

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

O((n-1)·

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

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

O(n·

log2k·

logkm)=O(n·

log2m)(k路歸并CPU時間與k無關)最佳歸并樹

將哈夫曼樹進行拓展，不僅對2叉樹，同樣可形成3叉、4叉、…、k叉樹，亦稱為哈夫曼樹，同樣可求得帶權路徑長度最小。對長度不等的m個初始歸并段，構造哈夫曼樹作為歸并樹，可使在進行外部歸并時所需要對外存進行的讀寫次數(shù)達到最小。

最佳歸并樹中，并不只是只有度為k和0的結點，會有缺額。當初始歸并段的數(shù)目不足時，需附加長度為0的虛段，按照哈夫曼樹的構造原則，權為0的葉子結點應離樹根最遠。問題：起因：由于初始歸并段通常不等長,進行歸并時,長度不同的初始歸并段歸并的順序不同,讀寫外存的總次數(shù)也不同。目的：減少讀寫外存的次數(shù)?！纠?-5】9個初始歸并段，記錄數(shù)分別為9、30、12、18、3、17、2、6、24。如果進行3-路歸并，請討論在各種情況下的對外存的讀寫次數(shù)。從外存讀121個記錄寫入外存121個記錄從外存讀121個記錄寫入外存121個記錄30129317186242513832121總共讀寫外存484個記錄讀寫磁盤次數(shù)=∑wj·

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

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

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

虛段的補法:

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

個。初始歸并段的個數(shù)為m個。設n=nk+m，故：從結點出發(fā)的分枝，共計有K*nk

個。若從進入結點的角度進行考慮，則共有：nk+m-1注意：沒有分枝進入根結點。所以，K*nk＝nk+m-1

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

這就意味著，若(m-1)MOD(K-1)＝0，無需增加虛段。否則，要增加虛段，其數(shù)目為：（K-1)-(m-1)MOD(K-1)限制：由于磁帶尋找具有最少記錄的初始歸并段，必須反復倒帶。所以，實用性不強；在磁盤的情況下，需要有段包含的記錄數(shù)信息、段的位置信息等；文件如集中放置在幾個相鄰的柱面上的情況比較合適。并行操作的緩沖區(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)

對k個歸并段進行k路歸并至少需要k個輸入和1個輸出緩沖區(qū)，要使輸入、輸出和歸并同時進行，k+1個緩沖區(qū)是不夠的，需要2k個輸入緩沖區(qū)實現(xiàn)并行操作。135789246152025(3)初始歸并段的生成步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……輸出結果0412151925273483

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

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

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

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

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

（3）初始歸并段的生成

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

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

磁帶的工作原理：使用時，將磁帶放在磁帶機上，驅動器控制磁帶盤轉動，帶動磁帶向前移動。通過讀/寫頭就可以讀出磁帶上的信息或者把信息寫入磁帶中。

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

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

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

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

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

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

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

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

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

輸入磁帶機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為例，用三臺磁帶機T1，T2，T3，假設初始歸并段長度為L。初始歸并段的段數(shù)為34。過程如表1所示。將上例遞歸過程從最后一步逆推，如表2所示。每一步歸并段總數(shù)排列成序列為：1，2，3，5，8，13，21，34,…剛好組成Fibonacci數(shù)列，F(xiàn)k=Fk-1+Fk-2K路多階段歸并，可從2路歸并擴充，對應k階Fibonacci數(shù)列。0≤n≤K-2n=K-1n≥K……結論：K+1臺磁帶機k路多階段歸并，在n-j步歸并段的分布規(guī)則=〉第j步歸并斷總數(shù)：其中第j步中邏輯磁帶機上第i臺磁帶機。表示：空磁帶機臺號=K+1當j=0或k+1的整數(shù)倍j%(k+1)j不為上述值注意：在多路歸并中，若要求歸并的文件其初始歸并段總數(shù)不是K階Fibonacci數(shù)，則需附加一些虛的歸并段數(shù)，以湊成k階Fibonacci數(shù)，同時還應該將虛歸并段適當?shù)胤植荚趉路歸并的k臺磁帶上。每一步都有一臺磁帶機是空的?！纠?-7】設有磁盤文件中記錄的關鍵字分別為：

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

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