要使用哪種數據結構

Question

我的系統在本地驅動器（例如c，d，e）中有數百萬個文件。現在要搜索一個文件，我們可以使用Windows的內置工具或Linux中的「find」等命令。 如果我想設計我自己的「查找」程序，它應該首先掃描所有目錄並將信息存儲在某個文件或數據庫中。現在，無論何時我想搜索文件，我們首先需要從數據庫或文件加載信息，然後搜索。

我需要建議，以決定使用哪種數據結構來存儲目錄結構，然後可以加載和查詢給定的文件名。

由於搜索是基於文件名，我想到了使用Hashmap，其中鍵將文件名和值將全路徑。使用Trie會使搜索速度變慢。另一個想法是使用倒置索引。但不知道哪一次更好。

謝謝。

Answer 1

一個散列表將會非常好，因爲它具有查找（以及插入和刪除）的O（1）。但問題是你不能使用散列表來進行「範圍搜索」。 「範圍搜索」就像「查找所有以擴展名cpp結尾的文件」。如果這不是你的問題，那麼我會建議實施哈希表。

Answer 2

您不能使用基於內存的結構（如正常的哈希表）。內存結構很適合搜索，但您必須將整個數據集加載到內存中才能搜索一條記錄。它非常緩慢，有時數據集太大而不適合內存。

我建議你嘗試一些基於磁盤的結構，如B-Tree或External Memory Hashmap。它們針對磁盤進行了優化，您可以在不加載整個數據集的情況下搜索記錄。

如果您不想自己編寫基於磁盤的搜索結構，請嘗試Google的LevelDB。