像 Voidtools 的 Everything 这样的软件如何在不到一秒的时间内索引超过 100k 个文件？

Question

有一个叫“Everything”的软件，它可以索引你机器上的所有文件，而且查找速度非常快；一旦文件被索引。

我预计索引阶段需要几分钟，但没有。索引一台完整的计算机需要几秒钟的时间。患有多发性结核病。这怎么可能？对文件进行简单的循环将花费更多时间。

我缺少什么？

Answer 1

事实上，通过官方 API 逐一枚举文件需要很长时间。但根据作者本人的说法，Everything 会读取主文件表（稍后更新会查看 USN Change Journal） ，从而绕过缓慢的文件枚举 API。

一台完整的计算机。患有多发性结核病

文件的总大小不相关，因为 Everything 不索引文件内容。MFT 条目每个为 1KB，因此对于 100K 文件，您可以期望读取 0.1GB 的量级来从头开始构建索引（实际上更多，因为非文件条目，但数量级相似，当然更新现有文件时会更少）指数）。毕竟这并不是很多数据，应该可以在一秒钟内读取它。

然后处理 100K 条目来构建索引可能看起来是一项可能很慢的任务，但为了规模感，您可以将其与当代计算机每秒可以执行的（数百）亿条指令进行比较。“4GHz”并不完全意味着“每秒 40 亿条指令”，但更好的是，即使像原始奔腾这样的旧 CPU 也可以每个周期执行几条指令。仅根据这个规模，在几秒钟内建立一个包含 100K 条目的索引并不是不可想象的。分钟似乎过多：这将对应于每个项目数百万条指令，即使对于 O(n log n) 算法（100K 的基数 2 log 约为 17）来说这也很糟糕，当然我们可以做得更好。

Answer 2

线程/多重处理可以极大地提高速度。他们可能正在利用多核。您说了一个简单的文件循环，所以我假设您不知道线程/多重处理。