第12章文件12/13/20221數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第1頁!12.1有關(guān)文件的基本概念12.2順序文件12.3索引文件12.4索引順序文件12.5直接存取文件12.6多關(guān)鍵字文件12/13/20222數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第2頁!一、文件即為記錄的集合，和“查找表”的差別在于，“文件”指的是存儲在外存儲器中的記錄的集合。

記錄是文件中可以存取的數(shù)據(jù)的

基本單位。12.1有關(guān)文件的基本概念12/13/20223數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第3頁!其二為數(shù)據(jù)庫文件，文件中的記錄帶有結(jié)構(gòu)，是數(shù)據(jù)項(xiàng)的集合。記錄是文件中可以存取的數(shù)據(jù)基本單位，數(shù)據(jù)項(xiàng)是文件中可以使用的

數(shù)據(jù)最小單位。12/13/20224數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第4頁!四、文件的邏輯結(jié)構(gòu)指的是呈現(xiàn)在用戶面前的文件中記錄之間的邏輯關(guān)系；文件的物理結(jié)構(gòu)指的是文件中的邏輯記錄在存儲器中的組織方式。12/13/20225數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第5頁!2．修改往文件中插入一個或一批記錄；更新文件中某個記錄的屬性。從文件中刪除一個或一批記錄；12/13/20226數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第6頁!本章討論文件的幾種常見的物理結(jié)構(gòu)：順序文件索引文件索引順序文件直接存取文件多關(guān)鍵字文件12/13/20227數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第7頁!順序文件的具體組織形式有兩種：串聯(lián)文件：物理記錄之間的順序由指針相鏈。連續(xù)文件：次序相繼的兩個物理記錄其存儲位置相鄰;12/13/20228數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第8頁!3．插入新的記錄只能加在文件的末尾；4．刪除記錄時，只作標(biāo)記；5．更新記錄必須生成新的文件。12/13/20229數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第9頁!（1）對于事務(wù)文件中的每個操作

首先要判別其“合法性”（2）事務(wù)文件中可能存在多個操作是對主文件中同一個記錄

進(jìn)行的但有兩點(diǎn)不同：12/13/202210數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第10頁!假設(shè)對外存進(jìn)行一次讀/取為s個記錄，則整個批處理過程中讀/寫外存的次數(shù)為2（m/s+(m+n)/s）（其中s為對外存進(jìn)行一次讀/取的記錄數(shù)）。12/13/202211數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第11頁!二、操作的特點(diǎn)：１．檢索方式為：直接存取和按關(guān)鍵字存取?！鞍搓P(guān)鍵字檢索”將分兩步進(jìn)行：先查索引，然后根據(jù)索引中指針?biāo)杆魅∮涗?；２．插入記錄時，“記錄”插入在主文件的末尾，而相應(yīng)的“索引項(xiàng)”必須插入在索引的合適位置上。因此，最好在建索引表時留有一定“空位”；12/13/202212數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第12頁!１．多級靜態(tài)索引２．動態(tài)索引12/13/202213數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第13頁!對主文件中每個記錄建立一個索引項(xiàng)：

主關(guān)鍵字

記錄在主文件中的存儲位置稱作稠密索引，由這些索引項(xiàng)構(gòu)成索引表。12/13/202214數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第14頁!索引表采用查找樹表或哈希表。

優(yōu)點(diǎn)：1）不需要建立多級索引；2）初建索引不需要進(jìn)行排序；3）插入或刪除記錄時，修改索引方便。２．動態(tài)索引12/13/202215數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第15頁!主文件按主關(guān)鍵字有序，對一組記錄建立一個索引項(xiàng)(建立非稠密索引)。結(jié)構(gòu)特點(diǎn)：12.4索引順序文件12/13/202216數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第16頁!１．文件的組織方式：

主文件按柱面集中存放，同時建立三級索引：磁道索引、柱面索引和主索引。關(guān)鍵字

指針

關(guān)鍵字

指針

磁道索引結(jié)構(gòu)基本索引項(xiàng)溢出索引項(xiàng)12/13/202217數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第17頁!檢索：

可有兩種方式：按關(guān)鍵字存取—從主索引開始,到柱面索引，到磁道索引，最后取得記錄，先后訪問四次外存。順序存取—依關(guān)鍵字最小至大順序存取。２．操作的特點(diǎn)：12/13/202218數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第18頁!刪除:在被刪記錄當(dāng)前存儲位置上作“刪除標(biāo)記”。12/13/202219數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第19頁!４．柱面索引的位置ISAM文件占有多個柱面，其柱面索引本身占有一個柱面，為使“磁頭”的平均移動距離最小，柱面索引應(yīng)設(shè)在數(shù)據(jù)文件所占全部柱面的中間位置上。12/13/202220數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第20頁!…............

索引集B+樹順序集控制區(qū)域控制區(qū)間數(shù)據(jù)集1．文件的結(jié)構(gòu)12/13/202221數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第21頁!３．順序集本身是一個單鏈表，它包含文件的全部索引項(xiàng)，同時，順序集中的每個結(jié)點(diǎn)即為B+樹的葉子結(jié)點(diǎn)，索引集中的結(jié)點(diǎn)即為B+樹的非葉結(jié)點(diǎn)。12/13/202222數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第22頁!５．VSAM文件通常被作為大型索引順序文件的標(biāo)準(zhǔn)組織方式。其缺點(diǎn)是：占有較多的存儲空間，一般只能保持約75%的存儲空間利用率。(因此，一般情況下，極少產(chǎn)生需要分裂控制區(qū)域的情況)其優(yōu)點(diǎn)是：動態(tài)地分配和釋放空間,不需要重組文件；能較快地實(shí)現(xiàn)對“后插入”的記錄的檢索；12/13/202223數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第23頁!２．哈希文件的結(jié)構(gòu)

由于記錄在外存上是成組存放的，因此允許多個記錄映象到同一個地址上。在此，稱外存儲器中存放多個記錄的“數(shù)據(jù)塊”為“桶”。因此由哈希函數(shù)得到的映象地址為“桶地址”。12/13/202224數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第24頁!在哈希文件中，“沖突”和“溢出”是不同的概念。一般情況下，假設(shè)桶的大小為m，則允許哈希地址產(chǎn)生m-1次的沖突，當(dāng)發(fā)生第m次沖突時，才需要進(jìn)行“沖突處理”，對散列文件而言，通常采用鏈地址法出路沖突。為區(qū)別起見，稱直接“散列”的數(shù)據(jù)塊為“基桶”，而因“溢出”存放的數(shù)據(jù)塊為“溢出桶”。12/13/202225數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第25頁!４．優(yōu)點(diǎn)：記錄隨機(jī)存放，不需要進(jìn)行排序；插入、刪除方便，存取速度快；節(jié)省存儲空間，不需要索引區(qū)。缺點(diǎn)：不能進(jìn)行順序存??；在經(jīng)過多次插入和刪除操作之后，需進(jìn)行“重組文件”的操作。12/13/202226數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第26頁!二、次索引的組織方法1．多重鏈表文件

特點(diǎn)：將所有具有相同次關(guān)鍵字的記錄鏈接在同一鏈表中，該鏈表的頭指針即為次索引項(xiàng)中“指針域”的值；12/13/202227數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第27頁!3．次關(guān)鍵字索引表本身的結(jié)構(gòu)可以是順序表，也可以是樹表或哈希表，視具體的次關(guān)鍵字的特性而定。12/13/202228數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第28頁!二、文件可按其中記錄的類型不同而分成兩類：其一為操作系統(tǒng)的文件，文件中的記錄僅是一個字符組。由于操作系統(tǒng)中的文件僅是一維的連續(xù)字符序列，為了用戶存取和加工的方便，將文件中的信息劃分為若干組，其中每一組信息稱作一個記錄；12/13/202229數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第29頁!三、記錄中能識別不同記錄的數(shù)據(jù)項(xiàng)被稱為關(guān)鍵字，若該數(shù)據(jù)項(xiàng)能唯一識別一個記錄，則稱為主關(guān)鍵字，若能識別多個記錄則稱為次關(guān)鍵字。12/13/202230數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第30頁!1．檢索順序存?。捍嫒　爱?dāng)前記錄的”下一個記錄；直接存?。捍嫒〉趇個記錄；按關(guān)鍵字存?。捍嫒∑潢P(guān)鍵字等于給定值的記錄。五、文件的操作：12/13/202231數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第31頁!文件的操作方式可以實(shí)時處理或批量處理。3．排序12/13/202232數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第32頁!結(jié)構(gòu)特點(diǎn)：記錄在文件中的排列順序是由記錄進(jìn)入存儲介質(zhì)的次序決定的，即文件物理結(jié)構(gòu)中記錄的排列順序和文件的邏輯結(jié)構(gòu)中記錄的排列順序一致。12.2順序文件12/13/202233數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第33頁!操作特點(diǎn)：1．便于進(jìn)行順序存??；2．不便于進(jìn)行直接存取，為取第i個記錄，必須先讀出前i-1個記錄，對于磁盤上的等長記錄的連續(xù)文件可以進(jìn)行折半查找；12/13/202234數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第34頁!

順序文件的插入、刪除和更新操作在多數(shù)情況下都采用批處理方式。此時，為處理方便，通常將順序文件作成有序文件，稱作“主文件”，同時將所有的操作作成一個“事務(wù)文件”（經(jīng)過排序也成為有序文件），所謂“批處理”，就是將這兩個文件“合”為一個新的主文件。具體操作相當(dāng)于“歸并兩個有序表”。12/13/202235數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第35頁!假設(shè)主文件中含有n個記錄，事務(wù)文件中含有m個記錄，則對事務(wù)文件進(jìn)行排序的時間復(fù)雜度為O(mlogm），內(nèi)部歸并的時間復(fù)雜度為O(m+n），則總的內(nèi)部處理的時間為O(mlogm+n）。

批處理的時間分析：12/13/202236數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第36頁!1．索引文件由“主文件”和多級“索引”組成；2．索引中的每個記錄由“關(guān)鍵字”和“指針”組成；3．通常，索引文件中的主文件是無序文件，索引是(按關(guān)鍵字有序)的有序文件；4．“索引”是在輸入數(shù)據(jù)建立文件時自動生成。初建時的“靜態(tài)索引”為無序文件，經(jīng)過排序后成為有序文件。一、結(jié)構(gòu)特點(diǎn)：12.3索引文件12/13/202237數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第37頁!３．刪除記錄時，僅需刪除索引表中相應(yīng)的索引項(xiàng)即可；４．更新記錄時，應(yīng)將更新后的記錄插入在主文件的末尾，同時修改相應(yīng)的索引項(xiàng)。12/13/202238數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第38頁!主文件

索引表

查找表

第二查找表

第三查找表…...…...…...…...

此時的索引文件結(jié)構(gòu)：１．多級靜態(tài)索引12/13/202239數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第39頁!從索引表建立的索引稱查找表，其中每個索引項(xiàng)為：

最大關(guān)鍵字

其所在數(shù)據(jù)塊的存儲位置稱這類索引為非稠密索引。類似地，由查找表建立的索引為第二查找表；由第二查找表建立的索引為第三查找表。按關(guān)鍵字進(jìn)行檢索時，從第三查找表開始，至多訪問外存五次。12/13/202240數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第40頁!用查找樹表作索引時，查找索引所需訪問外存次數(shù)的最大值恰為查找樹的深度。稠密索引的優(yōu)點(diǎn)是，可以實(shí)現(xiàn)“預(yù)查找”

缺點(diǎn)是，索引表占用的存儲空間大?？梢宰魉饕臉浔碛校憾媾判驑?、B-樹和鍵樹。12/13/202241數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第41頁!一、ISAM文件ISAM(IndexSequentialAccessMethod)(索引順序存取方法)是一種專為磁盤存取設(shè)計的文件組織方法。有兩種典型的索引順序文件：12/13/202242數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第42頁!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)一個柱面

….柱面索引992101024T0T1T2T3T4T512/13/202243數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第43頁!插入:

修改本磁道的索引項(xiàng)(包括基本索引項(xiàng)和溢出索引項(xiàng))。將該磁道上關(guān)鍵字最大的記錄移出到本柱面的溢出區(qū)中;將記錄插入在某個磁道的合適位置上;12/13/202244數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第44頁!３．文件重組在經(jīng)過多次的插入和刪除操作之后，大量的記錄進(jìn)入文件的“溢出區(qū)”，而“基本存儲區(qū)”中出現(xiàn)很多已被刪去的記錄空間，此時的文件結(jié)構(gòu)很不合理。因此，對ISAM文件，需要周期地進(jìn)行重整。12/13/202245數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第45頁!二、VSAM文件VSAM(VistualStorageAccessMethod)

文件是利用操作系統(tǒng)中提供的虛擬存儲器的功能組織的文件，免除了用戶為讀/寫記錄時直接對外存進(jìn)行的操作，對用戶而言，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲單位。12/13/202246數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第46頁!2.控制區(qū)間是用戶進(jìn)行一次存取的邏輯單位，可看成是一個邏輯磁道。但它的實(shí)際大小和物理磁道無關(guān)。VSAM文件初建時，每個控制區(qū)間內(nèi)的記錄數(shù)不足額定數(shù)，并且有的控制區(qū)間內(nèi)的記錄數(shù)為零?？刂茀^(qū)域由若干控制區(qū)間和它們的索引項(xiàng)組成，可看成是一個邏輯柱面。12/13/202247數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第47頁!４．文件的操作檢索：可進(jìn)行順序存取和按關(guān)鍵字存??；插入：按關(guān)鍵字大小插入在某個適當(dāng)?shù)目刂茀^(qū)間中，當(dāng)控制區(qū)間中的記錄數(shù)超過文件規(guī)定的大小時，要“分裂”控制區(qū)間，必要時，還需要“分裂”控制區(qū)域；刪除：必須“真實(shí)地”刪除記錄，因此要在控制區(qū)間內(nèi)“移動”記錄。12/13/202248數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十二章共54頁，您現(xiàn)在瀏覽的是第48頁!１．和前幾節(jié)討論的文件組織方法不同，直接存取文件的特點(diǎn)是，由記錄的關(guān)鍵字“直接”得到記錄在外存上的映象地址。類似于哈希表的構(gòu)造方法，根據(jù)文件中關(guān)鍵字的特點(diǎn)設(shè)計一種“哈