25 文件的逻辑结构

1 概述

文件系统设计的关键要素是指将这些记录构成一个文件的方法，以及将一个文件存储到外存上的方法。事实上，对于任何一个文件，都存在以下两种形式的结构：逻辑结构与物理结构

1.1 文件的逻辑结构

这是从用户观点出发观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织。

1.2 文件的物理结构

又称为文件的存储结构。是指文件在外存上的组织形式，这不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。

2 文件逻辑结构的类型

有结构文件指的是一个以及以上的记录构成的文件，故又把它称为记录式文件；无结构文件是指字符流构成的文件，故又称为流式文件。

2.1 有结构文件

在记录式文件中，每个记录都是用于描述实体集中的一个实体，各记录有着相同或不同数目的数据项。记录长度可分为定长和不定长的两类。

• 定长记录
  这是指文件中所有记录的长度都是相同的们所有记录中个数据项都是处在记录相同的位置，具有相同的顺序和长度。广泛用于数据处理中。

• 不定长记录
  这是指文件中各记录的长度不相同。例如病例记录中的病因、病史等。

有结构文件按记录的组织形式可以分为：顺序结构、索引结构、索引顺序结构。

2.2 无结构文件

如果说大量的数据结构和数据库是采用结构的形式文件的话，则大量的源程序、可执行文件、库函数等，所采用的则是无结构的文件形式，即流式文件。

对流式文件的访问是采用读写指针指出下一个要访问的字符。可以把流式文件看做是记录式文件的一个特例。

注意：在unix中，所有文件都被看做是流式文件，即使是记录式（有结构）文件也被视为流式文件，系统不对文件进行格式处理。

3 顺序文件

文件中的记录一个接一个地顺序排列，记录可以是定长的或变长的，可以顺序存储或以链表形式存储，在访问时需要顺序搜索文件。顺序文件有以下两种结构：

• 串结构
  记录之间的顺序与关键字无关。通常的办法是由时间决定，即按存入时间的先后排列，最先存入的记录作为第1个记录，其次存入的为第2个记录，依此类推。
• 顺序结构
  指文件中的所有记录按关键字顺序排列。

在对记录进行批量操作时，即每次要读或写一大批记录，对顺序文件的效率是所有逻辑文件中最高的；此外，也只有顺序文件才能存储在磁带上，并能有效地工作，但顺序文件对查找、修改、增加或删除单个记录的操作比较困难。

可以为顺序文件配置一个运行记录文件（事务文件）。把试图增加、删除或修改的信息记录其中，规定每隔一定时间，例如4小时，将运行记录文件与原来的主文件加以合并，产生一个关键字排序的新文件。

4 索引文件

对于定长记录文件，如果要查找第i个记录，可直接根据下式计算来获得第i个记录相对于第一个记录的地址：

然而，对于可变长记录的文件，要查找第i个记录时，必须顺序地查找前i-1个记录，从而获得相应记录的长度Li，然后才能按下式计算出第i个记录的首址：

变长记录文件只能顺序查找，系统开销较大。为此可以建立一张索引表以加快检索速度，索引表本身是定长记录的顺序文件。在记录很多或是访问要求高的文件中，需要引入索引以提供有效的访问。实际中，通过索引可以成百上千倍地提高访问速度。

由于索引文件有较快的检索速度，故它主要用于信息处理的及时性要求比较高的场合，例如飞机订票系统。

5 索引顺序文件

索引顺序文件是顺序和索引两种组织形式的结合。索引顺序文件将顺序文件中的所有记录分为若干个组，为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的关键字值和指向该记录的指针。

对于含有N个记录的顺序文件，查找某关键字值的记录时平均需要查找N/2次。

在索引顺序文件中，假设N个记录分为N^{1/2组，索引表中有N}1/2个表项，每组有N^{1/2个记录，在查找某关键字值的记录时，先顺序查找索引表，需要查找(N}1/2)/2次，然后再在主文件中对应的组中顺序查找，也需要查找(N^{1/2)/2次，这样总共查找***(N}1/2)/2+(N^1/2)/2=N1/2次***。

显然，索引顺序文件提高了查找效率，如果记录数很多，可以釆用两级或多级索引。索引文件和索引顺序文件都提高了存取的速度，但因为配置索引表而增加了存储空间。

6 直接文件或散列文件(Hash File)

给定记录的键值或通过Hash函数转换的键值直接决定记录的物理地址。这种映射结构不同于顺序文件或索引文件，没有顺序的特性。

散列文件有很高的存取速度，但是会引起冲突，即不同关键字的散列函数值相同。