优化磁盘数据的位置以进行顺序访问

Question

我需要在大约1k块的磁盘上存储大量数据.我将以难以预测的方式访问这些对象,但可能存在模式.

是否有我可以使用的算法或启发式算法将根据我的访问模式重新排列磁盘上的对象,以尝试最大化顺序访问,从而最大限度地减少磁盘搜索时间？

Answer 1

在现代操作系统（Windows、Linux 等）上，您绝对无法优化寻道时间！原因如下：

1. 您处于一个先发制人的多任务系统中。您的应用程序及其所有数据可以随时刷新到磁盘 - 用户切换任务、屏幕保护程序启动、电池电量耗尽等。
2. 您不能保证文件在磁盘上是连续的。执行 Aaron 的第一个要点并不能确保文件不碎片化。当您开始写入文件时，操作系统不知道文件将有多大，因此它可以将它放在一个很小的空间中，并在您向其中写入更多数据时将其分段。
3. 仅当文件大小小于应用程序中的可用地址范围时，内存映射文件才有效。在 Win32 上，可用的地址空间量约为 2Gb - 应用程序使用的内存。映射较大的文件通常涉及取消映射和重新映射文​​件的部分，这不是最好的做法。
4. 将数据放在文件的中心是没有帮助的，因为众所周知，文件的中心部分可能是最碎片化的部分。

套用Raymond Chen 的话，如果您必须询问操作系统限制，您可能做错了什么。将您的文件系统视为一个不可变的黑匣子，它就是这样（我知道，您可以使用 RAID 等来提供帮助）。

您必须采取的第一步（并且必须在您进行优化时采取）是衡量您目前所拥有的。永远不要假设任何事情。用硬数据验证一切。

从您的帖子来看，您似乎还没有真正编写任何代码，或者，如果您已经编写了，那么目前没有性能问题。

唯一真正的解决方案是着眼于更大的图景，并开发出在不停止应用程序的情况下从磁盘中获取数据的方法。这通常是通过异步访问和推测加载来实现的。如果您的应用程序总是访问磁盘并处理数据的小子集，您可能需要考虑重新组织数据，将所有有用的东西放在一个地方，将其他数据放在其他地方。如果不知道完整的问题域，就不可能真正有帮助。

Answer 2

根据您所说的“难以预测”的含义，我可以想到一些选择：

如果您始终基于相同的块字段/属性进行查找，请将按该字段排序的记录存储在磁盘上。这使您可以使用二分搜索来实现 O(log n) 效率。

如果您在不同的块字段上查找，请考虑为每个字段存储一个外部索引。B树的效率为 O(log n)。当您查找时，抓住适当的索引，在其中搜索您的块的数据文件地址并跳转到它。

更好的是，如果您的块是同构的，请考虑将它们分解为数据库记录。数据库为您提供优化的存储、索引以及免费执行高级查询的能力。