java重新组织文件中的数据

Question

我在使用一个预先存在的文件系统，所以我不能改变它的结构。我还使用Java，使用RandomAccessFile对象

一个文件可以保存许多独立的数据块。我知道在哪里可以找到正确的文件和每个块的开头，没有任何问题，并且知道它的确切大小。文件分为4 KB的“扇区”，其中数据只能从扇区的开头开始。数据块大小不一。这一切都很好，直到规模变化到足以容纳它所需的扇区数量发生变化为止。。。一个块可以是4到256个扇区之间的任何地方，所以我可以给每个块额外的空间以防它增长，这不是一件小事

我需要找到一种方法将这个编辑过的块保存回文件中，但它不适合以前的位置，所以我必须留出空间。我可以很容易地更新所有元数据，这些元数据告诉我现在所有东西都存储在哪里，这不是问题。问题是我不知道一种有效的方法来转移这个文件中的数据。该文件将有1024个数据块，每个数据块的范围从4到256个扇区（16KB到1MB）。因此，该文件的大小可能为1GB。一次加载所有文件是不可能的

我的第一个想法是做一种连锁反应。让块A成为我现在保存的更大、修改版本的块。在我的程序中保留一个扇区的内存，在Chunk a的旧位置后加载第一个扇区，将其保存在Chunk a用来开始的位置，并将后续扇区向后移动，直到文件结束，然后最后将新扇区固定到末尾。我忍不住觉得这个想法效率太低了。有人有更好的吗

如果有帮助的话，我可以轻松、稳定地访问文件中每个块的位置以及每个块占用的扇区数。都在文件头中

Answer 1

你所描述的问题基本上就是碎片问题。或者我应该说，碎片化通常是避免数据发生变化时过度移动的结果。你能做的最好的事情就是查看磁盘和内存碎片的现有解决方案，以获得想法。这个问题已经存在了很长一段时间，因为计算机已经有了存储（包括易失性和持久性），所以它得到了很好的研究

在文件系统中，文件将对应于chunks的数据，文件表是header的一种形式。文件系统具有将文件分解成不必在磁盘上形成连续块的碎片的能力。由于您不能更改必须维护的文件格式，因此您不能选择拆分块并在块的末尾保留指向其继续部分的指针。但是，当更改文件以使其比当前适合的文件更大时，文件系统显然不会移动所有后续文件以腾出空间。那将是一个极其昂贵的行动。同样，你也不想在编辑过的块之后移动所有的块。由于机械介质（旋转磁盘）的物理磁盘访问在数据集中（例如一个文件）的情况下变得越来越低效，因此偶尔会进行碎片整理，在一批中执行移动文件以更有效地利用空间的耗时任务

在内存中，程序必须分配内存才能使用。操作系统可以从物理内存空间中获取可用内存块，并将其呈现给它承载的程序，就好像每个程序都有自己的连续内存空间一样。这是一个必要的抽象，以确保程序可以独立运行，而不必相互跟踪。程序在处理数据时会不断地分配空间和取消分配空间，这会导致可用内存的碎片化。然而，有时需要一定数量的连续内存（如程序所示），比如大字节数组。如果程序的内存空间中不存在这样的可用内存块，则必须移动数据，直到空闲内存汇集在一个足够大的块中。如果做不到这一点，就会出现内存不足的错误。要了解这些事情是如何完成的，请调查C programming language memory allocation functions

上述方法的好处是：如果没有必要，不要试图始终将文件保持在最佳大小，但如果时间允许或情况需要，请重新安排

让我们看一个例子。假设有3个块，大小分别为4、8和6个扇区。标头记录每个块的起始位置

我们现在编辑区块2，它变为10个扇区长。它不再适合当前的空间。因此，我们遍历该文件，找到第一个有足够的可用空间容纳10个扇区的地址，将编辑的区块移动到那里，并更新标题。请注意，旧数据可以保留或被屏蔽

为了找到第一个足够大的可用空间块来容纳一个新的或编辑过的块，我们需要研究头来映射文件中的内存使用情况。例如，新的情况留下了8个未使用的扇区，从地址4到地址11。如果找不到足够大的空闲空间块，你就把它放在末尾。然后，文件的大小将不得不增加

那么我们如何控制碎片呢？必须偶尔对文件空间使用情况进行分析。使用头部，或者在更新期间保留一些元数据，这可能非常简单，不需要太多处理。如果满足某些条件（例如，文件的20%由未使用的扇区组成），则启动一轮碎片整理。如果必须将块放在文件，但没有剩余的空间（使用了1 GiB），您应该首先尝试进行一轮碎片整理，然后移动已编辑的块或添加新块。如果碎片整理没有释放出足够的空间，那么您就遇到了限制（比如程序内存不足错误）

碎片整理方法可能非常简单，也可能非常聪明，这取决于它需要的速度。简单的做法是：只需按块在文件中出现的顺序移动每个块，使其从前一块的末尾开始

这保证了完成后，文件的大小将尽可能小。然而，因为它没有留下“开放空间”，所以当你第一次以一种使块更大的方式编辑块时，你会再次引入碎片，因为根据定义，它不再适合（除非它是文件中的最后一个）。而且，它将从前面有空空间的第一个块开始移动所有块，因此这是一个昂贵的操作

你可以尝试更聪明的方法来加快搜索速度，比如从文件末尾开始搜索时，将每个块移动到最适合它的空白处。这不会移动所有的块。一些未使用的空间将保留下来，但比以前少了

如何对碎片整理算法建模取决于您的用例。你甚至可以动态地选择，比如当你达到最大文件大小时的重载方法，如果你只是超过了未使用空间的某个阈值，则可以选择更快、更轻的算法

Answer 2

其中一个想法是，每次修改都会创建一个新文件。假设你经历了一个修改周期，一旦完成，你就创建了一个新文件，并将所有修改和未修改的块以新的顺序和日志（跟踪块坐标）写入新文件
优点：提供每次修改的历史记录，相对简单的逻辑
缺点：磁盘空间效率低下，如果修改后的块是整个文件的一小部分，则写入可能效率低下

到目前为止，更复杂的想法是只存储原始文件和每次修改的增量序列。然后在检索时，您必须根据块的原始状态和与该特定块相关的增量动态构建块的状态