假设我们有一个由一堆固定大小的块组成的大文件。这些块中的每一个都包含一些可变大小的记录。每个记录必须完全适合单个块，然后根据定义，此类记录决不能大于一个完整的块。随着时间的流逝，随着记录从该"数据库"进出，记录将添加到这些块中或者从这些块中删除。

在某些时候，特别是在可能将许多记录添加到数据库中并删除了一些记录之后，许多块可能最终只能部分填充。

有什么好的算法可以对数据库中的记录进行混洗，从而通过更好地填充部分填充的块来压缩文件末尾的不必要块？

算法要求：

• 压缩必须代替原始文件进行，而不能临时将文件从其起始大小开始最多扩展几个块以上
• 该算法不应不必要地干扰已经基本上已满的块
• 整个块必须一次从文件中读取或者写入文件，并且应该假定写入操作相对昂贵
• 如果将记录从一个块移动到另一个块，则必须在将其从起始位置删除之前将其添加到新位置，以便在操作中断的情况下不会由于"失败"压缩而丢失任何记录。 (假定可以在恢复时检测到这种记录的临时重复)。
• 可用于此操作的内存可能只有几个块的数量级，仅占整个文件大小的很小一部分
• 假设记录的大小在10字节到1K字节之间，平均大小可能为100字节。固定大小的块约为4K或者8K，文件大小约为1000个块。

解决方案

如果没有对这些记录的排序，我只需使用从最后一个块中提取的记录填充前面的块。这将最大程度地减少数据的移动，这非常简单，并且应该在打包数据方面做得不错。

例如。：

// records should be sorted by size in memory (probably in a balanced BST)
records = read last N blocks on disk;

foreach (block in blocks) // read from disk into memory
{
    if (block.hasBeenReadFrom())
    {
        // we read from this into records already
        // all remaining records are already in memory

        writeAllToNewBlocks(records);

        // this will leave some empty blocks on the disk that can either
        // be eliminated programmatically or left alone and filled during
        // normal operation

        foreach (record in records)
        {
            record.eraseFromOriginalLocation();
        }

        break;
    }

    while(!block.full())
    {
        moveRecords = new Array; // list of records we've moved

        size = block.availableSpace();
        record = records.extractBestFit(size);
        if (record == null)
        {
            break;
        }

        moveRecords.add(record);
        block.add(record);

        if (records.gettingLow())
        {
            records.readMoreFromDisk();
        }
    }

    if(moveRecords.size() > 0)
    {
        block.writeBackToDisk();
        foreach (record in moveRecords)
        {
            record.eraseFromOriginalLocation();
        }
    }
}

更新：我忽略了内存中不阻塞的规则。我已经更新了伪代码来解决此问题。还解决了我的循环条件下的故障。

这听起来像是装箱问题的一种变体，但是在我们已经要改善的劣质分配中。因此，我建议研究成功解决垃圾箱包装问题的各种方法。

首先，我们可能想通过定义我们认为"足够充满"的内容(其中一个块足够充满而又不想触摸它)和什么是"太空"(其中一个块包含这么多的空白空间，因此必须添加更多的记录)。然后，我们可以将所有块分类为足够满，太空或者部分满(既不满也不空)。然后，将问题重新定义为如何通过创建尽可能多的足够多的块，同时最小化部分完全块的数量来消除所有太空的块。

我们还需要弄清更重要的事情：将记录放入尽可能少的块中，或者将它们适当地打包，但要读取和写入的块最少。

我的方法是对所有块进行初始遍历，将它们全部分类为上面定义的三个类之一。对于每个块，我们还希望跟踪其中的可用空间，对于太空的块，我们将需要具有所有记录及其大小的列表。然后，从太空的块中最大的记录开始，将它们移到部分充满的块中。如果要最大程度地减少读写，请将它们移到当前内存中的任何块中。如果要最小化浪费的空间，请找到仍保留记录的空白空间最少的块，并在必要时读取该块。如果没有任何块将保留该记录，请创建一个新块。如果内存中的某个块达到"足够多"的阈值，则将其写出。重复直到部分填充的块中的所有记录都已放置。

我已经跳过了许多细节，但这应该可以给我们一些想法。请注意，装箱问题是NP难题，这意味着对于实际应用，我们将需要确定对我们来说最重要的事情，因此可以选择一种在合理的时间内为我们提供最佳解决方案的方法。

尽管记录在固定大小的块内可能需要更多的工作，但我们可能可以利用这种算法。

有限时间内的堆碎片整理

修改在线(一次通过碎片整理)有界空间(内存要求)箱装箱算法的方法可能在这里起作用。

参见Coffman等人的"装箱近似算法：组合分析"。