索引顺序文件是顺序文件的扩展，其中各记录本身在介质上也是顺序排列的，它包含了直接处理和修改记录的能力。索引顺序文件能像顺序文件一样进行快速顺序处理，既允许按物理存放次序（记录出现的次序），也允许按逻辑顺序（由记录主关键字决定的次序）进行处理。索引顺序文件通常用树结构来组织索引。索引结构形成后，根据在系统运行时索引结构是否变化，又分为静态索引结构和动态索引结构。前者以 ISAM文件为代表，后者以VSAM为代表。ISAM文件和VSAM文件最常用的索引顺序文件。

ISAM为Indexed Sequential Access Methed（索引顺序存取方法）的缩写，它是一种专为磁盘存取文件设计的文件组织方式，采用静态索引结构。由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可对磁盘上的数据文件建立盘组、柱面和磁道多级索引。

ISAM文件由多级主索引、柱面索引、磁道索引和主文件组成。文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上。对同一柱面，则应按盘面的次序顺序存放。右图1所示的文件是存放在同一个磁盘组上的ISAM文件。

从图中可看出，主索引是柱面索引的索引，这里只有一级主索引。若文件占用的柱面索引很大，使得一级主索引也很大时，可采用多级主索引。当然，若柱面索引较小时，则主索引可省略。

通常主索引和柱面索引放在同一个柱面上，主索引放在该柱面最前的一个磁道上，其后的磁道中存放柱面索引。每个存放主文件的柱面都建立有一个磁道索引，放在该柱面的最前面的磁道上，其后的若干个磁道是存放主文件记录的基本区，该柱面最后的若干个磁道是溢出区。基本区中的记录是按主关键字大小顺序存储的，溢出区被整个柱面上的基本区中各磁道共享，当基本区中某磁道溢出时，就将该磁道的溢出记录，按主关键字大小链成一个链表（以下简称溢出链表）放入溢出区。

磁道索引中的每一个索引项，都由两个子索引项组成：基本索引和溢出索引项，如下图2所示。

在ISAM文件上检索记录时，从主索引出发，找到相应的柱面索引，从柱面索引找到记录所在柱面的磁道索引，从磁道索引找到记录所在磁道的起始地址，由此出发在该磁道上进行顺序查找，直到找到为止。若找遍该磁道均不存在此记录，则表明该文件中无此记录；若被查找的记录在溢出区，则可从磁道索引项的溢出索引项中得到溢出链表的头指针，然后对该表进行顺序查找。

当插人新记录时，首先找到它应插入的磁道。若该磁道不满，则将新记录插入该磁道的适当位置上即可；若该磁道已满，则新记录或者插在该磁道上，或者直接插入到该磁道的溢出链表上。插入后，可能要修改磁道索引中的基本索引项和溢出索引项。

VSAM是Virtual Storage AccessMethod（虚拟存储存取方法）的缩写，它也是一种索引顺序文件的组织方式，采用B+树作为动态索引结构。

VSAM文件的结构由三部分组成：索引集，顺序集和数据集，如右图3所示。

1、数据集

文件的记录均存放在数据集中。数据集中的一个结点称为控制区间（ControlInterval），它是一个I/O操作的基本单位，它由一组连续的存储单元组成。控制区间的大小可随文件的不同而不同，但同一个文件上的控制区间大小相同。每个控制区间含有一个或多个按关键字递增有序排列的数据记录。

2、顺序集和索引集

顺序集和索引集一起构成一棵B+树，作为文件的索引部分。顺序集中存放的每个控制区间的索引项由两部分信息组成：该控制区间中的最大关键字和指向控制区间的指针。若干相邻的控制区间的索引项，形成顺序集中的一个结点。结点之间用指针相链接，而每个结点又在其上一层的结点中建有索引，且逐层向上建立索引，所有的索引项都由最大关键字和指针两部分信息组成。这些高层的索引项形成B+树的非终端结点。

VSAM文件既可在顺序集中进行顺序存取，又可从最高层的索引（B+树的根结点）出发，进行按关键字的随机存取。顺序集中一个结点连同其对应的所有控制区间形成一个整体，称做控制区域（ControlRange）。它相当于ISAM文件中的一个柱面，而控制区间相当于一个磁道。

3、VSAM文件中控制区间的结构

在VSAM文件中，记录可以是不定长的。因而在控制区间中，除了存放记录本身之外，还有每个记录的控制信息（如记录的长度等）和整个区间的控制信息（如区间中存放的记录数等），控制区间的结构如下表所示。

VSAM文件中没有溢出区，解决插入的方法是在初建文件时留出空间：一是每个控制区间内并不填满记录，而是在最末一个记录和控制信息之间留有空隙；二是在每个控制区域中有一些完全空的控制区间，并在顺序集的索引中指明这些空区间。

当插入新记录时，大多数的新记录能插入到相应的控制区间内，但要注意：为了保持区间内记录的关键字从小至大有序，则需将区间内关键字大于插入记录关键字的记录，向控制信息的方向移动。若在若干记录插入之后控制区间已满，则在下一个记录插入时，要进行控制区间的分裂，即把近乎一半的记录移到同一控制区域内全空的控制区间中，并修改顺序集中相应索引。倘若控制区域中已经没有全空的控制区间，则要进行控制区域的分裂，此时顺序集中的结点亦要分裂，由此需要修改索引集中的结点信息。但由于控制区域较大，通常很少发生分裂的情况。

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

和ISAM文件相比，基于B+树的VSAM文件有如下优点：能保持较高的查找效率，查找一个后插入记录和查找一个原有记录具有相同的速度；动态地分配和释放存储空间，可以保持平均75%的存储利用率，而且永远不必对文件进行再组织。因而基于B+树的VSAM文件，通常被作为大型索引顺序文件的标准组织。