7.2　文件的逻辑结构

本节概览：先建立「文件的逻辑结构」的框架，再依次展开下列小节。

1. 文件逻辑结构的类型
2. 顺序文件(Sequential File)
3. 记录寻址
4. 索引文件(Index File)
5. 索引顺序文件 (Index Sequential File)
6. 直接文件和哈希文件

根据文件的组织方式，可把有结构文件分为三类。

1. 顺序文件
2. 索引文件
3. 索引顺序文件

按文件是否有结构分类。有结构文件可分为定长记录和变长记录。

对文件逻辑结构的基本要求：应方便对文件进行修改，即便于在文件中增加、删除和修改一个或多个记录；降低文件存放在外存上的存储费用；有助于提高检索速度，即在将大批记录组成文件时应采用一种有利于提高检索记录速度和效率的逻辑结构形式。

1. 定长记录
2. 变长记录

无结构文件：系统中运行的大量的源程序、可执行文件、库函数等所采用的就是无结构的文件形式，即流式文件，其文件长度以字节为单位。

在顺序文件中的记录可按各种不同顺序进行排列。

1. 串结构：通常按存入时间的先后进行排序，各记录之间的顺序与关键字无关
2. 顺序结构：由用户指定一个字段作为关键字，可按关键字大小排序，或按其英文字母排序

顺序文件的最佳应用场合是在对文件中的记录进行批量存取时（即每次要读或写一大批记录）。所有逻辑文件中顺序文件的存取效率最高。此外，对于顺序存储设备（如磁带），也只有顺序文件才能被存储并能有效工作。

顺序文件的优缺点：批量存取效率高，适合顺序存储设备；但随机存取效率低，记录的插入和删除较困难。

显式寻址方式可用于对定长记录的文件实现直接或随机访问，因为任何记录的位置都很容易通过记录长度计算出来。

对于可变长度记录的文件则不能利用显式寻址方式实现直接或随机访问，必须增加适当的支持机构方能实现。通过两种方式对定长记录实现随机访问。

1. 通过文件中记录的位置
2. 利用关键字

对于定长记录的顺序文件，如果已知当前记录的逻辑地址，便很容易确定下一个记录的逻辑地址，称为隐式寻址方式。

定长记录的文件可通过简单计算很容易地实现随机查找。但变长记录文件查找一个记录必须从第一个记录查起，一直顺序查找到目标记录为止，耗时很长。

按关键字建立索引表可解决此问题：为变长记录文件建立一张索引表，按关键字排序，通过索引表实现对记录的随机访问。

使用按关键字建立索引表的索引文件与顺序文件一样，都只能按该关键字进行检索。但实际应用中，不同用户为不同目的希望按不同属性（或不同关键字）来检索一条记录。

为此需要为顺序文件建立多个索引表，即为每一种可能成为检索条件的域（属性或关键字）都配置一张索引表，每张索引表按相应属性或关键字排序。

索引表的主要优点：将一个需要顺序查找的文件改造成一个可随机查找的文件，极大地提高了对文件的查找速度。

索引顺序文件是对顺序文件的一种改进，基本克服了变长记录顺序文件不能随机访问、不便于记录删除和插入的缺点。但它仍保留顺序文件的关键特征，即记录按关键字顺序组织。

它又增加了两个新特征：一是引入文件索引表，通过该表可实现对索引顺序文件的随机访问；二是增加溢出(overflow)文件，用来记录新增加的、删除的和修改的记录。

最简单的索引顺序文件只使用一级索引。建立方法是：首先将变长记录顺序文件中的所有记录分为若干个组（如50个记录为一组），然后为顺序文件建立一张索引表，为每组中的第一个记录在索引表中建立一个索引项，其中含有该记录的关键字和指向该记录的指针。索引顺序文件是最常见的一种逻辑文件形式。

对于非常大的文件，为找到一个记录而须查找的记录数目仍然很多。例如对含10^6个记录的顺序文件，作为索引顺序文件时为找到一个记录平均须查找1000个记录。

为进一步提高检索效率，可为顺序文件建立多级索引，即为索引文件再建立一张索引表，从而形成两级索引表。

对于直接文件，可根据给定的关键字直接获得指定记录的物理地址。换言之，关键字本身就决定了记录的物理地址。

目前应用最广泛的直接文件是哈希文件。它利用Hash函数（或称散列函数）可将关键字转换为相应记录的地址。但为能实现文件存储空间的动态分配，通常由Hash函数求得的并非相应记录的地址，而是指向某一目录表相应表目的指针，该表目的内容指向相应记录所在的物理块。

哈希(Hash)文件是利用Hash函数将关键字映射为记录物理地址的直接文件，是目前应用最广泛的直接文件形式。

Hash 检索法：建立一张 Hash 索引文件目录项，按文件名计算出 Hash 值，定位到相应桶，再在桶内进行线性查找。

优点是检索速度快；冲突时需处理溢出（如拉链法或开放定址法），并要考虑目录的动态扩充。