非连续空间存放方式

我们已经对连续分配的方式有了一定的了解，并且也清楚了它存在的问题和局限性。为了解决这些问题，非连续存放的方式应运而生。非连续空间存储大致可以分为两种形式：链表形式和索引形式。

链式分配

链式分配是一种离散分配的方式，用于为文件分配非连续的磁盘块。它有两种分配方式：显示链接和隐式链接。

隐式链接

隐式链表分配与我们已知的Java链表知识基本是一致的，都需要存储下一个节点的指针。但为什么称之为隐式链接呢？因为我们不知道每个节点的指针是什么，只有通过遍历的方式从头节点开始逐步获取下一个节点的指针。每次操作都是相同的，指针并没有存储起来。在隐式链接分配中，目录项只存储了头节点（磁盘块）指针和尾节点（磁盘块）指针。当需要分配新的磁盘块时，我们使用最后一个磁盘块中的指针指向新的磁盘块，并将新的磁盘块标记为最后一个磁盘块。

现在让我们考虑一个问题：使用隐式链接如何将逻辑块号转换为物理块号？我们可以将其类比为Java中的链表如何找到相应的元素。

当用户提供要访问的逻辑块号 i 时，操作系统需要找到所需访问文件的文件控制块（FCB）。从FCB中我们可以得知文件的起始块号，然后将逻辑块号 0 的数据读入内存，通过这个可以知道逻辑块号 1 的物理块号，然后再读入逻辑块号 1 的数据进入内存，如此类推，最终可以找到用户所需访问的逻辑块号 i。因此，访问逻辑块号 i 需要进行 i + 1 次磁盘 I/O 操作。隐式链接分配就像Java中的链表一样只能按顺序访问，不支持随机访问，因此查找效率较低。

现在让我们考虑另一个问题：使用隐式链接是否方便文件扩展？我们可以将其类比为Java中的链表是否方便进行扩容呢？

我们知道，目录项中存储了结束块号的物理地址。因此，如果要扩展文件，我们只需要将新分配的磁盘块挂载到结束块号的后面。我们修改结束块号的指针指向新分配的磁盘块，并更新目录项。隐式链接分配类似于Java中的链表，很方便进行文件扩展。所有的空闲磁盘块都可以被利用，没有碎片问题，存储利用率较高。

显式链接

有隐式连接那么就有显式链接，隐式链接我们说了没有存储各个节点指针所以每次都需要重新从头结点来获取下一指针节点，那么显示链接是把用于链接各个物理块的指针显式地存放在一张表中，该表称为文件分配表（FAT，File Allocation Table）。

由于查找记录的过程是在内存中进行的，从而显著提高了检索速度并减少了访问磁盘的次数。但也正是整个表都存放在内存中的关系，它的主要的缺点是不适用于大磁盘。

举个例子，假设有一个拥有200GB空间和1KB块大小的磁盘。根据显式链接的方式，需要在文件分配表中存储2亿项，每一项对应磁盘上的一个块。如果每一项需要4个字节的存储空间，那么文件分配表将占用800MB的内存。显然，对于大磁盘而言，这种方式并不适合。

索引分配

理解索引分配之前，可以先想一下MySQL中的索引结构，这样可以更好的理解索引分配的原理。

链表的方式解决了连续分配的磁盘碎片和文件动态扩展的问题，但是不能有效支持直接访问（FAT除外）。为了解决这个问题，可以采用索引的方式。

索引的实现是为每个文件创建一个「索引数据块」，里面存放的是指向文件数据块的指针列表，类似于书的目录。通过查阅索引数据块，可以快速找到对应的数据块。

此外，文件头还需要包含指向「索引数据块」的指针。这样可以通过文件头知道索引数据块的位置，然后通过索引数据块里的索引信息找到对应的数据块。

当创建文件时，索引块的所有指针都被设置为空。当首次写入第 i 块时，从空闲空间中获取一个块，并将其地址写入索引块的第 i 个条目。这样，通过文件头中的指向索引数据块的指针，可以知道索引数据块的位置，并通过索引数据块中的索引信息找到对应的数据块。

索引分配的优点包括：

• 创建、增大和缩小文件都很方便；
• 没有碎片问题；
• 支持顺序读写和随机读写。

然而，索引分配也有一些缺点。由于索引数据也需要存放在磁盘块中，如果文件很小，实际上只需要一个块就可以存放，但仍需要额外分配一个块来存放索引数据，这会带来额外的开销。

如果文件很大，以至于一个索引数据块无法容纳全部的索引信息，我们可以采用组合的方式来处理大文件的存储。

组合方式是链表 + 索引，也被称为「链式索引块」。在这种实现方式中，索引数据块中会预留一个指针，用于存放下一个索引数据块的地址。当一个索引数据块的索引信息用完时，可以通过该指针找到下一个索引数据块的信息。然而，这种方式也会面临链表方式的问题，即如果某个指针损坏了，后续的数据将无法读取。

为了解决这个问题，可以采用多级索引的方式。多级索引将一个大文件的索引信息分散到多个索引数据块中，以减轻单个索引数据块的负担。类似于MySQL的B+树索引结构，多级索引也在非叶子节点存储了索引数据，而索引指针指向叶子节点的数据。尽管存在一些不同，但它们的逻辑是相似的。

总结

非连续空间存放方式是为了解决连续分配方式的问题和局限性而提出的。其中，链式分配方式包括隐式链接和显式链接两种形式。隐式链接通过存储头节点和尾节点指针的方式实现文件的非连续分配，但查找效率较低且不支持随机访问，但方便文件扩展且没有碎片问题。显式链接通过文件分配表存储物理块的指针，提高了检索速度但不适用于大磁盘。

索引分配方式则通过为每个文件创建索引数据块，并在文件头和索引数据块中存储指针信息，实现了文件的非连续分配和直接访问。索引分配的优点包括方便创建、扩展和缩小文件，没有碎片问题，支持顺序和随机读写。然而，索引分配也存在一些缺点，如对小文件的额外开销。

为了解决大文件存储问题，可以采用链式索引块和多级索引的组合方式。链式索引块通过指针连接多个索引数据块，但可能面临指针损坏导致数据无法读取的问题。多级索引将大文件的索引信息分散到多个索引数据块中，提高了文件系统的性能和可靠性。通过这些优化，可以更好地处理大文件存储，并提高文件系统的效率。