performance - 是什么让 Everything 的文件搜索和索引如此高效？

Question

Everything是一个文件搜索程序。由于其作者尚未发布源代码，我想知道它是如何工作的。

它如何能如此高效地索引文件？

它使用什么数据结构进行文件搜索？

它的文件搜索怎么能这么快？

引用其常见问题解答，

"Everything" only indexes file and folder names and generally takes a few seconds to build its database. A fresh install of Windows 10 (about 120,000 files) will take about 1 second to index. 1,000,000 files will take about 1 minute.

如果索引整个Windows 10只需要一秒钟，而索引一百万个文件只需要1分钟，这是否意味着它每秒可以索引120,000个文件？

为了使搜索快速，必须有一个特殊的数据结构。按文件名搜索不仅从头搜索，大多数情况下也从中间搜索。这使它成为一些广泛使用的索引结构，例如 Trie和 Red–black tree无效。

常见问题进一步澄清。

Does "Everything" hog my system resources?

No, "Everything" uses very little system resources. A fresh install of Windows 10 (about 120,000 files) will use about 14 MB of ram and less than 9 MB of disk space. 1,000,000 files will use about 75 MB of ram and 45 MB of disk space.

Answer 1

• How could it index files so efficiently?

首先，它只索引文件/目录名称， not contents .

我不知道它是否足以满足您的需求，但通常的方法是使用 FindFirstFile功能。编写一个简单的 C 程序来递归地列出文件夹/文件，看看它是否对你来说足够快。优化的第二步是并行运行线程，但也许磁盘访问将成为瓶颈，如果这样多线程几乎没有什么好处。

如果这还不够，最后你可以尝试挖掘更低的 Native API职能;我没有这方面的经验，所以我不能给你进一步的建议。你会非常接近金属，也许是 Linux NTFS project有一些你需要学习的概念。

• What data structures does it use for file searching?
• How can its file searching be so fast?

嗯，你知道有许多不同的数据结构是为快速搜索而设计的……作者可能运行了很多基准测试。