外存的组织方式
目录
参考资料：
文件的物理结构直接与外存的组织方式有关。对于不同的外存组织方式，将形成不同的文件物理结构。目前常用的外存组织方式有：
- 连续组织方式：在对文件采取连续组织方式时，为每个文件分配一片连续的磁盘空间，由此所形成的文件物理结构将是顺序式的文件结构。
- 链接组织方式：在对文件采取链接组织方式时，可以为每个文件分配不连续的磁盘空间，通过链接指针将一个文件的所有盘块链接在一起，由此所形成的将是链接式文件结构。
- 索引组织方式：在对文件采取索引组织方式时，所形成的将是索引式文件结构。
各种文件组织方式的优劣，可类比对应的数据结构性能的优劣，如数组、链表、Hash 表等
1 连续组织方式
连续组织方式又称连续分配方式，要求为每一个文件分配一组相邻接的盘块。通常它们都位于一条磁道上，在进行读/写时，不必移动磁头。在采用连续组织方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。
这种组织方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。为使系统能找到文件存放的地址，应在目录项的“文件物理地址”字段中记录该文件第一个记录所在的盘块号和文件长度(以盘块为单位)。
- 连续组织方式的主要优点
顺序访问容易且访问速度快。由连续分配所装入的文件，其所占用的盘块可能是位于一条或几条相邻的磁道上，磁头的移动距离最少，因此，这种对文件访问的速度是几种存储空间分配方式中最高的一种。
- 连续组织方式的主要缺点
- 分配连续的存储空间，会产生出许多外部碎片，严重地降低了外存空间的利用率。如果定期利用紧凑方法来消除碎片则又需花费大量的机器时间。
- 必须事先知道文件的长度。文件的大小有时只能靠估算，一般情况下会将文件长度估得比实际的大（预防不足），从而造成浪费。
- 不能灵活地删除和插入记录。为保持文件的有序性，在删除和插入记录时，都需要对相邻的记录做物理上的移动，还会动态地改变文件的大小。
2 链接组织方式
采用链接组织方式时，可为文件分配多个不连续的盘块，再通过每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，由此所形成的物理文件称为链接文件。
链接组织方式的主要优点是：
解决了连续分配方式的不足
- 消除了磁盘的外部碎片，提高了外存的利用率。
- 对插入、删除和修改记录都非常容易。
- 能适应文件的动态增长，无需事先知道文件的大小。
链接方式又可分为隐式链接和显式链接两种形式。
2.1 隐式链接
采用隐式链接组织方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针，而在每个盘块中都含有一个指向下一个盘块的指针。如下图所示：
上图所示的链接顺序为：9->16->1->10->25，一共使用了 5 个盘块
如果一个指针占用 4 个字节，对于盘块大小为 512 字节的磁盘，则每个盘块中只有 508 个字节可供用户使用。
指针太多，浪费磁盘空间
隐式链接组织方式的主要问题在于，它只适合于顺序访问，它对随机访问是极其低效的。此外，只通过链接指针将一大批离散的盘块链接起来，其可靠性较差，因为只要其中的任何一个指针出现问题，都会导致整个链的断开。
随机访问低效+可靠性差
对指针占用磁盘空间的改进思路：
为了提高检索速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇(cluster)，以簇为单位进行盘块分配，但这种方式却增大了内部碎片。
就是把多个盘捆成一起使用一个指针，连续分配和链式分配的折中版本
2.2 显式链接
把用于链接文件各物理块的指针显式地存放在内存的一张链接表中，该表在整个磁盘中仅设置一张。
WARNING
真放在内存？
还是 FAT 在运行时调入内存？
指针不再是隐式的放在物理盘块中了，而是放在内存中的一张表里
如上图所示，表的序号是物理盘块号，从 0 开始，直至 N - 1（N 为盘块总数）。在每个表项中存放链接指针，即下一个盘块号。
链接顺序为：2->4->5->1
在该表中，凡是属于某一文件的第一个盘块号，均作为文件地址被填入文件的 FCB 的“物理地址”字段中。由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。
寻址提速
由于分配给文件的所有盘块号都放在该表中，故把该表称为文件分配表 FAT(File Allocation Table)。
在文件分配表的实际应用过程中，可以发现 FAT 始终与磁盘大小及利用率上存在着矛盾
windows 系统中的 FAT12 -> FAT16 -> FAT32 -> NTFS：
FAT12 以盘块为基本分配单位，每个 FAT 表项占 12 位，所以表中最多允许有 4096(2^12) 个表项。
如果盘块大小固定，那么存储空间的大小也就限制了，所以使用簇（多个磁盘块组合）
FAT16 将表项位数增至 16 位，最大表项数将增至 65536(2^16)个，支持硬盘容量的增加。
如果表项固定，磁盘容量太大，那么簇就越大（多个磁盘块组合），簇越大，内部碎片就越多
FAT32 将表项位数增至 32 位，能支持更小的簇，使磁盘具有更高的存储器利用率。
主要是随着磁盘空间加大，解决内部碎片过多的问题，因为 FAT32 比 FAT16 文件要大，所以访问效率要比 FAT16 慢。
NTFS 是以簇作为磁盘空间分配和回收的基本单位的。一个文件占用若干个簇，簇只属于一个文件。这样，在为文件分配磁盘空间时，就无须知道盘块的大小，只要根据不同的磁盘容量，选择相应大小的簇，使 NTFS 具有了与磁盘物理块大小无关的独立性。
NTFS（New Technology File System）以簇为基本单位
3 索引组织方式
链接组织方式虽然解决了连续组织方式所存在的问题，但又出现了另外两个问题，即：
- 不能支持高效的直接存取，要对一个较大的文件进行存取，须在 FAT 中顺序地查找许多盘块号。
- FAT 需占用较大的内存空间，当磁盘容量较大时，FAT 可能要占用数 MB 以上的内存空间。
3.1 单级索引组织方式
思想：事实上，在打开某个文件时，只需把该文件占用的盘块的编号调入内存即可，完全没有必要将整个 FAT 调入内存。
索引分配方法就是为每个文件分配一个索引块(表)，把分配给该文件的所有盘块号都记录在该索引块中。在建立一个文件时，只须在为之建立的目录项中填上指向该索引块的指针。
索引组织方式的主要优点是支持直接访问。当要读文件的第 i 个盘块时，可以直接从该文件的索引块中找到第 i 个盘块的盘块号；此外索引分配方式也不会产生外部碎片。当文件较大时，索引分配方式无疑要优于链接分配方式。
适合中大型文件
索引组织方式的主要问题是，每当建立一个索引文件时，应为该文件分配一个索引块，将分配给该文件的所有盘块号记录于其中。在每一个索引块中可存放数百个盘块号。但对于中、小型文件，其本身通常只占有数个到数十个盘块，甚至更少，但仍须为之分配一索引块。可见，对于小文件采用索引分配方式时，其索引块的利用率将是极低的。
对于小文件来说，浪费索引块空间
3.2 多级索引组织方式
当文件太大，其索引块太多时，应为这些索引块再建立一级索引，称为第一级索引，即系统再分配一个索引块，作为第一级索引的索引块，将第一块、第二块、···.··等索引块的盘块号填入到此索引表中，这样便形成了两级索引分配方式。如果文件非常大时，还可用三级、四级索引分配方式。
为索引块再建立索引
- 优点
大大加快了对大型文件的查找速度
- 缺点
在访问一个盘块时，其所需启动磁盘的次数随着索引级数的增加而增多，即使是对于小文件，也是如此。
实际情况是，通常总是以中、小文件居多，而大文件是较少的。因此可见，如果在文件系统中仅采用了多级索引组织方式，并不能获得理想的效果。
多级索引方式适合对大文件的查找
3.3 增量式索引组织方式
思想：为了能较全面地照顾到小、中、大及特大型作业，可以采取多种组织方式来构成文件的物理结构。
小文件使用直接寻址，中等文件使用单级索引，大型文件使用多级索引
所谓增量式索引组织方式，就是基于上述的基本思想来组织的，它既采用了直接寻址方式，又采用了单级和多级索引组织方式(间接寻址)。通常又可将这种组织方式称为混合组织方式。在 UNIX 系统中所采用的就是这种组织方式。
在 UNIX System V 的索引结点中设有 13 个地址项，即 addr-0 ~ addr-12，该系统的外存组织方式如下：
- 直接地址
为了提高对文件的检索速度，在索引结点中可设置直接地址项（一般为 10 个，addr-1 ~ addr-9），用来存放直接地址（盘块号），这样就可以直接获得该文件的盘块地址。一般把这种寻址方式称为直接寻址。
- 一次间接地址
对于大、中型文件，只采用直接地址是不现实的。为此，需再利用索引结点中的地址项 addr-10 来提供一次间接地址(single indirect)。这种方式的实质就是单级索引分配方式。
- 多次间接地址
当文件长度太大时，使用一次间址与 10 个直接地址项时地址空间仍不足，系统还需采用二次间址分配方式。这时，用地址项 addr-11 提供二次间接地址(double indirect)。该方式的实质是两级索引分配方式。同理，地址项 addr-12 作为三次间接地址(triple indirect)。