數(shù)據(jù)結構-文件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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