language-agnostic - 如何有效地搜索文件系统(算法方面)？

Question

深度优先搜索是一种可怕的文件系统搜索方式——在实践中，可能位于非常靠近根目录下的文件可能需要很长时间才能使用 DFS 找到，因为 DFS 会分散注意力另一个深层的、不相关的目录层次结构。
然而，它的资源需求非常好——它需要保持打开状态的文件句柄数量只与层次结构的深度成正比，而不是它的大小。

广度优先搜索是显而易见的解决方案——它非常快。
(我上次测量时，它与我系统上的 DFS 花费的时间大致相同，大约 8 秒。)

然而 BFS 有其自身的问题 -- BFS 需要保持打开非常大量的目录句柄，可能有数百万。 (在我的系统上，它大约有 100,000 个句柄，这高得离谱。它很可能会更多。)

这会导致几个问题:

• 保持打开如此多的句柄不仅会消耗内存(无论如何相对便宜)，还会消耗许多其他类型的资源，例如虚拟文件系统(网络、挂载目录等)中文件的句柄，以及可能是其他有限的内核级资源。

• 它还会给用户带来其他实际问题:例如，一个一直处于打开状态的虚拟目录无法再关闭!这意味着，例如，用户可能无法关闭程序、弹出某些设备或关闭某种外部连接。这种方法可能会出现各种各样的问题。

这似乎是迭代深化，然后才是解决方案。

问题是什么？实践起来很慢。
我的麻烦是大型目录(例如 Windows 中的 WinSxS)被重新枚举每个深度级别，即使它们不需要这样做。上次我尝试这样做时，迭代加深在我的系统上比 DFS 慢约 15 倍。所以 8 秒的搜索大约需要 120 秒左右，这是 Not Acceptable 。

当然，试图跟踪您不应该打开的目录(也许是因为您注意到您不再需要打开它们)违背了使用迭代深化的初衷，因为它揭示了我们的所有资源问题有 BFS。

所以，问题很简单:

如果您正在搜索一个您不熟悉的文件系统，您应该如何着手在速度和可用性之间取得可接受的平衡？有比 BFS 更好的选择吗？

Answer 1

如果您真的对文件的位置没有任何指导，那么我认为您无能为力。您应该尝试使用一些技巧来尽量减少寻道和寻道时间，但是文件系统会变得支离 splinter 并且您无法了解这一点，因此很难在那里做很多事情。在许多文件系统上，在搜索子目录之前搜索目录中的文件应该更快，尤其是当您正在寻找可能已内联的小文件时。使用完整的 BFS 不耗尽内核资源也是一件好事。

即使您只是知道文件可能在哪里，这也会有很大帮助。例如，如果它是用户放在某处然后忘记位置的文件，则从主目录、临时目录和驱动器的根目录开始，并执行 DFS 直到合理的递归限制(例如 6- 8 会在我的 Windows 或 OS X 机器上找到任何手动放置的文件或自动下载的文件)，理论上用户通常不会意外地得到很深的树，但自动生成的层次结构可能会很深。如果该搜索失败，请返回并搜索您之前跳过的深层目录。如果文件就是丢失了，无论如何搜索都会很慢，所以为了安全起见，回退到 DFS 并且不会在用户继续使用机器时造成太多问题。

最重要的是，如果系统有任何类型的搜索索引，请先检查它，即使这意味着要编写更多代码来支持它。