索引文件

所谓索引文件是指除了文件本身外，另建立一张指示逻辑记录和物理记录之间一一对应关系的索引表，索引表和主文件一起构成的文件就叫作索引文件。本节就来学习一下索引文件的分类及存储和操作等相关知识。

1、索引文件的分类

索引表中的每一项称为索引项，一般索引项都是由主关键字和该关键字所在记录的物理地址组成。索引表必须按主关键字有序，而主文件本身则可以近主关键字有序或无序。主文件本身按关键字有序则称为索引顺序文件，它有ISAM文件和VSAM文件两种。主文件关键字无序则称为索引非顺序文件。

在索引顺序文件中，可对一组记录建立一个索引项，这种索引表称为稀疏索引。对于索引非顺序文件，必须为每一个记录建立一个索引项，这样建立的索引表称为稠密索引。对于索引非顺序文件，因为主文件无序，顺序存取将会频繁的引起磁头的移动，适合于随机存取，不适合于顺序存取。而索引顺序文件既适合于随机存取也适合于顺序存取。

注意：通常我们所说的索引文件是指索引非顺序文件，它也是本节要讨论的文件，在接下的讲解中，所谓的索引文件就是指索引非顺序文件。

2、索引文件的存储

索引文件在存储器上分为两个区：索引区和数据区。索引区存放索引表，数据区存放主文件。在建立文件过程中，按输入记录的先后次序建立数据区和索引表，这样的索引表其关键字是无序的，待全部记录输入完毕后对索引表进行排序，排序后的索引表和主文件一起就形成了索引文件。例如，现在往文件中录入一组学生信息，以学号为关键字，如表1所示。

表1 学生信息（主文件）

在表1中，学生的学号与姓名是按次序录入的，按物理地址顺序存储下来，现在为主文件创建一张索引表，如表2所示。

表2 索引表

这个索引表所对应的主文件是未经排序的，现在对主文件以关键字排序，则排序后所对应的索引表如表3所示。

表3 排序后的索引表

经过排序之后，则表1与表2一起构成了一个索引文件。这就是索引文件的建立过程。

3、索引文件的操作

索引文件上的操作主要有两种：检索与更新。

检索操作分两步进行：第一步，将外存上含有索引区的页块送入内存，查找所需记录的物理地址；第二步，将含有该记录的页块送入内存。

注意，在读取索引表时，若索引表不大，则可将索引表一次读入内存，在索引文件中检索只需两次访问外存：一次读索引，一次读记录。在查找时，由于索引表有序，对索引表的查找可用顺序查找或二分查找等方法。

索引文件的更新操作也很简单，插入时，将插入记录置于数据区的末尾，并在索引表中插入索引项；删除时，删去相应的索引项；若要修改主关键字，则必须同时修改索引表。

当一个中记录数目很大时，索引表也会很大，以致一个页块容纳不下，在这种情况下查阅索引仍要多次访问外存，为此可以为索引也建立一个索引，称为查找表。当查找表中项目仍然很多时，可以建立更高一级的索引，通常最高可达四级索引，它们也被称为多级索引。多级索引是一种静态索引，其各级索引均为顺序表，结构简单，修改很不方便，每次修改都要重组索引。

当数据文件在使用过程中记录变动较多时，可利用二叉排序树、B树等树表结构来建立索引，称为动态索引。动态索引在插入删除时都很方便。动态索引本身是层次结构，无须建立多级索引，建立索引表的过程即为排序过程。