假设您有一个由许多固定大小块组成的大文件。每个块包含一些变量大小的记录。每条记录必须完全适合单个块中,因此这样的记录定义上永远不会比完整块更大。随着时间的推移,“数据库”中的记录被添加到这些块中并从中删除。
在某些时候,特别是在向数据库添加了许多记录并删除了几个记录之后,许多块可能仅部分填充。
什么是一种好的算法来重新排列这个数据库中的记录,以通过更好地填充部分填充的块来压缩文件末尾的不必要块?
算法的要求:
- 压缩必须在原始文件中进行,而不是通过暂时将文件扩展超过其起始大小的几个块。 - 算法不应不必要地干扰已经主要充满的块。 - 整个块必须一次从/写入文件,并且应该假定写操作相对昂贵。 - 如果将记录从一个块移动到另一个块,则必须在将其从起始位置删除之前将其添加到新位置,以便在操作中断时不会因“失败”的压缩而丢失记录。(假设可以在恢复时检测到这些记录的临时复制)。 - 可以用于此操作的内存可能只有几个块的数量,这是整个文件大小的非常小的百分比。 - 假设记录的数量为10字节到1K字节,平均大小可能为100字节。固定大小的块大约为4K或8K,文件大约为数千个块。
在某些时候,特别是在向数据库添加了许多记录并删除了几个记录之后,许多块可能仅部分填充。
什么是一种好的算法来重新排列这个数据库中的记录,以通过更好地填充部分填充的块来压缩文件末尾的不必要块?
算法的要求:
- 压缩必须在原始文件中进行,而不是通过暂时将文件扩展超过其起始大小的几个块。 - 算法不应不必要地干扰已经主要充满的块。 - 整个块必须一次从/写入文件,并且应该假定写操作相对昂贵。 - 如果将记录从一个块移动到另一个块,则必须在将其从起始位置删除之前将其添加到新位置,以便在操作中断时不会因“失败”的压缩而丢失记录。(假设可以在恢复时检测到这些记录的临时复制)。 - 可以用于此操作的内存可能只有几个块的数量,这是整个文件大小的非常小的百分比。 - 假设记录的数量为10字节到1K字节,平均大小可能为100字节。固定大小的块大约为4K或8K,文件大约为数千个块。