DEV Community

loading...
Cover image for I Wrote a Tree Control for Enormous Trees

I Wrote a Tree Control for Enormous Trees

gjcampbell
I've worked on wide variety of interesting and complex projects for many years. Programming and I have been happily married since I was a teenager, and my real wife is sometimes jealous.
・3 min read

A company I was contracting for had a legitimate need for a web-based (angular) tree control that could handle thousands of nodes. I looked around a ton and found nothing really good enough, so I made this one and it handles tens of thousands really well πŸ‘Œ

An Uncommon Problem, I Admit

Most tree controls only need to support a pretty small data set. Like, 100 items max, and it becomes bad UX after that, right? I agree, but after having seen this same problem, huge trees, come up for the third time (three different companies, three different business domains), I wonder if it's not so rare after all.

Yeah, most trees are small, but it happens occasionally, that devs are expected to implement a tree control to handle an amount of data that exposes the tree control's inefficiency.

Smells Like Bad UX, Right?

In most software, a UI featuring an enormous tree of data would be cruel or repellent 🦨 to users. However, trees are ubiquitous, and in the right context, a tree is such a concise data visualization, and what a tree control may lack in elegance is redeemed by its familiarity to users.

It's Challenging Though

Regardless of whether it's right to use a tree for tons of data, it's a tough thing to implement. The file system explorer and your IDE have very well-written tree controls, but try to find a tree implementation as good as those. You'll find innumerable reusable components on github, packed with features, easy to drop in, but absolutely crippled by a large data set. They take forever to load or make interaction laggy and delayed.

I've wondered why efficient tree controls are so hard to find. I assume it's because being super-efficient is rarely necessary for a tree control. And, the time needed to create an efficient reusable tree control is not justifiable, because demand for one is low. πŸ€·β€β™‚οΈ

Have I Done it Right?

I think my implementation is correct. It responds quickly to all interactions with a large data set loaded. It handles a huge amount of data, it has all the typical tree features built in, and has no limitations preventing extensibility into more exotic features.

It Works Like This

  • Virtualization - (not to be confused with virtual dom) To render a very long list of nodes, virtual scrolling is used. In a scrollable container, only the items scrolled into view are visible. Outside of the visible area, is a huge blank space. So, even though the tree may have 10's of thousands of items expanded out, only a handful are rendered in the DOM. Angular has a built in CDK component for virtual scrolling. (It's not great though)

  • Flattened DOM - Typical tree implementations nest DOM elements. That makes it super easy to implement expand/collapse, indentation, and data binding. However, nesting works against virtualization. Rendering only the visible items and not their parent nodes is complicated and inefficient. So, to accommodate virtualization, all items in the tree are DOM-siblings, regardless of the relationships of the data they represent.

  • Metadata Preserved - Fine, the DOM is flat in the tree, but the tree's look and feel must remain. Items have to be indented, their children collapsible, etc. So, although the DOM is flat and although it is bound to flattened view of the data, all the necessary relationship data of the hierarchy is preserved, depth, ancestry, etc.

The Short Version

The recipe πŸŽ‚ for an efficient tree control supporting tons of data is pretty simple:

  1. Preserve metadata (so that the tree can look right even though flat)
  2. Flatten (so that you can virtual scroll)
  3. Virtual scroll (so that you can handle a huge list)

Thanks

πŸ™Check out the demo and the source code, and let me know what you think!

Discussion (0)