如何高效地搜索文件系統（算法）？

Question

深度優先搜索是搜索文件系統的一種可怕方式 - 實際上，可能位於非常接近根目錄的文件可能需要很長時間才能在DFS中找到，因爲DFS會被另一個文件系統分散注意力深層的，不相關的目錄層次結構。
然而，它的資源需求非常好 - 它需要保持打開的文件句柄的數量只與層次結構的深度成正比，而不是其大小。

廣度優先搜索是顯而易見的解決方案 - 速度非常快。
（我最後一次測量，花了大約在同一時間，DFS我的系統上，約〜8秒。）

然而，BFS有自己的問題 - BFS需要保持開放非常大量目錄處理，可能在數百萬。 （在我的系統，它是10萬門左右的把手，這是高的離譜它可以很容易地多。）

這會導致幾個問題：

• 保持開放這麼多的句柄消耗不僅內存（這是但是還有很多其他類型的資源，例如處理虛擬文件系統（網絡，安裝目錄等）中的文件以及可能還有其他有限的內核級資源。

• 它也會導致用戶遇到其他實際問題：例如，保持打開的虛擬目錄不再可關閉！這意味着，例如，用戶可能無法關閉程序，彈出某個設備或關閉某種外部連接。這種方法可能會產生各種問題。

這似乎是迭代加深，那麼就是解決方案。

問題？這在實踐中非常緩慢。
我遇到的麻煩是，對於深度級別爲的大型目錄（例如Windows中的WinSxS）重新列舉，即使它們不需要。上次我嘗試這個時候，迭代加深比我的系統上的DFS慢了15倍。所以一個8秒鐘的搜索大約需要120秒左右，這是不可接受的。

當然，試圖跟蹤你不應該打開的目錄（可能是因爲你注意到你不需要打開它們），這首先破壞了使用迭代深化的目的，揭露了所有的資源問題我們曾與BFS合作過。

所以，問題很簡單：

如果您正在搜索你不熟悉的文件系統，你應該如何着手實現速度和可用性之間可接受的平衡？比BFS有更好的選擇嗎？

Answer 1

如果你真的沒有任何關於文件的位置的指導，那麼我認爲你可以做的事情不多。你應該嘗試儘量減少搜索並用一些技巧來尋找時間，但是文件系統是分散的，沒有辦法讓你知道，因此很難在那裏做很多事情。在搜索子目錄之前在目錄中搜索文件在許多文件系統上的速度應該更快，特別是如果您正在查找可能已被內聯的小文件。不要用完整的BFS耗盡內核資源也是一件好事。

即使您只有提示文件的位置，這可以幫助很多。例如，如果用戶放在某個地方然後忘記了位置的文件，則從主目錄，臨時目錄和驅動器的根目錄開始，並執行一個DFS達到合理的遞歸限制（例如， 8會在我的Windows或OS X機器上找到任何手動放置的文件或自動下載的文件），理論上用戶通常不會意外地以深層樹結束，但自動生成的層次結構可能會變得很深。如果搜索失敗，請返回並搜索先前跳過的深層目錄。如果文件是，丟失，則搜索速度將會很慢，因此回退DFS以保證安全，並且不會因用戶繼續使用本機而導致太多問題。

最重要的是，如果系統有任何種類的搜索索引，請首先檢查，即使這意味着要編寫更多的代碼來支持它。