Delphi文件目录快速搜索算法

http://windirstat.info/ (就到了它收集数据的地方,并且已经准备好构建它的空间使用图了。)

如果卷是NTFS,那么要真正提高性能,可以做的一件大事就是直接解析MFT。通过这样做,您可以非常方便地枚举文件, 非常 快——我们说的速度至少快了一个数量级。如果您需要的所有元数据都是MFT记录的一部分,那么您的搜索将更快地完成。即使您必须对额外的元数据进行更多的读取,您也能够非常快速地建立候选文件列表。

缺点是您必须自己解析MFT:据我所知,没有WinAPI函数可以用来解析MFT。在担心硬链接、连接、重分析点、符号链接、shell链接等事情时,您还需要担心shell通常为您做的事情。

然而,如果你想要速度,增加复杂性是实现它的唯一途径。

我不知道任何可用的Delphi代码已经实现了MFT解析器,所以您可能需要使用第三方库或者自己实现它。我打算推荐开源(GPL) NTFS Undelete ,它是用Delphi编写的,但是它通过Python代码实现MFT解析,并且内置了Delphi-Python桥。

如果您想获得真正快速的搜索结果,可以考虑使用Windows搜索(API)或索引服务。

其他改进可能是使用线程,将文件搜索和文件属性的收集分开,或者只执行线程搜索。

我曾经遇到过一个非常类似的问题,目录中的文件数量加上findfirst/findnext花费的时间超出了合理范围。对于一些文件来说,这不是问题,但是当您向上扩展到数千个或上万个文件时,性能会显著下降。

使用这种方法,我们不仅实现了几乎“实时”的文件处理(仅由处理队列文件的频率延迟),而且还确保了文件按添加顺序进行处理。

如果您的程序是在Windows7或Server2008R2上运行的,那么Windows上有一些增强功能 FindFirstFileEx 使其运行更快的函数。您必须复制和修改VCL函数以合并新选项。

findfirst/findnext循环没有太多的优化空间,因为它主要受I/O限制:操作系统需要从HDD读取这些信息!

证明:制作一个小程序,实现一个简单的findfirst/findnext循环,对找到的文件不做任何处理。重新启动你的电脑,在你的大目录上运行,记下完成的时间。然后再次运行它,而不重新启动计算机。您会注意到第二次运行要快得多,因为操作系统缓存了信息!

我用两个线程解决了一个类似的问题。这样,我可以“处理”文件的同时,他们从磁盘扫描。在我的情况下,处理速度明显慢于扫描,所以我还必须限制一次内存中的文件数。

TMyScanThread公司

扫描文件结构,对于每个“命中”,使用Syncronize()将path+文件添加到TList/TStringList或类似文件中。记住在循环中使用Sleep(),让操作系统也有一些时间。

线程的伪代码:

TMyScanThread=class(TThread)
private
  fCount : Cardinal;
  fLastFile : String;
  procedure GetListCount;
  procedure AddToList;  
public
  FileList : TStringList;
  procedure Execute; Override;
end;

procedure TMyScanThread.GetListCount;
begin
  fCount := FileList.Count;
end;

procedure TMyScanThread.AddToList;
begin
  FileList.Add(fLastFile);
end;

procedure TMyScanThread.Execute;
begin
     try
        { Get the list size }
        Syncronize( GetListCount );
        if fCount<500 then
        begin
          // FindFirst code goes here
          { Add a file to the list }
          fLastFile := SR.Name; // Store Filename in local var
          Syncronize( AddToList ); // Call method to add to list
          SleepEx(0,True);
        end else
          SleepEx(1000,True);
     finally
        Terminate;
     end;
end;

tmyprocessFiles线程

获取列表中最早的条目,并对其进行处理。然后将结果输出到数据库。

Syncronize()调用的一种替代方法是使用TCriticalSection。实现线程之间的同步通常是一个品味和手头的任务的问题。。。

你也可以尝试BFS和DFS。这可能会影响你的表现。

http://blogs.msdn.com/b/ericlippert/archive/2004/09/27/234826.aspx

http://en.wikipedia.org/wiki/Breadth-first_search

http://en.wikipedia.org/wiki/Depth-first_search

当我开始在文件系统中处理大量小文件时遇到性能问题,我开始将文件作为blob存储在数据库中。没有理由不在数据库中存储诸如大小、创建和作者之类的相关信息。一旦在数据库中填充了表,我怀疑数据库引擎在查找记录(文件)方面比我们将要提出的任何解决方案都要快得多,因为数据库代码非常专用于在大型数据集中进行高效搜索。这无疑会更加灵活,因为添加一个新的搜索就像创建一个新的Select语句一样简单。示例:从author='bob'和size>的文件中选择*;10000