Everything Search Engine這款軟體如何做到如此快速的搜索的？

12-30

比 Windows 內置搜索還快好多倍，這兩者原理有何區別？為何微軟不使用這種原理，或者收購這個公司呢？

Everything是我嚴重依賴的一個軟體，來答一答。

Everything和Windows搜索是有區別的，以下列幾點：

1. Everything只能搜索文件名和文件夾名，Windows搜索可以搜索文件名和文件內容；

2. Everything只能搜索NTFS格式的文件系統，Windows搜索可以搜索任意文件系統（例如FAT32，exFAT，NTFS）；

但有時我們需要的恰好就是快速搜索文件名，那麼Everything的工作原理是如何呢？

先簡單介紹一下NTFS的兩個功能，MFT和USN journal。

Master File Table (MTF)

在NTFS文件系統中，有一個特殊的表，稱為MTF表。所有文件夾和文件的名稱都被存儲在該表中，訪問該表的速度非常快，使應用程序可以不遍歷文件系統就能獲取當前卷（磁碟）中的所有文件的名稱和路徑。

USN journal

NTFS還有一個日誌功能。所有對文件系統有修改的操作都被記錄在了一個journal日誌文件中。

Everything的原理

程序啟動時，掃描系統所有NTFS卷（磁碟）的MTF表，將文件名稱以一種利於字元串檢索的演算法形式存儲在Everything的index索引資料庫中。

系統運行過程中，Everything還會監控NTFS卷的journal日誌文件，如果文件系統中的文件發生改變，Everything會更新它的index索引資料庫。

當用戶搜索文件時，Everything利用字元串查找演算法，在index索引資料庫中查找，可以直接搜索到文件。

那麼，現在回答題主問題。

Q：Search Everything 這款軟體如何做到如此快速的搜索的？

A：因為Everything在搜索時，根本沒有遍歷文件系統，它檢索的是自己組織好的索引資料庫，因此搜索速度飛快；

Q：Windows搜索時什麼原理？

A：Windows搜索用的是普通的文件系統遍歷查找。用的應該是標準WIN32 API，例如FindFirstFile/FindNextFile之類。當然，Windows7之後的版本現在已經內置帶索引的搜索功能，這項功能非常複雜，不僅可以搜索文件名，還可以搜索文件內容，而且適用任意文件系統。但缺點就是需要一個後台服務爬蟲不停的對文件系統進行索引，比較耗資源。

Q：為何微軟不使用這種原理？

A：個人覺得是因為這種方法不具備普適性，無法應用與非NTFS文件系統，所以無法集成到Windows中。

Q：為何微軟不收購這家公司?

A: 個人感覺還是技術含量不太高，而且微軟自家的ActiveDirectory早就在使用MTF快速檢索文件了。

Everything直接訪問了NTFS分區的文件日誌，同時構造索引。本質上和你自己讀一個文件，對這文件構造索引再搜索內容一樣，所以速度異常的快。

但該操作需要很高的磁碟訪問許可權，所以這個軟體需要管理員許可權才能正常運行。對於一般的Windows用戶，根本不知道許可權管理是什麼，隨便就給自己弄成管理員，然後關掉UAC。然後經常受到惡意軟體襲擊，再去抱怨Windows不安全。

Windows的搜索功能只是單純的訪問文件，因此沒有許可權的問題。

在Windows里，你可以建立文件索引。在控制面板內搜索「索引」二字，打開索引選項。把你想要建立索引的位置添加進去。或者打開想索引的文件夾，隨便搜點什麼。Windows會問你是否建立索引。

建立索引不僅能以極快的速度搜索文件名，同時還能搜索文件內容。方法是在分區上點右鍵-&>屬性-&>選上「除文件屬性外，還允許索引此驅動器上的文件內容。」

應 @robinh00d的邀請,特來回答這個問題.

沒有寫過everything,因為我不是everything的作者...

國內後來有個抄襲everything的東西,叫光速搜索.

我也沒有寫過光速搜索,因為我不是光速搜索的作者.

去年國內出了一個叫閃電搜索的,給鏈接:閃電搜索 | 毫秒級本地文件搜索神器

嗯,剛好本人曾經是這款軟體的第一作者,性能確實和everything有差距,但是七七八八的原理還是能說得清楚,就隨便說說吧.

實現everything,大概有幾步吧.

1. 建立文件名的索引庫.

這個的實現可以使用NTFS的USN機制來做,當然也可以使用FindFirstFile 這些Api來實現.

對於每個文件,可以構建一個如下的結構,

仔細看這個結構,其實最後可以實現一個類似B+樹的樹狀結構,可以從某盤符的根目錄,遍歷所有子文件. 這個FileEntry也可以通過parent指針往上回溯,可以獲得全路徑.其實第一步是所有實現中最簡單的,上面所有的答案,都只回答了這一點.

2. 實現文件的快速搜索,並顯示在UI上.

其實搜索才是這部分最難的,一個是everything要支持正則表達式,你要正確的解析所有的通配符,包括 *,? 等等,要支持對後綴名字的判斷,解析成功之後呢,要使用正確的字元搜索演算法去匹配. 常見的演算法 KMP, BM 等等,都可以.(Bla Bla 省略一千字)

比如你搜索 "123*" "12*3" "*123" 這些的解析都不竟相同.

然後通過字元匹配演算法,獲得一個一個符合該條件的 FileEntry. 然後再拋出這個結果.

拋出之後呢,可能符合結構的有很多,你要在界面上刷新和顯示出來,做得不好的,界面顯示會卡頓.等等.

3. 實現對所有磁碟文件變化的監測.

你看到everything,可以在你複製一個文件之後,又在everything搜索列表內馬上顯示出來. 其實是everything本身會創建好幾個線程,去監視所有磁碟的USN變化. 變化包括文件的增刪重命名等.

這個時候everything就要實時更新自己的文件索引庫.

當然對於不支持USN變化的FAT32磁碟就沒有辦法了? 辦法還是有的,有個叫ReadDirectoryChangW的函數,一樣可以監視磁碟的變化,一樣可以實現文件索引的更新.

總結: 其實呢,原理大概就這樣,第一點誰都能說,第二和第三點做得好的,很少.

回答題主的一個問題,為啥微軟不去做一個everything:

Windows設計本身的目的不是為了去做某款特定的產品,而是為廣大的用戶提供一個通用使用的東西. 他要去權衡性能,全球用戶的接受程度等等. 他提供介面,給開發人員去想像去實現,要知道微軟要做的是平台和生態圈這個概念,你就能理解了.

支持最高的答案寫了一大堆，可惜是錯的。

EVERYTHING不是靠遍歷MFT的，遍歷MFT木有那麼快。

everything是靠遍歷USN journal+同時建立索引。本人N年前曾經實現過一個類EVERYTHING的東東。

簡而言之：創建索引快是因為遍歷USN JOURNAL，搜索快是因為建立了索引。

通過遍歷MFT/FIND API函數來建立索引，速度都比較慢，在秒級是無法完成的。

具體細節已由 @coltor說明。

----

補充，只能說知乎上有些人對技術不了解只憑主觀想像就敢洋洋洒洒寫一大篇文字，實在佩服。