与其在表中存储对下一个节点的引用，为什么不能像传统的链表一样存储它，即使用下一个指针？
问问题
1815 次
3 回答
3
这是由于对齐。FAT（以及几乎任何其他文件系统）将文件数据存储在底层存储的一个或多个完整扇区中。因为底层存储只能读取和写入整个扇区，所以这种分配允许有效地访问文件的内容。
交错的问题
当一个程序想要在一个文件中存储一些东西时，它会提供一个缓冲区，比如要存储 1MB 的数据。现在，如果文件的数据扇区还必须保留next指向其下一个扇区的指针，则该指针信息将需要与实际的用户数据交错。因此文件系统需要建立另一个缓冲区（略大于提供的 1MB），为每个输出扇区复制一些用户数据和相应的next指针，并将这个新缓冲区提供给存储。这会有些低效。除非文件系统总是将文件数据存储到新扇区（通常不会），否则重写这些next指针也将是多余的。
更大的问题是在文件上尝试读取操作时。文件现在将像磁带设备一样工作：在文件的主要元数据中只知道第一个扇区的位置，为了到达扇区 1000，文件系统需要按顺序读取它之前的所有扇区：读取扇区 0，找到从加载扇区 1 的地址next指针、读取扇区 1 等。每个随机 I/O 的典型寻道时间约为 10 毫秒（假设是硬盘驱动器），到达扇区 1000 大约需要 10 秒。即使扇区是按顺序排列的，当文件系统驱动程序处理扇区 N 的数据时，磁盘头也会飞过下一个扇区，当发出对扇区 N+1 的读取时，可能为时已晚，需要磁盘旋转整个转（7200 RPM 驱动器为 8.3 毫秒），然后才能再次读取下一个扇区。不过，磁盘缓存可以并且将对此有所帮助。
写入单个扇区通常是原子操作（取决于硬件）：断电后读回扇区返回其旧内容或没有中间状态的新内容。数据库应用程序通常需要知道哪些写入是原子的。如果文件系统在同一扇区中交错文件数据和元数据，则需要向应用程序报告小于实际扇区大小的扇区。例如，它可能需要报告 504 而不是说 512 字节。但它不能这样做，因为应用程序通常假定扇区大小是 2 的幂。此外，如果将存储在此类文件系统上的文件复制到另一个文件系统，则很可能无法使用具有不同报告扇区大小的文件系统。
更好的方法
FAT 格式更好，因为所有next指针都存储在相邻扇区中。对于 FAT12、FAT16 和不是非常大的 FAT32 卷，整个表足够小以适合内存。FAT 仍然将文件的块记录在链表中，因此为了实现有效的随机访问，实现需要缓存每个文件的链。在足够大的卷上（可以运行足够大的文件），这样的缓存可能不再适合内存。
ext3使用直接和间接块。这种简单的格式避免了 FAT 所需的预处理需求，并且当需要间接块时，每个 I/O 只需最少的额外读取量即可完成。这些额外的读取由操作系统缓存，因此它们的开销通常可以忽略不计。
其他变体也是可能的，并被各种文件系统使用。
散记
为了完整起见，一些硬盘驱动器可以格式化为稍大的扇区大小（比如 520 字节），以便文件系统可以在同一扇区中打包 512 字节的文件数据和几个字节的元数据。然而由于上述原因，我不相信有人使用这种格式来存储文件下一个扇区的地址。这些额外的字节可以更好地利用：想到额外的校验和和时间戳。我相信时间戳用于提高某些 RAID 系统的性能。这种用法仍然很少见，大多数软件根本无法使用它们。
一些文件系统可以直接将足够小的文件内容保存在文件元数据中，而不占用不同的扇区。ReiserFS有争议的尾部包装。这在这里并不重要：大文件仍然受益于正确映射到存储扇区。
于 2014-03-15T14:05:36.163 回答
0
任何现代操作系统都需要的不仅仅是指向其文件系统的下一个数据块的指针：属性（加密、压缩、隐藏……）、安全描述符（ACL 列表项）、对不同硬件的支持、缓冲。这只是任何好的文件系统所具备的一小部分功能。
查看 Wikipedia 上的文件系统，了解任何现代文件系统的其他功能。
于 2014-03-15T10:07:42.520 回答
0
如果我们忽略 FAT12 在两个项目之间共享一个字节以将 12 位压缩为 1.5 个字节的细节，那么我们可以专注于这个问题的更深层次的含义。
事实证明，FAT系统相当于一个链表，有以下几点：
- “下一个”指针位于数组（FAT）中，而不是附加或附加到实际数据中
- “next”中写入的值是一个整数，而不是更熟悉的下一个节点的内存地址。
- 节点不是动态保留的，而是由另一个数组表示的。该阵列是硬盘驱动器的整个数据部分。
作为软件工程师教育的一部分，我们被分配的一个有趣的练习是将使用内存指针的应用程序转换为使用整数值的等效应用程序。理由是某些处理器（PDP-11？或另一个 PDP-xx）执行整数运算的速度比内存指针操作快得多，甚至可能禁止对指针进行任何运算。
于 2017-07-09T04:09:47.417 回答