08數(shù)據(jù)結(jié)構(gòu)-第十二章

本章說明

12.1文件的基本概念

12.2順序文件

12.3索引文件

12.4VSAM文件

12.5直接存取文件

12.6多關(guān)鍵字文件

本章小結(jié)數(shù)據(jù)結(jié)構(gòu)返回主目錄學(xué)習(xí)目標熟悉各類文件的結(jié)構(gòu)和特點，以及及其適用場合重點和難點本章重點在于了解各種文件的結(jié)構(gòu)特點及其適用場合本章說明知識點順序文件、索引、索引順序文件、VSAM文件、直接存取文件（散列文件）、多關(guān)鍵字文件學(xué)習(xí)指南

文件是外存的"集合"結(jié)構(gòu)，因此和查找表類似，為了提高對文件進行操作的效率，也存在一個數(shù)據(jù)的組織問題。因此在學(xué)習(xí)本章的過程中同樣應(yīng)著重了解文件的各種表示方法及其特點。本章說明12.1文件的基本概念文件(File)——是由大量性質(zhì)相同的記錄組成的集合。操作系統(tǒng)中的文件僅是一維的連續(xù)字符序列，無結(jié)構(gòu)、無解釋。按記錄類型分操作系統(tǒng)的文件數(shù)據(jù)庫的文件數(shù)據(jù)庫中的文件是帶有結(jié)構(gòu)的記錄的集合關(guān)鍵字:記錄中能唯一確定(或識別)一個記錄的數(shù)據(jù)項或數(shù)據(jù)項的組合定長文件:若文件所含記錄具有相同類型而且長度相等非定長文件(變長文件):各記錄的類型不同，或者類型相同而長度不等邏輯記錄——是用戶表示和存取信息的單位物理記錄——指外存信息存取的單位(即一個頁塊內(nèi)的信息)。在物理記錄和邏輯記錄之間可能存在下列三種關(guān)系：

一個物理記錄存放一個邏輯記錄；

一個物理記錄包含多個邏輯記錄；

多個物理記錄表示一個邏輯記錄。文件的操作有兩類：檢索和修改。

12.1文件的基本概念檢索三種方式順序存取：存取下一個邏輯記錄直接存?。捍嫒〉趇個邏輯記錄按關(guān)鍵字存?。航o定一個值，查詢一個或一批關(guān)鍵字與給定值相關(guān)的記錄12.1文件的基本概念12.2順序文件順序文件——是記錄的物理順序和邏輯順序完全一致的文件優(yōu)點：連續(xù)存取時速度快，批處理效率高，存儲節(jié)省缺點：隨機處理效率低，特別是對更新要求，一般不做隨機處理常存儲有歷史保留價值的海量數(shù)據(jù)，例如氣象部門的逐日氣象記錄數(shù)據(jù)等。如磁帶是一種典型的順序存儲設(shè)備。連續(xù)文件——次序相繼的兩個物理記錄在存儲介質(zhì)上的存儲位置是相鄰的串聯(lián)文件——物理記錄之間的次序由指針相鏈索引文件——由“索引”和“主文件(順序文件)”兩部分構(gòu)成，其中索引為指示邏輯記錄和物理記錄之間對應(yīng)關(guān)系的表，表中每一個記錄稱作索引項，包含(邏輯記錄的)關(guān)鍵碼和物理記錄位置兩個數(shù)據(jù)項，索引按關(guān)鍵字有序。索引文件存取直接存取按關(guān)鍵字存取存?。涸谒饕羞M行查找，然后按索引項中指示的記錄在主文件中的物理位置進行存取插入：記錄本身可插入在主文件的末尾，同時將相應(yīng)的索引項插入索引刪除：僅需刪除相應(yīng)的索引項更新：可將更新后的記錄插入主文件末尾，同時修改相應(yīng)的索引項。12.3索引文件組織索引文件的關(guān)鍵是如何組織索引。索引本身可以是順序結(jié)構(gòu)也可以是樹型結(jié)構(gòu)。由于大型文件的索引都相當大，則對順序結(jié)構(gòu)的索引需要建立多級索引，而樹型結(jié)構(gòu)本身就是一種“層次”結(jié)構(gòu)，因此常用以作為索引文件的索引。本節(jié)主要介紹大型索引文件的索引--B樹。B樹是一種查找樹，其本身是一種有序結(jié)構(gòu)，因此建立索引之后不需要再排序，插入或刪除記錄時修改索引很方便。12.3索引文件索引順序文件——索引文件中的主文件按關(guān)鍵碼有序非稠密索引——連續(xù)的一組記錄建立一個索引項，它由這組記錄中的最大關(guān)鍵碼和這組記錄的物理地址組成。稠密索引——對每個記錄建立一個索引索引的組織形式分靜態(tài)索引:以ISAM文件為代表，它是一種專為磁盤存取設(shè)計的文件組織方式，由索引區(qū)，數(shù)據(jù)區(qū)和溢出區(qū)三部分組成。索引區(qū)通常是與硬件層次一致的三級索引：總索引，柱面索引和磁道索引，溢出區(qū)用來存放后插入的記錄。當文件主要用于檢索時，ISAM文件效率高，既能隨機查找，又能順序查找，但若增刪頻繁，則存取效率退化，且需定期重組。動態(tài)索引:以B+樹為代表，其典型的文件組織為VSAM文件，它既便于檢索又便于更新。12.3索引文件12.4ISAM文件和VSAM文件ISAM文件（索引順序存取法）是一種專為磁盤存取而設(shè)計的文件組織方式。由于磁盤是以盤組、柱面和磁道三級地址存取的設(shè)備，則可對磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道三級索引。文件的記錄在同一盤組上存放時，應(yīng)先集中放在一個柱面上，然后再順序存放在相鄰的柱面上，對同一柱面，則應(yīng)按盤面的次序順序存放。用這種方法建立起來的索引文件稱為ISAM文件。包括：索引區(qū)、數(shù)據(jù)基本區(qū)、數(shù)據(jù)溢出區(qū)。數(shù)據(jù)區(qū)索引區(qū)溢出區(qū)ISAM文件的檢索查主索引（駐內(nèi)存），將相應(yīng)柱面索引（在其柱面上）調(diào)用內(nèi)存。查柱面索引，將磁道索引（一般放在第0道上）調(diào)入內(nèi)存；查磁道索引，將本磁道上的所有記錄送入內(nèi)存；順序?qū)@一組記錄查找。ISAM文件的插入定位應(yīng)插入的磁道；按關(guān)鍵字順序插入新紀錄，將同一磁道上最后一個記錄移至溢出區(qū)；同時修改磁道索引項。12.4ISAM文件和VSAM文件12.4ISAM文件和VSAM文件ISAM文件的刪除找到待刪除的記錄，在其存儲位置上作刪除標記即可，而不需要移動記錄或改變指針。ISAM文件的整理經(jīng)過多次的增刪后，文件的結(jié)構(gòu)可能變得很不合理。此時，大量的記錄進入溢出區(qū)，而基本區(qū)中又浪費很多空間。因此，通常需要周期地整理ISAM文件。把記錄讀入內(nèi)存，重新排列，復(fù)制成一個新的ISAM文件，填滿基本區(qū)而空出溢出區(qū)。12.4ISAM文件和VSAM文件VSAM（虛擬存儲存取方法）利用了操作系統(tǒng)的虛擬存儲器的功能，給用戶提供方便。對用戶來說，存儲記錄時不需要考慮記錄的具體存儲位置，也不需要考慮何時執(zhí)行對外存的讀寫命令。VSAM文件結(jié)構(gòu)三部分組成：索引集、順序集和數(shù)據(jù)集。12.4ISAM文件和VSAM文件B+樹59971544597297101521374451596372859197索引集順序集數(shù)據(jù)集控制區(qū)間控制區(qū)域VSAM文件的檢索在控制區(qū)間上存取一個記錄時，需從控制區(qū)間兩端出發(fā)，同時向中間掃描。VSAM文件的插入新記錄插入到相應(yīng)的控制區(qū)間內(nèi)，移動其它記錄，保持有序；控制區(qū)已滿時，要進行控制區(qū)的分裂，即將一半的記錄移入另一個控制區(qū)間，并修改順序集中相應(yīng)索引。VSAM文件的刪除刪除記錄時，需將同一控制區(qū)間中記錄關(guān)鍵字較大的記錄向前移動，把空間留給以后插入的新記錄?？刂茀^(qū)間變空時，則需修改順序集中相應(yīng)的索引項。12.4ISAM文件和VSAM文件VSAM文件缺點占有較多的存儲空間，一般只能保持約76%的存儲空間利用率。VSAM文件優(yōu)點動態(tài)地分配和釋放存儲空間，不需要對文件進行重組。能較快地對插入的記錄進行查找，查找一個后插入的記錄和查找一個原有記錄的時間是相同的。12.4ISAM文件和VSAM文件12.5直接存取文件（散列文件）直接存取文件——又稱散列文件，是由記錄的關(guān)鍵字“直接”得到記錄在外存（磁盤）上的映象地址。類似于構(gòu)造一個哈希表，根據(jù)文件中關(guān)鍵碼的特點設(shè)計一種“哈希函數(shù)”和“處理沖突的方法”，然后將記錄散列到外存儲設(shè)備上，故稱“散列文件”。散列文件由若干個"桶"組成，根據(jù)設(shè)定的哈希函數(shù)將記錄"映象"到某個桶號。處理沖突通常采用鏈地址法，即每個桶可以包括一個或幾個頁塊，頁塊之間以指針相鏈。每個頁塊中的記錄個數(shù)則由邏輯記錄和物理記錄的大小決定。例如：假設(shè)有18個記錄，它們的關(guān)鍵碼分別為：278,109,063,930,589,184,505,269,008,083,164,215,330,810,620,110,384,355。12.5直接存取文件設(shè)哈希文件中桶的個數(shù)為7，則可設(shè)哈希函數(shù)為keyMOD7，假設(shè)每個頁塊可以容納2個記錄，則所得散列文件如圖所示。圖中左側(cè)為桶目錄表，它由m個指針組成，分別指向第0至第m-1個桶的第一個頁塊。若某記錄的關(guān)鍵碼為kval，哈希函數(shù)為H，則H(kval)為桶號。主關(guān)鍵字文件的特點在對文件進行檢索操作時，不僅對主關(guān)鍵字進行簡單詢問，還經(jīng)常需要對次關(guān)鍵字進行其他類型的詢問檢索。因此，對多關(guān)鍵字文件，尚需建立一系列的次關(guān)鍵字索引。次關(guān)鍵字索引與主關(guān)鍵字索引所不同每個索引項應(yīng)包含次關(guān)鍵字、具有同一次關(guān)鍵字的多個記錄的主關(guān)鍵字或或物理記錄號。多重表文件和倒排文件是兩種多關(guān)鍵字文件的組織方法。12.6多關(guān)鍵字文件多重表文件（Multilistfile）的特點記錄按主關(guān)鍵字的順序構(gòu)成一個串聯(lián)文件，建立主關(guān)鍵字的索引（稱為主索引）；對每個次關(guān)鍵字項建立次關(guān)鍵字索引（稱為次索引），所有具有同一次關(guān)鍵字的記錄構(gòu)成一個鏈表。主索引為非稠密索引（一組記錄建立一個索引項），次索引為稠密索引（每個記錄建立一個索引項）。每個索引包括次關(guān)鍵字、頭指針和鏈表長度。在多重表中插入一個新記錄是很容易的，只要修改指針，將記錄插在鏈表的頭指針之后。但是，要刪去一個記錄卻很繁瑣，需要在每個次關(guān)鍵字的鏈表中刪去該記錄。12.6多關(guān)鍵字文件12.6.2倒排文件倒排文件（Invertedfile）和多重表文件的區(qū)別次關(guān)鍵字索引的結(jié)構(gòu)不同。倒排表倒排文件中的次關(guān)鍵字索引。在倒排表的索引項中沒有頭指針和鏈表長度項，而直接用一項存放具有同一關(guān)鍵字的所有記錄的物理記錄號或主關(guān)鍵字。12.6多關(guān)鍵字文件本章小結(jié)順序文件文件中記錄的物理順序和邏輯順序一致。對順序存儲器上的順序文件只能進行順序存取；對直接存儲器上的順序文件還可按記錄號或關(guān)鍵碼進行隨機存??；如果是定長記錄的順序有序文件，還可利用折半查找進行快速存取。插入記錄可以插入在文件的末尾或先存入附加文件。刪除記錄僅在原地作標志。更新記錄需對整個文件進行復(fù)制。更多情況下對順序文件的操作是按批處理方式進行的。索引文件對文件中的每個記錄都建立一個由記錄的關(guān)鍵碼和存儲地址構(gòu)成的索引項。所有記錄的索引項構(gòu)成一個按關(guān)鍵碼有序的索引表。索引表可以是順序結(jié)構(gòu)，也可以是查找樹結(jié)構(gòu)，對索引文件可以進行直接存取或按關(guān)鍵碼存取。按關(guān)鍵碼存取時，首先在索引中進行查找，然后按索引項中指示的存儲地址進行存取。插入記錄時，記錄本身可插入在主文件的末尾，同時將相應(yīng)的索引項插入索引中恰當位置。刪除記錄僅需刪除相應(yīng)的索引項。更新記錄時，可將更新后的記錄插入在主文件的末尾，同時修改相應(yīng)的索引項。本章小結(jié)索引順序文件記錄按關(guān)鍵碼有序，只需建立非稠密索引。VSAM文件是目前大型索引順序文件的一種標準組織方式，它由索引集、順序集和數(shù)據(jù)集三部分構(gòu)成，其中數(shù)據(jù)集為主文件，順序集和索引集分別為B+樹的葉子結(jié)點和非葉結(jié)點，構(gòu)成文件的索引。對VSAM文件可進行按關(guān)鍵碼存取，也可以進行順序存取，插入或刪除記錄時則必須保持控制區(qū)間內(nèi)的記錄按關(guān)鍵