大學(xué)考試數(shù)據(jù)結(jié)構(gòu)chap12文件

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

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

3、式。五、文件的操作：五、文件的操作：檢檢 索索 修修 改改排排 序序 1檢索檢索順序存取順序存取：存取“當(dāng)前記錄的”下一個(gè)記錄；直接存取直接存?。捍嫒〉趇個(gè)記錄；按關(guān)鍵字存取按關(guān)鍵字存?。捍嫒∑潢P(guān)鍵字等于給定值的記錄。2修改修改往文件中插入插入一個(gè)或一批記錄；更新更新文件中某個(gè)記錄的屬性。從文件中刪除刪除一個(gè)或一批記錄；文件的操作方式可以實(shí)時(shí)處理實(shí)時(shí)處理或批量處理。批量處理。3排序排序 本章討論文件的幾種常見的物理結(jié)構(gòu)：順序文件順序文件索引文件索引文件索引順序文件索引順序文件直接存取文件直接存取文件多關(guān)鍵字文件多關(guān)鍵字文件結(jié)結(jié) 構(gòu)構(gòu) 特特 點(diǎn)：點(diǎn)： 記錄在文件中的排列順序是由記錄進(jìn)入存儲(chǔ)介質(zhì)的

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

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

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

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

8、的存儲(chǔ)位置稱這類索引為非稠密索引。類似地，由查找表建立的索引為第二查找表；由第二查找表建立的索引為第三查找表。按關(guān)鍵字進(jìn)行檢索時(shí)，從第三查找表開始，至多訪問外存五次。索索引表采用查找樹表或哈希表。優(yōu)點(diǎn)優(yōu)點(diǎn)： 1）不需要建立多級(jí)索引； 2）初建索引不需要進(jìn)行排序； 3）插入或刪除記錄時(shí)，修改索引方便。動(dòng)態(tài)索引動(dòng)態(tài)索引用查找樹表作索引時(shí)，查找索引所需訪問外存次數(shù)的最大值恰為查找樹的深度。 稠密索引的優(yōu)點(diǎn)是，可以實(shí)現(xiàn)“預(yù)查找” 缺點(diǎn)是，索引表占用的存儲(chǔ)空間大。可以作索引的樹表有：二叉排序樹、B-樹和鍵樹。主文件按主關(guān)鍵字有序，對(duì)一組記錄建立一個(gè)索引項(xiàng)(建立非稠密索引)。結(jié)構(gòu)特點(diǎn)：結(jié)構(gòu)特點(diǎn)：12.4

9、索索 引引 順順 序序 文文 件件一、一、ISAM文件文件ISAM(Index Sequential Access Method)(索引順序存取方法)是一種專為磁盤存取設(shè)計(jì)的文件組織方法。有兩種典型的索引順序文件：文件的組織方式文件的組織方式： 主文件按柱面集中存放，同時(shí)建立 三級(jí)索引：磁道索引、柱面索引和 主索引。 關(guān)鍵字 指針 關(guān)鍵字 指針 磁道索引結(jié)構(gòu)磁道索引結(jié)構(gòu)基本索引項(xiàng)基本索引項(xiàng)溢出索引項(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) 溢 出 區(qū)

10、 磁道索引 r(1024)一一 個(gè)個(gè) 柱柱 面面 .柱柱面面索索引引992101024T0T1T2T3T4T5檢索：檢索： 可有兩種方式：按關(guān)鍵字存取 從主索引開始,到 柱面索引，到磁道索引，最后取 得記錄，先后訪問四次外存。順序存取 依關(guān)鍵字最小至大順序 存取。操作的特點(diǎn)：操作的特點(diǎn)：檢檢 索索 插入插入刪除刪除插入插入: :修改本磁道的索引項(xiàng)(包括基本索 引項(xiàng)和溢出索引項(xiàng))。將該磁道上關(guān)鍵字最大的記錄移出到本柱面的溢出區(qū)中; 將記錄插入在某個(gè)磁道的合適位置上;刪除刪除: :在被刪記錄當(dāng)前存儲(chǔ)位置上 作“刪除標(biāo)記”。文件重組文件重組 在經(jīng)過多次的插入和刪除操作之后，大量的記錄進(jìn)入文件的“溢出

11、區(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ǔ)單位。 . 索引集索引集B+樹樹 順序集順序集控制區(qū)域控制區(qū)間數(shù)據(jù)集數(shù)據(jù)

12、集1 1文件的結(jié)構(gòu)文件的結(jié)構(gòu) 2. 控制區(qū)間控制區(qū)間是用戶進(jìn)行一次存取的邏輯單位，可看成是一個(gè)邏輯磁道。但它的實(shí)際大小和物理磁道無關(guān)。 VSAM文件初建時(shí)，每個(gè)控制區(qū)間內(nèi)的記錄數(shù)不足額定數(shù)，并且有的控制區(qū)間內(nèi)的記錄數(shù)為零。 控制區(qū)域控制區(qū)域由若干控制區(qū)間和它們的索引項(xiàng)組成，可看成是一個(gè)邏輯柱面。順序集順序集本身是一個(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í)，要“分

13、裂”控制區(qū)間，必要時(shí)，還需要“分裂”控制區(qū)域；刪除：刪除：必須“真實(shí)地”刪除記錄，因此要在控制區(qū)間內(nèi)“移動(dòng)”記錄。VSAM文件文件通常被作為大型索引順序文件的標(biāo)準(zhǔn)組織方式。其缺點(diǎn)是缺點(diǎn)是：占有較多的存儲(chǔ)空間，一般只 能保持約75%的存儲(chǔ)空間利用 率。(因此，一般情況下，極少 產(chǎn)生需要分裂控制區(qū)域的情況)其優(yōu)點(diǎn)是優(yōu)點(diǎn)是：動(dòng)態(tài)地分配和釋放空間, 不需 要重組文件；能較快地實(shí)現(xiàn)對(duì) “后插入”的記錄的檢索；和前幾節(jié)討論的文件組織方法不同，直接存取文件的特點(diǎn)直接存取文件的特點(diǎn)是，由記錄的關(guān)鍵字“直接直接”得到得到記錄在外存上的映象地址映象地址。 類似于哈希表的構(gòu)造方法，根據(jù)文件中關(guān)鍵字的特點(diǎn)設(shè)計(jì)一種“哈

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

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