數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)嚴(yán)蔚敏清華大學(xué)出版社課件第十二章 ....ppt

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

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

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

4、中記錄的排列順序一致。,12.2 順序文件,2020/7/23,13,順序文件的具體組織形式有兩種：,串聯(lián)文件：物理記錄之間的順序由指 針相鏈。,連續(xù)文件：次序相繼的兩個(gè)物理記錄 其存儲(chǔ)位置相鄰;,2020/7/23,14,操作特點(diǎn)：,1便于進(jìn)行順序存??； 2不便于進(jìn)行直接存取，為取第i個(gè)記錄，必須先讀出前i-1個(gè)記錄，對(duì)于磁盤上的等長(zhǎng)記錄的連續(xù)文件可以進(jìn)行折半查找；,2020/7/23,15,3插入新的記錄只能加在文件的末尾； 4刪除記錄時(shí)，只作標(biāo)記； 5更新記錄必須生成新的文件。,2020/7/23,16,順序文件的插入、刪除和更新操 作在多數(shù)情況下都采用批處理方式。 此時(shí)，為處理方便，通

5、常將順序文件 作成有序文件，稱作“主文件”，同時(shí) 將所有的操作作成一個(gè)“事務(wù)文件” （經(jīng)過(guò)排序也成為有序文件），所謂 “批處理”，就是將這兩個(gè)文件“合”為 一個(gè)新的主文件。具體操作相當(dāng)于 “歸并兩個(gè)有序表”。,2020/7/23,17,（1）對(duì)于事務(wù)文件中的每個(gè)操作 首先要判別其“合法性”,（2）事務(wù)文件中可能存在多個(gè)操 作是對(duì)主文件中同一個(gè)記錄 進(jìn)行的,但有兩點(diǎn)不同：,2020/7/23,18,假設(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）。,批處理的

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

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

8、索引項(xiàng)：,主關(guān)鍵字 記錄在主文件中的存儲(chǔ)位置,稱作稠密索引，由這些索引項(xiàng)構(gòu)成 索引表。,2020/7/23,26,從索引表建立的索引稱查找表，其中 每個(gè)索引項(xiàng)為：,最大關(guān)鍵字 其所在數(shù)據(jù)塊的存儲(chǔ)位置,稱這類索引為非稠密索引。,類似地，由查找表建立的索引為第二 查找表；由第二查找表建立的索引為第 三查找表。,按關(guān)鍵字進(jìn)行檢索時(shí)，從第三查找表 開(kāi)始，至多訪問(wèn)外存五次。,2020/7/23,27,索引表采用查找樹表或哈希表。優(yōu)點(diǎn)：,1）不需要建立多級(jí)索引； 2）初建索引不需要進(jìn)行排序； 3）插入或刪除記錄時(shí)，修改索引方便。,動(dòng)態(tài)索引,2020/7/23,28,用查找樹表作索引時(shí)，查找索引所 需訪問(wèn)外

9、存次數(shù)的最大值恰為查找 樹的深度。,稠密索引的優(yōu)點(diǎn)是，可以實(shí)現(xiàn)“預(yù)查找” 缺點(diǎn)是，索引表占用的存儲(chǔ)空間大。,可以作索引的樹表有：二叉排序樹、 B-樹和鍵樹。,2020/7/23,29,主文件按主關(guān)鍵字有序，對(duì)一組記 錄建立一個(gè)索引項(xiàng)(建立非稠密索引)。,結(jié)構(gòu)特點(diǎn)：,12.4 索引順序文件,2020/7/23,30,一、ISAM文件 ISAM(Index Sequential Access Method) (索引順序存取方法)是一種專為磁 盤存取設(shè)計(jì)的文件組織方法。,有兩種典型的索引順序文件：,2020/7/23,31,文件的組織方式：,主文件按柱面集中存放，同時(shí)建立 三級(jí)索引：磁道索引、柱面索

10、引和 主索引。,關(guān)鍵字 指針 關(guān)鍵字 指針,磁道索引結(jié)構(gòu),基本索引項(xiàng),溢出索引項(xiàng),2020/7/23,32,210,1024,主 索 引,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è) 柱 面,.,柱 面 索 引,99,210,1024,T0 T1 T2 T3 T4 T5,2020/7/23,33,檢索： 可有兩種方式：,按關(guān)鍵字存取 從主索引開(kāi)始,到 柱面索引，到磁道索引，最后取 得記錄，先后訪問(wèn)四次外存。,順序存取 依關(guān)鍵字最小至大順序存取

11、。,操作的特點(diǎn)：,2020/7/23,34,插入:,修改本磁道的索引項(xiàng)(包括基本索 引項(xiàng)和溢出索引項(xiàng))。,將該磁道上關(guān)鍵字最大的記錄移出 到本柱面的溢出區(qū)中;,將記錄插入在某個(gè)磁道的合適位置上;,2020/7/23,35,刪除:,在被刪記錄當(dāng)前存儲(chǔ)位置上 作“刪除標(biāo)記”。,2020/7/23,36,文件重組,在經(jīng)過(guò)多次的插入和刪除操作之 后，大量的記錄進(jìn)入文件的“溢出區(qū)”，而“基本存儲(chǔ)區(qū)”中出現(xiàn)很多已被刪去的記錄空間，此時(shí)的文件結(jié)構(gòu)很不合理。因此，對(duì)ISAM文件， 需要周期地進(jìn)行重整。,2020/7/23,37,柱面索引的位置,ISAM文件占有多個(gè)柱面，其柱 面索引本身占有一個(gè)柱面，為使“磁頭

12、”的平均移動(dòng)距離最小，柱面索引應(yīng)設(shè)在數(shù)據(jù)文件所占全部柱面的中間位置上。,2020/7/23,38,二、VSAM文件 VSAM(Vistual Storage Access Method),文件是利用操作系統(tǒng)中提供的虛擬存儲(chǔ)器的功能組織的文件，免除了用戶為讀/寫記錄時(shí)直接對(duì)外存進(jìn)行的操作，對(duì)用戶而言，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲(chǔ)單位。,2020/7/23,39, .,.,.,.,索引集 B+樹 順序集,控制區(qū)域,控制區(qū)間,數(shù)據(jù)集,1文件的結(jié)構(gòu),2020/7/23,40,2. 控制區(qū)間是用戶進(jìn)行一次存取的 邏輯單位，可看成是一個(gè)邏輯磁道。 但它的實(shí)際大小和物理磁道無(wú)關(guān)。,VSAM文件初建時(shí)

13、，每個(gè)控制區(qū) 間內(nèi)的記錄數(shù)不足額定數(shù)，并且有的 控制區(qū)間內(nèi)的記錄數(shù)為零。,控制區(qū)域由若干控制區(qū)間和它們 的索引項(xiàng)組成，可看成是一個(gè)邏輯柱面。,2020/7/23,41,順序集本身是一個(gè)單鏈表，它 包含文件的全部索引項(xiàng)，同時(shí)，順 序集中的每個(gè)結(jié)點(diǎn)即為B+樹的葉子 結(jié)點(diǎn)，索引集中的結(jié)點(diǎn)即為B+樹的 非葉結(jié)點(diǎn)。,2020/7/23,42,文件的操作,檢索：可進(jìn)行順序存取和按關(guān)鍵字存??； 插入：按關(guān)鍵字大小插入在某個(gè)適當(dāng)?shù)目刂茀^(qū)間中，當(dāng)控制區(qū)間中的記錄數(shù)超過(guò)文件規(guī)定的大小時(shí)，要“分裂”控制區(qū)間，必要時(shí)，還需要“分裂”控制區(qū)域； 刪除：必須“真實(shí)地”刪除記錄，因此要在控制區(qū)間內(nèi)“移動(dòng)”記錄。,2020/

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

15、20/7/23,45,哈希文件的結(jié)構(gòu),由于記錄在外存上是成組存放的，因此允許多個(gè)記錄映象到同一個(gè)地址上。在此，稱外存儲(chǔ)器中存放多個(gè)記錄的“數(shù)據(jù)塊”為“桶”。 因此由哈希函數(shù)得到的映象地址為“桶地址”。,2020/7/23,46,例如：有一組關(guān)鍵字如下所列 589，063，269，505，764，182，166，330 假設(shè)哈希函數(shù)為 key MOD 7，每個(gè)桶可以容納 3個(gè)記錄（稱桶的容量為3），則哈希文件如下:,基桶,063 182,589 505 764,269,166,330,溢出桶,2020/7/23,47,在哈希文件中，“沖突”和“溢出” 是不同的概念。一般情況下，假設(shè)桶 的大小為m

16、，則允許哈希地址產(chǎn)生m-1 次的沖突，當(dāng)發(fā)生第m次沖突時(shí)，才 需要進(jìn)行“沖突處理”，對(duì)散列文件而 言，通常采用鏈地址法出路沖突。為 區(qū)別起見(jiàn)，稱直接“散列”的數(shù)據(jù)塊為 “基桶”，而因“溢出”存放的數(shù)據(jù)塊為 “溢出桶”。,2020/7/23,48,文件的操作,檢索：只能進(jìn)行按關(guān)鍵字的查找，不能進(jìn)行順序查找。檢索時(shí)，先在基桶內(nèi)進(jìn)行查找，若不存在，則再到溢出桶中進(jìn)行查找； 插入：當(dāng)查找不成功時(shí)，將記錄插入在相應(yīng)的基桶或溢出桶內(nèi)； 刪除：對(duì)被刪記錄作特殊標(biāo)記。,2020/7/23,49, 優(yōu)點(diǎn)：記錄隨機(jī)存放，不需要進(jìn)行排 序；插入、刪除方便，存取速 度快；節(jié)省存儲(chǔ)空間，不需要 索引區(qū)。,缺點(diǎn)：不能進(jìn)行順序存取；在經(jīng)過(guò)多 次插入和刪除操作之后，需進(jìn) 行“重組文件”的操作。,2020/7/23,50,一、多關(guān)鍵字文件的特點(diǎn) 除需要對(duì)主關(guān)鍵字建立“主索引”外， 尚需對(duì)各個(gè)次關(guān)鍵字建立“次索引”。,次索引項(xiàng)： 次關(guān)鍵字 （指向記錄的）指針,12.6 多關(guān)鍵字文件,2020/7/23,51,二、次索引的組織方法,1多重鏈表文件特點(diǎn)：將所