ISAM File and VSAM File
ISAM: 索引顺序存取方法 (Indexed Sequential Access Method)
VSAM: 虚拟存取方法 (Virtual Storage Access Method)
ISAM文件
ISAM是一种专门为磁盘存取设计的文件组织方式。
一般对磁盘上的数据文件建立盘组、柱面和磁道三级索引(因为磁盘是以盘组、柱面和磁道三级地址存取的设备)。
文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上，对同一柱面，则应按盘面的次序 顺序存放。
文件结构
每个柱面建立一个磁道索引，每个磁道索引由两部分组成：基本索引项和溢出索引项(每一部分都包括关键字和指针两项，前者表示该柱面中最末一个记录的关键字(最大关键字)，后者指示该磁道中第一个记录的位置)。
柱面索引的每一个索引项也由关键字和索引两部分组成，前者表示该柱面中最末一个记录的关键字(最大关键字)，后者指示该柱面上的磁道索引位置。
柱面索引放在某个柱面上，若柱面索引较大，占多个磁道时，则可建立柱面索引的索引——主索引。
检索
在ISAM文件中如何检索记录呢？
- 从主索引出发找到相应的柱面索引；
- 从柱面索引找到记录所在柱面的磁道索引；
- 从磁道索引找到记录所在磁道的第一个记录的位置；
- 由此在该磁道上进行顺序查找直到找到为止；反之，找遍该磁道而不存在此记录，则表明该文件中无此记录。
下面是图，please配合食用：
插入和溢出
从上图可以看到，每个柱面上还开辟有一个溢出区；并且，磁道索引项中有溢出索引项，这是为插入记录所设置的。
由于ISAM文件中记录是按关键字顺序存放，则在插入记录时，需要移动记录，并将同一磁道上最末一个记录移至溢出区，同时修改磁道索引。(“磁道索引”相关内容在上文“文件结构”一部分中有提到，原因也在里头)
溢出区的3种设置方法：
- 集中存放。整个文件设一个大的单一的溢出区；
- 分散存放。每个柱面设一个溢出区；
- 集中与分散相结合。溢出时记录先移至每个柱面各自的溢出区，待满之后再使用公共溢出区。
(上文图中使用的是第二种设置方法)
每个柱面的基本区是顺序存储结构，而溢出区是链表结构。同一磁道溢出的记录由指针相连，该磁道索引的溢出索引项中的关键字指示该磁道溢出记录的最大关键字；而指针则指示在溢出区中的第一个记录。
下面是ISAM文件的插入和溢出处理：
删除
ISAM文件中，删除记录的操作要比插入简单的多，只需找到待删除的记录，在其存储位置上作删除记录即可，而不需要移动记录或改变指针。
但经过多次的增删后，文件的结构可能变得很不合理。此时，大量的记录进入溢出区，而基本区中又浪费很多空间。
通常需要周期地整理ISAM文件。-> 把记录读入内存，重新排列，复制成一个新的ISAM文件，填满基本区而空出溢出区。
柱面索引的位置
由于每一次检索都需要先查找柱面索引，而磁头需在各柱面间来回移动。 -> 我们希望磁头移动距离的平均值最小。
假设文件占有n个柱面，柱面索引在第x柱面上。
磁头移动距离的平均值为：
令 ，得到
。
上述计算结果说明，柱面索引应放在数据文件的中间位置的柱面上。
VSAM文件
VSAM利用了操作系统的虚拟存储器的功能，给用户提供了方便。
为什么给用户提供了方便呢？ 因为对用户来说，文件只有控制区间和控制区域等逻辑存储单元，与外存储器中柱面、磁道等具体存储单位没有必然的联系。用户在存取文件中，不需要考虑这个记录的当前位置是否在内存，也不需要考虑何时对外存进行“读/写”的指令。
文件结构
从上图，可以看出VSAM文件结构由3部分组成：索引集、顺序集和数据集。
文件结构的详细介绍
文件的记录均存放在数据集中，数据集中的一个结点称为控制区间(Control Interval)。
控制区间：
- 一个I/O操作的基本单位；
- 由一组连续的存储单元组成；
- 大小可随文件不同而不同，但同一文件上控制区间的大小相同；
- 每个控制区间含有一个或多个按关键字递增有序排列的记录。
顺序集和索引集一起构成一棵树，为文件的索引部分。
顺序集：
- 存放每个控制区间的索引项；
- 每个控制区间的索引项由两部分信息组成(该控制区间中的最大关键字和指向控制区间的指针)；
- 若干相邻控制区间的索引项形成顺序集中的一个结点，结点之间用指针相链接，而每个结点又在其上一层的结点中建有索引，且逐层向上建立索引；
- 逐层向上建立的所有的索引都由最大关键字和指针两部分信息组成，这些高层的索引项形成
树的非终端结点。
因此，从上述内容，我们可以知道，VSAM文件即可在顺序集中进行顺序存取，又可从最高层的索引(
控制区域：
- 顺序集中一个结点连同其对应的所有控制区间形成一个整体，称作控制区域(Control Range)。
- 每个控制区间可视为一个逻辑磁道，每个控制区域可视为一个逻辑柱面。
VSAM文件中，记录可以是不定长的，则在控制区间中除了存放记录本身以外，还要存放每个记录的控制信息和整个区间的控制信息(如区间中存有的记录数等)，控制区间的结构如下图所示。
(在控制区间上存取一个记录时需要从控制区间的两端出发同时向中间扫描)
插入和溢出
VSAM文件中没有溢出区，解决插入的方法：初建文件时留有空间。
- 方法一：每个控制区间内不填满记录，在最末一个记录和控制信息之间留有空隙(仔细看上图)；
- 方法二：在每个控制区域中有一些完全空的控制区间，并在顺序集的索引中指明这些空区间。
当插入新纪录时，大多数的新纪录能插入到相应的控制区间内，但要注意，为了保持区间内记录的关键字自小至大有序，则需将区间内关键字大于插入记录关键字的记录向控制信息的方向移动(仔细看上图)。
分裂
若在若干记录插入之后控制区间已满，则在下一个记录插入时要进行控制区间的分裂。
控制区间的分裂：将近乎一半的记录移到同一控制区域中全空的控制区间中，并修改顺序集中相应的索引。
倘若控制区域中已无全空的控制区间，则要进行控制区域的分裂。
控制区域的分裂：此时顺序集中的结点亦需分裂，所以还要修改索引集中的结点信息。(但由于控制区域较大，很少发生控制区域分裂的情况)
删除
在VSAM文件中删除记录：将同一控制区间中较删除记录关键字大的记录向前移动，把空间留给以后插入的新记录。若整个控制区域变空，则需修改顺序集中相应的索引项。
优缺点
缺点：
VSAM文件占有较多的存储空间，一般只能保持约75%的存储空间利用率。
优点：
动态地分配和释放存储空间，不需要对文件进行重组，并能较快地对插入的记录进行查找(查找一个后插入记录的时间和查找一个原有记录的时间是相同的)。
为了作性能上的优化，VSAM用了其他的技术，如指针和关键字的压缩、索引的存放处理等。详细情况自行查询。