Everything高速搜索文件原理及实现

网上找了很多的资料，还是没有很清楚的了解Everything这款软件。所以自己研究了一下，并记录下来。

Everything是一个搜索文件速度超快的软件，相比Windows自带的搜索功能，Everything可以做到在数十万文件中做到秒搜。

本文来分析一下Everything背后的原理以及自己实现一个Everything。

Everything的工作原理 Everything在第一次打开程序时会扫描整个磁盘，并建立一个索引库。需要注意的是，Everything并不是像Windows文件夹遍历那样一个文件一个文件的搜索并记录。而是通过NTFS文件系统的特性，MFT和USN journal。这也是Everything仅支持NTFS文件系统的原因。

Master File Table (MFT)

在NTFS文件系统中，有一个特殊的表，称为MFT表。所有文件夹和文件的名称都被存储在该表中，Everything通过遍历这个表的所有内容，实现在不遍历文件系统就能获取当前磁盘中的所有文件的名称和路径。

USN journal

NTFS的日志功能。所有对文件系统的修改操作都被记录在了一个journal日志文件中。Everything通过监控这个日志文件实现对文件修改的监控。

文件查找

通过字符串匹配算法从之前建立的索引中对字符串进行匹配，并显示文件名称和路径。

关于usn日志的相关信息，个人认为这篇文章写的比较清楚

NTFS USN日志记录读取历险记 - Irix的博客 | Irix’s Blog (atr.pub)

以及官方文档

Change Journals - Win32 apps | Microsoft Learn

Keeping an Eye on Your NTFS Drives: the Windows 2000 Change Journal Explained | Microsoft Learn

自己实现一个Everything 我自己已经实现了一个完整的类似于Everything的软件，代码已经在GitHub上开源，欢迎各位去点个star呀。

XUANXUQAQ/File-Engine: An app launcher && efficiency tool (github.com)

一、建立数据库索引 首先，我们需要做的就是对文件的路径进行索引。我这里选用SQLite。不知道Everything是使用了什么数据库才使他们的索引文件做到这么小，至于为什么这么快，推测可能是先将索引放入内存，索引可用后，程序在后台慢慢同步到硬盘的吧。

搜索的核心方法是通过创建USN日志并进行读取，然后将数据还原成文件路径并写入数据库。

1. 首先是获取驱动盘的句柄

通过CreateFile方法打开磁盘，并返回磁盘句柄。

关于CreateFile的用法详见MSDNCreateFileW function (fileapi.h) - Win32 apps | Microsoft Docs

12345678910111213141516171819202122232425bool volume::get_handle(){ // 为\\.\C:的形式 CString lp_file_name(_T("\\\\.\\c:")); lp_file_name.SetAt(4, vol); hVol = CreateFile(lp_file_name, GENERIC_READ | GENERIC_WRITE, // 可以为0 FILE_SHARE_READ | FILE_SHARE_WRITE, // 必须包含有FILE_SHARE_WRITE nullptr, OPEN_EXISTING, // 必须包含OPEN_EXISTING, CREATE_ALWAYS可能会导致错误 FILE_ATTRIBUTE_READONLY, // FILE_ATTRIBUTE_NORMAL可能会导致错误 nullptr); if (INVALID_HANDLE_VALUE != hVol) { return true; } auto&& info = std::wstring(L"create file handle failed. ") + lp_file_name.GetString() + L"error code: " + std::to_wstring(GetLastError()); fprintf(stderr, "fileSearcherUSN: %ls", info.c_str()); return false;}

2. 之后开始创建USN日志

通过DeviceIoControl方法向磁盘发送FSCTL_CREATE_USN_JOURNAL命令，创建USN日志。

关于DeviceIoControl的用法，详见MSDNDeviceIoControl function (ioapiset.h) - Win32 apps | Microsoft Docs

DeviceIoControl的各个命令操作，详见MSDNVolume Management Control Codes - Win32 apps | Microsoft Docs

这里创建USN日志使用的是FSCTL_CREATE_USN命令FSCTL_CREATE_USN_JOURNAL - Win32 apps | Microsoft Docs

1234567891011121314151617181920212223bool volume::create_usn(){ cujd.MaximumSize = 0; // 0表示使用默认值 cujd.AllocationDelta = 0; // 0表示使用默认值 DWORD br; if ( DeviceIoControl(hVol, // handle to volume FSCTL_CREATE_USN_JOURNAL, // dwIoControlCode &cujd, // input buffer sizeof(cujd), // size of input buffer nullptr, // lpOutBuffer 0, // nOutBufferSize &br, // number of bytes returned nullptr) // OVERLAPPED structure ) { return true; } auto&& info = "create usn error. Error code: " + std::to_string(GetLastError()); fprintf(stderr, "fileSearcherUSN: %s\n", info.c_str()); return false;}

3. 获取USN日志信息

还是通过DeviceIoControl方法发送FSCTL_QUERY_USN_JOURNAL命令，获取当前卷USN日志的各项信息，检查USN日志是否获取成功。

FSCTL_QUERY_USN_JOURNAL - Win32 apps | Microsoft Docs

1234567891011121314151617181920bool volume::get_usn_info(){ DWORD br; if ( DeviceIoControl(hVol, // handle to volume FSCTL_QUERY_USN_JOURNAL, // dwIoControlCode nullptr, // lpInBuffer 0, // nInBufferSize &ujd, // output buffer sizeof(ujd), // size of output buffer &br, // number of bytes returned nullptr) // OVERLAPPED structure ) { return true; } auto&& info = "query usn error. Error code: " + std::to_string(GetLastError()); fprintf(stderr, "fileSearcherUSN: %s\n", info.c_str()); return false;}

4. 获取 USN Journal 文件的基本信息

仍然通过DeviceIoControl发送FSCTL_ENUM_USN_DATA遍历USN日志。

FSCTL_ENUM_USN_DATA - Win32 apps | Microsoft Docs

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849bool volume::get_usn_journal(){ MFT_ENUM_DATA med; med.StartFileReferenceNumber = 0; med.LowUsn = ujd.FirstUsn; med.HighUsn = ujd.NextUsn; // 根目录 CString tmp(_T("C:")); tmp.SetAt(0, vol); constexpr auto BUF_LEN = sizeof(USN) + 0x100000; // 尽可能地大，提高效率; CHAR* buffer = new CHAR[BUF_LEN]; DWORD usn_data_size; pfrn_name pfrn_name; while (0 != DeviceIoControl(hVol, FSCTL_ENUM_USN_DATA, &med, sizeof med, buffer, BUF_LEN, &usn_data_size, nullptr)) { DWORD dw_ret_bytes = usn_data_size - sizeof(USN); // 找到第一个 USN 记录 auto usn_record = reinterpret_cast(buffer + sizeof(USN)); while (dw_ret_bytes > 0) { // 获取到的信息 const CString cfile_name(usn_record->FileName, usn_record->FileNameLength / 2); pfrn_name.filename = cfile_name; pfrn_name.pfrn = usn_record->ParentFileReferenceNumber; // frnPfrnNameMap[UsnRecord->FileReferenceNumber] = pfrnName; frnPfrnNameMap.insert(std::make_pair(usn_record->FileReferenceNumber, pfrn_name)); // 获取下一个记录 const auto record_len = usn_record->RecordLength; dw_ret_bytes -= record_len; usn_record = reinterpret_cast(reinterpret_cast(usn_record) + record_len); } // 获取下一页数据 med.StartFileReferenceNumber = *reinterpret_cast(buffer); } delete[] buffer; return true;}

这里我将获取到的信息放入了frnPfrnNameMap中

1234567typedef struct _pfrn_name{ DWORDLONG pfrn = 0; CString filename;} pfrn_name;typedef unordered_map Frn_Pfrn_Name_Map;

这里不得不说USN日志文件的数据结构。

12345678910111213141516typedef struct { DWORD RecordLength; WORD MajorVersion; WORD MinorVersion; DWORDLONG FileReferenceNumber; DWORDLONG ParentFileReferenceNumber; USN Usn; LARGE_INTEGER TimeStamp; DWORD Reason; DWORD SourceInfo; DWORD SecurityId; DWORD FileAttributes; WORD FileNameLength; WORD FileNameOffset; WCHAR FileName[1];} USN_RECORD_V2, *PUSN_RECORD_V2;

这里我们需要用到FileReferenceNumber、ParentFileReferenceNumber、FileName。

USN日志在Windows中也有对应的命令，使用fsutil就可以创建日志

12fsutil usn createJournal C:fsutil usn enumData 1 0 1 C:

此时，可以看到USN日志的数据。

包含文件参照号，父文件参照号，以及文件名。

也就是上文提到的FileReferenceNumber、ParentFileReferenceNumber、FileName

USN日志是一个树状结构，通过文件号和父文件号不断向上找，最终可以拼接出一个完整的路径。获得路径后即可存入数据库。

最后删除USN日志。

1fsutil usn deleteJournal /D C:

5. 删除USN日志文件

因为USN日志默认并不存在，所以在程序创建之后可以将它删除。

仍然是通过DeviceIoControl方法发送命令。

FSCTL_DELETE_USN_JOURNAL - Win32 apps | Microsoft Docs

1234567891011121314151617181920212223bool volume::delete_usn() const{ DELETE_USN_JOURNAL_DATA dujd; dujd.UsnJournalID = ujd.UsnJournalID; dujd.DeleteFlags = USN_DELETE_FLAG_DELETE; DWORD br; if (DeviceIoControl(hVol, FSCTL_DELETE_USN_JOURNAL, &dujd, sizeof(dujd), nullptr, 0, &br, nullptr) ) { CloseHandle(hVol); return true; } CloseHandle(hVol); return false;}

6. 此时就可以通过遍历frnPfrnNameMap还原出每个文件的路径，并存入数据库

通过不断向上遍历查找，最后拼接出文件的路径。

123456789101112131415void volume::get_path(DWORDLONG frn, CString& output_path){ const auto end = frnPfrnNameMap.end(); while (true) { auto it = frnPfrnNameMap.find(frn); if (it == end) { output_path = L":" + output_path; return; } output_path = _T("\\") + it->second.filename + output_path; frn = it->second.pfrn; }}

此时，我们已经实现了实现Everything的第一步，建立数据库索引。二、监控文件的变化监控文件的变化在这里我采用的是ReadDirectoryChangesW方法进行监控。ReadDirectoryChangesW function (winbase.h) - Win32 apps | Microsoft Docs

文件操作类型有四种，分别为 创建、更改、删除、重命名

对应到Windows API里是FILE_ACTION_ADDED、FILE_ACTION_MODIFIED、FILE_ACTION_REMOVED、FILE_ACTION_RENAMED_OLD_NAME。

通过监控这四个操作，我们可以实现监控文件的变化，并更新数据库索引。

1234567891011121314151617181920212223242526272829303132333435363738394041424344/** * 开始监控文件夹 */void monitor_path(const std::string& path){ const auto wPath = string2wstring(path); DirectoryChangesReader dcr(wPath); auto&& flag = stop_flag.at(path); while (flag.load()) { dcr.EnqueueReadDirectoryChanges(); if (const DWORD rv = dcr.WaitForHandles(); rv == WAIT_OBJECT_0) { for (auto&& res = dcr.GetDirectoryChangesResultW(); const auto& [action, data] : res) { switch (action) { case FILE_ACTION_ADDED: case FILE_ACTION_RENAMED_NEW_NAME: if (data.find(L"$RECYCLE.BIN") == std::wstring::npos) { std::wstring data_with_disk; data_with_disk.append(wPath).append(data); add_record(data_with_disk); } break; case FILE_ACTION_REMOVED: case FILE_ACTION_RENAMED_OLD_NAME: if (data.find(L"$RECYCLE.BIN") == std::wstring::npos) { std::wstring data_with_disk; data_with_disk.append(wPath).append(data); delete_record(data_with_disk); } break; case FILE_ACTION_MODIFIED: default: break; } } } Sleep(10); }}

DirectoryChangesReader将ReadDirectoryChanges()方法的调用封装进DirectoryChangesReader对象中，当调用EnqueueReadDirectoryChanges()方法后，文件更改记录将会被写入缓存中。

然后执行GetDirectoryChangesResultW()方法，调用GetOverlappedResult()方法读取出文件更改信息，然后将所有信息保存进一个vector中，再返回。

GetOverlappedResult function (ioapiset.h) - Win32 apps | Microsoft Learn

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165#pragma once#include #include #include #include #include // A base class for handles with different invalid values.template class Handle{public: Handle(const Handle&) = delete; Handle(Handle&& rhs) noexcept : hHandle(std::exchange(rhs.hHandle, hInvalid)) { } Handle& operator=(const Handle&) = delete; Handle& operator=(Handle&& rhs) noexcept { std::swap(hHandle, rhs.hHandle); return *this; } // converting to a normal HANDLE operator HANDLE() const { return hHandle; }protected: Handle(HANDLE v) : hHandle(v) { // throw if we got an invalid handle if (hHandle == reinterpret_cast(hInvalid) || hHandle == INVALID_HANDLE_VALUE) throw std::runtime_error("invalid handle"); } ~Handle() { if (hHandle != reinterpret_cast(hInvalid)) CloseHandle(hHandle); }private: HANDLE hHandle;};using InvalidNullptrHandle = Handle<(std::uintptr_t)nullptr>;// A class for directory handlesclass DirectoryHandleW : public InvalidNullptrHandle{public: DirectoryHandleW(const std::wstring& dir) : Handle( CreateFileW( dir.c_str(), FILE_LIST_DIRECTORY, FILE_SHARE_READ | FILE_SHARE_DELETE | FILE_SHARE_WRITE, nullptr, OPEN_EXISTING, FILE_FLAG_BACKUP_SEMANTICS | FILE_FLAG_OVERLAPPED, nullptr) ) { }};// A class for event handlesclass EventHandle : public InvalidNullptrHandle{public: EventHandle() : Handle(CreateEvent(nullptr, true, false, nullptr)) { }};// A stepping function for FILE_NOTIFY_INFORMATION*bool StepToNextNotifyInformation(FILE_NOTIFY_INFORMATION*& cur){ if (cur->NextEntryOffset == 0) return false; cur = reinterpret_cast( reinterpret_cast(cur) + cur->NextEntryOffset ); return true;}// A ReadDirectoryChanges support classtemplate class DirectoryChangesReader{public: static_assert(Handles > 0, "There must be room for at least 1 HANDLE"); static_assert(BufByteSize >= sizeof(FILE_NOTIFY_INFORMATION) + MAX_PATH, "BufByteSize too small"); static_assert(BufByteSize % sizeof(DWORD) == 0, "BufByteSize must be a multiple of sizeof(DWORD)"); DirectoryChangesReader(const std::wstring& dirname) : hDir(dirname), ovl{}, hEv{}, handles{ hEv }, buffer{ std::make_unique(BufByteSize / sizeof(DWORD)) } { } // A function to fill in data to use with ReadDirectoryChangesW void EnqueueReadDirectoryChanges() { ovl = OVERLAPPED{}; ovl.hEvent = hEv; const BOOL rdc = ReadDirectoryChangesW( hDir, buffer.get(), BufByteSize, TRUE, FILE_NOTIFY_CHANGE_FILE_NAME | FILE_NOTIFY_CHANGE_DIR_NAME | FILE_NOTIFY_CHANGE_ATTRIBUTES | FILE_NOTIFY_CHANGE_SIZE | FILE_NOTIFY_CHANGE_LAST_WRITE | FILE_NOTIFY_CHANGE_LAST_ACCESS | FILE_NOTIFY_CHANGE_CREATION | FILE_NOTIFY_CHANGE_SECURITY, nullptr, &ovl, nullptr ); if (rdc == 0) throw std::runtime_error("EnqueueReadDirectoryChanges failed"); } // A function to get a vector of , pairs std::vector> GetDirectoryChangesResultW() { std::vector> retval; auto* fni = reinterpret_cast(buffer.get()); DWORD ovlBytesReturned; if (GetOverlappedResult(hDir, &ovl, &ovlBytesReturned, TRUE)) { do { retval.emplace_back( fni->Action, std::wstring{ fni->FileName, fni->FileName + fni->FileNameLength / sizeof(wchar_t) } ); } while (StepToNextNotifyInformation(fni)); } return retval; } // wait for the handles in the handles array DWORD WaitForHandles() { constexpr DWORD wait_threshold = 5000; return ::WaitForMultipleObjects(Handles, handles, false, wait_threshold); } // access to the handles array HANDLE& operator[](size_t idx) { return handles[idx]; } constexpr size_t handles_count() const { return Handles; }private: DirectoryHandleW hDir; OVERLAPPED ovl; EventHandle hEv; HANDLE handles[Handles]; std::unique_ptr buffer; // DWORD-aligned};

至此，实现Everything第二步，监控文件变化完成。三、实现UI界面 由于项目是我几年前写的，所以当时用了Java的Swing框架。上文写到的创建数据库索引的工具编译成了exe，由Java调用。而监控文件变化的工具编译成了dll，通过jni进行调用。

1. 首先，制作一个搜索框

使用JFrame创建窗口，JTextField放上面作为搜索框，下面放JLabel作为结果的显示就好，这里就不再贴代码。

2. 监听用户输入，并查询数据库

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354private void addTextFieldDocumentListener() { textField.getDocument().addDocumentListener(new DocumentListener() { private boolean isSendSignal; @Override public void insertUpdate(DocumentEvent e) { changeFontOnDisplayFailed(); clearAllAndResetAll(); isSendSignal = setRunningMode(); if (isSendSignal) { startTime = System.currentTimeMillis(); startSignal.set(true); isSqlNotInitialized.set(true); } if (runningMode == Constants.Enums.RunningMode.PLUGIN_MODE && currentUsingPlugin != null) { currentUsingPlugin.textChanged(getSearchBarText()); currentUsingPlugin.clearResultQueue(); } } @Override public void removeUpdate(DocumentEvent e) { changeFontOnDisplayFailed(); clearAllAndResetAll(); isSendSignal = setRunningMode(); if (getSearchBarText().isEmpty()) { lastMousePositionX = 0; lastMousePositionY = 0; listResultsNum.set(0); currentResultCount.set(0); startTime = System.currentTimeMillis(); startSignal.set(false); isSqlNotInitialized.set(false); } else { if (isSendSignal) { startTime = System.currentTimeMillis(); startSignal.set(true); isSqlNotInitialized.set(true); } if (runningMode == Constants.Enums.RunningMode.PLUGIN_MODE && currentUsingPlugin != null) { currentUsingPlugin.textChanged(getSearchBarText()); currentUsingPlugin.clearResultQueue(); } } } @Override public void changedUpdate(DocumentEvent e) { startTime = System.currentTimeMillis(); startSignal.set(false); isSqlNotInitialized.set(false); } }); }

这里采用记录startTime和startSignal的方式，通过线程池来检测搜索信号，并进行数据库的搜索。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253/** * 生成未格式化的sql * 第一个map中key保存未格式化的sql，value保存表名称，第二个map为搜索结果的暂时存储容器 * * @return map */ private LinkedHashMap, ConcurrentSkipListSet> getNonFormattedSqlFromTableQueue() { if (isDatabaseUpdated.get()) { isDatabaseUpdated.set(false); initPriority(); } LinkedHashMap, ConcurrentSkipListSet> sqlColumnMap = new LinkedHashMap<>(); if (priorityMap.isEmpty()) { return sqlColumnMap; } initTableQueueByPriority(); int asciiSum = 0; if (keywords.get() != null) { for (String keyword : keywords.get()) { int ascII = GetAscII.INSTANCE.getAscII(keyword); asciiSum += Math.max(ascII, 0); } } int asciiGroup = asciiSum / 100; String firstTableName = "list" + asciiGroup; if (searchCase.get() != null && Arrays.asList(searchCase.get()).contains("d")) { LinkedHashMap _priorityMap = new LinkedHashMap<>(); String _sql = "SELECT %s FROM " + firstTableName + " WHERE PRIORITY=" + 0; _priorityMap.put(_sql, firstTableName); tableQueue.stream().filter(each -> !each.equals(firstTableName)).forEach(each -> { String sql = "SELECT %s FROM " + each + " WHERE PRIORITY=" + 0; _priorityMap.put(sql, each); }); ConcurrentSkipListSet container; container = new ConcurrentSkipListSet<>(); sqlColumnMap.put(_priorityMap, container); } else { for (Pair i : priorityMap) { LinkedHashMap eachPriorityMap = new LinkedHashMap<>(); String _sql = "SELECT %s FROM " + firstTableName + " WHERE PRIORITY=" + i.priority; eachPriorityMap.put(_sql, firstTableName); tableQueue.stream().filter(each -> !each.equals(firstTableName)).forEach(each -> { String sql = "SELECT %s FROM " + each + " WHERE PRIORITY=" + i.priority; eachPriorityMap.put(sql, each); }); ConcurrentSkipListSet container; container = new ConcurrentSkipListSet<>(); sqlColumnMap.put(eachPriorityMap, container); } } tableQueue.clear(); return sqlColumnMap; }

这一步生成所有的查询SQL，简单来说就是生成SELECT * FROM [数据表] 命令并执行，这里因为后面是异步多线程查询，所以为每一个SQL语句都分配了一个用来装数据的容器，后续再进行合并，提高效率，%s字符串格式化主要是为后来可能增加的字段留出升级空间。

3. 字符串匹配

运行SQL后，文件路径将被查出来，通过文件名匹配。

这里我添加了路径搜索，以及是否忽略大小写和拼音搜索的功能。如果只是单纯的匹配字符串，直接用string.contains()或者string.indexof()即可。

关于为什么不使用KMP算法而只是暴力匹配。因为文件路径中并不存在大量重复字符串，并且路径字符串一般都不会很长。此时使用KMP算法由于大量运算反而会起反效果。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950/** * 判断文件路径是否满足当前匹配结果（该方法由check方法使用），检查文件路径使用check方法。 * * @param path 文件路径 * @param isIgnoreCase 是否忽略大小谢 * @return true如果匹配成功 * @see #check(String, String[], String, String[]) ; */ private static boolean notMatched(String path, boolean isIgnoreCase, String[] keywords) { String matcherStrFromFilePath; boolean isPath; for (String eachKeyword : keywords) { if (eachKeyword == null || eachKeyword.isEmpty()) { continue; } char firstChar = eachKeyword.charAt(0); if (firstChar == '/' || firstChar == File.separatorChar) { //匹配路径 isPath = true; Matcher matcher = RegexUtil.slash.matcher(eachKeyword); eachKeyword = matcher.replaceAll(Matcher.quoteReplacement("")); //获取父路径 matcherStrFromFilePath = FileUtil.getParentPath(path); } else { //获取名字 isPath = false; matcherStrFromFilePath = FileUtil.getFileName(path); } //转换大小写 if (isIgnoreCase) { matcherStrFromFilePath = matcherStrFromFilePath.toLowerCase(); eachKeyword = eachKeyword.toLowerCase(); } //开始匹配 if (matcherStrFromFilePath.indexOf(eachKeyword) == -1) { if (isPath) { return true; } else { if (PinyinUtil.isStringContainChinese(matcherStrFromFilePath)) { if (PinyinUtil.toPinyin(matcherStrFromFilePath, "").indexOf(eachKeyword) == -1) { return true; } } else { return true; } } } } return false; }

4. 显示结果

最后直接将搜索出来的结果显示在JLabel上就好了，这里就不再粘贴代码。

至此，一个最基本的Everything制作完成项目源代码在Github开源。XUANXUQAQ/File-Engine: An app launcher && efficiency tool (github.com)