索引順序檔案

索引順序檔案是順序檔案的擴展，其中各記錄本身在介質上也是順序排列的，它包含了直接處理和修改記錄的能力。索引順序檔案能像順序檔案一樣進行快速順序處理，既允許按物理存放次序（記錄出現的次序），也允許按邏輯順序（由記錄主關鍵字決定的次序）進行處理。索引順序檔案通常用樹結構來組織索引。索引結構形成後，根據在系統運行時索引結構是否變化，又分為靜態索引結構和動態索引結構。前者以 ISAM檔案為代表，後者以VSAM為代表。ISAM檔案和VSAM檔案最常用的索引順序檔案。

基本介紹

• 中文名：索引順序檔案
• 外文名：Indexed sequential files
• 分類：靜態索引結構和動態索引結構
• 典型代表：ISAM檔案和VSAM檔案
• 屬性：順序檔案的擴展
• 所屬學科：信息科學

ISAM檔案

ISAM為Indexed Sequential Access Methed（索引順序存取方法）的縮寫，它是一種專為磁碟存取檔案設計的檔案組織方式，採用靜態索引結構。由於磁碟是以盤組、柱面和磁軌三級地址存取的設備，則可對磁碟上的數據檔案建立盤組、柱面和磁軌多級索引。

ISAM檔案的組成

ISAM檔案由多級主索引、柱面索引、磁軌索引和主檔案組成。檔案的記錄在同一盤組上存放時，應先集中放在一個柱面上，然後再順序存放在相鄰的柱面上。對同一柱面，則應按盤面的次序順序存放。右圖所示的檔案是存放在同一個磁碟組上的ISAM檔案。

從圖中可看出，主索引是柱面索引的索引，這裡只有一級主索引。若檔案占用的柱面索引很大，使得一級主索引也很大時，可採用多級主索引。當然，若柱面索引較小時，則主索引可省略。

通常主索引和柱面索引放在同一個柱面上，主索引放在該柱面最前的一個磁軌上，其後的磁軌中存放柱面索引。每個存放主檔案的柱面都建立有一個磁軌索引，放在該柱面的最前面的磁軌上，其後的若干個磁軌是存放主檔案記錄的基本區，該柱面最後的若干個磁軌是溢出區。基本區中的記錄是按主關鍵字大小順序存儲的，溢出區被整個柱面上的基本區中各磁軌共享，當基本區中某磁軌溢出時，就將該磁軌的溢出記錄，按主關鍵字大小鏈成一個鍊表（以下簡稱溢出鍊表）放入溢出區。

各級索引中的索引項結構

磁軌索引中的每一個索引項，都由兩個子索引項組成：基本索引和溢出索引項，如下圖所示。

ISAM檔案的檢索

在ISAM檔案上檢索記錄時，從主索引出發，找到相應的柱面索引，從柱面索引找到記錄所在柱面的磁軌索引，從磁軌索引找到記錄所在磁軌的起始地址，由此出發在該磁軌上進行順序查找，直到找到為止。若找遍該磁軌均不存在此記錄，則表明該檔案中無此記錄；若被查找的記錄在溢出區，則可從磁軌索引項的溢出索引項中得到溢出鍊表的頭指針，然後對該表進行順序查找。

ISAM檔案的插入操作

當插人新記錄時，首先找到它應插入的磁軌。若該磁軌不滿，則將新記錄插入該磁軌的適當位置上即可；若該磁軌已滿，則新記錄或者插在該磁軌上，或者直接插入到該磁軌的溢出鍊表上。插入後，可能要修改磁軌索引中的基本索引項和溢出索引項。

VSAM檔案

VSAM是Virtual Storage AccessMethod（虛擬存儲存取方法）的縮寫，它也是一種索引順序檔案的組織方式，採用B⁺樹作為動態索引結構。

VSAM檔案的結構

VSAM檔案的結構由三部分組成：索引集，順序集和數據集，如右圖所示。

1、數據集

檔案的記錄均存放在數據集中。數據集中的一個結點稱為控制區間（ControlInterval），它是一個I/O操作的基本單位，它由一組連續的存儲單元組成。控制區間的大小可隨檔案的不同而不同，但同一個檔案上的控制區間大小相同。每個控制區間含有一個或多個按關鍵字遞增有序排列的數據記錄。

2、順序集和索引集

順序集和索引集一起構成一棵B+樹，作為檔案的索引部分。順序集中存放的每個控制區間的索引項由兩部分信息組成：該控制區間中的最大關鍵字和指向控制區間的指針。若干相鄰的控制區間的索引項，形成順序集中的一個結點。結點之間用指針相連結，而每個結點又在其上一層的結點中建有索引，且逐層向上建立索引，所有的索引項都由最大關鍵字和指針兩部分信息組成。這些高層的索引項形成B+樹的非終端結點。

VSAM檔案既可在順序集中進行順序存取，又可從最高層的索引（B+樹的根結點）出發，進行按關鍵字的隨機存取。順序集中一個結點連同其對應的所有控制區間形成一個整體，稱做控制區域（ControlRange）。它相當於ISAM檔案中的一個柱面，而控制區間相當於一個磁軌。

3、VSAM檔案中控制區間的結構

在VSAM檔案中，記錄可以是不定長的。因而在控制區間中，除了存放記錄本身之外，還有每個記錄的控制信息（如記錄的長度等）和整個區間的控制信息（如區間中存放的記錄數等），控制區間的結構如下表所示。

VSAM檔案的插入方法

VSAM檔案中沒有溢出區，解決插入的方法是在初建檔案時留出空間：一是每個控制區間內並不填滿記錄，而是在最末一個記錄和控制信息之間留有空隙；二是在每個控制區域中有一些完全空的控制區間，並在順序集的索引中指明這些空區間。

當插入新記錄時，大多數的新記錄能插入到相應的控制區間內，但要注意：為了保持區間內記錄的關鍵字從小至大有序，則需將區間內關鍵字大於插入記錄關鍵字的記錄，向控制信息的方向移動。若在若干記錄插入之後控制區間已滿，則在下一個記錄插入時，要進行控制區間的分裂，即把近乎一半的記錄移到同一控制區域內全空的控制區間中，並修改順序集中相應索引。倘若控制區域中已經沒有全空的控制區間，則要進行控制區域的分裂，此時順序集中的結點亦要分裂，由此需要修改索引集中的結點信息。但由於控制區域較大，通常很少發生分裂的情況。

VSAM檔案的刪除

在VSAM檔案中刪除記錄時，需將同一控制區間中比刪除記錄關鍵字大的記錄向前移動，把空間留給以後插人的新記錄。若整個控制區間變空，則回收作空閒區間用，且需刪除順序集中相應的索引項。

VSAM檔案的優點

和ISAM檔案相比，基於B⁺樹的VSAM檔案有如下優點：能保持較高的查找效率，查找一個後插入記錄和查找一個原有記錄具有相同的速度；動態地分配和釋放存儲空間，可以保持平均75%的存儲利用率，而且永遠不必對檔案進行再組織。因而基於B⁺樹的VSAM檔案，通常被作為大型索引順序檔案的標準組織。