FastSearch
FastSearch copied to clipboard
bzmework
如何根据这个库产生文件索引？
你好：
由于我平时不常查看邮件，因此如果你能用QQ的话，欢迎加入QQ群：948127686 FastSearch是一个未完成的项目，还处于初级阶段，目标是达到Everything的程度，但是在开发过程中发现要达到它的高度很困难， 主要技术难点是：扫描出磁盘中的所有文件后要能快速的索引和排序，并且不能占用过多的内存，这方面我没有找到核心的算法。
如果想要快速地扫描出磁盘中的所有文件，经过研究表明读取USN信息是最快的方法，FastSearch的思路是： 1、打开所有磁盘分区； 2、读取每个分区的USN文件信息放入字典中； 3、从字典中查询指定的文件。 因此你只需要关注：
和
在实现的时候，采用了IO完成端口或者多线程读取每个分区的所有文件，实践表明异步IO速度更快。
IO完成端口(iocp.h)的原理请参考《Windows核心编程》（美）Jeffrey Richter。
我对你的建议是增加sorteddictionary.h排序字典，可以参考微软的.NET Frameworks源码：SortedDictionary。 目前在所有字典算法中.NET Frameworks的Dictionary是非常好的，因此你会发现在不考虑排序的情况下FastSearch加载和搜索速度是最快的。
下面的排序思路可供你参考： 1、扫描出所有分区中的文件放在各个分区字典中； 2、查找数据时，将找到的文件放在SortedDictionary中； 3、将SortedDictionary中的数据显示在界面上，在显示的时候采用虚拟加载，即拖动滚动条的时候动态显示指定部分。 采用SortedDictionary，会产生性能损失，但对于查找数据的话，因为进行了过滤，性能损失不大。 这个思路的缺点是： 1、由于没有索引，每次查找数据都会扫描整个字典(这类似于数据库全表扫描，实际上你会发现多线程扫描字典速度非常快，因为其在内存中进行的)； 2、如果找到的数据很多(例如:*.txt)，会占用大量的内存，为了避免这种情形，搜索的时候应该记录字典搜索位置，当移动滚动条的时候再从字典中查找一定数量的数据（这类似数据库游标）。
显然，Everything不是这样处理的，其作者对数据库的索引和排序有深入的研究，由于我对这块没有涉猎，因此没有更好的思路供你参考。 但我的总体设计思路是：将所有文件扫描到字典中，把字典当成内存数据库，化繁为简。 但是要达到Everything一模一样的程度，要下很多功夫。
最后，我写的代码已经是非常简洁了，为了便于阅读源码，你在跟踪调试的时候，我建议你先用多线程的方式扫描文件信息，不要用IO完成端口，因为其难于跟踪，如下： filejournal.cpp
把“fileObj->pRefresh();”的注释取消； 把“fileObj->pRefreshIocp();”注释掉。 这样就采用多线程扫描文件了。
------------------ 原始邮件 ------------------ 发件人: "Jingwei Tu"<[email protected]>; 发送时间: 2020年4月24日(星期五) 中午11:50 收件人: "bzmework/FastSearch"<[email protected]>; 抄送: "Subscribed"<[email protected]>; 主题: [bzmework/FastSearch] 如何根据这个库产生文件索引？ (#1)
目前正在阅读您的代码。 但是我仍未搞清楚如何调用接口以产生一个卷的文件索引。 希望能解答，谢谢。
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or unsubscribe.
我现在已经成功使用Deviceiocontrol获取文件的句柄以及父句柄，目前使用的是C++ STL库的map<string fileReference, FileInfo* fileInfo>作为存储结构，在一百万文件中先遍历查找文件名test再生成查找结果的文件完整路径用时大概在2-3s左右（我设计的生成路径算法在所有文件的路径都被生成的情况下的复杂度为n*log(n)，n来自于遍历所有文件，log(n)来自于查找文件对应的父级目录）。
//文件信息的结构
class FileInfo
{
public:
string filename;
string fileRef;
string fileParentRef;
string fullPath;
string vol;
FileInfo(string fn, string fr, string fpr, string c)
{
filename = fn;
fileRef = fr;
fileParentRef = fpr;
fullPath = "";
vol = c;
}
~FileInfo() {};
};
//生成文件路径
void __buildPath(unordered_map<string, FileInfo*>& fileMap, FileInfo* f)
{
unordered_map<string, FileInfo*>::iterator it = fileMap.find(f->fileParentRef);
if (it == fileMap.end())
{
f->fullPath = f->vol + ":\\" + f->filename;
}
else
{
if ((*it).second->fullPath == "")
{
__buildPath(fileMap, (*it).second);//在生成路径时，同时生成所有祖宗节点的路径，这样同级文件以及子文件的生成用时会降低。
}
f->fullPath = (*it).second->fullPath + "\\" + f->filename;
}
}
在自己设计的字典结构的插入与访问速度能超越stl库的map/unordered_map之前，我认为map和unordered_map都是很不错的选择。 但这也是我设计的目的与您有所出入，我对性能和效率没有极致的需求。 我现在遇到的另一个问题是如何实时监控文件的变化（例如新建了一个文件、重命名文件），并将之添加到我的数据库中而不需要重新遍历USN信息。
很好的方式。为了性能，也可以考虑在listview控件显示文件的时候，根据文件号遍历出路径并显示出来。目前我们主要面临的问题还有一个是排序，例如根据文件名、文件路径、创建日期、修改日期、文件大小等排序。我的计算机上大约有300多万文件，如何对其按照不同维度进行快速排序并显示（最好能达到everything的速度），我想采用多线程归并排序或是选项之一，具体请你研究一下。另外，map的效率是否高于我改写的微软dictionary，如果你有时间的话请测试一下，我没有进行对比测试。在开发过程中可以参考：https://sourceforge.net/projects/swiftsearch/ 只是其代码写得实在太乱，阅读起来很不友好。
发自我的iPhone
------------------ 原始邮件 ------------------ 发件人: Jingwei Tu <[email protected]> 发送时间: 2020年4月28日 07:46 收件人: bzmework/FastSearch <[email protected]> 抄送: mo <[email protected]>, Comment <[email protected]> 主题: 回复：[bzmework/FastSearch] 如何根据这个库产生文件索引？ (#1)
我现在已经成功使用Deviceiocontrol获取文件的句柄以及父句柄，目前使用的是C++ STL库的map<string fileReference, FileInfo* fileInfo>作为存储结构，在一百万文件中先遍历查找文件名test再生成查找结果的文件完整路径用时大概在2-3s左右（我设计的生成路径算法在所有文件的路径都被生成的情况下的复杂度为nlog(n)，n来自于遍历所有文件，log(n)来自于查找文件对应的父级目录）。 //文件信息的结构 class FileInfo { public: string filename; string fileRef; string fileParentRef; string fullPath; string vol; FileInfo(string fn, string fr, string fpr, string c) { filename = fn; fileRef = fr; fileParentRef = fpr; fullPath = ""; vol = c; } ~FileInfo() {}; }; //生成文件路径 void __buildPath(unordered_map<string, FileInfo>& fileMap, FileInfo* f) { unordered_map<string, FileInfo*>::iterator it = fileMap.find(f->fileParentRef); if (it == fileMap.end()) { f->fullPath = f->vol + ":\" + f->filename; } else { if ((*it).second->fullPath == "") { __buildPath(fileMap, (*it).second);//在生成路径时，同时生成所有祖宗节点的路径，这样同级文件以及子文件的生成用时会降低。 } f->fullPath = (*it).second->fullPath + "\" + f->filename; } }
在自己设计的字典结构的插入与访问速度能超越stl库的map/unordered_map之前，我认为map和unordered_map都是很不错的选择。 但这也是我设计的目的与您有所出入，我对性能和效率没有极致的需求。 我现在遇到的另一个问题是如何实时监控文件的变化（例如新建了一个文件、重命名文件），并将之添加到我的数据库中而不需要重新遍历USN信息。
— You are receiving this because you commented. Reply to this email directly, view it on GitHub, or unsubscribe.
补充：监控文件的增删改，开启一个线程，调用相应的API（可以找到示例），只需要以文件名为key放入字典中即可，如果有必要可以将字典进行压缩持久化到磁盘中。监控文件变化考虑的主要因素是删除或移动大量文件时带来的性能影响，监控不一定是非常准确的，有时候可能会重新扫描磁盘分区进行修正。最精确的监控是驱动级的，例如杀毒软件对文件的监控，如果你有耐心和精力可以考虑。
发自我的iPhone
------------------ 原始邮件 ------------------ 发件人: Jingwei Tu <[email protected]> 发送时间: 2020年4月28日 07:46 收件人: bzmework/FastSearch <[email protected]> 抄送: mo <[email protected]>, Comment <[email protected]> 主题: 回复：[bzmework/FastSearch] 如何根据这个库产生文件索引？ (#1)
我现在已经成功使用Deviceiocontrol获取文件的句柄以及父句柄，目前使用的是C++ STL库的map<string fileReference, FileInfo* fileInfo>作为存储结构，在一百万文件中先遍历查找文件名test再生成查找结果的文件完整路径用时大概在2-3s左右（我设计的生成路径算法在所有文件的路径都被生成的情况下的复杂度为nlog(n)，n来自于遍历所有文件，log(n)来自于查找文件对应的父级目录）。 //文件信息的结构 class FileInfo { public: string filename; string fileRef; string fileParentRef; string fullPath; string vol; FileInfo(string fn, string fr, string fpr, string c) { filename = fn; fileRef = fr; fileParentRef = fpr; fullPath = ""; vol = c; } ~FileInfo() {}; }; //生成文件路径 void __buildPath(unordered_map<string, FileInfo>& fileMap, FileInfo* f) { unordered_map<string, FileInfo*>::iterator it = fileMap.find(f->fileParentRef); if (it == fileMap.end()) { f->fullPath = f->vol + ":\" + f->filename; } else { if ((*it).second->fullPath == "") { __buildPath(fileMap, (*it).second);//在生成路径时，同时生成所有祖宗节点的路径，这样同级文件以及子文件的生成用时会降低。 } f->fullPath = (*it).second->fullPath + "\" + f->filename; } }
在自己设计的字典结构的插入与访问速度能超越stl库的map/unordered_map之前，我认为map和unordered_map都是很不错的选择。 但这也是我设计的目的与您有所出入，我对性能和效率没有极致的需求。 我现在遇到的另一个问题是如何实时监控文件的变化（例如新建了一个文件、重命名文件），并将之添加到我的数据库中而不需要重新遍历USN信息。
— You are receiving this because you commented. Reply to this email directly, view it on GitHub, or unsubscribe.
由于我打算用qt来完成界面，并且qt的tableView自带排序功能，我并没有太多地去考虑排序算法的问题。 但如果要我从零开始设计的话，我不完全认为归并排序是最优的选择：对于文件名、文件路径这两个字符串的排序，我认为归并排序、快排（或者改进的内省排序）都是很不错的选择；同时对于文件路径，我认为这一项里的拥有相同的头部字符子串的可能性更大，也就是说有序的可能性会更大？（这点我不是很确定）而在基本有序的情况下，插入排序更好。对于日期类的创建日期和修改日期，分治处理年月日，三者的波动范围并不大，很适合桶排序。文件大小则是难以有特征的随机数据，我倾向于快排。 对于归并排序，特别是大数据量下使用归并排序，我认为内存拷贝对于性能的影响更大，这也是虽然归并排序算法和快排是同一复杂度的算法时快排的表现往往更好的原因。 我不知道多线程对各种排序算法的影响有多大，以上只是对单线程排序的看法。具体参考百万级数据如何排序 监控方法已看到，我在完成后如果有时间的话会加入进来。 另外，dictionary和map的性能比较我也会在空余时间完成后继续回复。
究竟哪一种排序适合，可能需要根据不同场景进行优化选择，考虑多线程归并排序是基于everything的猜想。你在使用过程中开启everything的debug模式，会发现其排序采用了多线程。everything的大体过程是扫描文件、创建索引、进行排序、监控变化。我们不一定要按照他的设计思路做，就像我们把文件扫描进字典一样。期待你的好消息！
发自我的iPhone
------------------ 原始邮件 ------------------ 发件人: Jingwei Tu <[email protected]> 发送时间: 2020年4月28日 11:55 收件人: bzmework/FastSearch <[email protected]> 抄送: mo <[email protected]>, Comment <[email protected]> 主题: 回复：[bzmework/FastSearch] 如何根据这个库产生文件索引？ (#1)
由于我打算用qt来完成界面，并且qt的tableView自带排序功能，我并没有太多地去考虑排序算法的问题。 但如果要我从零开始设计的话，我不完全认为归并排序是最优的选择：对于文件名、文件路径这两个字符串的排序，我认为归并排序、快排（或者改进的内省排序）都是很不错的选择；同时对于文件路径，我认为这一项里的拥有相同的头部字符子串的可能性更大，也就是说有序的可能性会更大？（这点我不是很确定）而在基本有序的情况下，插入排序更好。对于日期类的创建日期和修改日期，分治处理年月日，三者的波动范围并不大，很适合桶排序。文件大小则是难以有特征的随机数据，我倾向于快排。 对于归并排序，特别是大数据量下使用归并排序，我认为内存拷贝对于性能的影响更大，这也是虽然归并排序算法和快排是同一复杂度的算法时快排的表现往往更好的原因。 我不知道多线程对各种排序算法的影响有多大，以上只是对单线程排序的看法。具体参考百万级数据如何排序 监控方法已看到，我在完成后如果有时间的话会加入进来。 另外，dictionary和map的性能比较我也会在空余时间完成后继续回复。
— You are receiving this because you commented. Reply to this email directly, view it on GitHub, or unsubscribe.
感觉我理解的对不对？这个程序只扫描了USN，USN只是增量的文件。是不是应该先读取MFT中的文件列表就可以了？USN只是为了后续文件变更快速更新索引，如果对实时性要去不高，其实是可以直接重新读取一次MFT？
感觉我理解的对不对？这个程序只扫描了USN，USN只是增量的文件。是不是应该先读取MFT中的文件列表就可以了？USN只是为了后续文件变更快速更新索引，如果对实时性要去不高，其实是可以直接重新读取一次MFT？
我现在的处理方式就是你说的这样的。 有一个简陋的demo，如果需要的话我可以提供。
好像可以参考ntfs-search里面是有，不过，我的疑问是你说ntfs-search速度比较慢，是说哪里慢？我觉得好像还可以，是加载速度慢，还是说搜索的过程慢？还是说搜索内容和ui绑定慢？
好像可以参考ntfs-search里面是有，不过，我的疑问是你说ntfs-search速度比较慢，是说哪里慢？我觉得好像还可以，是加载速度慢，还是说搜索的过程慢？还是说搜索内容和ui绑定慢？
我不是很清楚你说的ntfs-search是哪个。 但如果是我之前的回复里说的效率低，主要有几个点：1. 当文件数据条目过多时，读入速度慢，这是不可避免的；2. 对建立文件的路径信息等派生信息需要时间，并且这个建立算法会极大地影响效率；以上两点均可以通过建立数据库来解决。
https://github.com/aliakseis/NTFS-Search 我说的是这个，Fast-search首页作者说它比较慢，“在国内或者国外都有优秀的文件快速搜索程序，但开源的很少，网络上的源码大多数仅停留在基本的如何操作USN读取文件的层面， 出于商业目的，对具体的文件排序、文件压缩、文件索引、UI虚拟呈现等算法没有人愿意开源分享， 目前，能找到的开源程序有：https://sourceforge.net/projects/swiftsearch/ 和 https://sourceforge.net/projects/ntfs-search/ 但是，前者SwiftSearch采用异步IO扫描但源码可读性很差，而NTFS Search速度太慢，并且作者在其发布的新版中， 采用了内存映射技术，令扫描出来的文件占用内存较少，然而作者敝帚自珍，不再公布源码。“ 这段
Emm...我对ntfs-search这个项目了解不多。 单以我完成我的Demo的经验来讲，整个项目可以划分为三个主要的部分：1. USN读取模块、2. Search-Demo搜索模块、3. UI界面设计。 其中，USN读取模块使用的是微软提供的API，个人开发者很难再大幅提升性能。当然，组织能力好的话，设计一个好的数据结构来存取USN读取到的数据也会有帮助。 第二部分则是可操作性最强的地方了。搜索采用kmp算法是必然的，我在我的Demo中是遍历所有文件名并且kmp判断是否和关键词匹配。但这应该还不是最优解，可能可以用散列、映射等的方法来替换遍历所有文件名的做法，又或者是对文件名先做一个预处理，如将含有不同字符的文件名分类等，没有实践过，对程序效率的提升效果不清楚，空间则应该会占用更多一点，如何取舍还需要在实践时考虑。 第三部分也是个人开发者无需花费太多精力的部分。 第一、二部分间还有个步骤1.5.处理USN数据。USN数据中最关键的是Parent Index（父目录索引Pi）和Child Index（自身索引Ci），一个Ci只有一个Pi，根目录没有Pi，需要根据两个索引来构造文件的完整路径。文件路径构建算法对于开发者来说也是值得下一番功夫的。我是将整个文件系统当成一棵树来构造，目前需要处理的文件F，当它的存在Pi时，他的路径就是Pi的路径加上它自身的文件名，依此递归处理，当递归到Pi对应的文件的路径已经被生成或者不存在Pi时停止递归。涉及到的几个地方：1. Pi、Ci、文件名FileName间选用什么数据结构来存储有利于存取数据？2. 选用什么算法来生成路径（如何进一步优化文件路径生成算法？） 3. USN中读取到的数据应选用多少项最有利于处理？如何处理USN中读到的raw数据以供程序使用？等 都值得考虑。 至于文件排序，同之前的回复一样，我认为在没有预处理的情况下，多线程归并排序应该就是最优解了。 我之前只是用来应付课设，所以研究仅限于此。
我现在已经成功使用Deviceiocontrol获取文件的句柄以及父句柄，目前使用的是C++ STL库的map<string fileReference, FileInfo* fileInfo>作为存储结构，在一百万文件中先遍历查找文件名test再生成查找结果的文件完整路径用时大概在2-3s左右（我设计的生成路径算法在所有文件的路径都被生成的情况下的复杂度为n*log(n)，n来自于遍历所有文件，log(n)来自于查找文件对应的父级目录）。
//文件信息的结构 class FileInfo { 上市： 字符串文件名； 字符串fileRef; 字符串fileParentRef; 字符串fullPath; 弦卷 FileInfo（字符串fn，字符串fr，字符串fpr，字符串c） { 文件名= fn; fileRef = fr; fileParentRef = fpr; fullPath = “ ” ; vol = c; } 〜FileInfo（）{}; };//生成文件路径 void __buildPath(unordered_map<string, FileInfo*>& fileMap, FileInfo* f) { unordered_map <string，FileInfo *> :: iterator = FileMap。查找（f-> fileParentRef）; 如果（它== fileMap。端（）） { f-> fullPath = f-> vol + “：\\ ” + f->文件名； } 其他 { 如果（（*它）。第二- > FULLPATH == “ ”） { __buildPath(fileMap, (*it).second);//在生成路径时，同时生成所有祖宗节点的路径，这样同级文件以及子文件的生成用时会降低。 } f-> fullPath =（* it）。第二-> fullPath + “ \\ ” + f->文件名； } }在自己设计的字典结构的插入与访问速度能超越stl库的map/unordered_map之前，我认为map和unordered_map都是很不错的选择。 但这也是我设计的目的与您有所出入，我对性能和效率没有极致的需求。 我现在遇到的另一个问题是如何实时监控文件的变化（例如新建了一个文件、重命名文件），并将之添加到我的数据库中而不需要重新遍历USN信息。
您好 我也有这个需要 ，您可以共享代码吗
