3

我的系统的本地驱动器(例如:c、d、e)中有数百万个文件。现在要搜索文件,我们可以使用 Windows 的内置工具或 linux 中的“查找”等命令。如果我想设计我自己的“查找”程序,它应该首先扫描所有目录并将信息存储在某个文件或数据库中。现在每当我想搜索文件时,我们首先需要从数据库或文件中加载信息然后搜索。

我需要建议来决定使用哪种数据结构来存储目录结构,然后可以加载和查询给定的文件名。

由于搜索是基于文件名的,所以我想到了使用 Hashmap,其中键是文件名,值是完整路径。使用 Trie 会使搜索变慢。另一个想法是使用倒排索引。但不确定哪个更好。

谢谢。

4

2 回答 2

0

哈希表对此非常有用,因为它具有 O(1) 用于查找(以及插入和删除)。但问题是您不能使用哈希表进行“范围搜索”。“范围搜索”类似于“查找所有以扩展名 cpp 结尾的文件”。如果这对您来说不是问题,那么我建议实施哈希表。

于 2013-04-27T18:43:07.107 回答
0

您不能使用基于内存的结构(如普通哈希表)。内存结构有利于搜索,但您必须将整个数据集加载到内存中才能搜索一条记录。它非常慢,有时数据集太大而无法放入内存。

我建议您尝试一些基于磁盘的结构,例如 B-Tree 或 External Memory Hashmap。它们针对磁盘进行了优化,您无需加载整个数据集即可搜索记录。

如果您不想自己编写基于磁盘的搜索结构,请尝试 Google 的 LevelDB。

于 2013-04-28T14:35:21.530 回答