删除文件中间的字节而不移动结尾？

Question

例如,如果我有大量的数据条目存储在一个文件中,每个都有不同的大小,我有1000个条目,使文件像100MB大,如果我然后想删除文件中间的条目,大小为50KB,如何删除文件中空的50KB字节而不移动所有结束字节来填充它？

我正在使用诸如此类的winapi函数进行文件管理:

CreateFile,WriteFile,ReadFile和SetFilePointerEx

Answer 1

如果你真的想这样做,请在你的条目中设置一个标志.如果要从文件中删除条目,只需使该标志无效(逻辑删除),无需物理删除.下次添加条目时,只需浏览该文件,查找第一个无效条目,然后覆盖它.如果所有都经过验证,请将其附加到最后.这需要O(1)时间来删除条目并O(n)添加新条目,假设从磁盘读取/写入单个条目是基本操作.

您甚至可以进一步优化它.在文件的开头,存储位图(1用于无效).例如,0001000...表示文件中的第4个条目无效.添加条目时,1在位图中搜索第一个并使用随机文件I/O(与顺序文件I/O相反)将文件指针直接重定向到该条目的覆盖.以这种方式添加只需要O(1)时间.

哦,我注意到你的评论.如果您希望通过物理删除条目有效地执行此操作,一种简单的方法是将条目删除与文件中的最后一个交换,并删除最后一个,假设您的条目未排序.时间也很好,O(1)既可以添加也可以删除.

编辑:就像乔提到的那样this requires that all of your entries have the same size.您可以实现一个具有可变长度条目的条目,但这将比此处讨论的更复杂.