數(shù)據(jù)結(jié)構(gòu)-文件

1、第十章第十章 文件文件n 基本概念基本概念n 順序文件順序文件n 索引文件索引文件n ISAMISAM文件和文件和VSAMVSAM文件文件n 散列文件（直接存取文件）散列文件（直接存取文件）n 多關(guān)鍵字文件多關(guān)鍵字文件基本概念基本概念n 文件：是由大量性質(zhì)相同的記錄組成的集合。文件：是由大量性質(zhì)相同的記錄組成的集合。 （通常，存儲(chǔ)在外存儲(chǔ)器中。）（通常，存儲(chǔ)在外存儲(chǔ)器中。）n 操作系統(tǒng)文件（系統(tǒng)文件）：僅是一維的連續(xù)的字符序列，操作系統(tǒng)文件（系統(tǒng)文件）：僅是一維的連續(xù)的字符序列， 無結(jié)構(gòu)、無解釋。無結(jié)構(gòu)、無解釋。n 數(shù)據(jù)庫文件：是帶有結(jié)構(gòu)的記錄的集合，這類記錄是由一數(shù)據(jù)庫文件：是帶有結(jié)構(gòu)的記錄

2、的集合，這類記錄是由一 個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成的集合。個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成的集合。 （分為：單關(guān)鍵字文件、多關(guān)鍵字文件）（分為：單關(guān)鍵字文件、多關(guān)鍵字文件）n 定長記錄文件：文件中每個(gè)記錄含有的信息長度相同。定長記錄文件：文件中每個(gè)記錄含有的信息長度相同。n 不定長記錄文件：文件中含有信息長度不等。不定長記錄文件：文件中含有信息長度不等?；靖拍罨靖拍頽 記錄的邏輯結(jié)構(gòu)：是指記錄在用戶或應(yīng)用程序員面記錄的邏輯結(jié)構(gòu)：是指記錄在用戶或應(yīng)用程序員面 前呈現(xiàn)的方式，是用戶對(duì)數(shù)據(jù)的表示和存取方式。前呈現(xiàn)的方式，是用戶對(duì)數(shù)據(jù)的表示和存取方式。 （它著眼于用戶使用方便）（它著眼于用戶使用方便）n 記錄的物理結(jié)構(gòu)

3、：是數(shù)據(jù)在物理存儲(chǔ)器上的存儲(chǔ)方記錄的物理結(jié)構(gòu)：是數(shù)據(jù)在物理存儲(chǔ)器上的存儲(chǔ)方 式，是數(shù)據(jù)的物理表示和組織。（它著眼于存儲(chǔ)空式，是數(shù)據(jù)的物理表示和組織。（它著眼于存儲(chǔ)空 間的提高和存取時(shí)間的減少）間的提高和存取時(shí)間的減少）基本概念基本概念n 文件的操作：檢索和修改文件的操作：檢索和修改n 檢索檢索（1 1）順序存?。捍嫒∠乱粋€(gè)邏輯記錄）順序存取：存取下一個(gè)邏輯記錄（2 2）直接存?。捍嫒〉冢┲苯哟嫒。捍嫒〉趇 i個(gè)記錄個(gè)記錄（3 3）按關(guān)鍵字存?。航o定一個(gè)值，查詢一個(gè)和一批關(guān)鍵字）按關(guān)鍵字存?。航o定一個(gè)值，查詢一個(gè)和一批關(guān)鍵字 與給定值相關(guān)的記錄。與給定值相關(guān)的記錄。 查詢：（查詢：（1 1）簡單

4、查詢：查詢關(guān)鍵字等于給定值的記錄。）簡單查詢：查詢關(guān)鍵字等于給定值的記錄。 （2 2）區(qū)域查詢：查詢關(guān)鍵字屬于某個(gè)區(qū)域的記錄。）區(qū)域查詢：查詢關(guān)鍵字屬于某個(gè)區(qū)域的記錄。 （3 3）函數(shù)查詢：給定關(guān)鍵字的某個(gè)函數(shù)。）函數(shù)查詢：給定關(guān)鍵字的某個(gè)函數(shù)。 （4 4）布爾查詢：將上述三種查詢用布爾運(yùn)算組合）布爾查詢：將上述三種查詢用布爾運(yùn)算組合 起來的查詢。起來的查詢?；靖拍罨靖拍頽 修改修改 插入插入 刪除刪除 更新更新n 文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu) 文件在存儲(chǔ)介質(zhì)上的組織方式。文件在存儲(chǔ)介質(zhì)上的組織方式。 （1 1）順序組織）順序組織 （2 2）隨機(jī)組織）隨機(jī)組織 （3 3）鏈組織）鏈組織順序

5、文件順序文件順序文件是物理結(jié)構(gòu)最簡單的文件，也是數(shù)據(jù)處理歷史上最早使用的文件結(jié)構(gòu)。順序文件是記錄按其在文件中的邏輯順序依次進(jìn)入而建立的，即順序文件中物理記錄的順序和邏輯記錄的順序一致。n 連續(xù)文件：若次序相繼的兩個(gè)物理記錄在存儲(chǔ)介質(zhì)上的 存儲(chǔ)位置是相鄰的，則又稱為連續(xù)文件。n 串聯(lián)文件：若物理記錄之間的次序由指針相連表示，則 稱為串聯(lián)文件。 順序文件順序文件當(dāng)需要對(duì)磁帶順序文件進(jìn)行檢索時(shí)，一般是采用順序掃描的方式來檢索滿足查詢條件的記錄。例如，若要檢索第i個(gè)記錄，則必須先檢索前面的i-1個(gè)記錄。為了提高平均檢索效率，可采用批量處理技術(shù)。如果將對(duì)文件的多個(gè)檢索請(qǐng)求加以積累和排序，則形成一個(gè)稱為待

6、辦文件（或事務(wù)文件）的文件。如果將被查詢的文件稱為主文件，則批量檢索就是按照待辦文件的要求成批地檢索主文件。批量檢索對(duì)于實(shí)時(shí)應(yīng)用來說是不適宜的，因?yàn)閷?shí)時(shí)查詢要求響應(yīng)時(shí)間快，而在很短的時(shí)間間隔內(nèi)，積累的批處理文件規(guī)模太小，不能表現(xiàn)出它的優(yōu)越性。在磁帶順序文件中插入記錄，只能加在文件的末尾，不能插在兩個(gè)原有記錄之間。順序文件順序文件修改記錄，即使在新舊記錄等長的情況下，將新記錄寫在舊記錄的位置上，一般不但不可能完全重合，甚至還會(huì)破壞鄰近記錄的信息。因此，修改一個(gè)磁帶文件，需要用另一條磁帶將原文件復(fù)制過來，在復(fù)制過程中進(jìn)行插入、刪除、修改記錄的操作。為了提高效率，修改一個(gè)順序文件，也采用成批處理技術(shù)

7、。這種批量修改方式很適用于銀行帳戶結(jié)算管理系統(tǒng)。例如，可把一天的零星支取和存入分別作為記錄收集在一起，構(gòu)成為一個(gè)待辦文件，在當(dāng)天下班時(shí)再按照待辦文件進(jìn)行批量修改主文件（頭天下班修改過的主文件）的工作，便得到一個(gè)新主文件。順序文件順序文件順序文件的基本優(yōu)點(diǎn)是在連續(xù)存取時(shí)速度較快。例如，如果文件中的第i個(gè)記錄剛被存取過，而下一個(gè)要存取的記錄就是第i+1個(gè)記錄，則此次存取將會(huì)很快完成。磁帶是比較適用于這種應(yīng)用的外存設(shè)備。存放于磁帶上的文件也只能是順序文件，這是由磁帶的物理特性決定的。存放于磁盤上的文件，既可以是順序文件，也可以是索引結(jié)構(gòu)或其它結(jié)構(gòu)類型的文件。索引文件索引文件順序文件的查詢速度很慢。采

8、用索引文件可以提高檢索效率。 索引用來表示關(guān)鍵字與相應(yīng)記錄的存儲(chǔ)地址之間的對(duì)應(yīng)關(guān)系。換言之，索引指出了記錄在存儲(chǔ)器中的存儲(chǔ)地址。設(shè)記錄Ri的關(guān)鍵字為Ki，Ri在外存中的存儲(chǔ)地址為Ai，則（Ki，Ai）稱為記錄Ri的索引項(xiàng)。索引表（簡稱索引）是索引項(xiàng)的集合。如果文件中的每個(gè)記錄都有一個(gè)索引項(xiàng)，則這樣的索引稱為稠密索引。如果多個(gè)記錄只有一個(gè)索引項(xiàng)，則這樣的索引稱為非稠密索引。帶有索引的文件稱為索引文件。索引也稱為目錄。索引文件索引文件索引文件在外存（磁盤、磁鼓等）中可分為兩個(gè)存儲(chǔ)區(qū)：索引區(qū)和記錄區(qū)（數(shù)據(jù)區(qū)）。索引表中的索引項(xiàng)順序存放在索引區(qū)中，但為了便于檢索，索引項(xiàng)一般按關(guān)鍵字的大小次序排列。文件

9、中的記錄按輸入的先后次序存放到記錄區(qū)；記錄區(qū)按關(guān)鍵字大小次序排列的索引文件稱為索引順序文件。對(duì)于索引順序文件，可以不必使用稠密索引，只為一個(gè)記錄塊（含多個(gè)有序記錄）建立一個(gè)索引項(xiàng)。記錄區(qū)不按關(guān)鍵字大小次序排列的索引文件稱為索引非順序文件，這時(shí)應(yīng)使用稠密索引。索引文件索引文件通常，索引項(xiàng)所含的數(shù)據(jù)信息比記錄少得多，因而索引所需的存儲(chǔ)空間比文件本身（記錄區(qū)）所需要的存儲(chǔ)空間少得多。在文件的記錄數(shù)較少的情況下，可以為每個(gè)記錄建立一個(gè)索引項(xiàng)。文件建立時(shí)，開辟一個(gè)索引區(qū)，一般固定在某個(gè)磁盤面的一個(gè)或多個(gè)磁道上。寫入一個(gè)記錄到記錄區(qū)時(shí)，在索引區(qū)相應(yīng)登入一個(gè)索引項(xiàng)，即把該記錄的關(guān)鍵字（主關(guān)鍵字）和記錄的存儲(chǔ)

10、地址順序?qū)懭胨饕齾^(qū)。文件建立后，將索引區(qū)中的索引讀入內(nèi)存的緩沖區(qū)，按關(guān)鍵字進(jìn)行內(nèi)部排序。最后將排序好的索引項(xiàng)順序?qū)懟氐酱疟P上的索引區(qū)。 根據(jù)關(guān)鍵字查找索引文件的記錄分兩步進(jìn)行。第1步，訪問外存的索引區(qū)，將索引讀入內(nèi)存緩沖區(qū)，使用順序查找或折半查找法找出所查記錄在外存數(shù)據(jù)區(qū)中的地址，這一過程稱為預(yù)查找。第2步，如果在預(yù)查中已找到了所查記錄的地址，則第2次訪問外存，根據(jù)已查到的地址，讀取所查的記錄ISAMISAM文件和文件和VSAMVSAM文件文件ISAM(Indexed Sequential Access MethedISAM(Indexed Sequential Access Methed)

11、)索引順序存取方法索引順序存取方法是專為磁盤存取設(shè)計(jì)的一種文件組織方式。由于磁盤由盤組、柱面和磁道(實(shí)際是盤片)三級(jí)組成，因此通常對(duì)磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道(盤面)三級(jí)索引。在ISAM文件上檢索記錄時(shí)，先從主索引(柱面索引的索引)找到相應(yīng)柱面索引。再從柱面索引找到記錄所在柱面的磁道索引，最后從磁道索引找到記錄所在磁道的第一個(gè)記錄的位置，由此出發(fā)在該磁道上進(jìn)行順序查找直到查到為止;反之，若找遍該磁道而未找到所查記錄，則文件中無此記錄。ISAMISAM文件和文件和VSAMVSAM文件文件ISAM文件中記錄按關(guān)鍵字順序存放，插入記錄時(shí)需移動(dòng)記錄并將同一磁道上最后的一個(gè)記錄移至溢出區(qū)，同時(shí)

12、修改磁道索引項(xiàng)，刪除記錄只需在存儲(chǔ)位置作標(biāo)記，不需移動(dòng)記錄和修改指針。經(jīng)過多次插入和刪除記錄后，文件結(jié)構(gòu)變得不合理，需周期整理ISAM文件。ISAMISAM文件和文件和VSAMVSAM文件文件VSAM(Virtual Storage Access Method)VSAM(Virtual Storage Access Method)虛擬存儲(chǔ)存取方法虛擬存儲(chǔ)存取方法這種存取方法利用了操作系統(tǒng)的虛擬存儲(chǔ)器的功能。對(duì)用戶來說，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲(chǔ)單位，與外存儲(chǔ)器中柱面、磁道等具體存儲(chǔ)單位沒有必然聯(lián)系。VSAM文件采用B+樹動(dòng)態(tài)索引結(jié)構(gòu)，VSAM文件結(jié)構(gòu)包括索引集、順序集和數(shù)據(jù)集三部分，

13、記錄存于數(shù)據(jù)集中，順序集和索引集構(gòu)成B+樹，作為文件的索引部分可實(shí)現(xiàn)順鏈查找和從根結(jié)點(diǎn)開始的隨機(jī)查找。ISAMISAM文件和文件和VSAMVSAM文件文件與ISAM文件相比，VSAM文件有如下優(yōu)點(diǎn)：動(dòng)態(tài)分配和釋放存儲(chǔ)空間，不需對(duì)文件進(jìn)行重組;能保持較高的查找效率，且查找先后插入記錄所需時(shí)間相同。因此，基于B+樹的VSAM文件通常作為大型索引順序文件的標(biāo)準(zhǔn)組織。直接存取文件（散列文件）直接存取文件（散列文件）直接存取文件，根據(jù)關(guān)鍵字的散列函數(shù)值和處理沖突的方法，將記錄散列到外存上。這種文件組織只適用于像磁盤那樣的直接存取設(shè)備，其優(yōu)點(diǎn)是文件隨機(jī)存放，記錄不必排序，插入、刪除方便，存取速度快，無需索

14、引區(qū)，節(jié)省存儲(chǔ)空間。缺點(diǎn)是散列文件不能順序存取，且只限于簡單查詢。經(jīng)多次插入、刪除后，文件結(jié)構(gòu)不合理，需重組文件，這很費(fèi)時(shí)。多關(guān)鍵字文件多關(guān)鍵字文件多關(guān)鍵字文件的特點(diǎn)是，在對(duì)文件進(jìn)行檢索操作時(shí)，不僅對(duì)主關(guān)鍵字進(jìn)行簡單詢問，還經(jīng)常需要對(duì)次關(guān)鍵字進(jìn)行其它類型的詢問檢索。多重表文件多重表文件多重表文件是把索引與鏈接結(jié)合而形成的組織方式。記錄按主關(guān)鍵字順序構(gòu)成一個(gè)串聯(lián)文件，建立主關(guān)鍵字的索引(主索引)。對(duì)每一次關(guān)鍵字建立次關(guān)鍵字索引，具有同一關(guān)鍵字的記錄構(gòu)成一個(gè)鏈表。主索引為非稠密索引，次索引為稠密索引，每個(gè)索引項(xiàng)包括次關(guān)鍵字，頭指針和鏈表長度。多重表文件易于編程，也易于插入，但刪除繁鎖。需在各次關(guān)鍵

15、字鏈表中刪除。多關(guān)鍵字文件多關(guān)鍵字文件倒排文件倒排文件倒排文件是一種多關(guān)鍵字的文件，主數(shù)據(jù)文件按關(guān)鍵字順序構(gòu)成串聯(lián)文件，并建立主關(guān)鍵字索引。對(duì)次關(guān)鍵字也建立索引，該索引稱為倒排表。倒排表包括兩項(xiàng)，一項(xiàng)是次關(guān)鍵字，另一項(xiàng)是具有同一次關(guān)鍵字值的記錄的物理記錄號(hào)(若數(shù)據(jù)文件非串聯(lián)文件，而是索引順序文件如ISAM，則倒排表中存放記錄的主關(guān)鍵字而不是物理記錄號(hào))。倒排表作索引的優(yōu)點(diǎn)是索引記錄快，缺點(diǎn)是維護(hù)困難。在同一索引表中，不同的關(guān)鍵字其記錄數(shù)不同，各倒排表的長度不同，同一倒排表中各項(xiàng)長度也不相等。附錄附錄磁帶：磁帶：磁帶有不同的規(guī)格。目前使用的磁帶一般有磁帶有不同的規(guī)格。目前使用的磁帶一般有1/21

16、/2英寸英寸寬，最長可達(dá)寬，最長可達(dá)36003600英尺。英尺。1/21/2英寸的帶在橫向上可記英寸的帶在橫向上可記錄錄9 9位或位或7 7位二進(jìn)制信息（分別稱為位二進(jìn)制信息（分別稱為9 9道帶或道帶或7 7道帶）。道帶）。磁帶上的信息是以塊為單位存放的。一個(gè)信息塊由若磁帶上的信息是以塊為單位存放的。一個(gè)信息塊由若干個(gè)字節(jié)構(gòu)成，如干個(gè)字節(jié)構(gòu)成，如512512字節(jié)或字節(jié)或10241024字節(jié)，要讀寫某一字節(jié)，要讀寫某一塊上信息，首先要定位，即通過磁帶的移動(dòng)使磁頭對(duì)塊上信息，首先要定位，即通過磁帶的移動(dòng)使磁頭對(duì)準(zhǔn)磁塊的前端，磁帶不是連續(xù)運(yùn)轉(zhuǎn)的設(shè)備，而是一種準(zhǔn)磁塊的前端，磁帶不是連續(xù)運(yùn)轉(zhuǎn)的設(shè)備，而是

17、一種啟停設(shè)備。為適應(yīng)啟動(dòng)時(shí)的加速和停止時(shí)的滑動(dòng)，磁啟停設(shè)備。為適應(yīng)啟動(dòng)時(shí)的加速和停止時(shí)的滑動(dòng)，磁帶上塊與塊之間隙。間隙通常為帶上塊與塊之間隙。間隙通常為1/4-3/41/4-3/4英尺長。間英尺長。間隙 是 一 段 空 白 區(qū) ， 不 存 放 數(shù) 據(jù) 信 息 。隙 是 一 段 空 白 區(qū) ， 不 存 放 數(shù) 據(jù) 信 息 。 一個(gè)信息塊就是磁帶存儲(chǔ)器的一個(gè)物理記錄。通常一一個(gè)信息塊就是磁帶存儲(chǔ)器的一個(gè)物理記錄。通常一個(gè)信息塊可存放多個(gè)邏輯記錄。個(gè)信息塊可存放多個(gè)邏輯記錄。 附錄附錄磁盤：磁盤：磁盤存儲(chǔ)器是目前使用得最廣泛的外存設(shè)備。磁盤有點(diǎn)磁盤存儲(chǔ)器是目前使用得最廣泛的外存設(shè)備。磁盤有點(diǎn)像唱片，