3） 索引文件 (P189)

记录大小可以不定长，不必排序，存入主文件中。建立索引表，每个索引项指向一个记录，索引项按记录中某关键字排序。对同一主文件，针对不同关键字可以建立多个索引。

4） 哈希文件（直接文件）

记录大小相等，由主文件和溢出文件组成。检索时给出记录键值，通过哈希函数计算出该记录在文件中的相对位置。

四． 外存分配（文件的物理组织）（ P192 ）

1． 连续文件（顺序文件）：逻辑上连续的信息存放于连续的物理块中。

l 顺序访问速度快。

l 缺点：要求连续的存贮空间，文件不便增大与缩小。

2． 链接文件：逻辑上连续的信息可存放于不连续的物理块中。

l 适用于顺序访问。

l 优点：空间利用率高，便于文件增大和缩小。

l 缺点：访问速度慢，不能预缓冲输入。

3． 索引文件（ P195 ）

逻辑上连续的信息可存放于不连续的物理块中，由索引表指示信息所在的物理块。

l 一级索引方式（图 6—11 ）。

l 二级索引方式（图 6—12 ）。

l 混合索引方式（图 6—13 ）， UNIX 系统采用的方法。可适用于各种类型的文件。

五． 目录管理（ P198 ）

目录作用：用于标识和检索系统中全部文件，目录由目录项（文件控制块 FCB ）组成，位于文件卷上特定位置。卷：文件存储介质的逻辑单位。

1． 目录项的内容

集合了一个文件全部说明信息（文件属性），其中部分信息用户可获取。

1 ）基本信息

l 文件名：字符串，通常在不同系统中允许不同的最大长度。

l 文件类型：可有多种不同的划分方法，如：记录式文件、流式文件、二进制文件、文本文件、源代码文件、目标代码文件、可执行文件、系统文件、隐含文件、顺序文件、索引文件。

2 ）地址信息 l 存放位置：包括存放的设备或文件卷 volume ，以及各个存储块位置。 l 文件长度：以字节、字或存储块为单位。可以通过写入或创建、打开、关闭等操作而变化。

1） 访问控制信息：文件主、访问权限等。

2） 使用信息：创建时间、最后一次读访问的时间、最后一次写访问的时间。

2 ．目录结构类型

l 一级目录（ P200 图 6--16 ）：整个目录组织是一个线性结构，所有文件都建立在一张目录表中，特点：结构简单，文件不能重名，目录检索时间长。适用于单用户系统。 l 二级目录（ P201 图 6--17 ）：在根目录（主目录）下，每个用户对应一个目录（用户目录，第二级目录）；在用户目录下是该用户的文件，而不再有下级目录。适用于多用户系统，各用户可有自己的专用目录。 l 多级目录（ P202 图 6--18 ）：树状目录。在文件数目较多时，便于系统和用户将文件分散管理。目录级别太多时，会增加路径检索时间。 1） 目录的层次关系：根目录、当前目录 ( 工作目录 ) 、父目录、子目录等； 2） 路径：每个目录或文件，可以由根目录开始依次经由的各级目录名，加上最终的目录名或文件名来表示。 l 符号文件目录和索引结点（ P199 ） 为了提高目录检索速度，可把目录中的文件说明信息分成两个部分： 1） 符号文件目录（ SFD ）：由文件名和文件的索引结点编号组成。 2） 盘索引节点：存放除文件名以外的文件属性。每个索引结点号所对应索引结点在文件卷上的物理位置是固定的。

4． 目录查询（ P204 ）

l 基于符号文件目录和索引结点的线性查询。（ UNIX 系统采用的方法。）

l 哈希查询。

l 存贮空间管理（ P205 ）

l 空闲表与空闲链表：实现原理可参考内存管理的可变分区。

l 位示图：每一位表示一个分配单位（块），取值 0 和 1 分别表示空闲和占用。