Jingwei Tu

我的TUN网卡没有创建成功，使用sing-box1.8.5并且切换到系统代理模式就好了

我现在已经成功使用Deviceiocontrol获取文件的句柄以及父句柄，目前使用的是C++ STL库的map作为存储结构，在一百万文件中先遍历查找文件名test再生成查找结果的文件完整路径用时大概在2-3s左右（我设计的生成路径算法在所有文件的路径都被生成的情况下的复杂度为n*log(n)，n来自于遍历所有文件，log(n)来自于查找文件对应的父级目录）。 ```C++ //文件信息的结构 class FileInfo { public: string filename; string fileRef; string fileParentRef; string fullPath; string vol; FileInfo(string fn, string fr, string fpr, string c) { filename = fn;...

由于我打算用qt来完成界面，并且qt的tableView自带排序功能，我并没有太多地去考虑排序算法的问题。 但如果要我从零开始设计的话，我不完全认为归并排序是最优的选择：对于文件名、文件路径这两个字符串的排序，我认为归并排序、快排（或者改进的内省排序）都是很不错的选择；同时对于文件路径，我认为这一项里的拥有相同的头部字符子串的可能性更大，也就是说有序的可能性会更大？（这点我不是很确定）而在基本有序的情况下，插入排序更好。对于日期类的创建日期和修改日期，分治处理年月日，三者的波动范围并不大，很适合桶排序。文件大小则是难以有特征的随机数据，我倾向于快排。 对于归并排序，特别是大数据量下使用归并排序，我认为内存拷贝对于性能的影响更大，这也是虽然归并排序算法和快排是同一复杂度的算法时快排的表现往往更好的原因。 我不知道多线程对各种排序算法的影响有多大，以上只是对单线程排序的看法。具体参考[百万级数据如何排序](https://zhuanlan.zhihu.com/p/108358283) 监控方法已看到，我在完成后如果有时间的话会加入进来。 另外，dictionary和map的性能比较我也会在空余时间完成后继续回复。

是的

> 感觉我理解的对不对？这个程序只扫描了USN，USN只是增量的文件。是不是应该先读取MFT中的文件列表就可以了？USN只是为了后续文件变更快速更新索引，如果对实时性要去不高，其实是可以直接重新读取一次MFT？ 我现在的处理方式就是你说的这样的。 有一个简陋的demo，如果需要的话我可以提供。

> 好像可以参考ntfs-search里面是有，不过，我的疑问是你说ntfs-search速度比较慢，是说哪里慢？我觉得好像还可以，是加载速度慢，还是说搜索的过程慢？还是说搜索内容和ui绑定慢？ 我不是很清楚你说的ntfs-search是哪个。 但如果是我之前的回复里说的效率低，主要有几个点：1. 当文件数据条目过多时，读入速度慢，这是不可避免的；2. 对建立文件的路径信息等派生信息需要时间，并且这个建立算法会极大地影响效率；以上两点均可以通过建立数据库来解决。

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数据以供程序使用？等 都值得考虑。 至于文件排序，同之前的回复一样，我认为在没有预处理的情况下，多线程归并排序应该就是最优解了。 我之前只是用来应付课设，所以研究仅限于此。