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

第十章文件基本概念順序文件索引文件

ISAM文件和VSAM文件散列文件（直接存取文件）多關(guān)鍵字文件基本概念文件：是由大量性質(zhì)相同的記錄組成的集合。（通常，存儲在外存儲器中。）操作系統(tǒng)文件（系統(tǒng)文件）：僅是一維的連續(xù)的字符序列，無結(jié)構(gòu)、無解釋。數(shù)據(jù)庫文件：是帶有結(jié)構(gòu)的記錄的集合，這類記錄是由一個或多個數(shù)據(jù)項組成的集合。（分為：單關(guān)鍵字文件、多關(guān)鍵字文件）定長記錄文件：文件中每個記錄含有的信息長度相同。不定長記錄文件：文件中含有信息長度不等?；靖拍钣涗浀倪壿嫿Y(jié)構(gòu)：是指記錄在用戶或應(yīng)用程序員面前呈現(xiàn)的方式，是用戶對數(shù)據(jù)的表示和存取方式。（它著眼于用戶使用方便）記錄的物理結(jié)構(gòu)：是數(shù)據(jù)在物理存儲器上的存儲方式，是數(shù)據(jù)的物理表示和組織。（它著眼于存儲空間的提高和存取時間的減少）基本概念文件的操作：檢索和修改檢索（1）順序存取：存取下一個邏輯記錄（2）直接存?。捍嫒〉趇個記錄（3）按關(guān)鍵字存?。航o定一個值，查詢一個和一批關(guān)鍵字與給定值相關(guān)的記錄。查詢：（1）簡單查詢：查詢關(guān)鍵字等于給定值的記錄。（2）區(qū)域查詢：查詢關(guān)鍵字屬于某個區(qū)域的記錄。（3）函數(shù)查詢：給定關(guān)鍵字的某個函數(shù)。（4）布爾查詢：將上述三種查詢用布爾運算組合起來的查詢?；靖拍钚薷牟迦雱h除更新文件的物理結(jié)構(gòu)文件在存儲介質(zhì)上的組織方式。（1）順序組織（2）隨機組織（3）鏈組織順序文件順序文件是物理結(jié)構(gòu)最簡單的文件，也是數(shù)據(jù)處理歷史上最早使用的文件結(jié)構(gòu)。順序文件是記錄按其在文件中的邏輯順序依次進入而建立的，即順序文件中物理記錄的順序和邏輯記錄的順序一致。連續(xù)文件：若次序相繼的兩個物理記錄在存儲介質(zhì)上的存儲位置是相鄰的，則又稱為連續(xù)文件。串聯(lián)文件：若物理記錄之間的次序由指針相連表示，則稱為串聯(lián)文件。

順序文件當(dāng)需要對磁帶順序文件進行檢索時，一般是采用順序掃描的方式來檢索滿足查詢條件的記錄。例如，若要檢索第i個記錄，則必須先檢索前面的i-1個記錄。為了提高平均檢索效率，可采用批量處理技術(shù)。如果將對文件的多個檢索請求加以積累和排序，則形成一個稱為待辦文件（或事務(wù)文件）的文件。如果將被查詢的文件稱為主文件，則批量檢索就是按照待辦文件的要求成批地檢索主文件。批量檢索對于實時應(yīng)用來說是不適宜的，因為實時查詢要求響應(yīng)時間快，而在很短的時間間隔內(nèi)，積累的批處理文件規(guī)模太小，不能表現(xiàn)出它的優(yōu)越性。在磁帶順序文件中插入記錄，只能加在文件的末尾，不能插在兩個原有記錄之間。順序文件修改記錄，即使在新舊記錄等長的情況下，將新記錄寫在舊記錄的位置上，一般不但不可能完全重合，甚至還會破壞鄰近記錄的信息。因此，修改一個磁帶文件，需要用另一條磁帶將原文件復(fù)制過來，在復(fù)制過程中進行插入、刪除、修改記錄的操作。為了提高效率，修改一個順序文件，也采用成批處理技術(shù)。這種批量修改方式很適用于銀行帳戶結(jié)算管理系統(tǒng)。例如，可把一天的零星支取和存入分別作為記錄收集在一起，構(gòu)成為一個待辦文件，在當(dāng)天下班時再按照待辦文件進行批量修改主文件（頭天下班修改過的主文件）的工作，便得到一個新主文件。順序文件順序文件的基本優(yōu)點是在連續(xù)存取時速度較快。例如，如果文件中的第i個記錄剛被存取過，而下一個要存取的記錄就是第i+1個記錄，則此次存取將會很快完成。磁帶是比較適用于這種應(yīng)用的外存設(shè)備。存放于磁帶上的文件也只能是順序文件，這是由磁帶的物理特性決定的。存放于磁盤上的文件，既可以是順序文件，也可以是索引結(jié)構(gòu)或其它結(jié)構(gòu)類型的文件。索引文件順序文件的查詢速度很慢。采用索引文件可以提高檢索效率。索引用來表示關(guān)鍵字與相應(yīng)記錄的存儲地址之間的對應(yīng)關(guān)系。換言之，索引指出了記錄在存儲器中的存儲地址。設(shè)記錄Ri的關(guān)鍵字為Ki，Ri在外存中的存儲地址為Ai，則（Ki，Ai）稱為記錄Ri的索引項。索引表（簡稱索引）是索引項的集合。如果文件中的每個記錄都有一個索引項，則這樣的索引稱為稠密索引。如果多個記錄只有一個索引項，則這樣的索引稱為非稠密索引。帶有索引的文件稱為索引文件。索引也稱為目錄。索引文件索引文件在外存（磁盤、磁鼓等）中可分為兩個存儲區(qū)：索引區(qū)和記錄區(qū)（數(shù)據(jù)區(qū)）。索引表中的索引項順序存放在索引區(qū)中，但為了便于檢索，索引項一般按關(guān)鍵字的大小次序排列。文件中的記錄按輸入的先后次序存放到記錄區(qū)；記錄區(qū)按關(guān)鍵字大小次序排列的索引文件稱為索引順序文件。對于索引順序文件，可以不必使用稠密索引，只為一個記錄塊（含多個有序記錄）建立一個索引項。記錄區(qū)不按關(guān)鍵字大小次序排列的索引文件稱為索引非順序文件，這時應(yīng)使用稠密索引。索引文件通常，索引項所含的數(shù)據(jù)信息比記錄少得多，因而索引所需的存儲空間比文件本身（記錄區(qū)）所需要的存儲空間少得多。在文件的記錄數(shù)較少的情況下，可以為每個記錄建立一個索引項。文件建立時，開辟一個索引區(qū)，一般固定在某個磁盤面的一個或多個磁道上。寫入一個記錄到記錄區(qū)時，在索引區(qū)相應(yīng)登入一個索引項，即把該記錄的關(guān)鍵字（主關(guān)鍵字）和記錄的存儲地址順序?qū)懭胨饕齾^(qū)。文件建立后，將索引區(qū)中的索引讀入內(nèi)存的緩沖區(qū)，按關(guān)鍵字進行內(nèi)部排序。最后將排序好的索引項順序?qū)懟氐酱疟P上的索引區(qū)。根據(jù)關(guān)鍵字查找索引文件的記錄分兩步進行。第1步，訪問外存的索引區(qū)，將索引讀入內(nèi)存緩沖區(qū)，使用順序查找或折半查找法找出所查記錄在外存數(shù)據(jù)區(qū)中的地址，這一過程稱為預(yù)查找。第2步，如果在預(yù)查中已找到了所查記錄的地址，則第2次訪問外存，根據(jù)已查到的地址，讀取所查的記錄ISAM文件和VSAM文件ISAM(IndexedSequentialAccessMethed)索引順序存取方法是專為磁盤存取設(shè)計的一種文件組織方式。由于磁盤由盤組、柱面和磁道(實際是盤片)三級組成，因此通常對磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道(盤面)三級索引。在ISAM文件上檢索記錄時，先從主索引(柱面索引的索引)找到相應(yīng)柱面索引。再從柱面索引找到記錄所在柱面的磁道索引，最后從磁道索引找到記錄所在磁道的第一個記錄的位置，由此出發(fā)在該磁道上進行順序查找直到查到為止;反之，若找遍該磁道而未找到所查記錄，則文件中無此記錄。ISAM文件和VSAM文件ISAM文件中記錄按關(guān)鍵字順序存放，插入記錄時需移動記錄并將同一磁道上最后的一個記錄移至溢出區(qū)，同時修改磁道索引項，刪除記錄只需在存儲位置作標(biāo)記，不需移動記錄和修改指針。經(jīng)過多次插入和刪除記錄后，文件結(jié)構(gòu)變得不合理，需周期整理ISAM文件。ISAM文件和VSAM文件VSAM(VirtualStorageAccessMethod)虛擬存儲存取方法這種存取方法利用了操作系統(tǒng)的虛擬存儲器的功能。對用戶來說，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲單位，與外存儲器中柱面、磁道等具體存儲單位沒有必然聯(lián)系。VSAM文件采用B+樹動態(tài)索引結(jié)構(gòu)，VSAM文件結(jié)構(gòu)包括索引集、順序集和數(shù)據(jù)集三部分，記錄存于數(shù)據(jù)集中，順序集和索引集構(gòu)成B+樹，作為文件的索引部分可實現(xiàn)順鏈查找和從根結(jié)點開始的隨機查找。ISAM文件和VSAM文件與ISAM文件相比，VSAM文件有如下優(yōu)點：動態(tài)分配和釋放存儲空間，不需對文件進行重組;能保持較高的查找效率，且查找先后插入記錄所需時間相同。因此，基于B+樹的VSAM文件通常作為大型索引順序文件的標(biāo)準(zhǔn)組織。直接存取文件（散列文件）直接存取文件，根據(jù)關(guān)鍵字的散列函數(shù)值和處理沖突的方法，將記錄散列到外存上。這種文件組織只適用于像磁盤那樣的直接存取設(shè)備，其優(yōu)點是文件隨機存放，記錄不必排序，插入、刪除方便，存取速度快，無需索引區(qū)，節(jié)省存儲空間。缺點是散列文件不能順序存取，且只限于簡單查詢。經(jīng)多次插入、刪除后，文件結(jié)構(gòu)不合理，需重組文件，這很費時。多關(guān)鍵字文件多關(guān)鍵字文件的特點是，在對文件進行檢索操作時，不僅對主關(guān)鍵字進行簡單詢問，還經(jīng)常需要對次關(guān)鍵字進行其它類型的詢問檢索。多重表文件多重表文件是把索引與鏈接結(jié)合而形成的組織方式。記錄按主關(guān)鍵字順序構(gòu)成一個串聯(lián)文件，建立主關(guān)鍵字的索引(主索引)。對每一次關(guān)鍵字建立次關(guān)鍵字索引，具有同一關(guān)鍵字的記錄構(gòu)成一個鏈表。主索引為非稠密索引，次索引為稠密索引，每個索引項包括次關(guān)鍵字，頭指針和鏈表長度。多重表文件易于編程，也易于插入，但刪除繁鎖。需在各次關(guān)鍵字鏈表中刪除。多關(guān)鍵字文件倒排文件倒排文件是一種多關(guān)鍵字的文件，主數(shù)據(jù)文件按關(guān)鍵字順序構(gòu)成串聯(lián)文件，并建立主關(guān)鍵字索引。對次關(guān)鍵字也建立索引，該索引稱為倒排表。倒排表包括兩項，一項是次關(guān)鍵字，另一項是具有同一次關(guān)鍵字值的記錄的物理記錄號(若數(shù)據(jù)文件非串聯(lián)文件，而是索引順序文件—如ISAM，則倒排表中存放記錄的主關(guān)鍵字而不是物理記錄號)。倒排表作索引的優(yōu)點是索引記錄快，缺點是維護困難。在同一索引表中，不同的關(guān)鍵字其記錄數(shù)不同，各倒排表的長度不同，同一倒排表中各項長度也不相等。附錄磁帶：磁帶有不同的規(guī)格。目前使用的磁帶一般有1/2英寸寬，最長可達3600英尺。1/2英寸的帶在橫向上可記錄9位或7位二進制信息（分別稱為9道帶或7道帶）。磁帶上的信息是以塊為單位存放的。一個信息塊由若干個字節(jié)構(gòu)成，如512字節(jié)或1024字節(jié)，要讀寫某一塊上信息，首先要定位，即通過磁帶的移動使磁頭對準(zhǔn)磁塊的前端，磁帶不是連續(xù)運轉(zhuǎn)的設(shè)備，而是一種啟停設(shè)備。為適應(yīng)啟動時的加速和停止時的滑動，磁帶上塊與塊之間隙。間隙通常為1/4--3/4英尺長。間隙是一段空白區(qū)，不存放