ISAM and VSAM

一、ISAM文件

索引顺序存取方法ISAM为Indexed Sequential Access Method的缩写，它是一种专为磁盘存取设计的文件组织方式。由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放再相邻的柱面上，对同一柱面，则应按盘面的次序顺序存放。例如图（a）为存放在一个磁盘组上的ISAM文件，每个柱面建立一个磁道索引，每个磁道索引由两个部分组成：基本索引和溢出索引项，如图（b）所示。每一部分都包括关键字和指针两项，前者表示该磁道中最末一个记录的关键字（在此为最大关键字），后者指示该磁道中第一个记录的位置，柱面索引的每一个索引项也由关键字和指针两部分组成，前者表示该柱面中最末一个记录的关键字（最大关键字），后者指示该柱面上的磁道索引位置。柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，则可建立柱面索引的索引——主索引。

图10-4(a) ISAM文件结构示例

图10-4(b) 磁道索引项结构

在ISAM文件上检索记录时，先从主索引出发找到相应的柱面索引，再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至找到为止；反之，若找遍该磁道而不存在该记录，则表明该文件中无此记录。

在每个柱面上还开辟了一个溢出区；并且，磁道索引项中有溢出索引项，这是为了插入记录所设置的。由于ISAM文件中记录是按关键字顺序存放的，则在插入记录时需要移动记录并将同一磁道上最末一个记录移至溢出区，同时修改磁道索引项。通常溢出区有三种设置方法：（1）集中存放——整个文件设一个大的单一的溢出区；（2）分散存放——每个柱面设一个溢出区；（3）集中与分散结合——溢出时记录先移至每个柱面各自的溢出区，待满之后再使用公共溢出区。

ISAM文件中删除记录的操作要比插入简单得多，只需找到待删除的记录，在其存储位置上作删除标记即可，而不需要移动记录或改变指针。则在经过多次的增删后，文件的结构可能变得很不合理。此时，大量的记录进入溢出区，而基本区中又浪费很多空间。因此，通常需要周期地整理ISAM文件。把记录读入内存，重新排列，复制成一个新的ISAM文件，填满基本区而空出溢出区。

 

二、VSAM文件

虚拟存储存取方法VSAM是Virtual Storage Access Method的缩写。这种存取方法利用了操作系统的虚拟存储器的功能，给用户提供方便。对用户来说，文件只有控制区间和控制区域等逻辑存储单元，与外存储器中柱面、磁道等具体存储单元没有必要的联系。用户在存取文件中的记录时，不需要考虑这个记录的当前位置是否在内存，也不需要考虑何时执行对外存进行“读/写”的指令。

VSAM文件的结构如图（C）所示。它由三个部分组成：索引集、顺序集和数据集。

图10-4(c) VSAM文件的结构示意图

文件的记录均存放在数据集中，数据集中的一个结点称为控制区间，它是一个I/O操作的基本单位，它由一组连续的存储单元组成。控制区间的大小可随文件不同而不同，但同一文件上控制区间的大小相同。每个控制区间含有一个或多个关键字递增有序排列的记录。顺序集和索引集一起构成一棵B+树，为文件的索引部分。顺序集中存放每个控制区间的索引项。每个控制区间的索引项由两部分信息组成，即该控制区间中的最大关键字和指向控制区间的指针。若干相邻控制区间的索引项形成顺序集中的一个结点，结点之间用指针相链结，而每个结点有在其上一层的结点中建有索引，且逐层向上建立索引，所有的索引项都由最大关键字和指针两个部分信息组成。因此，VSAM文件既可在顺序集中进行顺序存取，又可从最高层的索引出发进行按关键字存取。顺序集中一个结点连同其对应的所有控制区间形成一个整体，称做控制区域。每个控制区间可视为一个逻辑磁道，而每个控制区域可视为一个逻辑柱面。

VSAM文件中没有溢出区，解决插入的办法是在初建文件时留有空间。一是每个控制区间内没有填满记录，而是在最末一个记录和控制信息之间留有空隙；二是在每个控制区域中有一些完全空的控制区间，并在顺序集的索引中指明这些空区间。当插入新记录时，大多数的新记录能插入到相应的控制区间内。但要注意为了保持区间内记录的关键字自小至大有序，则需将区间内关键字大于插入记录关键字的向控制信息的方向移动。若在若干记录插入之后控制区间已满，则在下一个记录插入时要进行控制区间的分裂，即将近乎一半的记录移到同一控制区域中全空的控制区间中，并修改顺序集中相应索引。倘若控制区域中已经没有全空的控制区间，则要进行控制区域的分裂，此时顺序集中的结点亦要分裂，由此尚需修改索引集中的结点信息。但由于控制区间很大，很少发生分裂的情况。

在VSAM文件中删除记录时，需将同一控制区间中较删除记录关键字大的记录向前移动，把空间留给以后插入新的记录。若整个控制区间变空，则需修改顺序集中相应的索引项。

由此可见，VSAM文件占有较多的存储空间，一般只能保持约75％的存储空间利用率。但它的优点是：动态地分配和释放存储，不需要对文件进行重组，并能较快地对插入的记录进行查找，查找一个后插入记录的时间与查找一个原有记录的时间是相同的。