Fast TreeView

• Download source code - 39.4 KB

Introduction

When loading items into Windows Forms standard TreeView, you will find it can take an enormous time when loading many items! This simple extension will make loading lightning fast.

In this simple demo application, I use my own TreeViewFast control and compare it with the standard TreeView. As you can see, the difference is substantial.

Background

In my project, I need to load ~100 000 items in one go. When using the TreeView control, I was kind of depressed when I found out it took me 40-50 minutes ....

My first attempt was to reorganize the items using the SQL Server 2008 HierarchyId. That was interesting and useful in many ways, but for my case, it made very little difference. We have a typical "adjacency" table list where each item is stored in a table with a possible reference to a parentId.

When adding items to TreeView nodes collection, I don't know their structure except for the reference to the parent. That means I am forced to use the Find method of the TreeViewNodesCollection to get hold of parent. Obviously, the TreeView has a very poor performance on the inner data structure making it painfully slow for large item collections.

I know there are many nice controls to buy having many nice features. But I just wanted to prove the case that if all you need is better performance, then a simple extension to the existing TreeView will actually do.

Standard Approach

I start by generating a large set of demo items. In this case, they are employees with a consecutive Id property and randomly generated name combinations. Each employee is related to a manager by an optional ManagerId. If set to NULL, it means the employee is at the top level.

The standard way of adding these as nodes in TreeView control is like this:

foreach (var employee in employees)
{
    var node = new TreeNode { Name = employee.EmployeeId.ToString(), 
                              Text = employee.Name,
                              Tag = employee };
    if (employee.ManagerId.HasValue)
    {
        var parentId = employee.ManagerId.Value.ToString();
        var parentNode = myTreeView.Nodes.Find(parentId, true)[0];
        parentNode.Nodes.Add(node);
    }
    else
    {
        myTreeView.Nodes.Add(node);
    }
}  

When having small collections, this is fine, but when you start to count in thousands, it is terrible. In fact, the loading time is exponential to the number of items as seen in the following table.
Given times are in milliseconds. 100 000 items take 3 427 380 ms to load into standard TreeView. That's the same as 57 minutes! In the TreeViewFast, it takes 1 467 ms, that is 1.4 seconds.
I skipped trying to load 1 000 000 items into the normal TreeView ....

In the TreeViewFast implementation, the loading times are proportional or even faster.

Optimized Approach

I decided to use the standard TreeView but just extend it slightly. So I created a class TreeViewFast that inherits from the TreeView. The major trick is to create an internal Dictionary to store all nodes. That way, all parent lookups will always be fast, even for large collections.

I decided to use int as data type for item Id and int? for parentId. That can be questioned but in most cases, I think it will fit the existing data structure. I tried to use string but found it will give 10% slower times. If you need string or guid, it is very simple to just modify the code.

private readonly Dictionary<int, TreeNode> _treeNodes = new Dictionary<int, TreeNode>();  

As you can see, I decided to store the TreeNode items in the Dictionary. That will make it convenient to use. The item objects will be stored in the TreeNode generic Tag property. That way, we have easy access to the item objects all the time.

Ideally, we would like to have a generic constructor of the control class. Something like:

public class TreeViewFast<T> : TreeView 

That would make it really easy to refer to the type everywhere in the class. But unfortunately, the Windows Forms designer cannot handle controls with generic constructors.

A better idea would be to use types implementing a common interface, like ITreeViewFastItem.
But that would force all entities to have access to that interface. In my setup, the entities are defined in projects that must not have any dependency to the Windows Forms project where I define all controls.

So in my case, I decided to allow each method to have a T specifier and where necessary, I enter parsing functions to help the loader to interpret the object. This means the Load method will look like this:

/// <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, int> getId, 
       Func<T, int?> 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);
            parentNode.Nodes.Add(node);
        }
        else
        {
            Nodes.Add(node);
        }
    }
} 

The actual storage of nodes and objects is in the Dictionary.

To make the nodes visible, they are added to the TreeView internal Nodes collection making the expected hierarchy be seen as expected. The Nodes collection will in fact only hold references to the Dictionary objects so we don't waste any memory.

The important difference is the GetNode lookup which can now make use of the fast Dictionary lookup.

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

Calling the above Load method is simple:

// Define functions needed by the load method
Func<Employee, int> getId = (x => x.EmployeeId);
Func<Employee, int?> getParentId = (x => x.ManagerId);
Func<Employee, string> getDisplayName = (x => x.Name);
 
// Load items into TreeViewFast
myTreeViewFast.LoadItems(employees, getId, getParentId, getDisplayName); 

Some additional methods are added to the control for convenience: GetItems and GetDescendants. They are useful when you need to search the internal items collection or lookup children to a specific item.

Lessons Learned

• It is always useful to do detailed performance measuring to find crucial bottlenecks!
• Large sets of data is in itself not a problem as long as you handle them with care.
• I love Dictionaries. They seem to rescue me over and over again.

History

• First version