ISAM文件
ISAM是Indexed Sequential Access Methed(索引顺序存取方法)的缩写，它是一种专为磁盘存取设计的文件组织形式，采用的是静态索引结构。由于磁盘是以盘组、柱面和磁道三级地址存取的设备，因此可对磁盘上的数据文件建立盘组、柱面和磁道多级索引。在下面的学习中我们只讨论在同一个盘组上建立的ISAM文件。
1、ISAM文件的组成
ISAM文件由三部分组成：基本数据区、溢出区和多级索引。
基本数据区：由一个或多个柱面组成，文件的记录按关键字有序存放于柱面的每个磁道上。
溢出区：每个柱面都开出一个溢出区，为插入记录而设，当一个磁道存满记录而又要在该磁道插入记录时，就将该磁道的最后一个记录移至溢出区，再将新记录插入到此磁道的适当位置。每个磁道的溢出数据在溢出区中组成链表。
多级索引：由磁道索引、柱面索引和主索引各级结构组成。
磁道索引包括基本索引项和溢出索引项，基本索引项含本磁道的最大关键字及起始地址；溢出索引项含本磁道溢出记录的最大关键字及本磁道溢出区首地址。
柱面索引包含柱面中的最大关键字和该柱面磁道索引的起始地址。
主索引是柱面索引的索引，每个索引项包含柱面索引中一组记录最大关键字及该柱面索引项的起始地址。检索时由高级索引到低级索引逐级查找，找到待查找记录所在的磁道，再在磁道中查找待查找记录。
例如现在有一个磁盘组上的ISAM文件，如图1所示。
图1 ISAM文件结构示例
在图1中，C表示柱面；T表示磁道；CiTj表示i号柱面，j号磁道；Ri表示关键字为i的记录。从图10-1可以看出，主索引是柱面索引的索引，这里只有一级主索引，若文件占用的柱面索引很大，使得一级主索引也很大时，可采用多级主索引。当然，若柱面索引较小时，则主索引可省略。
通常主索引和柱面索引放在同一个柱面上，主索引放在柱面最前的一个磁道上，其后的磁道中存放柱面索引。每个存放主文件的柱面都建立有一个磁道索引，放在该柱面的最前面的磁道头上。其后的若干个磁道是存放主文件记录的基本区，该柱面最后的若干个磁道是溢出区。基本区中的记录是按主关键字大小顺序存储的，溢出区被整个柱面上的基本区中各磁道共享，当基本区中某磁道溢出时，就将该磁道的溢出记录，按主关键辽大小链成一个链表（简称溢出链表）放入溢出区。
2、各级索引的索引项结构
磁道索引项由四项索引项构成：基本索引项关键字、基本索引项指针、溢出索引项关键字和溢出索引项指针。每个柱面索引项有两项：关键字和指针；主索引也是由关键字和指针两部分组成。各级索引的索引项结构如图2所示。
图2 各种索引项格式
注意：磁道索引中的每一个索引项都由基本索引项和溢出索引项两个基本索引项组成。
3、ISAM文件的检索
在ISAM文件上检索记录时，有两种检索路径：
（1）若检索记录在某柱面的基本区中，则检索路径为：主索引->柱面索引->某磁道索引->某柱面基本区中某磁道有序表的顺序扫描；
（2）若被检索记录在某柱面的溢出区，则检索路径为：主索引->柱面索引->某磁道索引->某柱面有序溢出链表的顺序扫描。
例如现在要在图10-1中的ISAM文件中查找R80，则查找主索引，即读入C0T0；因为80<300，则查找柱面索引的C0T1，即读入C0T1；因为70<80<150，则进一步把C2T0读入内存；查找磁道索引，因为80<81，所以C2T1即为R80所存放的磁道，读入C2T1后即可查找得到R80；如果没找到，则不存在R80。
为了提高检索效率，通常可让主索引常驻内存，并将柱面索引放在数据文件所占空间居中位置的柱面上，这样，从柱面索引查找到磁道索引时，磁道移动距离的平均值最小。
4、ISAM文件的插入删除
文件建立的时候，磁道索引的溢出索引项都是空的，各个柱面溢出区也都为空，如图1中的文件，各个柱面溢出区都是为空的。当有新的记录插入时，首先找到它应插入的磁道，若该磁道不满，则将新记录插入磁道的适当位置即可；若该磁道已满，则新记录或者插在该磁道上，或者直接插入到该磁道的溢出链表上，插入后，可能要修改磁道索引中的基本索引项和溢出索引项。
例如，现在要依次将记录R72,R87,R91插入到图1所示的文件中，当插入R72时， 应将它插入在C2T1，因为72<75，所以R72应插在该磁道的第一个记录的位置上，而该磁道上原记录依次后移一个位置，于是最后一个记录R80被移入溢出区。由于该磁道上最大关键字由80变成79，故它的溢出链表也由空变成含有一个R80记录的非空表。因此将C2T1对应的磁道索引项中基本索引项的最大关键字，由80改为79；将溢出索引项的最大关键字置为80，且令溢出链表的头指针指向R80的位置。则插入R72后第二个柱面的变化如图3所示。
图3 插入R72记录
类似的，将R87和R91先后插入到第2号柱面的第2号磁道上，插入R87时，R100被移到溢出区；插入R91时，R95被移到溢出区。如图4所示。
图4 插入R87与R91记录
注意：当有记录从基本区移入溢出区时，在溢出链表中的记录要按移入的先后顺序存放。
ISAM文件中删除记录的操作，比插入简单得多，只要找到待删除的记录，在其存储位置上作删除标记即可，而不需要移动记录或改变指针。在经过多次的增删后，文件的结构可能变得很不合理。此时，大量的记录进入溢出区，而基本区中又浪费很多的空间。因此，通常需要周期性地整理ISAM文件，把记录读入内存重新排列，复制成一个新的ISAM文件，填满基本区而空出溢出区。
隐藏目录
