Click here to Skip to main content
15,792,510 members
Articles / Programming Languages / XML

Fast TreeView

Rate me:
Please Sign up or sign in to vote.
4.97/5 (24 votes)
9 Nov 2013CPOL4 min read 88.8K   6.6K   56   18
Extension to the TreeView control making it very fast to load items

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.

Image 1

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:

C#
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 ....

Image 2

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

Image 3

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.

C#
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:

C#
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:

C#
/// <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.

C#
/// <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:

C#
// 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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
Sweden Sweden
20 years of development on Microsoft platform.

Comments and Discussions

 
QuestionExcellent material and outstanding presentation Pin
Member 1567105821-Apr-23 5:46
Member 1567105821-Apr-23 5:46 
PraiseAbsolutely Awesome! Pin
Shebarn762518-May-21 7:28
Shebarn762518-May-21 7:28 
QuestionPopulate cascade treeview from cascade data txt file Pin
Member 145288942-Mar-21 12:19
Member 145288942-Mar-21 12:19 
QuestionFastreeview Pin
Member 145288946-Feb-21 7:30
Member 145288946-Feb-21 7:30 
PraiseThis is great Pin
Chamila Nishantha28-May-20 20:46
Chamila Nishantha28-May-20 20:46 
QuestionFast TreeView Pin
Member 140383731-Nov-18 4:02
Member 140383731-Nov-18 4:02 
QuestionSort On ID Pin
hbs248026-Feb-18 1:28
hbs248026-Feb-18 1:28 
AnswerRe: Sort On ID Pin
hbs248026-Feb-18 1:35
hbs248026-Feb-18 1:35 
SuggestionDefault is as fast, just... Pin
Paw Jershauge15-Mar-17 6:37
Paw Jershauge15-Mar-17 6:37 
GeneralRe: Default is as fast, just... Pin
dhaskins13-Jul-19 17:34
dhaskins13-Jul-19 17:34 
Generalreally fast Pin
Southmountain13-Nov-15 14:35
Southmountain13-Nov-15 14:35 
SuggestionThe real point of TreeView is : Pin
Member 1127725916-Mar-15 8:10
Member 1127725916-Mar-15 8:10 
QuestionSet Id as type Pin
Laurent Muller29-Apr-14 20:34
professionalLaurent Muller29-Apr-14 20:34 
Great code. I have enhanced the tree view so keys can be any type.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;

namespace TreeViewFast.Controls
{
    public class TreeViewFast : TreeView
    {
        private Dictionary<K, TreeNode> _treeNodes = new Dictionary<K, TreeNode>();

        /// <summary>
        /// Load the TreeView with items.
        /// </summary>
		/// <typeparam name="K">Key type</typeparam>
        /// <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<K, T>(IEnumerable<T> items, Func<T, K> getId, Func<T, K?> getParentId, Func<T, string> getDisplayName)
        {
            // Clear view and internal dictionary
            Nodes.Clear();
			_treeNodes = new Dictionary<K, TreeNode>();

            // 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);
                }
            }
        }

        /// <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>
		/// <typeparam name="K">Key type</typeparam>
        /// <param name="id">Item id</param>
        public TreeNode<K> GetNode(K id)
        {
            return _treeNodes[id];
        }

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


        /// <summary>
        /// Get parent item.
        /// Will return NULL if item is at top level.
        /// </summary>
		/// <typeparam name="K">Key type</typeparam>
        /// <typeparam name="T">Item type</typeparam>
        /// <param name="id">Item id</param>
        /// <returns>Item object</returns>
        public T GetParent<K,T>(K 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="K">Key type</typeparam>
        /// <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<K, T>(K 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 = int.Parse(childNode.Name);
                    var descendants = GetDescendants<T>(childId, childDeepLimit);
                    items.AddRange(descendants);
                }
            }
            return items;
        }
    }
}

AnswerRe: Set Id as type Pin
Member 1096184323-May-15 6:02
Member 1096184323-May-15 6:02 
QuestionExcellent code Pin
liviucatrina29-Mar-14 22:59
liviucatrina29-Mar-14 22:59 
QuestionHow to make the TreeNode.Text changes dynamically by a object.ToString()? Pin
pclion11-Nov-13 20:58
pclion11-Nov-13 20:58 
QuestionNot sure about your measures of the standard approach... Pin
Jorge Varas11-Nov-13 10:15
Jorge Varas11-Nov-13 10:15 
Questionhmmm Pin
ndinges7-Nov-13 9:50
ndinges7-Nov-13 9:50 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.