第十二章學習目標熟悉各類文件的特點，構造方法以及如何實現檢索，插入和刪除等操作。重點和難點重點：了解各種文件的結構特點及其適用場合。知識點順序文件、索引文件、索引順序文件、VSAM文件、散列文件、多關鍵字文件2/5/2023112.1有關文件的基本概念文件(File)是由大量性質相同的記錄組成的集合，一般放在外存上。記錄是數據項的集合，是可存取的數據的基本單位。數據項由一個或多個位或字節組成，是不可分割的數據最小單位。定長記錄文件文件中每個記錄含有的信息長度相等。不定長文件文件中含有信息長度不等的不定長記錄。2/5/20232單關鍵字文件文件中的記錄只有一個唯一標識記錄的主關鍵字。多關鍵字文件文件中的記錄除了含有一個主關鍵字外，還含有若干個次關鍵字。記錄的屬性記錄中所有非關鍵字的數據項。記錄的邏輯結構記錄在用戶或應用程序員面前呈現的方式，是用戶對數據的表示和存取方式。記錄的物理結構數據在物理存儲器上存儲的方式，是數據的物理表示和組織。2/5/20233物理記錄計算機用一條I/0命令進行讀寫的基本數據單位（物理塊）。物理記錄和邏輯記錄之間可能存在下列三種關系：一個物理記錄存放一個邏輯記錄；一個物理記錄包含多個邏輯記錄；多個物理記錄表示一個邏輯記錄。文件的檢索方式順序存取：存取下一個邏輯記錄。直接存取；存取第i個邏輯記錄。按關鍵字存取：簡單查詢、區域查詢、函數查詢、布爾查詢2/5/20234文件的修改記錄的插入、刪除、修改。文件的物理結構文件在外存上的組織方式。順序組織隨機組織鏈組織2/5/2023512.2順序文件順序文件定義

記錄按其在文件中的邏輯順序依次進入存儲介質而建立的，即物理記錄和邏輯記錄的順序是一致的。分類連續（順序）文件次序相繼的兩個物理記錄在存儲介質上的存儲位置是相鄰的。串聯（順序）文件物理記錄之間的次序由指針相鏈表示。2/5/20236特點存取第i個記錄，必須先搜索在它之前的i-1個記錄。新的記錄只能加在文件末尾。更新記錄，必須將整個文件復制。優點連續存取的速度快，主要用于只進行順序存取、批量修改的情況。存取設備磁帶適合于文件的數據量大、平時記錄變化少、只作批量修改的情況。磁盤2/5/2023712.3索引文件引入原因對于按關鍵字存取得記錄結構，順序查找和折半查找的速度很慢。為了避免大量與外存打交道，可以保存一個索引表來指示關鍵字與記錄地址之間的對應關系。索引文件包括數據區和索引表兩部分。為按建立時，系統自動開辟索引區。按記錄進入的順序登記索引項。索引項指出該記錄的物理地址。最后，索引表按關鍵字排序。只能存儲在磁盤存儲設備上。2/5/202382/5/20239索引文件的檢索將索引表讀入內存（若一個物理塊可容納一個索引表，則僅一次讀入，否則需要多次讀入）；查找索引表，確定記錄的物理地址（索引表有序，可折半查找）；根據物理地址，一次讀取記錄。索引文件的修改刪除僅刪去相應的索引項。插入記錄進入數據區末尾，索引項插入索引表中（或重新排序）。更新刪除與插入的結合。2/5/202310多級索引記錄數目很大，導致一個物理塊容納不了索引表。此時，查找索引表需要多次訪問內存。對索引表再建立一個索引。最高可以有四級索引，此時檢索需要訪問外存5次。2/5/20231112.4ISAM文件和VSAM文件ISAM文件（索引順序存取法）是一種專為磁盤存取而設計的文件組織方式。由于磁盤是以盤組、柱面和磁道三級地址存取的設備，則可對磁盤上的數據文件建立盤組、柱面和磁道三級索引。文件的記錄在同一盤組上存放時，應先集中放在一個柱面上，然后再順序存放在相鄰的柱面上，對同一柱面，則應按盤面的次序順序存放。用這種方法建立起來的索引文件稱為ISAM文件。包括：索引區、數據基本區、數據溢出區。2/5/202312數據區索引區溢出區2/5/202313ISAM文件的檢索查主索引（駐內存），將相應柱面索引（在其柱面上）調用內存。查柱面索引，將磁道索引（一般放在第0道上）調入內存；查磁道索引，將本磁道上的所有記錄送入內存；順序對這一組記錄查找。ISAM文件的插入定位應插入的磁道；按關鍵字順序插入新紀錄，將同一磁道上最后一個記錄移至溢出區；同時修改磁道索引項。2/5/202314ISAM文件的刪除找到待刪除的記錄，在其存儲位置上作刪除標記即可，而不需要移動記錄或改變指針。ISAM文件的整理經過多次的增刪后，文件的結構可能變得很不合理。此時，大量得記錄進入溢出區，而基本區中又浪費很多空間。因此，通常需要周期地整理ISAM文件。把記錄讀入內存，重新排列，復制成一個新的ISAM文件，填滿基本區而空出溢出區。2/5/20231512.4.2VSAM文件VSAM（虛擬存儲存取方法）利用了操作系統的虛擬存儲器的功能，給用戶提供方便。對用戶來說，存儲記錄時不需要考慮記錄的具體存儲位置，也不需要考慮何時執行對外存的讀寫命令。VSAM文件結構三部分組成：索引集、順序集和數據集。2/5/202316B+樹59971544597297101521374451596372859197索引集順序集數據集控制區間控制區域2/5/202317VSAM文件的檢索在控制區間上存取一個記錄時，需從控制區間兩端出發，同時向中間掃描。VSAM文件的插入新記錄插入到相應的控制區間內，移動其它記錄，保持有序；控制區已滿時，要進行控制區的分裂，即將一半的記錄移入另一個控制區間，并修改順序集中相應索引。VSAM文件的刪除刪除記錄時，需將同一控制區間中記錄關鍵字較大的記錄向前移動，把空間留給以后插入的新記錄。控制區間變空時，則需修改順序集中相應的索引項。2/5/202318VSAM文件缺點占有較多的存儲空間，一般只能保持約76%的存儲空間利用率。VSAM文件優點動態地分配和釋放存儲空間，不需要對文件進行重組。能較快地對插入的記錄進行查找，查找一個后插入的記錄和查找一個原有記錄的時間是相同的。2/5/20231912.5直接存取文件（散列文件）散列文件特點由記錄的關鍵碼“直接”得到記錄在外存（磁盤）上的映象地址。類似哈希表，根據文件中關鍵碼的特點設計一種“哈希函數”和“處理沖突的方法”，然后將記錄散列到外存儲設備上，故稱“散列文件”。桶散列文件的存儲單位，以磁道或塊為單位，由若干個記錄組成。基桶一個桶能存放m個記錄，表示這m個有相同哈希函數值的記錄具有同一個桶地址，該桶稱為“基桶”。溢出桶當發生“溢出”時，需要將第m+1個同義詞存放到另一個桶中。2/5/202320溢出桶可以有多個，它們和基桶大小相同，相互之間用指針相鏈接。當在基桶中沒有找到待查記錄時，就順指針所指到溢出桶中進行查找。因此，希望同一散列地址的溢出桶和基桶在磁盤上的物理位置不要相距太遠，最好在同一柱面上。2/5/20232112.6多關鍵字文件主關鍵字文件的特點在對文件進行檢索操作時，不僅對主關鍵字進行簡單詢問，還經常需要對次關鍵字進行其他類型的詢問檢索。因此，對多關鍵字文件，尚需建立一系列的次關鍵字索引。次關鍵字索引與主關鍵字索引所不同每個索引項應包含次關鍵字、具有同一次關鍵字的多個記錄的主關鍵字或或物理記錄號。多重表文件和倒排文件是兩種多關鍵字文件的組織方法。2/5/20232212.6.1多重表文件多重表文件（Multilistfile）的特點記錄按主關鍵字的順序構成一個串聯文件，建立主關鍵字的索引（稱為主索引）；對每個次關鍵字項建立次關鍵字索引（稱為次索引），所有具有同一次關鍵字的記錄構成一個鏈表。主索引為非稠密索引（一組記錄建立一個索引項），次索引為稠密索引（每個記錄建立一個索引項）。每個索引包括次關鍵字、頭指針和鏈表長度。在多重表中插入一個新記錄是很容易的，只要修改指針，將記錄插在鏈表的頭指針之后。但是，要刪去一個記錄卻很繁瑣，需要在每個次關鍵字的鏈表中刪去該記錄。2/5/2023232/5/20232412.6.2倒排文件倒排文件（Invertedfile）和多重表文件的區別次關鍵字索引的結構不同。倒排表倒排文件中的次關鍵字索引。在倒排表的索引項中沒有頭指針和鏈表長度項，而直接用一項存放具有同一關鍵字的所有記錄的物理記錄號或主關鍵字。2/5/2023252/5/202326本章小結順序文件文件中記錄的物理順序和邏輯順序一致。對順序存儲器上的順序文件只能進行順序存取；對直接存儲器上的順序文件還可按記錄號或關鍵碼進行隨機存取；如果是定長記錄的順序有序文件，還可利用折半查找進行快速存取。插入記錄可以插入在文件的末尾或先存入附加文件。刪除記錄僅在原地作標志。更新記錄需對整個文件進行復制。更多情況下對順序文件的操作是按批處理方式進行的。2/5/202327索引文件對文件中的每個記錄都建立一個由記錄的關鍵碼和存儲地址構成的索引項。所有記錄的索引項構成一個按關鍵碼有序的索引表。索引表可以是順序結構，也可以是查找樹結構，對索引文件可以進行直接存取或按關鍵碼存取。按關鍵碼存取時，首先在索引中進行查找，然后按索引項中指示的存儲地址進行存取。插入記錄時，記錄本身可插入在主文件的末尾，同時將相應的索引項插入索引中恰當位置。刪除記錄僅需刪除相應的索引項。更新記錄時，可將更新后的記錄插入在主文件的末尾，同時修改相應的索引項。2/5/202328索引順序文件記錄按關鍵碼有序，只需建立非稠密索引。VSAM文件是目前大型索引順序文件的一種標準組織方式，它由索引集、順序集和數據集三部分構成，其中數據集為主文件，順序集和索引集分別為B+樹的葉子結點和非葉結點，構成文件的索引。對VSAM文件可進行按關鍵碼存取，也可以進行順序存取，插入或刪除記錄時則必須保持控制區間內的記錄按關鍵碼有序，需在控制區間內進行記錄的移動。優點：動態地分配和釋放存儲空