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

Question

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

• 它如何能如此高效地索引文件？
• 它使用什么数据结构进行文件搜索？
• 它的文件搜索怎么能这么快？

引用其常见问题解答，

“Everything” 只索引文件和文件夹名称，通常需要几秒钟来构建它的数据库。全新安装的 Windows 10（大约 120,000 个文件）将需要大约 1 秒的时间来编制索引。1,000,000 个文件大约需要 1 分钟。

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

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

常见问题进一步澄清。

“一切”会占用我的系统资源吗？

不，“一切”使用很少的系统资源。全新安装的 Windows 10（大约 120,000 个文件）将使用大约 14 MB 的内存和不到 9 MB 的磁盘空间。1,000,000 个文件将使用大约 75 MB 的内存和 45 MB 的磁盘空间。

Answer 1

• 它如何能够如此有效地索引文件？

首先，它仅索引文件/目录名称，而不索引内容。

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

如果这还不够，最后你可以尝试深入研究更低级的 Native API函数；我对这些没有经验，所以无法给你进一步的建议。您已经非常接近金属了，也许Linux NTFS 项目有一些您需要学习的概念。

• 它使用什么数据结构进行文件搜索？
• 它的文件搜索速度怎么这么快？

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