everything 索引原理探讨

[hkhk366]

everything 索引原理探讨

MFT 如何获取硬盘所有文件信息和监控整个硬盘文件变动，这两个比较简单，我做了一个简单实现可以在 200 毫秒扫描整个硬盘所有分区下所有文件信息，总共 100 万个对象的信息，这个第一步比较简单。

主要是第二步，如何高效的为文件增加索引？ everything 如何在 5 毫秒内完成 100 万文件的全文搜索并排序的？我利用 everything 开启 HTTP 服务，发送请求计算出来总共需要 5 毫秒就能完成这个搜索。这对我来说太难，我想了很久也没有想明白是如何做的。

思路 1：使用全文搜索，建立倒排索引，因为文件名经常出现比如“abc.txt“”这样的，所以很难分词，如果按每个字母建立倒排索引的话，100 万文件大约需要 1 个 GB 的空间，因为太多的文件有"a"这种字符，所以这个方案不行。

我看到论坛里有个开源的项目实现的，我粗略的看了一下，他套了一个全文搜索引擎，但是如果搜"a"这种字符，首先结果出来不全，可能只截取了一部分，但是 everything 可以搜索完立刻就知道总共有多少条符合的，而且搜索出来就已经排序了，比如按文件大小排序，我想不明白 5 毫秒内如何做到的。

思路 2：并行计算，我把 100 万文件并行去计算，我的极限可以把 100 万文件全文搜索控制在 6 毫秒，而且还没排序，但是我 7900x 的 24 核心芯片的每一个核心都参与了计算，而我在 everything 搜索的时候，我发现其 CPU 基本不怎么波动，没有出现大量核参与运算的样子，他是如何做的？

思路 3：使用 simd ，看着也不像，我感觉 everything 搜索的时候 CPU 波动非常的小。

思路 4：前缀树后缀树，这个只能搜索某个字符串开头的，没法实现全文搜索。

思路 5：我研究了一些多模态匹配字符串搜索算法，但是无论我怎么优化，都无法实现 5 毫秒这么快的速度。

思路 6：我研究了各种排序算法，我个人认为比如搜索“a”在我机器上有几十万个文件，无论用什么有我知道的算法，极限并行排序 100 万文件需要 10 毫秒左右，所以我才猜测 everything 不像是结果直接全部排序完成才返回的，更像是只获取前 100 个，然后后面慢慢排序，在你拖动滚动条的时候再把结果放出来。

思路 7：B+树，这个可能对排序建立索引有点用，但是全文搜索没什么帮助。

思路 8：索引建立速度，根据我录屏然后慢速分析，我发现，everything 1.4 扫描所有文件信息到建立索引，在我的机器上 1 秒以内就能完成，这是如何做的，我尝试了很久，如果算法太复杂就会消耗太多时间，显然 everything 的算法应该非常轻量高效。

希望高人能指点一下上面的谜题，让我能了解一下这个原理，非常感谢。

[lervard358]

https://stackoverflow.com/questions/47686560/what-makes-everythings-file-search-and-index-so-efficient

[tool2d]

先用 bloom filter 过滤一下，能直接把数据量从 200 万降低到 20 万。

再用红蓝树/std::priority_queue 之类的查询，速度一般来说还是挺快的。

你看以前上亿数据库是怎么分库的，就是分而治之呗。只要数据量下来了，什么都好办。

[hkhk366]

@lervard358 谢谢回复，但是这个 stackoverflow 的帖子没什么帮助，那个帖子主要是在讨论 MFT 的知识，这些我早就已经解决了，并且已经在本帖最开头就已经提到了，我的话题是仅仅讨论 everything 的索引原理，有什么其他关于索引的分享吗？谢谢。

[MoYi123]

用这个数据结构为基础, 我猜应该可以做到差不多的性能.
https://github.com/BurntSushi/fst

[hkhk366]

@tool2d 感谢回帖，我也想过 bloom filter ，但是我自己测试是这样的，上面也有提到，我的硬盘中有 100 万文件，其中几十万（具体 90 万）文件都包含"a"，我不知道他是如何在 5 毫秒（ everything 单个字符搜索 5 毫秒，二哥字符 15 毫秒）内完成的，现在 bloom filter 对这个案例过滤不了多少，并且用 priority_queue 也无法保证在 5 毫秒内完成 90 万文件搜索+排序。所以最大的问题是，everything 能再 5 毫秒内完成 90 万文件的操作，并且整个过程中好像还没有并行计算，我观察 CPU 都多核没变化。如果按照分库分表并行的话，必然 CPU 会有不少波动，我上面说的并行方法其实就用的分库分表，不能符合预期。还有什么其他的方法愿意分享吗？多谢

[matrix1010]

没明白 abc.txt 难分词的原因，搜索 a 那所有包含 a 的文件都应该显示。另外"倒排 100 万文件大约需要 1 个 GB 的空间"感觉也不对，你是用 sqlite 的全文检索测试的吗

[tool2d]

@hkhk366 就我个人来说，并不觉得 everything 用了太多黑科技算法。可能就是单纯代码写的好，优化的好。

现代 CPU 缓存也挺重要的，说不定 5ms 只是占了高速缓存的便宜。长字符串搜索，相对优势就没那么明显了。

bloom filter 也有很多变种，针对文件名高度优化后的效果，肯定和普通开源代码有区别的。

[mosakashaka]

@hkhk366 SO 帖子里评论说，数据是存在 sqlite 里面的。加载到内存里查询。

[xtreme1]

试没试过 ripgrep..

[shinession]

内存占用也很少, 大概 100 万文件, 只占用不到 100M 内存, 同样感兴趣, mark 下

[aoguai]

我记得 everything 用的 NTFS 文件系统的 USN 日志所以那么快。具体可以搜搜。随便找的一篇👇🏻
GitHub - LeiHao0/Fake-Everything: Everything 的原理猜想与实现
https://github.com/LeiHao0/Fake-Everything

[kuituosi]

全文索引加剪枝就能实现，文件名中有大量重复的内容，剪枝可以减少很多内存

[SmiteChow]

空间换时间，没有魔法

[xiang0818]

esdb

[kuanat]

其实你这个思路偏了啊，当你意识到 5ms 连文件 IO 都完成不了的时候，应该考虑这不是个算法问题而是个策略问题。



官方页面上已经说得很清楚了，因为关键内容不多，我就直接复制过来：

来自 https://www.voidtools.com/support/everything/searching/

Content Searching

Warning: content searching is extremely slow.

File content is not indexed.

Please combine content: functions with other filters for the best performance.

Content search functions:
content:<text> Search file content using the associated iFilter. If no iFilter exists UTF-8 content is used.
ansicontent:<text> File contents are treated as ANSI text.
utf8content:<text> File contents are treated as UTF-8 text.
utf16content:<text> File contents are treated as UTF-16 (Unicode) text.
utf16becontent:<text> File contents are treated as UTF-16 (Big Endian) text.

另外 https://www.voidtools.com/forum/viewtopic.php?t=9793 这里有更详细的说明。

Everything will keep content in memory.
Content indexing is intended for indexing user documents only.
I do not recommend indexing over 1GB of text.
For the best performance, set an include only folder.

By default, Everything will index the following file types for content:
*.doc;*.docx;*.pdf;*.txt;*.xls;*.xlsx



这 5ms 就做了一个内存数据库的检索，而且数量级并不是你想象中的 100 万。你在没有验证的情况下，就认为它扫描了文件，所以思路跑偏了。即使没有一点逆向基础，也有很简单的办法知道一个程序运行的时候打开读取了哪些文件，如果你验证了这一点，估计已经找到答案了。

所有的“索引”类算法，核心思想并不在“算”上面，而在于将原始数据结构以一种易于被检索的数据格式存储。换句话说，之所以索引可以加速搜索，是因为提前生成了要查询的结果。

Windows 自身有个索引服务，但是绝大多数文件格式都是二进制的，在不了解它的文件结构的情况下，是没有办法进行文本搜索的。所以 Windows 提供了一个 IFilter 机制，由文件格式的创建者，主动暴露可以被索引的信息。然后再通过后台服务对于相关的文件格式进行索引，首次全盘索引完成之后，只有文件内容发生变化，才会触发索引更新。几大操作系统的索引都是相同的机制。

Everything 的说明就是这样一个意思，它会在内存索引少数路径下的特定格式的文件，为其建立文本内容索引。后续的搜索只是内存搜索引。至于全文匹配到底用了什么算法，是不是有指令集优化，是另外的事情，到了这个层面，只要思路对，算法是不是最优化已经不重要了。（ Everything 是 C 写的，但是没有什么混淆加密，稍微逆向一下大概就能弄清楚。）

[denok]

是内存，我记得 8G 到 32G 的时候，速度肉眼可见的变快

[littlewing]

这个帖子的回复已经有 3 个人是不看内容只看标题的，所以楼主以后还是把标题写长一点写清楚一点吧

[cy18]

我记得好像哪看到好像就是直接把索引丢 sqlite 里面然后用 sqlite 搜索？

[BeautifulSoap]

虽然但是，，，，，，，，，我试了下，用 go 生成了包含 100 万个随机字符串的数组，然后直接简单粗暴地用 for 遍历整个数组，然后对每个成员做 strings.Contains() 搜索，遍历完成都才花了 11ms

lz 你是不是对现代计算机的性能有误解。。。。。

[hkhk366]

@kuanat 你好，谢谢你的回复，但是你完全没有仔细阅读 1 楼的内容，我从来没有讨论文件内容索引的问题，我从来没提文件 IO 的事情。我一直讨论的是文件名，文件路径，文件大小，修改时间这些快速索引，搜索，排序的问题。

至于 x64 逆向我会，但是你能从从汇编反向推出来核心索引算法吗？除非花费大量的时间，否则根本不可能，你顶多下个断点，知道什么时候触发一下。