數(shù)據(jù)結構第13章 文件

第13章文件

本章小結13.1文件的基本概念13.2順序文件13.4哈希文件13.3索引文件13.5多關鍵字文件13.1文件的基本概念13.1.1什么是文件文件是性質相同的記錄的集合。文件的數(shù)據(jù)量通常很大,它被放置在外存上。數(shù)據(jù)結構中所討論的文件主要是數(shù)據(jù)庫意義上的文件，而不是操作系統(tǒng)意義上的文件。操作系統(tǒng)中研究的文件是一維的無結構連續(xù)字符序列，數(shù)據(jù)庫中所研究的文件是帶有結構的記錄集合，每個記錄可由若干個數(shù)據(jù)項構成。

記錄是文件中存取的基本單位，數(shù)據(jù)項是文件可使用的最小單位。數(shù)據(jù)項有時也稱為字段。其值能惟一標識一個記錄的數(shù)據(jù)項或數(shù)據(jù)項的組合稱為主關鍵字項，其他不能惟一標識一個記錄的數(shù)據(jù)項則稱為次關鍵字項，主關鍵字項(或次關鍵字項)的值稱為主關鍵字(或次關鍵字)。為討論方便起見，我們仍不嚴格區(qū)分關鍵字項和關鍵字,即在不易混淆時，將主(或次)關鍵字項簡稱為主(或次)關鍵字，并且假定主關鍵字項只含一個數(shù)據(jù)項。

文件可以按照記錄中關鍵字的多少，分成單關鍵字文件和多關鍵字文件。若文件中的記錄只有一個惟一標識記錄的主關鍵字，則稱其為單關鍵字文件；若文件中的記錄除了含有一個主關鍵字外，還含有若干個次關鍵字，則稱為多關鍵字文件。文件又可分成定長文件和不定長文件。若文件中記錄含有的信息長度相同，則稱這類記錄為定長記錄，由這種定長記錄組成的文件稱做定長文件；若文件中記錄含有的信息長度不等，則稱做不定長文件。13.1.2文件的邏輯結構及操作文件中各記錄之間存在著邏輯關系，當一個文件的各個記錄按照某種次序排列起來時(這種排列的次序可以是記錄中關鍵字的大小，也可以是各個記錄存入該文件的時間先后等等),各記錄之間就自然地形成了一種線性關系。在這種次序下,文件中每個記錄最多只有一個后繼記錄和一個前驅記錄，而文件的第一個記錄只有后繼沒有前驅，文件的最后一個記錄只有前驅而沒有后繼。因此，文件可看成是一種線性結構。文件上的操作主要有兩類：檢索和維護。13.1.3文件的存儲結構文件的存儲結構是指文件在外存上的組織方式。采用不同的組織方式就得到不同的存儲結構?；镜慕M織方式有四種：順序組織、索引組織、哈希組織和鏈組織。文件組織的各種方式往往是這四種基本方式的結合。幾種常用的文件組織方式：順序文件、索引文件、哈希文件和多關鍵字文件。選擇哪一種文件組織方式,取決于對文件中記錄的使用方式和頻繁程度、存取要求、外存的性質和容量。13.2順序文件

順序文件是指按記錄進入文件的先后順序存放、其邏輯順序跟物理順序一致的文件。若順序文件中的記錄按其主關鍵字有序,則稱此順序文件為順序有序文件；否則稱為順序無序文件。為了提高檢索效率,常常將順序文件組織成有序文件。

順序文件的結構特點：記錄在文件中的排列順序是由記錄進入存儲介質的次序決定的，即文件物理結構中記錄的排列順序和文件的邏輯結構中記錄的排列順序一致。順序文件的操作特點：

(1)便于進行順序存取；

(2)不便于進行直接存取，為取第i個記錄，必須先讀出前i-1個記錄，對于磁盤上的等長記錄的連續(xù)文件可以進行折半查找；

(3)插入新的記錄只能加在文件的末尾；

(4)刪除記錄時，只作標記；

(5)更新記錄必須生成新的文件。13.3索引文件用索引的方法組織文件時，通常是在文件本身(稱為主文件)之外，另外建立一張表，它指明邏輯記錄和物理記錄之間的一一對應關系，這張表就叫做索引表，它和主文件一起構成的文件稱作索引文件。索引表中的每一項稱作索引項，一般索引項都是由主關鍵字和該關鍵字所在記錄的物理地址組成的。顯然,索引表必須按主關鍵字有序，而主文件本身則可以按主關鍵字有序或無序，前者稱為索引順序文件，后者稱為索引非順序文件。對于索引非順序文件，由于主文件中記錄是無序的,則必須為每個記錄建立一個索引項，這樣建立的索引表稱為稠密索引。對于索引順序文件，由于主文件中記錄按關鍵字有序，則可對一組記錄建立一個索引項，例如,讓文件中每個頁塊對應一個索引項，這種索引表稱之為稀疏索引。通常可將索引非順序文件簡稱為索引文件，本節(jié)只討論這種文件。

索引文件在存儲器上分為兩個區(qū)：索引區(qū)和數(shù)據(jù)區(qū)，前者存放索引表，后者存放主文件。在建立文件過程中，按輸入記錄的先后次序建立數(shù)據(jù)區(qū)和索引表，這樣的索引表其關鍵字是無字的，待全部記錄輸入完畢后再對索引表進行排序，排序后的索引表和主文件一起就形成了索引文件。14物理地址12345學號姓名其他物理地址關鍵字物理地址物理地址關鍵字物理地址1李明

101110115王平

115211333張萍

123312458陳強

138413524馬偉

144584索引文件的結構特點：

(1)索引文件由“主文件”和多級“索引”組成；

(2)索引中的每個記錄由“關鍵字”和“指針”組成；

(3)通常，索引文件中的主文件是無序文件，索引是(按關鍵字有序)的有序文件；

(4)“索引”是在輸入數(shù)據(jù)建立文件時自動生成。初建時的“靜態(tài)索引”為無序文件，經過排序后成為有序文件。索引文件的操作特點：

(1)檢索方式為：直接存取和按關鍵字存取?！鞍搓P鍵字檢索”將分兩步進行：先查索引，然后根據(jù)索引中指針所指索取記錄；

(2)插入記錄時，“記錄”插入在主文件的末尾，而相應的“索引項”必須插入在索引的合適位置上。因此,最好在建索引表時留有一定“空位”；

(3)刪除記錄時，僅需刪除索引表中相應的索引項即可；

(4)更新記錄時，應將更新后的記錄插入在主文件的末尾，同時修改相應的索引項。有兩種典型的索引順序文件。13.2.1ISAM文件

ISAM(IndexSequentialAccessMethod)(索引順序存取方法)是一種專為磁盤存取設計的文件組織方法。1.文件的組織方式

主文件按柱面集中存放,同時建立三級索引：

(1)磁道索引

(2)柱面索引

(3)主索引磁道索引結構如下：基本索引項溢出索引項關鍵字

指針

關鍵字

指針2101024主索引r(14)r(21)r(38)r(41)r(57)r(63)r(72)r(85)r(99)溢出區(qū)磁道索引r(514)……溢出區(qū)磁道索引……r(1024)一個柱面

….柱面索引992101024T0T1T2T3T4T5R64

柱面溢出區(qū)7081……1407081………∧R140R130R138R68…T1T2R63R72R75……T0基本區(qū)R131R74R73…R136R65…磁道索引柱面C2R70∧R81∧R79C2T0磁道索引∧∧R70R66R76在文件中插入記錄插入64，74，7668767981２．操作的特點(1)檢索可有兩種方式：順序存取—依關鍵字最小至大順序存取。按關鍵字存取—從主索引開始，到柱面索引，到磁道索引，最后取得記錄，先后訪問四次外存。(2)插入將記錄插入在某個磁道的合適位置上；將該磁道上關鍵字最大的記錄移出到本柱面的溢出區(qū)中；修改本磁道的索引項(包括基本索引項和溢出索引項)。(3)刪除在被刪記錄當前存儲位置上作“刪除標記”。３．文件重組在經過多次的插入和刪除操作之后，大量的記錄進入文件的“溢出區(qū)”，而“基本存儲區(qū)”中出現(xiàn)很多已被刪去的記錄空間，此時的文件結構很不合理。因此，對ISAM文件，需要周期地進行重整。13.3.2VSAM文件

VSAM是虛擬存儲存取方法(VirtualStorageAccessMethod)的英文縮寫。VSAM文件是一種采用虛擬存儲存取方法的文件。VSAM文件的存儲單位是控制區(qū)間和控制區(qū)域,這是一些邏輯存儲單位，與柱面、磁道等實際存儲單位并沒有必然的聯(lián)系。用戶在存取VSAM文件的記錄時，不需要考慮該記錄的當前位置是在內存還是在外存，也不需要考虎何時執(zhí)行對外存進行讀／寫的命令?？梢姡@種文件較ISAM文件更方便用戶使用。1．文件的結構…............

索引集B+樹順序集控制區(qū)域控制區(qū)間數(shù)據(jù)集2.控制區(qū)間和控制區(qū)域控制區(qū)間：是用戶進行一次存取的邏輯單位，可看成是一個邏輯磁道。但它的實際大小和物理磁道無關?？刂茀^(qū)域：由若干控制區(qū)間和它們的索引項組成，可看成是一個邏輯柱面。

VSAM文件初建時，每個控制區(qū)間內的記錄數(shù)不足額定數(shù)，并且有的控制區(qū)間內的記錄數(shù)為零。３．順序集本身是一個單鏈表，它包含文件的全部索引項，同時，順序集中的每個結點即為B+樹的葉子結點，索引集中的結點即為B+樹的非葉結點。４．文件的操作檢索：可進行順序存取和按關鍵字存??；

插入：按關鍵字大小插入在某個適當?shù)目刂茀^(qū)間中，當控制區(qū)間中的記錄數(shù)超過文件規(guī)定的大小時，要“分裂”控制區(qū)間，必要時，還需要“分裂”控制區(qū)域；

刪除：必須“真實地”刪除記錄，因此要在控制區(qū)間內“移動”記錄。５．VSAM文件通常被作為大型索引順序文件的標準組織方式。優(yōu)點：動態(tài)地分配和釋放空間,不需要重組文件；能較快地實現(xiàn)對“后插入”的記錄的檢索；缺點：占有較多的存儲空間,一般只能保持約75%的存儲空間利用率。(因此,一般情況下,極少產生需要分裂控制區(qū)域的情況)13.4哈希文件哈希文件也稱為散列文件，是利用哈希存儲方式組織的文件,亦稱為直接存取文件。它類似于哈希表，即根據(jù)文件中關鍵字的特點，設計一個哈希函數(shù)和處理沖突的方法，將記錄哈希到存儲設備上。與哈希表不同的是，對于文件來說，磁盤上的文件記錄通常是成組存放的，若干個記錄組成一個存儲單位，在哈希文件中，這個存儲單位叫做桶。假如一個桶能存放m個記錄，則當桶中已有m個同義詞的記錄時，存放第m+1個同義詞會發(fā)生“溢出”。處理溢出雖可采用哈希表中處理沖突的各種方法，但對哈希文件而言，主要采用鏈地址法。當發(fā)生“溢出”時,需要將第m+1個同義詞存放到另一個桶中，通常稱此桶為“溢出桶”。相對地，稱前m個同義詞存放的桶為“基桶”。溢出桶和基桶大小相同，相互之間用指針鏈接。當在基桶中沒有找到待查記錄時，就沿著指針到所指溢出桶中進行查找，因此，希望同一哈希地址的溢出桶和基桶在磁盤上的物理位置不要相距太遠，最好在同一柱面上。

例如,某一文件有16個記錄,其關鍵字集合為{23,5,26,1,10,18,27,12,7,9,4,19,6,16,33,24}。桶的容量m=3,桶數(shù)b=7。用除留余數(shù)法作哈希函數(shù)H(key)=key%7。給出對應的哈希文件。在哈希文件中進行查找時，首先根據(jù)給定值求出哈希桶地址，將基桶的記錄讀入內存，進行順序查找，若找到關鍵字等于給定值的記錄，則檢索成功；否則，讀入溢出桶的記錄繼續(xù)進行查找。在哈希文件中刪去一個記錄，僅需對被刪記錄作刪除標記即可。優(yōu)點：文件隨機存放,記錄不需進行排序；插入、刪除方便；存取速度快；不需要索引區(qū)，節(jié)省存儲空間。缺點：不能進行順序存取，只能按關鍵字隨機存取，且詢問方式限于簡單詢問，并且在經過多次插入、刪除后，也可能造成文件結構不合理，需要重新組織文件。13.5多關鍵字文件前面介紹的文件都是只含一個主關鍵字的文件。為了提高查找效率，還需要對被查詢的次關鍵字建立相應的索引，這種包含有多個次關鍵字索引的文件稱為多關鍵字文件。次關鍵字索引本身可以是順序表，也可以是樹表。下面討論兩種多關鍵字文件的組織方法。13.5.1多重表文件多重表文件是將索引方法和鏈接方法相結合的一種組織方式，它對每個需要查詢的次關鍵字建立一個索引，同時將具有相同次關鍵字的記錄鏈接成一個鏈表，并將此鏈表的頭指針、鏈表長度及次關鍵字，作為索引表的一個索引項。通常多重表文件的主文件是一個順序文件。例如，教材中圖13.8(a)是一個多重表文