目录

连续分配

特点

优势

劣势

链接分配

概念

隐式链接（对用户透明，题目默认）

特点：

优势：

劣势：

显式链接

特点：

优势：

劣势：

索引分配

概念：

特点：

工作原理：

优势

劣势

优化方法

---

连续分配

特点

• 物理块号计算：文件的物理块号可以通过起始块号（由文件控制块FCB提供）加上逻辑块号来计算。
• 文件存储：每个文件在磁盘上占据一组连续的块。

优势

• 随机存取：由于文件块是连续的，可以快速定位到文件中的任意位置，实现随机存取。

劣势

• 文件长度动态增加困难：文件长度不宜动态增加，因为需要保证块的连续性，这可能导致外部碎片的产生。
• 空间利用率问题：如果文件被删除或缩短，留下的空闲块可能太小而无法被其他文件使用，造成空间浪费。

链接分配

概念

链接分配通过离散分配方式来组织文件的块，从而消除了外部碎片。

隐式链接（对用户透明，题目默认）

隐式链接是一种常见的链接分配方式，它使得文件的块可以非连续地分布在磁盘的任何位置。

特点：

• 离散分配：文件的各个块可以随机分布在磁盘上，不要求连续。
• 指针链：除了最后一个块外，每个磁盘块都包含一个指向下一个磁盘块的指针。

优势：

• 空间利用率：由于块可以任意分配，磁盘空间得到了更有效的利用，减少了外部碎片。
• 灵活性：文件可以动态增长，不需要预先分配连续的空间。

劣势：

• 顺序访问：隐式链接仅支持顺序访问，如果要访问文件中的特定块，必须从第一个块开始，依次通过指针找到目标块。
• 访问效率低：查找特定块可能需要多次磁盘操作，这会降低访问效率。
• 额外空间：每个块中的指针也需要占用一定的存储空间。

显式链接

显式链接则是将文件的块号显式地存放在内存中的文件分配表（FAT）中，以此来管理文件的物理块。

特点：

• FAT表：文件的每个块号都存储在一个称为FAT的表中，该表通常驻留在内存中。
• 随机访问：通过FAT表，可以直接访问文件的任意块，无需顺序遍历。

优势：

• 检索速度：由于可以直接通过FAT表定位到文件的任意块，因此显著提高了文件的检索速度。
• 支持随机访问：用户可以随机访问文件的任何部分，而不必从文件开头开始。

劣势：

• 内存占用：FAT表需要占用较多的内存空间，尤其是在处理大量文件和磁盘块时。
• 维护开销：文件系统的每次修改（如文件的创建、删除或扩展）都可能需要更新FAT表，这增加了文件系统的维护开销。
• 性能瓶颈：如果FAT表过大，频繁的读写操作可能会导致性能瓶颈。

索引分配

概念：

索引分配的核心思想是将文件的所有磁盘块号集中存放在一个称为索引块的数据结构中。这个索引块充当了文件与存储介质之间的桥梁，使得文件的随机存取变得异常高效。

特点：

• 索引块：每个文件都有一个与之对应的索引块，这个索引块包含了文件所有数据块的地址信息。
• 随机存取：由于索引块中记录了文件所有块的地址，用户可以直接通过索引块定位到文件中的任意块，无需顺序访问，从而实现了高效的随机存取。
• 灵活性：索引分配不受文件块连续性的限制，文件的数据块可以分散在存储介质的任何位置，这样不仅减少了外部碎片，还提高了磁盘空间的利用率。

工作原理：

1. 当文件被创建时，文件系统为其分配一个索引块。
2. 索引块中为文件的数据块建立目录项，每个目录项包含一个指向实际数据块的指针。
3. 用户访问文件时，首先读取索引块，根据需要访问的逻辑块号找到对应的数据块地址，然后直接访问该数据块。

优势

• 快速定位：索引分配允许用户快速定位到文件中的任意位置，大大减少了访问文件时的磁盘寻址时间。
• 动态扩展：文件长度可以动态增加，只需在索引块中添加新的块地址即可，无需考虑块的连续性。
• 减少碎片：由于数据块可以非连续存储，有效减少了外部碎片，提高了磁盘空间的利用率。

劣势

• 额外的存储开销：索引块本身也需要占用存储空间，对于小文件来说，这可能造成一定的空间浪费。
• 管理复杂度：索引块的管理相对复杂，需要文件系统精心设计以维护其一致性。

优化方法

• 链接方案：对于大文件，可以将多个索引块链接在一起，以扩展索引块的数量。
• 多层索引：类似于操作系统的多级页表，多层索引解决了单个索引块大小限制的问题，允许更大的文件。
• 混合索引：结合了直接索引和多层索引的优点，对于小文件使用直接索引，对于大文件使用多层索引或链接，以优化存储效率和访问速度。