表示/分配文件中空闲空间的数据结构和算法
我有一个带有“洞”的文件，并希望用数据填充它们; 我还需要能够释放“已用”空间并腾出空间。
我正在考虑使用映射偏移量和长度的双映射。 但是，如果文件中存在真正的微小差距，我不确定这是否是最好的方法。 位图可以工作，但我不知道如何轻松切换到某些特定区域的空间。 也许某种基数树是要走的路？
对于它的价值，我正在加快现代文件系统设计（ZFS，HFS +，NTFS，XFS，分机......），我发现他们的解决方案严重不足。
我的目标是有相当不错的空间节省（因此对小碎片的关注）。 如果我不在意这一点，我只会去两棵张开的树木......一个按偏移排序，另一个按照偏移量排序的长度排序。 请注意，这会为所有日志（m）的工作集时间分配log（n）...相当不错...但如前所述，不处理有关高碎片的问题。
我已经发布了能够做到这一点的商业软件。 在最新的迭代中，我们最终将文件的块分类为“类型”和“索引”，因此您可以读取或写入“foo类型的第三个块”。 该文件的结构如下：
1）文件头。 在主类型列表中的点。 2）数据。 每个块都有一个包含类型，索引，逻辑大小和填充大小的标题。 3）每个给定类型的（偏移量，大小）元组数组。 4）跟踪类型的（类型，偏移量，数量）数组。
我们定义它以便每个块都是一个原子单元。 你开始写一个新的块，并且在开始其他任何事情之前写完了。 你也可以“设置”块的内容。 开始一个新的块总是附加在文件的末尾，所以你可以追加尽可能多的，而不是分割块。 “设置”块可以重新使用空块。
当你打开文件时，我们将所有索引加载到RAM中。 在刷新或关闭文件时，我们在文件末尾重新编写了已更改的每个索引，然后在文件末尾重新编写了索引索引，然后更新了前面的标头。 这意味着对文件的更改都是原子的 - 要么提交到标题更新点，要么不提交。 （有些系统使用两个头8 kB的头部拷贝来保存头部，即使磁盘扇区坏了;我们没有那么做）
其中一个块“类型”是“空闲块”。 当重写改变的索引以及替换块的内容时，磁盘上的旧空间被合并到保留在空闲块数组中的空闲列表中。 相邻的空闲块合并成一个更大的块。 当您“设置内容”或更新的类型块索引时，空闲块会被重新使用，但不会用于索引索引，索引索引始终写入最后。
因为索引总是保存在内存中，所以使用打开的文件非常快 - 通常只需一次读取即可获取单个数据块的数据（或获取流式数据块的句柄）。 打开和关闭有点复杂，因为它需要加载和刷新索引。 如果它成为问题，我们可以根据需要加载次要类型索引，而不是预先分摊成本，但它对我们来说从来不是问题。
持久性（磁盘上）存储的首要优先事项：稳健性！ 即使计算机在处理文件时断电，也不要丢失数据！ 磁盘存储的第二优先级：不要做更多的I / O！ 搜寻是昂贵的。 在闪存驱动器上，每个单独的I / O都很昂贵，并且写入是双倍的。 尝试对齐和批量I / O。 使用类似malloc（）的磁盘存储通常不是很好，因为它的搜索次数太多。 这也是我不喜欢内存映射文件的原因 - 人们倾向于将它们当作RAM来对待，然后I / O模式变得非常昂贵。
对于内存管理，我是BiBOP *方法的粉丝，通常在管理碎片方面效率很高。
这个想法是根据它们的大小分离数据。 这种方式，在一个“袋子”内，你只有“块”的小块，具有相同的大小：
该包保留了一个简单的可用页面的自由列表。 每个页面都在可用存储单元的自由列表中覆盖这些单元。
您需要一个索引来将大小映射到相应的包。
您还需要针对“超出规范”请求的特殊待遇（即要求分配大于页面大小的请求）。
这种存储空间效率极高，特别是对于小型对象，因为开销不是按对象进行的，但存在一个缺点：最终可能会出现仍然包含一个或两个占用存储单元的“几乎空”的页面。
如果您有能力“移动”现有对象，这可以得到缓解。 这有效地允许合并页面。
（*）BiBOP：大包页
我会建议根据FUSE制作定制的文件系统（当然可能包含一个文件）。 FUSE有许多可用的解决方案可供您基于 - 我建议选择不相关但最简单的项目，以便轻松学习。
选择什么算法和数据结构，可以高度满足您的需求。 它可以是：地图，列表或文件通过即时压缩/解压缩分割成块。
你提出的数据结构是好主意。 正如你清楚看到的那样有一个折衷：分裂与压缩。
一方面 - 最好的压缩，最高的碎片 - 张开和许多其他种类的树木。
另一方面 - 最低碎片化，最差压实链表。
在B树和其他之间。
正如你所理解的那样，你说优先考虑：节省空间 - 同时关心性能。
为了达到所有要求，我会推荐你混合使用数据结构。
这种解决方案可以根据需求快速响应，同时在使用时优化其中的内容（例如“每次读取10MB数据 - > 1MB碎片整理）或空闲时刻。
链接地址: http://www.djcxy.com/p/4579.html上一篇: Data structure and algorithm for representing/allocating free space in a file
下一篇: Why std::atomic overloads each method with the volatile