數(shù)據(jù)結(jié)構(gòu)第13章 文件

第13章文件

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

記錄是文件中存取的基本單位，數(shù)據(jù)項(xiàng)是文件可使用的最小單位。數(shù)據(jù)項(xiàng)有時(shí)也稱為字段。其值能惟一標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)或數(shù)據(jù)項(xiàng)的組合稱為主關(guān)鍵字項(xiàng)，其他不能惟一標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)則稱為次關(guān)鍵字項(xiàng)，主關(guān)鍵字項(xiàng)(或次關(guān)鍵字項(xiàng))的值稱為主關(guān)鍵字(或次關(guān)鍵字)。為討論方便起見(jiàn)，我們?nèi)圆粐?yán)格區(qū)分關(guān)鍵字項(xiàng)和關(guān)鍵字,即在不易混淆時(shí)，將主(或次)關(guān)鍵字項(xiàng)簡(jiǎn)稱為主(或次)關(guān)鍵字，并且假定主關(guān)鍵字項(xiàng)只含一個(gè)數(shù)據(jù)項(xiàng)。

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

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

順序文件的結(jié)構(gòu)特點(diǎn)：記錄在文件中的排列順序是由記錄進(jìn)入存儲(chǔ)介質(zhì)的次序決定的，即文件物理結(jié)構(gòu)中記錄的排列順序和文件的邏輯結(jié)構(gòu)中記錄的排列順序一致。順序文件的操作特點(diǎn)：

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

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

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

(4)刪除記錄時(shí)，只作標(biāo)記；

(5)更新記錄必須生成新的文件。13.3索引文件用索引的方法組織文件時(shí)，通常是在文件本身(稱為主文件)之外，另外建立一張表，它指明邏輯記錄和物理記錄之間的一一對(duì)應(yīng)關(guān)系，這張表就叫做索引表，它和主文件一起構(gòu)成的文件稱作索引文件。索引表中的每一項(xiàng)稱作索引項(xiàng)，一般索引項(xiàng)都是由主關(guān)鍵字和該關(guān)鍵字所在記錄的物理地址組成的。顯然,索引表必須按主關(guān)鍵字有序，而主文件本身則可以按主關(guān)鍵字有序或無(wú)序，前者稱為索引順序文件，后者稱為索引非順序文件。對(duì)于索引非順序文件，由于主文件中記錄是無(wú)序的,則必須為每個(gè)記錄建立一個(gè)索引項(xiàng)，這樣建立的索引表稱為稠密索引。對(duì)于索引順序文件，由于主文件中記錄按關(guān)鍵字有序，則可對(duì)一組記錄建立一個(gè)索引項(xiàng)，例如,讓文件中每個(gè)頁(yè)塊對(duì)應(yīng)一個(gè)索引項(xiàng)，這種索引表稱之為稀疏索引。通?？蓪⑺饕琼樞蛭募?jiǎn)稱為索引文件，本節(jié)只討論這種文件。

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

101110115王平

115211333張萍

123312458陳強(qiáng)

138413524馬偉

144584索引文件的結(jié)構(gòu)特點(diǎn)：

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

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

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

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

(1)檢索方式為：直接存取和按關(guān)鍵字存取?！鞍搓P(guān)鍵字檢索”將分兩步進(jìn)行：先查索引，然后根據(jù)索引中指針?biāo)杆魅∮涗洠?/p>

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

(3)刪除記錄時(shí)，僅需刪除索引表中相應(yīng)的索引項(xiàng)即可；

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

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

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

(1)磁道索引

(2)柱面索引

(3)主索引磁道索引結(jié)構(gòu)如下：基本索引項(xiàng)溢出索引項(xiàng)關(guān)鍵字

指針

關(guān)鍵字

指針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)一個(gè)柱面

….柱面索引992101024T0T1T2T3T4T5R64

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

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

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

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

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

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

例如,某一文件有16個(gè)記錄,其關(guān)鍵字集合為{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。給出對(duì)應(yīng)的哈希文件。在哈希文件中進(jìn)行查找時(shí)，首先根據(jù)給定值求出哈希桶地址，將基桶的記錄讀入內(nèi)存，進(jìn)行順序查找，若找到關(guān)鍵字等于給定值的記錄，則檢索成功；否則，讀入溢出桶的記錄繼續(xù)進(jìn)行查找。在哈希文件中刪去一個(gè)記錄，僅需對(duì)被刪記錄作刪除標(biāo)記即可。優(yōu)點(diǎn)：文件隨機(jī)存放,記錄不需進(jìn)行排序；插入、刪除方便；存取速度快；不需要索引區(qū)，節(jié)省存儲(chǔ)空間。缺點(diǎn)：不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取，且詢問(wèn)方式限于簡(jiǎn)單詢問(wèn)，并且在經(jīng)過(guò)多次插入、刪除后，也可能造成文件結(jié)構(gòu)不合理，需要重新組織文件。13.5多關(guān)鍵字文件前面介紹的文件都是只含一個(gè)主關(guān)鍵字的文件。為了提高查找效率，還需要對(duì)被查詢的次關(guān)鍵字建立相應(yīng)的索引，這種包含有多個(gè)次關(guān)鍵字索引的文件稱為多關(guān)鍵字文件。次關(guān)鍵字索引本身可以是順序表，也可以是樹(shù)表。下面討論兩種多關(guān)鍵字文件的組織方法。13.5.1多重表文件多重表文件是將索引方法和鏈接方法相結(jié)合的一種組織方式，它對(duì)每個(gè)需要查詢的次關(guān)鍵字建立一個(gè)索引，同時(shí)將具有相同次關(guān)鍵字的記錄鏈接成一個(gè)鏈表，并將此鏈表的頭指針、鏈表長(zhǎng)度及次關(guān)鍵字，作為索引表的一個(gè)索引項(xiàng)。通常多重表文件的主文件是一個(gè)順序文件。例如，教材中圖13.8(a)是一個(gè)多重表文