枚举 100,000 多个文件夹层次结构需要数小时

Enumerating 100,000+ folder hierarchy taking hours

为什么这段代码需要几个小时才能完成:

public void SetRoot(string path)
{
    Tag = path;
    BeginUpdate();
    AddFolderRecursive(Nodes, path);
    EndUpdate();
}

private void AddFolderRecursive(TreeNodeCollection nodes, string path)
{
    try
    {
        var dirs = Directory.EnumerateDirectories(path).OrderBy(d => d).Select(d => d.Split(Path.DirectorySeparatorChar).Last());
        TreeNode node;
        ShellFileGetInfo.FolderIcons fi;
        foreach (var d in dirs)
        {
            node = nodes.Add(Path.Combine(path, d), d, ImageList.Images.Count);
            node.Tag = Path.Combine(path, d);
            node.SelectedImageIndex = ImageList.Images.Count + 1;
            fi = ShellFileGetInfo.GetFolderIcon((string)node.Tag, false);
//                  ImageList.Images.Add(fi.closed);
//                  ImageList.Images.Add(fi.open);
            AddFolderRecursive(node.Nodes, (string)node.Tag);
        }
    }
    catch (UnauthorizedAccessException)
    {

    }
}

我已经离开这段代码 运行 14 个小时了,它仍然没有完成获取所有文件夹的列表,就像 SetRoot( @"c:\" ); 一样调用它。代码正在运行,它正在添加到树中,但这太荒谬了。

基本上,我想在我的驱动器上使用所有文件夹来流行树视图(因此树视图是可搜索的)并使用实际的文件夹图标(我正在使用 SHGetFileInfo p/invoke 和必要的这样做的参数)。即使没有获取图标(我遇到的另一个问题是获取文件夹的图标在逐个文件夹的基础上是唯一的,即使图标图像本身可能相同。我看不到确定的方法 -很快 - 如果我已经将该图像保存在我的 TreeView 的 ImageList 中 - 也就是说,'c:\windows' 的文件夹图标与 'c:\windows\system32' 相同,但是句柄等都是 return不同的信息,因此似乎没有任何东西可以继续对它们进行唯一索引。)。

可以在我的代码中进行哪些调整以加快此过程,同时仍保留系统中的文件夹图标?请记住,我还想要所有文件夹而不跳过空文件夹

(我什至无法显示 TreeView 的图片,因为我在 运行 完成显示前 14 小时后停止了循环)。

为了测试TreeView控件的速度,我写了下面的代码:

DateTime start = DateTime.UtcNow;
treeView1.BeginUpdate();
await Task.Run(() =>
{
    int x = 0;
    while (x < 100000)
    {
        x++;
        if (treeView1.InvokeRequired)
        {
            treeView1.Invoke((MethodInvoker)delegate { treeView1.Nodes.Add("Node - " + x); } );
        }
    }
});
treeView1.EndUpdate();
Text = start.ToLongTimeString() + " - " + DateTime.UtcNow.ToLongTimeString();

这是结果的屏幕截图:

如您所见,如果您使用 BeginUpdateEndUpdate 来阻止,用 100,000 个项目填充 TreeView 的速度 非常 大约需要 2 分钟从每个项目上绘制或刷新的控件。这也表明,绝对不是 TreeView 控件让我退缩——14 小时太多了——即使使用 1996 年的驱动器,14 小时来枚举 100,000 个文件夹,也太长了。

我敢打赌代码不是原因,它可能是以下两种情况之一:

  1. 你的硬盘很乱,可以试试碎片化的方法

  2. (我也发生了什么)你的文件夹没有被 windows 索引(索引 - https://en.m.wikipedia.org/wiki/Indexing_Service)要修复它你需要转到你所在的主文件夹继续工作并要求 windows 为文件夹及其所有子文件夹(文件夹框上的某处)编制索引,此过程大约需要一天时间,但之后您的程序应该可以正常(且快速)运行。

Windows 树视图控件的设计根本无法容纳这么多节点。您根本不可能在现实时间内用数千个节点填充此控件。更何况在短时间内将所有这些项目都列举出来肯定是不现实的。更尴尬的是试图提前为树中的每个 object 提取图标。

前进的方向是不要尝试用所有项目填充控件。只需填充 parent 个节点。然后当它们打开时枚举并添加 children。这就是所有 shell 程序的运行方式。

经过进一步研究,我发现问题是可用于枚举文件和文件夹的方法非常慢,并且当无法访问文件夹时会抛出 UnauthorizedAccessException,其固有延迟约为每个事件 200 毫秒。这些异常会叠加并导致很大的延迟。

此外,Davids 关于将项目添加到 TreeView 的二次指数导致进一步延迟的声明也是正确的,但是在这种情况下,额外的延迟仅与 TreeView 节点添加的缩放比例不成比例。

为了解决这个问题,我能够将其缩小到 3 个问题,我已经完全解决了其中两个问题,因此控制的那些部分在合理的时间范围内起作用。分解一下,这是导致 OP 问题延迟的 3 个问题:

  • TreeView 节点添加速度越慢,树越深,添加的节点越多。
  • 文件系统访问不访问可用于 NTFS 的本机日记系统,因此每个文件或目录在每次调用时都是单独获取的。此外,如果文件夹被标记为受限,UnauthorizedAccessException 会在每次遇到时人为延迟大约 200 毫秒。
  • 自定义文件夹图标的检索请求多个 IO 操作(具有各自的延迟),而且上述存储每个图标对的方法效率低下,导致它自己的额外延迟,即使在这个范围内很小,延迟也是相关。

在缩小延迟的范围后,我能够针对这些因素一一减少。


正在加快获取文件夹列表的速度

我必须做的第一件事是用更可行的方法替换文件系统访问方法 - 直接访问 NTFS 日志系统,我可以通过从 StCroixSkipper's USN Journal Explorer v1.3 and MFT Scanner in VB.NET to make the following class NtfsUsnJournal.cs 收集一些代码来做到这一点放上 pastebin,因为这超出了我在 Whosebug 上的能力 post。

此更改使我能够在 4 秒内递归检索 C 盘上的所有文件夹

注意:到目前为止,我一直无法找到一种无需应用程序提升(管理员)权限即可访问期刊的方法。所有在未提升权限的情况下访问日志的尝试都导致拒绝访问异常。


提高大量嵌套节点的 TreeView 性能

接下来,我需要提高 TreeView 的性能,以便能够在加载当前文件夹结构时添加超过 100,000 个嵌套节点。为此,需要一些 Google-fu,并进行一些修改以调整代码以适用于上述 class 的 Usn 格式。

结果是对扩展 TreeView 的客户用户控件的以下添加:

#region TreeViewFast
private readonly Dictionary<ulong, TreeNode> _treeNodes = new Dictionary<ulong, TreeNode>();

/// <summary>
/// Load the TreeView with items.
/// </summary>
/// <typeparam name="T">Item type</typeparam>
/// <param name="items">Collection of items</param>
/// <param name="getId">Function to parse Id value from item object</param>
/// <param name="getParentId">Function to parse parentId value from item object</param>
/// <param name="getDisplayName">Function to parse display name value from item object. This is used as node text.</param>
public void LoadItems<T>(IEnumerable<T> items, Func<T, ulong> getId, Func<T, ulong?> getParentId, Func<T, string> getDisplayName)
{
    // Clear view and internal dictionary
    Nodes.Clear();
    _treeNodes.Clear();

    // Load internal dictionary with nodes
    foreach (var item in items)
    {
        var id = getId(item);
        var displayName = getDisplayName(item);
        var node = new TreeNode { Name = id.ToString(), Text = displayName, Tag = item };
        _treeNodes.Add(getId(item), node);
    }

    // Create hierarchy and load into view
    foreach (var id in _treeNodes.Keys)
    {
        var node = GetNode(id);
        var obj = (T)node.Tag;
        var parentId = getParentId(obj);

        if (parentId.HasValue)
        {
            var parentNode = GetNode(parentId.Value);
            if(parentNode == null)
            {
                Nodes.Add(node);
            } else
            {
                parentNode.Nodes.Add(node);
            }
        }
        else
        {
            Nodes.Add(node);
        }
    }
}

/// <summary>
/// Get a handle to the object collection.
/// This is convenient if you want to search the object collection.
/// </summary>
public IQueryable<T> GetItems<T>()
{
    return _treeNodes.Values.Select(x => (T)x.Tag).AsQueryable();
}

/// <summary>
/// Retrieve TreeNode by Id.
/// Useful when you want to select a specific node.
/// </summary>
/// <param name="id">Item id</param>
public TreeNode GetNode(ulong id)
{
    try
    {
        return _treeNodes[id];
    } catch (KeyNotFoundException)
    {
        return null;
    }
}

/// <summary>
/// Retrieve item object by Id.
/// Useful when you want to get hold of object for reading or further manipulating.
/// </summary>
/// <typeparam name="T">Item type</typeparam>
/// <param name="id">Item id</param>
/// <returns>Item object</returns>
public T GetItem<T>(ulong id)
{
    return (T)GetNode(id).Tag;
}


/// <summary>
/// Get parent item.
/// Will return NULL if item is at top level.
/// </summary>
/// <typeparam name="T">Item type</typeparam>
/// <param name="id">Item id</param>
/// <returns>Item object</returns>
public T GetParent<T>(ulong id) where T : class
{
    var parentNode = GetNode(id).Parent;
    return parentNode == null ? null : (T)Parent.Tag;
}

/// <summary>
/// Retrieve descendants to specified item.
/// </summary>
/// <typeparam name="T">Item type</typeparam>
/// <param name="id">Item id</param>
/// <param name="deepLimit">Number of generations to traverse down. 1 means only direct children. Null means no limit.</param>
/// <returns>List of item objects</returns>
public List<T> GetDescendants<T>(ulong id, int? deepLimit = null)
{
    var node = GetNode(id);
    var enumerator = node.Nodes.GetEnumerator();
    var items = new List<T>();

    if (deepLimit.HasValue && deepLimit.Value <= 0)
        return items;

    while (enumerator.MoveNext())
    {
        // Add child
        var childNode = (TreeNode)enumerator.Current;
        var childItem = (T)childNode.Tag;
        items.Add(childItem);

        // If requested add grandchildren recursively
        var childDeepLimit = deepLimit.HasValue ? deepLimit.Value - 1 : (int?)null;
        if (!deepLimit.HasValue || childDeepLimit > 0)
        {
            var childId = ulong.Parse(childNode.Name);
            var descendants = GetDescendants<T>(childId, childDeepLimit);
            items.AddRange(descendants);
        }
    }
    return items;
}
#endregion

为了使用,我创建了一个新方法作为一个简单的 'loader',如下所示:

public void PopulateTree(string path)
{
    Tag = path;
    using (NtfsUsnJournal ntfs = new NtfsUsnJournal(new DriveInfo(path)))
    {
        List<NtfsUsnJournal.UsnEntry> folders;
        ntfs.GetNtfsVolumeFolders(out folders);


        Func<NtfsUsnJournal.UsnEntry, ulong> getId = (x => x.FileReferenceNumber);
        Func<NtfsUsnJournal.UsnEntry, ulong?> getParentId = (x => x.ParentFileReferenceNumber);
        Func<NtfsUsnJournal.UsnEntry, string> getDisplayName = (x => x.Name);

        LoadItems(folders, getId, getParentId, getDisplayName);
    }
}

经过测试,现在只需要6秒就可以将100,000+个文件夹全部加载到TreeView中,用户体验瞬间提升


带有自定义图标的文件夹

这是我目前挂断的最后一个地方,并且仍在寻找一种方法来全面改进它。

到目前为止我所做的是检查文件夹中是否存在 desktop.ini,如果存在,然后 调用 SHGetFileInfo pinvoke 获取自定义文件夹图标。然后,我将正在展开的文件夹添加到一个内部列表中,表明我已经检查了该文件夹并获得了任何关联的图标,这一切都发生在 OnBeforeExpand 事件中。虽然这些调用成本低廉,但它仍然会显着增加进程的延迟(扩展 c:\windows 需要 12 秒)。

这是相关代码(也在自定义 TreeView 中)

private List<string> _expandedCache;

protected override void OnBeforeExpand(TreeViewCancelEventArgs e)
{
    if (!_expandedCache.Contains(e.Node.FullPath))
    {
        BeginUpdate();
        ShellFileGetInfo.FolderIcons fi;
        _expandedCache.Add(e.Node.FullPath);
        string curPath;
        foreach(TreeNode n in e.Node.Nodes)
        {
            curPath = Path.Combine((string)Tag, n.FullPath.Replace('/', Path.DirectorySeparatorChar));
            if (File.Exists(Path.Combine(curPath, "desktop.ini")) == true)
            {
                fi = ShellFileGetInfo.GetFolderIcon(curPath, false);
                if(fi.closed != null || fi.open != null)
                {
                    ImageList.Images.Add(fi.closed);
                    ImageList.Images.Add(fi.open);
                    n.SelectedImageIndex = ImageList.Images.Count - 1;
                    n.ImageIndex = ImageList.Images.Count - 2;
                }
            }
        }
        EndUpdate();
    }
    base.OnBeforeExpand(e);
}

这是最后一个重大挫折,我相信有一种方法可以比传统的 File.Exists() 方法和 SHGetFileInfo pinvoke 更快地访问以获得自定义文件夹图标以便宜的方式

更新:经过更多测试后,我能够将最后一个问题缩小到将图标添加到 ImageList 时。每次将图像添加到连接到 TreeView 的 ImageList 时,都会刷新节点的整个 TreeView。如果有人知道如何让所有这些一起工作,同时在如此大的图像下保持高性能,请告诉我。或者,如果这种内部刷新可以以某种方式以不锁定 UI.

的方式推送到后台