什么使得Everything文件搜索和索引如此高效？

Question

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

• 它是如何如此高效地索引文件的？
• 它使用哪些数据结构来进行文件搜索？
• 它如何实现如此快速的文件搜索？

引用其常见问题解答：

"Everything"仅索引文件和文件夹名称，并且通常需要几秒钟来构建其数据库。在Windows 10上进行全新安装（约120,000个文件）将花费约1秒钟进行索引。 100万个文件将需要大约1分钟。

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

为了使搜索快速，必须有一种特殊的数据结构。按文件名搜索不仅从开头搜索，而且在大多数情况下还从中间开始搜索。这使得一些广泛使用的索引结构，如Trie和红黑树失去了效力。

常见问题解答进一步澄清了问题：

"Everything"是否占用我的系统资源？

不，"Everything"使用非常少的系统资源。在Windows 10上进行全新安装（约120,000个文件）将使用大约14MB的RAM和不到9MB的磁盘空间。100万个文件将使用大约75MB的RAM和45MB的磁盘空间。

- Sraw

---

据说它不索引文件内容。这使得这个谜团变得不那么有趣了。 - Veedrac

请注意，每分钟1,000,000个文件/仅大约为20k个文件每秒; 可能全新的Windows安装允许跳过某些文件或更快地处理它们。 - Veedrac

在最佳条件下，对文本文件进行基本的正则表达式搜索可以以每秒多GB的速度运行；即使使用线性扫描处理几十MB内存上的查询也不算令人印象深刻。 - Veedrac

仅使用简单的文本文件？嗯...这并不是一个好主意。 - Sraw

为什么不呢？如果它能工作，那就行了。 - Veedrac

我投票关闭此问题，因为它正在询问我们一个特定的闭源应用程序如何工作。我建议重新表述问题，不要询问这个程序具体做什么，而是如何一般性地解决问题（但你在这里提出了多个问题，这是不鼓励的，其中一个似乎纯粹是一个磁盘I/O问题，与数据结构无关，而另一个可能是在寻找“后缀树”）。 - Bernhard Barker

Answer 1

短答案：MFT（主文件表）

获取数据

许多搜索引擎过去都会递归地遍历整个磁盘结构，以便找到所有文件。因此，即使不索引内容，完成索引过程也需要更长的时间。如果还要索引内容，那么时间就更长了。

从我对Everything的分析来看，它根本不进行递归。如果我们观察速度，在约5秒钟内，它就可以索引整个1TB驱动器（SSD）。即使必须进行递归，也会花费更长的时间，因为有成千上万个小文件，每个文件都有自己的文件大小、日期等，分散在各个地方。

相反，Everything甚至不接触实际数据，它读取和解析硬盘的“索引”。对于NTFS，MFT存储所有文件名，它们的物理位置（类似于Linux中iNodes的概念）。因此，在一个小的连续区域（一个文件）中，MFT内部的所有数据都存在。因此，搜索索引程序无需浪费时间查找下一个文件的信息，也无需寻找。由于MFT是连续的设计（仅在有更多文件且MFT由于某种原因填满或损坏时会链接到新文件，这将导致寻道时间-但这种边缘情况非常罕见），因此搜索速度很快。

MFT不是纯文本，需要进行解析。Everything的开发人员为NFT设计了超快的解析器和解码器，因此一切都很好。

FSCTL_GET_NTFS_VOLUME_DATA（在winioctl.h中声明）将为您获取mft的簇位置。或者，您可以使用NTFSInfo（Microsoft SysInternals - NTFSInfo v1.2）。

MFT区域簇：90400352-90451584

存储和检索

我的索引中的.db文件位于C:\Users\XXX\AppData\Local\Everything。我假设这是一个常规的基于文件的nosql数据库。由于它使用的是DB而不是平面文件，这有助于提高速度。此外，在程序启动时，它将该db文件加载到RAM中，因此所有查询都不会在磁盘上查找DB，而是在RAM上进行。所有这些组合起来使其非常流畅。

- ProgramingEnthusiast

---

可能最好先说明MFT代表“主文件表”。然后，由于这是一个面向编程的网站，列出一些用于MFT访问的API。目前来看，这是SuperUser上一个很好的答案，但在这里却没有重点。 - Ben Voigt

非常感谢您指出这一点。我会编辑我的答案并添加相同的内容。 - ProgramingEnthusiast

一个人也可以利用MFT而不编写自定义解析器，通过使用FSCTL_ENUM_USN_DATA ioctl。这会牺牲一些性能，以换取对可能更改磁盘格式的文件系统未来修订版本的可移植性。 - Ben Voigt

我相信 Everything.db 文件是一个 SQLite 数据库。当我试图打开它时，会提示输入密码。 - tolsen64

我同意并有同感。从数据来看，我相当确定它是SQLite/Derivative格式，但由于无法使用常规查看器打开，我无法确认。我猜测这个数据库可能被开发人员进行了优化。感谢分享！ - ProgramingEnthusiast

Answer 2

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

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

我不知道它是否足够满足您的需求，但普通的方法是使用FindFirstFile函数。编写一个简单的C程序来递归列出文件夹/文件，并查看它是否足够快。第二步通过优化是并行运行线程，但如果磁盘访问是瓶颈，那么多个线程将带来很少的好处。

如果这还不够，最后你可以尝试挖掘更低层的本地API函数；我没有使用过这些函数，所以无法给你进一步的建议。你会接近底层，也许Linux NTFS 项目有一些你需要学习的概念。

• 它使用哪些数据结构进行文件搜索？
• 它的文件搜索速度如何如此之快？

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

- rodrigocfd