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

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

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

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