[科普中国]-索引顺序访问方法

索引文件

索引文件由数据文件组成，它是带索引的顺序文件。索引本身非常小，只占两个字段：顺序文件的键和在磁盘上相应记录的地址。存取文件中的记录需按以下步骤：

（1）整个索引文件都载入到内存中（文件很小，只占用很小的内存空间）。

（2）搜索项目，用高效的算法（如折半查询法）查找目标键。

（3）检索记录的地址。

（4）按照地址，检索数据记录并返回给用户。2

索引文件由索引表和主文件两部分构成。

索引表是一张指示逻辑记录和物理记录之间对应关系的表。索引表中的每项称作索引项。索引项是按键（或逻辑记录号）顺序排列。若文件本身也是按关键字顺序排列，则称为索引顺序文件。否则，称为索引非顺序文件。

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

如图所示的文件是存放在同一个磁盘组上的ISAM文件。

其中：

① C表示柱面；

② T表示磁道；

③ CiTi表示i号柱面，j号磁道；

④ Ri表示主关键字为i的记录。

分析：

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

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

各级索引中的索引项结构

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

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

为了提高检索效率，通常可让主索引常驻内存，并将柱面索引放在数据文件所占空间居中位置的柱面上，这样，从柱面索引查找到磁道索引时，磁头移动距离的平均值最小。

队列顺序访问方法(QSAM)与 BISAM 类似，QSAM 以记录进入的顺序安排记录的存放位置，形成一个顺序数据集。但与BISAM 不同的是QSAM 由系统组织记录的成组与分解，也就是说，系统将多个记录组成块。为了提高性能，使用队列顺序访问方法往往在记录或文件在使用之前，就已经将记录或文件提前读入内存。