1.ISAM文件

????????索引順序存取方法ISAM 為Indexed Sequential Access Methed的縮寫,它是一種專為磁盤存取設計的文件組織方式。由于磁盤是以盤組,柱面和磁道三級地址存取的設備，則可對磁盤上的數據文件建立盤組、柱面和磁道R三級索引。文件的記錄在同一盤組上存放時,應先集中放在一個柱面上,然后再順序存放在相鄰的柱面上,對同一柱面,則應按盤面的次序順序存放。例如圖1為存放在一個磁盤組上的ISAM文件,每個柱面建立一個磁道索引,每個磁道索引項由兩部分組成:基本索引項和溢出索引項,如圖2所示,每一部分都包括關鍵字和指針兩項,前者表示該磁道中最末一個記錄的關鍵字(在此為最大關鍵字),后者指示該磁道中第一個記錄的位置,柱面索引的每一個索引項也由關鍵字和指針兩部分組成,前者表示該柱面中最末一個記錄的關鍵字(最大關鍵字),后者指示該柱面上的磁道索引位置。柱面索引存放在某個柱面上,若柱面索引較大,占多個磁道時,則可建立柱面索引的索引一主索引。

????????在ISAM文件上檢索記錄時,先從主索引出發找到相應的柱面索引,再從柱面索引找到記錄所在柱面的磁道索引,最后從磁道索引找到記錄所在磁道的第一個記錄的位置，由此出發在該磁道上進行順序查找直至找到為止;反之,若找遍該磁道而不存在此記錄,則表明該文件中無此記錄。例如,查找關鍵字為21的記錄時的查找路徑如圖1中的粗實線所示。

圖1 ISAM文件結構示例

?????????從圖1中可看到,每個柱面上還開辟有一個溢出區;并且,磁道索引項中有溢出索引項,這是為插入記錄所設置的。由于ISAM文件中記錄是按關鍵字順序存放的，則在插入記錄時需移動記錄,并將同一磁道上最末一個記錄移至溢出區,同時修改磁道索引項。通常溢出區可有3種設置方法:(1)集中存放——整個文件設一個大的單一的溢出區;(2)分散存放——每個柱面設一個溢出區;(3)集中與分散相結合—溢出時記錄先移至每個柱面各自的溢出區,待滿之后再使用公共溢出區。圖1是第二種設置法。

圖2 磁道索引項結構

????????每個柱面的基本區是順序存儲結構,而溢出區是鏈表結構。同一磁道溢出的記錄由指針相鏈,該磁道索引的溢出索引項中的關鍵字指示該磁道溢出的記錄的最大關鍵字;而指針則指示在溢出區中的第一個記錄。圖3所示為插入記錄和溢出處理的具體例子。其中(a)為插人前的某一柱面上的狀態;(b)為插入 時,將第二道中關鍵字大于65的記錄順次后移,且使 溢出至溢出區的情況;(c)為插入 之后的狀態,此時2道的基本索引項的關鍵字改為80,且溢出索引項的關鍵字改為90,其指針指向第4道第一個記錄即 ;(d)是相繼插入和后的狀態, 插入在第3道的第一個記錄的位置而使溢出。而由于80<83≤90,則Rss被直接插入到溢出區,作為第⒉道在溢出區的第一個記錄,并將它的指針指向Rz的位置,同時修改第⒉道索引的溢出索引項的指針指向 。

圖3 ISAM文件的插入和溢出處理 (a)插入前；（b）插入R65時記錄移動的情形；（c）插入R65后；（d）先插入R95再插入R83后

????????ISAM文件中刪除記錄的操作要比插人簡單得多,只需找到待刪除的記錄,在其存儲位置上作刪除標記即可,而不需要移動記錄或改變指針,但在經過多次的增刪后,文件的結構可能變得很不合理。此時,大量的記錄進入溢出區,而基本區中又浪費很多空間。因此,通常需要周期地整理ISAM文件。把記錄讀入內存,重新排列,復制成一個新的ISAM文件,填滿基本區而空出溢出區。

????????通常,磁道索引放在每個柱面的第一道上,那么,柱面索引是否也放在文件的第一個柱面上呢?由于每一次檢索都需先查找柱面索引,則磁頭需在各柱面間來回移動,我們希望磁頭移動距離的平均值最小。假設文件占有n個柱面,柱面索引在第α柱面上。則磁頭移動距離的平均值為:

????????令 ?，得到x= 。這就是說,柱面索引應放在數據文件的中間位置的柱面上。

2. VSAM文件

????????虛擬存儲存取方法VSAM是Virtual Storage Access Method 的縮寫。這種存取方法利用了操作系統的虛擬存儲器的功能,給用戶提供方便。對用戶來說,文件只有控制區間和控制區域等邏輯存儲單位,與外存儲器中柱面、磁道等具體存儲單位沒有必然的聯系。用戶在存取文件中的記錄時,不需要考慮這個記錄的當前位置是否在內存,也不需要考慮何時執行對外存進行“讀/寫”的指令。

VSAM文件的結構如圖4所示。它由3部分組成:索引集、順序集和數據集。

圖4 VSAM文件的結構示意圖

?????????文件的記錄均存放在數據集中,數據集中的一個結點稱為控制區間(Control Interval),它是一個I/O操作的基本單位,它由一組連續的存儲單元組成?？刂茀^間的大小可隨文件不同而不同,但同--文件上控制區間的大小相同。每個控制區間含有一個或多個按關鍵字遞增有序排列的記錄。順序集和索引集一起構成一棵B+樹,為文件的索引部分。順序集中存放每個控制區間的索引項。每個控制區間的索引項由兩部分信息組成,即該控制區間中的最大關鍵字和指向控制區間的指針。若干相鄰控制區間的索引項形成順序集中的一個結點,結點之間用指針相鏈結,而每個結點又在其上一層的結點中建有索引,且逐層向上建立索引。所有的索引項都由最大關鍵字和指針兩部分信息組成,這些高層的索引項形成B+樹的非終端結點。因此，VSAM文件既可在順序集中進行順序存取,又可從最高層的索引(B+樹的根結點)出發進行按關鍵字存取。順序集中一個結點連同其對應的所有控制區間形成一個整體,稱做控制區域(Control Range)。每個控制區間可視為一個邏輯磁道,而每個控制區域可視為一個邏輯柱面。

????????在VSAM文件中,記錄可以是不定長的,則在控制區間中除了存放記錄本身以外,還有每個記錄的控制信息(如記錄的長度等)和整個區間的控制信息(如區間中存有的記錄數等),控制區間的結構如圖5所示。在控制區間上存取一個記錄時需從控制區間的兩端出發同時向中間掃描。

圖5 控制區間的結構示意圖

?????????VSAM文件中沒有溢出區,解決插人的辦法是在初建文件時留有空間。一是每個控制區間內不填滿記錄,在最末一個記錄和控制信息之間留有空隙;二是在每個控制區域中有一些完全空的控制區間,并在順序集的索引中指明這些空區間。當插入新記錄時,大多數的新記錄能插入到相應的控制區間內,但要注意為了保持區間內記錄的關鍵字自小至大有序,則需將區間內關鍵字大于插入記錄關鍵字的記錄向控制信息的方向移動。若在若干記錄插入之后控制區間已滿,則在下一個記錄插人時要進行控制區間的分裂,即將近乎一半的記錄移到同一控制區域中全空的控制區間中,并修改順序集中相應索引。倘若控制區域中已經沒有全空的控制區間,則要進行控制區域的分裂,此時順序集中的結點亦要分裂,由此尚需修改索引集中的結點信息。但由于控制區域較大,很少發生分裂的情況。

????????在VSAM文件中刪除記錄時,需將同一控制區間中較刪除記錄關鍵字大的記錄向前移動,把空間留給以后插入的新記錄。若整個控制區間變空,則需修改順序集中相應的索引項。

????????由此可見,VSAM文件占有較多的存儲空間，一般只能保持約75%的存儲空間利用率。但它的優點是:動態地分配和釋放存儲空間,不需要對文件進行重組,并能較快地對插人的記錄進行查找,查找一個后插人記錄的時間與查找一個原有記錄的時間是相同的。

????????為了作性能上的優化,VSAM用了一些其他的技術,如指針和關鍵字的壓縮、索引的存放處理等。

然后今天就講到這里啦，大家記得點贊收藏，分享轉發，關注小哥哥哦！ 最后，如果你想學或者正在學C/C++編程，可以加入小編的編程學習C/C++企鵝圈https://jq.qq.com/?_wv=1027&k=vLNylJeG

總結

以上是生活随笔為你收集整理的数据结构之ISAM文件和VSAM文件的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。