8.1　外存的组织方式

本节概览：先建立「外存的组织方式」的框架，再依次展开下列小节。

1. 连续组织方式
2. 链接组织方式
3. FAT技术
4. NTFS的文件组织方式
5. 索引组织方式

连续组织方式又称连续分配方式，要求为每个文件分配一组相邻接的盘块。第一盘块地址为 b，则第二块为 b+1，第三块为 b+2……通常位于一条磁道上，读写时不必移动磁头。

把逻辑文件中的记录顺序存储到邻接的各物理盘块中，所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。

连续组织方式的主要优点如下：

1. 顺序访问容易
2. 顺序访问速度快。 连续组织方式的主要缺点有如下。

仍存在下述问题。

1. 要求为一个文件分配连续的存储空间
2. 必须事先知道文件的长度
3. 不能灵活地删除和插入记录
4. 对于那些动态增长的文件

显式链接：把用于链接文件各物理块的指针显式地存放在内存的一张链接表中，该表在整个磁盘中只设置一张。

由于链接表在内存中，查找盘块号不必读盘，可显著加快随机访问速度；FAT 即采用此思路。

隐式链接：在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针；中间盘块的链接指针存放在每个盘块自身中。

若可将文件装到多个离散的盘块中，就可消除连续组织方式的上述缺点。链接组织方式为文件分配多个不连续的盘块，再通过每个盘块上的链接指针，将同属一个文件的多个离散盘块链接成链表，所形成的物理文件称为链接文件。

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

1. 消除了磁盘的外部碎片，提高了外存的利用率
2. 对插入、删除和修改记录都非常容易
3. 能适应文件的动态增长，无需事先知道文件的大小

结合图 8-3 显式链接结构理解：文件各物理块通过链接指针显式链接，FAT 表记录所有盘块的链接关系。

以簇为单位的 FAT12：若把每个盘块（扇区）的容量增大 n 倍，磁盘最大容量便可增加 n 倍，但增大盘块容量既不方便也不灵活，于是引入簇（cluster）的概念。

簇是若干连续扇区的组合，作为分配和寻址的基本单位；通过增大簇可扩大 FAT12 所支持的磁盘容量。

FAT12 以盘块为基本分配单位。FAT 是文件系统中最重要的数据结构，为安全起见，每个分区都配有两张相同的文件分配表 FAT1 和 FAT2。

FAT 的每个表项中存放下一个盘块号，实际上是盘块之间链接的指针，通过它可将一个文件的所有盘块链接起来；文件的第一个盘块号放在自己的 FCB 中。

FAT12 对磁盘容量限制的原因在于 FAT 表项数有限，最多只允许 4096 个。随着磁盘容量增加，簇的大小和簇内碎片也随之增加。

FAT16 将表项数扩展到 65535，但仍会随磁盘容量增大而使簇变大、簇内碎片增多。

NTFS 文件组织：以卷为单位，将卷中所有文件信息、目录信息及可用未分配空间信息，都以文件记录的方式记录在一张主控文件表 MFT（Master File Table）中。

MFT 是 NTFS 卷结构的中心：从逻辑上讲，卷中每个文件作为一条记录在 MFT 中占一行，其中包括 MFT 自己这一行。每行大小固定为 1 KB，称为该文件对应的元数据（metadata），也称为文件控制字。

NTFS（New Technology File System）是专为 Windows NT 开发的全新文件系统，并适用于 Windows 2000/XP 及后续 Windows OS。

磁盘组织：NTFS 以簇作为磁盘空间分配和回收的基本单位，一个文件占用若干簇，一个簇只属于一个文件。这样为文件分配磁盘空间时无须知道盘块大小，只要根据磁盘容量选择相应大小的簇，使 NTFS 具有与磁盘物理块大小无关的独立性。

链接方式解决了连续分配不便随机访问的问题，但又带来两个新麻烦。

1. 不能支持高效的直接存取：对较大文件进行存取，须在 FAT 中顺序查找许多盘块号。
2. FAT 需占用较大内存空间：一个文件所占盘块号随机分布在 FAT 中，只有把整个 FAT 调入内存，才能保证找到该文件的所有盘块号。

多级索引组织方式：在为大文件分配磁盘空间时，若所分配盘块号已装满一个索引块，OS 须再为该文件分配另一个索引块，用于记录后续分配的盘块号，依此类推，再通过链指针将各索引块按序链接起来。

进一步可建立两级或多级索引，使大文件、超大文件的访问都只需几次读盘即可定位数据盘块。

UNIX System V 的组织方式：在其索引结点中设有 13 个地址项 i.addr(0)~i.addr(12)，按地址项性质分为三类。

1. 直接地址
2. 一次间接地址
3. 多次间接地址

增量式索引组织方式：为较全面照顾小、中、大及特大型作业，采取多种方式构成文件物理结构。若盘块大小为 1 KB 或 4 KB，小文件最多只占 10 个盘块，为提高对数量众多的小型作业的访问速度，最好将每个盘块地址都直接放入 FCB（或索引结点）中。

结合图 8-8 混合索引方式理解：索引结点中既包含直接地址，又包含一级、二级、三级间接地址，兼顾小文件和大文件的访问效率。