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

Question

有一个叫做“Everything”的软件，它可以索引你机器上的所有文件，并且可以非常快速地找到任何东西；一旦文件被索引。

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

我错过了什么？

Answer 1

确实，通过官方 API 一个一个地枚举文件需要很长时间。但根据 the author himself，一切都读取主文件表(以及后来的更新查看 USN 变更日志)。 ，从而绕过缓慢的文件枚举 API。

a full computer. with multiple TB

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

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