沒有幻燈片標(biāo)題 - 重慶三峽學(xué)院

1、第十二章第十二章 文文 件件 12.1 有關(guān)文件的基本概念有關(guān)文件的基本概念12.2 順順 序序 文文 件件12.3 索索 引引 文文 件件12.4 索索 引引 順順 序序 文文 件件12.5 直直 接接 存存 取取 文文 件件12.6 多多 關(guān)關(guān) 鍵鍵 字字 文文 件件12.1 有關(guān)文件的基本概念有關(guān)文件的基本概念一、文件一、文件即為記錄的集合為記錄的集合，和“查找 表”的差別在于，“文件”指的是存 儲在外存儲器中的記錄的集合。 記錄是文件中可以存取的數(shù)據(jù)數(shù)據(jù)的 基本單位基本單位。二、文件二、文件可按其中記錄的類型不同而 分成兩類兩類：其一為操作系統(tǒng)的文件，文件中的記 錄僅是一個字符組。由于

2、操作系 統(tǒng)中的文件僅是一維的連續(xù)字符 序列，為了用戶存取和加工的方 便，將文件中的信息劃分為若干 組，其中每一組信息稱作一個記 錄；其二為數(shù)據(jù)庫文件，文件中的記錄帶 有結(jié)構(gòu)，是數(shù)據(jù)項的集合。記錄 是文件中可以存取的數(shù)據(jù)基本單 位，數(shù)據(jù)項是文件中可以使用的 數(shù)據(jù)最小單位。數(shù)據(jù)最小單位。三、三、記錄中能識別不同記錄的數(shù)據(jù)項 被稱為關(guān)鍵字關(guān)鍵字，若該數(shù)據(jù)項能唯 一識別一個記錄，則稱為主關(guān)鍵主關(guān)鍵 字字，若能識別多個記錄則稱為次次 關(guān)鍵字關(guān)鍵字。四、文件的邏輯結(jié)構(gòu)四、文件的邏輯結(jié)構(gòu)指的是呈現(xiàn)在用 戶面前的文件中記錄之間的邏輯 關(guān)系；文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)指的是文 件中的邏輯記錄在存儲器中的組 織

3、方式。五、文件的操作：五、文件的操作：檢檢 索索修修 改改排排 序序 1檢索檢索 順序存取順序存?。捍嫒　爱?dāng)前記錄的”下一個記錄； 直接存取直接存?。捍嫒〉趇個記錄； 按關(guān)鍵字存取按關(guān)鍵字存取：存取其關(guān)鍵字等于給定值的記錄。2修改修改往文件中插入插入一個或一批記錄；更新更新文件中某個記錄的屬性。從文件中刪除刪除一個或一批記錄；文件的操作方式可以實時處理實時處理或批量處理。批量處理。3排序排序 本章討論文件的幾種常見的物理結(jié)構(gòu)：順序文件順序文件索引文件索引文件索引順序文件索引順序文件直接存取文件直接存取文件多關(guān)鍵字文件多關(guān)鍵字文件12.2 順順 序序 文文 件件結(jié)結(jié) 構(gòu)構(gòu) 特特 點：點： 記錄在

4、文件中的排列順序是由記錄進(jìn)入存儲介質(zhì)的次序決定的， 即文件物理結(jié)構(gòu)中記錄物理結(jié)構(gòu)中記錄的排列順序排列順序和文件的邏輯結(jié)構(gòu)中記錄邏輯結(jié)構(gòu)中記錄的排列順序排列順序一致。順序文件的具體組織形式有兩種：串聯(lián)文件串聯(lián)文件：物理記錄之間的順序由指 針相鏈。連續(xù)文件連續(xù)文件：次序相繼的兩個物理記錄 其存儲位置相鄰;操作特點操作特點： 1便于便于進(jìn)行順序存??； 2不便于不便于進(jìn)行直接存取，為取第i個記錄，必須先讀出前i-1個記錄，對于磁盤上的等長記錄的連續(xù)文件可以進(jìn)行折半查找；3插入新的記錄只能只能加在文件的末尾；4刪除記錄時，只作標(biāo)記只作標(biāo)記；5更新記錄必須生成新的文生成新的文件件。 順序文件的插入、刪除和

5、更新操作在多數(shù)情況下都采用批處理方式批處理方式。此時，為處理方便，通常將順序文件作成有序文件，稱作“主文件”，同時將所有的操作作成一個“事務(wù)文件”（經(jīng)過排序也成為有序文件），所謂“批處理”，就是將這兩個文件“合”為一個新的主文件。具體操作相當(dāng)于“歸并兩個有序表”。（1）對于事務(wù)文件中的每個操作 首先要判別其“合法性”（2）事務(wù)文件中可能存在多個操 作是對主文件中同一個記錄 進(jìn)行的但有兩點不同：但有兩點不同： 假設(shè)主文件中含有n個記錄，事務(wù)文件中含有m個記錄，則對事務(wù)文件進(jìn)行排序的時間復(fù)雜度為O(mlogm），內(nèi)部歸并的時間復(fù)雜度為O(m+n），則總的內(nèi)部處理的時間為O(mlogm+n）。 批處

6、理的時間分析批處理的時間分析： 假設(shè)對外存進(jìn)行一次讀/取為s個記錄，則整個批處理過程中讀/寫外存的次數(shù)為2（m/s+(m+n)/s） （其中s為對外存進(jìn)行一次讀/取的記錄 數(shù)）。12.3 12.3 索索 引引 文文 件件一、結(jié)構(gòu)特點：一、結(jié)構(gòu)特點： 1索引文件由“主文件”和多級“索引”組成； 2索引中的每個記錄由“關(guān)鍵字”和“指針”組成； 3通常，索引文件中的主文件是無序文件，索引是 (按關(guān)鍵字有序)的有序文件； 4“索引”是在輸入數(shù)據(jù)建立文件時自動生成。初建時的“靜態(tài)索引”為無序文件，經(jīng)過排序后成為有序文件。二、操作的特點：二、操作的特點： 檢索方式為：直接存取和按關(guān)鍵字存取?！鞍搓P(guān)鍵字檢索

7、”將分兩步進(jìn)行：先查索引，然后根據(jù)索引中指針?biāo)杆魅∮涗洠?插入記錄時，“記錄”插入在主文件的末尾，而相應(yīng)的“索引項”必須插入在索引的合適位置上。因此，最好在建索引表時留有一定“空位”； 刪除記錄時，僅需刪除索引表中相應(yīng)的索引項即可； 更新記錄時，應(yīng)將更新后的記錄插入在主文件的末尾，同時修改相應(yīng)的索引項。多多 級級 靜靜 態(tài)態(tài) 索索 引引動動 態(tài)態(tài) 索索 引引多級靜態(tài)索引多級靜態(tài)索引 主 文 件 索 引 表 查 找 表 第 二 查 找表 第三查找表 . . . . 此時的索引文件結(jié)構(gòu)：對主文件中每個記錄每個記錄建立一個索引項索引項： 主關(guān)鍵字 記錄在主文件中的存儲位置稱作稠密索引，由這些索引項

8、構(gòu)成索引表。從索引表建立的索引稱查找表，其中每個索引項為： 最大關(guān)鍵字 其所在數(shù)據(jù)塊的存儲位置稱這類索引為非稠密索引。類似地，由查找表建立的索引為第二查找表；由第二查找表建立的索引為第三查找表。按關(guān)鍵字進(jìn)行檢索時，從第三查找表開始，至多訪問外存五次。索索引表采用查找樹表或哈希表。優(yōu)點優(yōu)點： 1）不需要建立多級索引； 2）初建索引不需要進(jìn)行排序； 3）插入或刪除記錄時，修改索引方便。動態(tài)索引動態(tài)索引用查找樹表作索引時，查找索引所需訪問外存次數(shù)的最大值恰為查找樹的深度。 稠密索引的優(yōu)點是，可以實現(xiàn)“預(yù)查找” 缺點是，索引表占用的存儲空間大?？梢宰魉饕臉浔碛校憾媾判驑?、B-樹和鍵樹。12.4 索

9、索 引引 順順 序序 文文 件件主文件按主關(guān)鍵字有序，對一組記錄建立一個索引項(建立非稠密索引)。結(jié)構(gòu)特點：結(jié)構(gòu)特點：一、一、ISAM文件文件ISAM(Index Sequential Access Method)(索引順序存取方法)是一種專為磁盤存取設(shè)計的文件組織方法。有兩種典型的索引順序文件：文件的組織方式文件的組織方式： 主文件按柱面集中存放，同時建立 三級索引：磁道索引、柱面索引和 主索引。 關(guān)鍵字 指針 關(guān)鍵字 指針 磁道索引結(jié)構(gòu)磁道索引結(jié)構(gòu)基本索引項基本索引項溢出索引項溢出索引項2101024主主索索引引 r(14) r(21) r(38) r(41) r(57) r(63) r(

10、72) r(85) r(99) 溢 出 區(qū) 磁 道 索 引 r(514) 溢 出 區(qū) 磁道索引 r(1024)一一 個個 柱柱 面面 .柱柱面面索索引引992101024T0T1T2T3T4T5操作的特點：操作的特點：檢檢 索索插入插入刪除刪除檢索：檢索： 可有兩種方式： 按關(guān)鍵字存取 從主索引開始,到 柱面索引，到磁道索引，最后取 得記錄，先后訪問四次外存。順序存取 依關(guān)鍵字最小至大順序 存取。插入插入: : 修改本磁道的索引項(包括基本索 引項和溢出索引項)。將該磁道上關(guān)鍵字最大的記錄移出 到本柱面的溢出區(qū)中; 將記錄插入在某個磁道的合適位置上;刪除刪除: :在被刪記錄當(dāng)前存儲位置上 作“

11、刪除標(biāo)記”。文件重組文件重組 在經(jīng)過多次的插入和刪除操作之后，大量的記錄進(jìn)入文件的“溢出區(qū)”，而“基本存儲區(qū)”中出現(xiàn)很多已被刪去的記錄空間，此時的文件結(jié)構(gòu)很不合理。因此，對ISAM文件， 需要周期地進(jìn)行重整。柱面索引的位置柱面索引的位置 ISAM文件占有多個柱面，其柱面索引本身占有一個柱面，為使“磁頭”的平均移動距離最小，柱面索引應(yīng)設(shè)在數(shù)據(jù)文件所占全部柱面的中間位置上。二、二、VSAM文件文件VSAM(Vistual Storage Access Method) 文件是利用操作系統(tǒng)中提供的虛擬存儲器的功能組織的文件，免除了用戶為讀/寫記錄時直接對外存進(jìn)行的操作，對用戶而言，文件只有控制區(qū)間和控

12、制區(qū)域等邏輯存儲單位。 . 索引集索引集B+樹樹 順序集順序集控制區(qū)域控制區(qū)間數(shù)據(jù)集數(shù)據(jù)集1 1文件的結(jié)構(gòu)文件的結(jié)構(gòu) 2. 控制區(qū)間控制區(qū)間是用戶進(jìn)行一次存取的邏輯單位，可看成是一個邏輯磁道。但它的實際大小和物理磁道無關(guān)。 VSAM文件初建時，每個控制區(qū)間內(nèi)的記錄數(shù)不足額定數(shù)，并且有的控制區(qū)間內(nèi)的記錄數(shù)為零。 控制區(qū)域控制區(qū)域由若干控制區(qū)間和它們的索引項組成，可看成是一個邏輯柱面。順序集順序集本身是一個單鏈表，它包含文件的全部索引項，同時，順序集中的每個結(jié)點即為B+樹的葉子結(jié)點，索引集索引集中的結(jié)點即為B+樹的非葉結(jié)點。文件的操作文件的操作 檢索：檢索：可進(jìn)行順序存取和按關(guān)鍵字存取； 插入：插

13、入：按關(guān)鍵字大小插入在某個適當(dāng)?shù)目刂茀^(qū)間中，當(dāng)控制區(qū)間中的記錄數(shù)超過文件規(guī)定的大小時，要“分裂”控制區(qū)間，必要時，還需要“分裂”控制區(qū)域； 刪除：刪除：必須“真實地”刪除記錄，因此要在控制區(qū)間內(nèi)“移動”記錄。VSAM文件文件通常被作為大型索引順序文件的標(biāo)準(zhǔn)組織方式。其缺點是缺點是：占有較多的存儲空間，一般只 能保持約75%的存儲空間利用 率。(因此，一般情況下，極少 產(chǎn)生需要分裂控制區(qū)域的情況)其優(yōu)點是優(yōu)點是：動態(tài)地分配和釋放空間, 不需 要重組文件；能較快地實現(xiàn)對 “后插入”的記錄的檢索；12.5 直直 接接 存存 取取 文文 件件和前幾節(jié)討論的文件組織方法不同，直接存取文件的特點直接存取文

14、件的特點是，由記錄的關(guān)鍵字“直接直接”得到得到記錄在外存上的映象地址映象地址。 類似于哈希表的構(gòu)造方法，根據(jù)文件中關(guān)鍵字的特點設(shè)計一種“哈希函數(shù)”和“處理沖突的方法”將記錄散列到外存儲設(shè)備上，又稱“散列文件”。哈希文件的結(jié)構(gòu)哈希文件的結(jié)構(gòu) 由于記錄在外存上是成組存放的，因此允許多個記錄映象到同一個地址上。在此，稱外存儲器中存放多個記錄的“數(shù)據(jù)塊”為“桶”。 因此由哈希函數(shù)得到的映象地址為“桶地址”。例如：有一組關(guān)鍵字如下所列 589，063，269，505，764，182，166，330假設(shè)哈希函數(shù)為 key MOD 7，每個桶可以容納3個記錄（稱桶的容量為3），則哈希文件如下:基桶063 1

15、82589 505 764269166330溢出桶 在哈希文件中，“沖突沖突”和和“溢出溢出”是不同的概念是不同的概念。一般情況下，假設(shè)桶的大小為m，則允許哈希地址產(chǎn)生m-1次的沖突，當(dāng)發(fā)生第m次沖突時，才需要進(jìn)行“沖突處理”，對散列文件而言，通常采用鏈地址法出路沖突。為區(qū)別起見，稱直接“散列”的數(shù)據(jù)塊為“基桶基桶”，而因“溢出”存放的數(shù)據(jù)塊為“溢出桶溢出桶”。文件的操作文件的操作 檢索檢索：只能進(jìn)行按關(guān)鍵字的查找，不能進(jìn)行順序查找。檢索時，先在基桶內(nèi)進(jìn)行查找，若不存在，則再到溢出桶中進(jìn)行查找； 插入插入：當(dāng)查找不成功時，將記錄插入在相應(yīng)的基桶或溢出桶內(nèi)； 刪除刪除：對被刪記錄作特殊標(biāo)記。優(yōu)點

16、：優(yōu)點：記錄隨機(jī)存放，不需要進(jìn)行排 序；插入、刪除方便，存取速 度快；節(jié)省存儲空間，不需要 索引區(qū)。缺點：缺點：不能進(jìn)行順序存??；在經(jīng)過多 次插入和刪除操作之后，需進(jìn) 行“重組文件”的操作。12.6 多多 關(guān)關(guān) 鍵鍵 字字 文文 件件一、多關(guān)鍵字文件的特點一、多關(guān)鍵字文件的特點 除需要對主關(guān)鍵字建立“主索引”外， 尚需對各個次關(guān)鍵字建立“次索引”。次索引項：次索引項： 次關(guān)鍵字次關(guān)鍵字 （指向記錄的）指針（指向記錄的）指針二、次索引的組織方法二、次索引的組織方法 1多重鏈表文件多重鏈表文件特點：將所有具有相同次關(guān)鍵字的具有相同次關(guān)鍵字的記錄鏈接在同一鏈表中記錄鏈接在同一鏈表中，該鏈表的頭指針即為次索引項中“指針域”的值； 2倒排文件倒排文件