第十三章文件有關(guān)文件的基本概念順序文件索引文件索引順序文件直接存取文件多關(guān)鍵字文件13.1

有關(guān)文件的基本概念一、文件即為記錄的集合，和“查找

表”的差別在于，“文件”指的是儲(chǔ)在外存儲(chǔ)器中的記錄的集合。

記錄是文件中可以存取的數(shù)據(jù)的基本單位。二、文件可按其中記錄的類型不同而分成兩類：其一為操作系統(tǒng)的文件，文件中的記錄僅是一個(gè)字符組。由于操作系統(tǒng)中的文件僅是一維的連續(xù)字符序列，為了用戶存取和加工的方便，將文件中的信息劃分為若干組，其中每一組信息稱作一個(gè)記錄；其二為數(shù)據(jù)庫(kù)文件，文件中的記錄帶有結(jié)構(gòu)，是數(shù)據(jù)項(xiàng)的集合。記錄是文件中可以存取的數(shù)據(jù)基本單位，數(shù)據(jù)項(xiàng)是文件中可以使用的數(shù)據(jù)最小單位。三、記錄中能識(shí)別不同記錄的數(shù)據(jù)項(xiàng)被稱為關(guān)鍵字，若該數(shù)據(jù)項(xiàng)能唯一識(shí)別一個(gè)記錄，則稱為主關(guān)鍵字，若能識(shí)別多個(gè)記錄則稱為次關(guān)鍵字。四、文件的邏輯結(jié)構(gòu)指的是呈現(xiàn)在用戶面前的文件中記錄之間的邏輯關(guān)系；文件的物理結(jié)構(gòu)指的是文件中的邏輯記錄在存儲(chǔ)器中的組織方式。五、文件的操作：檢索修改排序1．檢索順序存?。捍嫒　爱?dāng)前記錄的”下一個(gè)記錄；直接存?。捍嫒〉趇個(gè)記錄；按關(guān)鍵字存?。捍嫒∑潢P(guān)鍵字等于給定值的記錄。2．修改往文件中插入一個(gè)或一批記錄；從文件中刪除一個(gè)或一批記錄；更新文件中某個(gè)記錄的屬性。3．排序文件的操作方式可以實(shí)時(shí)處理或批量處理。本章討論文件的幾種常見的物理結(jié)構(gòu)：順序文件索引文件索引順序文件直接存取文件多關(guān)鍵字文件13.2

順

序

文

件結(jié)構(gòu)特點(diǎn)：記錄在文件中的排列順序是由記錄進(jìn)入存儲(chǔ)介質(zhì)的次序決定的，即文件物理結(jié)構(gòu)中記錄的排列順序和文件的邏輯結(jié)構(gòu)中記錄的排列順序一致。順序文件的具體組織形式有兩種：連續(xù)文件：次序相繼的兩個(gè)物理記錄其存儲(chǔ)位置相鄰;串聯(lián)文件：物理記錄之間的順序由指針相鏈。操作特點(diǎn)：便于進(jìn)行順序存??；不便于進(jìn)行直接存取，為取第i個(gè)記錄，必須先讀出前i-1個(gè)記錄，對(duì)于磁盤上的等長(zhǎng)記錄的連續(xù)文件可以進(jìn)行折半查找；插入新的記錄只能加在文件的末尾；刪除記錄時(shí)，只作標(biāo)記；更新記錄必須生成新的文件。13.3索引文件一、結(jié)構(gòu)特點(diǎn)：索引文件由“主文件”和多級(jí)“索引”組成；索引中的每個(gè)記錄由“關(guān)鍵字”和“指針”組成；通常，索引文件中的主文件是無(wú)序文件，索引是(按關(guān)鍵字有序)的有序文件；“索引”是在輸入數(shù)據(jù)建立文件時(shí)自動(dòng)生成。初建時(shí)的“靜態(tài)索引”為無(wú)序文件，經(jīng)過排序后成為有序文件。二、操作的特點(diǎn)：１．檢索方式為：直接存取和按關(guān)鍵字存取。“按關(guān)鍵字檢索”將分兩步進(jìn)行：先查索引，然后根據(jù)索引中指針?biāo)杆魅∮涗?；２．插入記錄時(shí)，“記錄”插入在主文件的末尾，而相應(yīng)的“索引項(xiàng)”必須插入在索引的合適位置上。因此，最好在建索引表時(shí)留有一定“空位”；３．刪除記錄時(shí)，僅需刪除索引表中相應(yīng)的索引項(xiàng)即可；４．更新記錄時(shí)，應(yīng)將更新后的記錄插入在主文件的末尾，同時(shí)修改相應(yīng)的索引項(xiàng)。１．多級(jí)靜態(tài)索引２．動(dòng)態(tài)索引１．多級(jí)靜態(tài)索引主

文

件第三查找表…

...第二查找表…

...查

找

表…

...索

引

表…

...此時(shí)的索引文件結(jié)構(gòu)：對(duì)主文件中每個(gè)記錄建立一個(gè)索引項(xiàng)：主關(guān)鍵字

記錄在主文件中的存儲(chǔ)位置稱作稠密索引，由這些索引項(xiàng)構(gòu)成索引表。從索引表建立的索引稱查找表，其中每個(gè)索引項(xiàng)為：最大關(guān)鍵字其所在數(shù)據(jù)塊的存儲(chǔ)位置稱這類索引為非稠密索引。類似地，由查找表建立的索引為第二

查找表；由第二查找表建立的索引為第三查找表。優(yōu)點(diǎn)：不需要建立多級(jí)索引；初建索引不需要進(jìn)行排序；插入或刪除記錄時(shí)，修改索引方便。２．動(dòng)態(tài)索引索引表采用查找樹表或哈希表。用查找樹表作索引時(shí)，查找索引所需訪問外存次數(shù)的最大值恰為查找樹的深度?？梢宰魉饕臉浔碛校憾媾判驑洹-樹和鍵樹。稠密索引的優(yōu)點(diǎn)是，可以實(shí)現(xiàn)“預(yù)查找”缺點(diǎn)是，索引表占用的存儲(chǔ)空間大。13.4

索引順序文件主文件按主關(guān)鍵字有序，對(duì)一組記錄建立一個(gè)索引項(xiàng)(建立非稠密索引)。結(jié)構(gòu)特點(diǎn)：有兩種典型的索引順序文件：一、ISAM文件ISAM(Index

Sequential

AccessMethod)(索引順序存取方法)是一種專為磁盤存取設(shè)計(jì)的文件組織方法。關(guān)鍵字指針關(guān)鍵字指針１．文件的組織方式：主文件按柱面集中存放，同時(shí)建立三級(jí)索引：磁道索引、柱面索引和主索引。磁道索引結(jié)構(gòu)基本索引項(xiàng)溢出索引項(xiàng)2101024主索引磁道索引r(14)

r(21)

r(38)r(41)

r(57)

r(63)r(72)

r(85)

r(99)溢出區(qū)磁道索引r(514) …………

r(1024)溢出區(qū)—個(gè)柱面….柱面索引992101024T0T1T2T3T4T5２．操作的特點(diǎn)：檢索插入刪除檢索：可有兩種方式：順序存取—依關(guān)鍵字由小至大順序存取。按關(guān)鍵字存取—從主索引開始,到柱面索引，到磁道索引，最后取得記錄，先后訪問四次外存。插入:將記錄插入在某個(gè)磁道的合適位置上;將該磁道上關(guān)鍵字最大的記錄移出到本柱面的溢出區(qū)中;修改本磁道的索引項(xiàng)(包括基本索引項(xiàng)和溢出索引項(xiàng))。刪除:在被刪記錄當(dāng)前存儲(chǔ)位置上作“刪除標(biāo)記”。３．文件重組在經(jīng)過多次的插入和刪除操作之后，大量的記錄進(jìn)入文件的“溢出區(qū)”而“基本存儲(chǔ)區(qū)”中出現(xiàn)很多已被刪去的記錄空間，此時(shí)的文件結(jié)構(gòu)很不合理。因此，對(duì)ISAM文件， 需要周期地進(jìn)行重整。４．柱面索引的位置ISAM文件占有多個(gè)柱面，其柱面索引本身占有一個(gè)柱面，為使

“磁頭”的平均移動(dòng)距離最小，柱面索引應(yīng)設(shè)在數(shù)據(jù)文件所占全部柱面的中間位置上。二、VSAM文件VSAM(Vistual

Storage

Access

Method)文件是利用操作系統(tǒng)中提供的虛擬

存儲(chǔ)器的功能組織的文件，免除了

用戶為讀/寫記錄時(shí)直接對(duì)外存進(jìn)行的操作，對(duì)用戶而言，文件只有控

制區(qū)間和控制區(qū)域等邏輯存儲(chǔ)單位?！?/p>

............索引集B+樹順序集控制區(qū)域控制區(qū)間數(shù)據(jù)集1．文件的結(jié)構(gòu)2.

控制區(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+樹的葉子結(jié)點(diǎn)，索引集中的結(jié)點(diǎn)即為B+樹的非葉結(jié)點(diǎn)。４．文件的操作檢索：可進(jìn)行順序存取和按關(guān)鍵字存??；插入：按關(guān)鍵字大小插入在某個(gè)適當(dāng)?shù)目刂茀^(qū)間中，當(dāng)控制區(qū)間中的記錄數(shù)超過文件規(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.5

直接存取文件１．和前幾節(jié)討論的文件組織方法

不同，直接存取文件的特點(diǎn)是，由

記錄的關(guān)鍵字“直接”得到記錄在外存上的映象地址。類似于哈希表的構(gòu)造方法，根據(jù)文件中關(guān)鍵字的特點(diǎn)設(shè)計(jì)一種“哈希函數(shù)”和“處理沖突的方法”將記錄散列到外存儲(chǔ)設(shè)備上，又稱“散列文件”。２．哈希文件的結(jié)構(gòu)由于記錄在外存上是成組存放的，因此允許多個(gè)記錄映象到同一個(gè)地址

上。在此，稱外存儲(chǔ)器中存放多個(gè)記

錄的“數(shù)據(jù)塊”為“桶”。因此由哈希數(shù)得到的映象地址為“桶地址”。例如：有一組關(guān)鍵字如下所列{589，063，269，505，764，182，166，330}假設(shè)哈希函數(shù)為keyMOD

7，每個(gè)桶可以容納

3個(gè)記錄（稱桶的容量為3），則哈希文件如下:基桶063

182589505

764269166330溢出桶在哈希文件中，“沖突”和“溢出是不同的概念。一般情況下，假設(shè)桶

的大小為m，則允許哈希地址產(chǎn)生m-1次的沖突，當(dāng)發(fā)生第m次沖突時(shí)，才

需要進(jìn)行“沖突處理”，對(duì)散列文件而言，通常采用鏈地址法處理沖突。為

區(qū)別起見，稱直接“散列”的數(shù)據(jù)塊為

“基桶”，而因“溢出”存放的數(shù)據(jù)塊

“溢出桶”。３．文件的操作檢索：只能進(jìn)行按關(guān)鍵字的查找，不能進(jìn)行順序查找。檢索時(shí)，先在基桶內(nèi)進(jìn)行查找，若不存在，則再到溢出桶中進(jìn)行查找；插入：當(dāng)查找不成功時(shí)，將記錄插入在相應(yīng)的基桶或溢出桶內(nèi)；刪除：對(duì)被刪記錄作特殊標(biāo)記。４．優(yōu)點(diǎn)：記錄隨機(jī)存放，不需要進(jìn)行排序；插入、刪除方便，存取速度快；節(jié)省存儲(chǔ)空間，不需要索引區(qū)。缺點(diǎn)：不能進(jìn)行順序存取；在經(jīng)過多次插入和刪除操作之后，需進(jìn)行“重組文件”的操作。13.6

多關(guān)鍵字文件一、多關(guān)鍵字文件的特點(diǎn)除需要對(duì)主關(guān)鍵字建立“主索引”外，尚需對(duì)各個(gè)次關(guān)鍵字建立“次索引”次索引項(xiàng)：次關(guān)鍵字（指向記錄的）指針二、次索引的組織方法1．多重鏈表文件特點(diǎn)：將所有具有相同次關(guān)鍵字的記錄鏈接在同一鏈表中，該鏈表的頭指針即為次索