[科普中国]-磁盘文件结构

简介

磁盘具有可直接访问的特性，故当利用磁盘来存放文件时，具有很大的灵活性。磁盘文件结构是指文件在磁盘上的分配方式。属于文件外存分配方式，文件的物理结构直接与外存分配方式有关。在采用不同的分配方式时，将形成不同的文件物理结构。例如，在采用连续分配方式时的文件物理结构，将是顺序式的文件结构；链接分配方式将形成链接式文件结构；而索引分配方式则将形成索引式文件结构。

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

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

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

无论是文件的逻辑结构，还是其物理结构，都会影响对文件的检索速度。

磁盘文件结构的种类顺序式的文件结构顺序式的文件结构即文件采用连续分配方式，连续分配(Continuous Allocation)要求为每一个文件分配一组相邻接的盘块。 一组盘块的地址定义了磁盘上的一段线性地址。例如，第一个盘块的地址为 b，则第二个盘块的地址为b+1，第三个盘块的地址为 b+2……。通常，它们都位于一条磁道上，在进行读/写时，不必移动磁头，仅当访问到一条磁道的最后一个盘块后，才需要移到下一条磁道，于是又去连续地读/写多个盘块。在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。为使系统能找到文件存放的地址，应在目录项的“文件物理地址”字段中，记录该文件第一个记录所在的盘块号和文件长度(以盘块数进行计量)。图 1示出了连续分配的情况。图中假定了记录与盘块的大小相同。Count 文件的第一个盘块号是 0，文件长度为 2，因此是在盘块号为 0 和 1 的两盘块中存放文件 1 的数据。

连续分配的主要优点如下：

(1) 顺序访问容易。访问一个占有连续空间的文件非常容易。系统可从目录中找到该顺序文件所在的第一个盘块号，从此开始顺序地、逐个盘块地往下读/写。连续分配也支持直接存取。例如，要访问一个从 b 块开始存放的文件中的第 i 个盘块的内容，就可直接访问b+i 号盘块。

(2) 顺序访问速度快。因为由连续分配所装入的文件，其所占用的盘块可能是位于一条或几条相邻的磁道上，这时，磁头的移动距离最少，因此，这种对文件访问的速度是几种存储空间分配方式中最高的一种。

连续分配的主要缺点如下：

(1) 要求有连续的存储空间。要为每一个文件分配一段连续的存储空间，这样，便会产生出许多外部碎片，严重地降低了外存空间的利用率。如果是定期地利用紧凑方法来消除碎片，则又需花费大量的机器时间。

(2) 必须事先知道文件的长度。要将一个文件装入一个连续的存储区中，必须事先知道文件的大小，然后根据其大小，在存储空间中找出一块其大小足够的存储区，将文件装入。在有些情况下，知道文件的大小是件非常容易的事，如可拷贝一个已存文件。但有时却很难，在此情况下，只能靠估算。如果估计的文件大小比实际文件小，就可能因存储空间不足而中止文件的拷贝，须再要求用户重新估算，然后再次执行。这样，显然既费时又麻烦。这就促使用户往往将文件长度估得比实际的大，甚至使所计算的文件长度比实际长度大得多，显然，这会严重地浪费外存空间。对于那些动态增长的文件，由于开始时文件很小，在运行中逐渐增大，比如，这种增长要经历几天、几个月。在此情况下，即使事先知道文件的最终大小，在采用预分配存储空间的方法时，显然也将是很低效的，即它使大量的存储空间长期地空闲着。1

链接式文件结构链接式文件结构即文件采用链接分配方式，如同内存管理一样， 连续分配所存在的问题就在于: 必须为一个文件分配连续的磁盘空间。如果在将一个逻辑文件存储到外存上时，并不要求为整个文件分配一块连续的空间，而是可以将文件装到多个离散的盘块中，这样也就可以消除上述缺点。在采用链接分配(Chained Allocation)方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的物理文件称为链接文件。由于链接分配是采取离散分配方式，消除了外部碎片，故而显著地提高了外存空间的利用率；又因为是根据文件的当前需要，为它分配必需的盘块，当文件动态增长时，可动态地再为它分配盘块，故而无需事先知道文件的大小。此外，对文件的增、删、改也十分方便。

链接方式又可分为隐式链接和显式链接两种形式。

隐式链接

在采用隐式链接分配方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。图 2 中示出了一个占用 5 个盘块的链接式文件。在相应的目录项中，指示了其第一个盘块号是 9，最后一个盘块号是 25。而在每个盘块中都含有一个指向下一个盘块的指针，如在第一个盘块 9 中设置了第二个盘块的盘块号是 16；在16 号盘块中又设置了第三个盘块的盘块号 1。如果指针占用 4 个字节，对于盘块大小为 512字节的磁盘，则每个盘块中只有 508 个字节可供用户使用。

隐式链接分配方式的主要问题在于：它只适合于顺序访问，它对随机访问是极其低效的。如果要访问文件所在的第 i 个盘块，则必须先读出文件的第一个盘块……，就这样顺序地查找直至第 i 块。当 i=100 时，须启动 100 次磁盘去实现读盘块的操作，平均每次都要花费几十毫秒。可见，随机访问的速度相当低。此外，只通过链接指针来将一大批离散的盘块链接起来，其可靠性较差，因为只要其中的任何一个指针出现问题，都会导致整个链的断开。

为了提高检索速度和减小指针所占用的存储空间， 可以将几个盘块组成一个簇(cluster)。比如，一个簇可包含 4 个盘块，在进行盘块分配时，是以簇为单位进行的。在链接文件中的每个元素也是以簇为单位的。这样将会成倍地减小查找指定块的时间，而且也可减小指针所占用的存储空间，但却增大了内部碎片，而且这种改进也是非常有限的。

显式链接

这是指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表在整个磁盘仅设置一张，如图 3所示。表的序号是物理盘块号，从 0 开始，直至 N-1；N 为盘块总数。在每个表项中存放链接指针，即下一个盘块号。在该表中，凡是属于某一文件的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件地址被填入相应文件的 FCB 的“物理地址”字段中。由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件的所有盘块号都放在该表中，故把该表称为文件分配表 FAT(File Allocation Table)。

索引式文件结构索引式文件结构即文件采用索引分配方式，一般分为单级索引分配、多级索引分配、混合索引分配方式。

单级索引分配

链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了下述另外两个问题：

(1) 不能支持高效的直接存取。 要对一个较大的文件进行直接存取， 须首先在 FAT 中顺序地查找许多盘块号。

(2) FAT 需占用较大的内存空间。由于一个文件所占用盘块的盘块号是随机地分布在FAT 中的， 因而只有将整个 FAT 调入内存， 才能保证在 FAT 中找到一个文件的所有盘块号。当磁盘容量较大时，FAT 可能要占用数兆字节以上的内存空间，这是令人难以接受的。事实上，在打开某个文件时，只需把该文件占用的盘块的编号调入内存即可，完全没有必要将整个 FAT 调入内存。为此，应将每个文件所对应的盘块号集中地放在一起。索引分配方法就是基于这种想法所形成的一种分配方法。它为每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组。在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。图4示出了磁盘空间的索引分配图。

索引分配方式支持直接访问。当要读文件的第 i 个盘块时，可以方便地直接从索引块中找到第 i 个盘块的盘块号；此外，索引分配方式也不会产生外部碎片。当文件较大时，索引分配方式无疑要优于链接分配方式。

索引分配方式的主要问题是：可能要花费较多的外存空间。每当建立一个文件时，便须为之分配一个索引块，将分配给该文件的所有盘块号记录于其中。但在一般情况下，总是中、小型文件居多，甚至有不少文件只需 1～2 个盘块，这时如果采用链接分配方式，只需设置 1～2 个指针。如果采用索引分配方式，则同样仍须为之分配一索引块。通常是采用一个专门的盘块作为索引块，其中可存放成百个、甚至上千个盘块号。可见，对于小文件采用索引分配方式时，其索引块的利用率将是极低的。

多级索引分配

当 OS 为一个大文件分配磁盘空间时， 如果所分配出去的盘块的盘块号已经装满一个索引块时， OS 便为该文件分配另一个索引块， 用于将以后继续为之分配的盘块号记录于其中。依此类推，再通过链指针将各索引块按序链接起来。显然，当文件太大，其索引块太多时，这种方法是低效的。此时，应为这些索引块再建立一级索引，称为第一级索引，即系统再分配一个索引块，作为第一级索引的索引块，将第一块、第二块……等索引块的盘块号填入到此索引表中，这样便形成了两级索引分配方式。如果文件非常大时，还可用三级、四级索引分配方式。

混合索引分配方式

所谓混合索引分配方式，是指将多种索引分配方式相结合而形成的一种分配方式。例如，系统既采用了直接地址，又采用了一级索引分配方式，或两级索引分配方式，甚至还采用了三级索引分配方式。 这种混合索引分配方式已在 UNIX 系统中采用。 在 UNIX SystemⅤ的索引结点中， 共设置了13个地址项， 即iaddr(0)～iaddr(12)， 如图5所示。 在BSD UNIX的索引结点中，共设置了 13 个地址项，它们都把所有的地址项分成两类，即直接地址和间接地址。