6.2.2　文件逻辑结构与物理结构

1.逻辑结构

逻辑结构是用户可见的结构，即是从用户的角度所观察到的文件的组织形式，是文件逻辑上的组织形式。从逻辑结构上看，文件可分为无结构文件和有结构文件两种。

（1）无结构文件

无结构文件又称字符流文件或流式文件。构成的基本单位是字符，文件内的数据是一个完整的字符流，不可以进一步细分。如源程序文件、可执行文件、文本文件。

（2）有结构文件

有结构文件又称记录式文件。构成的基本单位是记录，由若干条逻辑记录组成，记录是一个具有特定意义的信息单位，每个记录有一个记录键（关键字），可按键进行查找记录。

记录式文件是一组有序记录的集合。记录式文件可把记录按各种不同的方式排列，以便用户对文件中的记录进行修改、追加、查找和管理。

记录式文件可分为定长记录文件和变长记录文件两种。定长记录文件中各个记录长度相等，在检索时，可以根据记录号及记录长度来确定该记录的逻辑地址。变长记录文件中各个记录长度不等，在查找时，必须从第一个记录开始，逐个进行记录的查找，直到找到所需的记录。

2.文件的物理结构

文件的物理结构是指文件的内部组织形式，即逻辑文件在物理存储空间中的存放方法和组织关系。由于文件的物理结构决定了文件信息在存储设备上的存储位置，因此文件信息的逻辑块号到物理块号的转换也是由文件的物理结构决定的。此外，文件的存取方式也与文件的物理结构有关。

常用的物理结构有文件的顺序结构、文件的链接结构和文件的索引结构。

（1）文件的顺序结构

顺序结构又称连续结构。这是一种最简单的物理结构。在这种结构中，将文件连续存放在外存上，即将逻辑上连续的文件信息顺序地存储到连续的物理盘块中。这样，在逻辑文件中的记录次序与在存储介质上存放的记录次序是一致的。只要知道文件在存储设备上的起始地址（首块号）和文件长度（总块数），就能很快地进行存取。

这种结构的优点是访问速度快，缺点是文件长度增加困难。

（2）文件的链接结构

在链接结构中，将文件以链接块的方式存放在外存上，即将逻辑上连续的文件信息分散存放在若干不连续（或不相邻）的物理块中。每个物理块设有一个指针，指向其后续的物理块，通过指针将这些物理块链接成一个链表。只要指明文件的第一个物理块号，就可以按链指针检索整个文件。

这种结构的优点是文件长度容易动态变化，其缺点是不适合随机存取访问。

（3）文件的索引结构

在索引结构中，将文件以索引表方式存放在外存上。它是指各个文件中的记录可存在不相邻接的各个物理块中，但系统必须为每个文件建立一张索引表，记录文件信息所在的逻辑块号和与之对应的物理块号。索引表也以文件的形式存在磁盘上。给出索引表的地址，就可以查找到与文件逻辑块号对应的物理块号。

当文件的记录个数太多，以至于一个物理存储块无法容纳该文件的索引表时，可考虑建立多级索引。

这种结构的优点是访问速度快，文件长度可以动态变化。缺点是存储开销大，因为每个文件有一个索引表，而索引表亦由物理块存储，故需要占用额外的外存空间。另外，当文件被打开时，索引表需要读入内存，否则访问速度会降低一半，故又需要占用额外的内存空间，当同时打开的文件很多时，内存开销是可观的。这种结构限制了文件的最大长度，例如，若采用三级索引结构，文件长度最多可达2563+2562+256+10个块，如图6-2所示。

图　6-2　文件的三级索引结构