Created by: gwideman, Mar 16, 2012 5:49 am
Revised by: gwideman, Feb 19, 2013 7:45 pm (7 revisions)

Overview

Some notes on implementing and assessing tree and tree-grid controls in HTML with JavaScript and CSS for the functionality such as expand/collapse.
The problem at hand is how best to implement a tree or tree-grid which contains 10,000 to 100,000 nodes, while attending to the following requirements:
  • Time to load and become available to the user
  • Responsive scroll up and down
  • Responsive expand and collapse of
    • And individual node and their direct children
    • A node and all its descendants
      • Possibly including expanding or collapsing all nodes at one
  • Change of icon when expanding or collapsing (eg: [+] or [-], rotating triangle, close/open folder)
  • Search for text through all items in the tree
  • Sync: Ability to open to a particular node (having a particular URL, say), and scroll that node into view

Main challenges

The main choices in this problem are how to implement
  • the structure of the tree or tree-grid in html and/or javascript data structures
  • functions to find nodes to be operated upon
  • functions to operate on large numbers of nodes
  • detecting and responding to user actions on one of a large number of nodes
  • Mobile:
    • Way less CPU on mobile, and also slow JS implementations on some mobile browsers
    • Difficulty of operating small expand/collapse widgets with finger.
  • UI usability issues:
    • Nodes that have children AND have links. It would be nice to have click on node to open children, especially as that would present a bigger target for finger operation on mobile. But that conflicts with click on node to follow link.

Structure

The first implementation tension arises in connection with whether or not the the desired appearance and behavior can be implemented with intrinsically nested html constructs, such as ul/li or div.
Nested constructs allow branches of the tree to be treated as nested containers, where the display attribute of each node element intrinsically controls whether all contained nodes are displayed. A single operation display=none on a single ul will precipitate a single browser reflow in which all subsidiary nodes vanish. Vice versa for expansion. (The display=none operation can be performed on the node's style directly, or via changing the CSS class of the node.)
This can operate quickly because very little needs to be communicated between JavaScript and the DOM, and, at least for expand/collapse, the DOM/browser is called upon to do the bare minimum of operations.

Columns lead to table-based implementation

For tree-grid controls, we want each item to contain columns. These could be implemented within a ul/li using subsidiary spans, but typically we want the columns to align from one row to the next. At current writing, it seems to me that this alignment is only available reliably via the special layout semantics of the table/tr/td apparatus. In such an implementation, one of the columns (say the leftmost) would be dedicated to presenting the "tree", with children visually indented (using padding or margin), and further descendants moreso.

Implementating containership within a table

Unfortunately, the table apparatus does not naturally include containership, so some other structure needs to be introduced to remember which table rows are tree-descendants of which other rows.
The challenge becomes devising a use of the DOM, or an additional JavaScript structure, in which to capture the nested structure and its current state, and functions to navigate and manipulate it.

Possible alternatives

Containership specified by CSS "class membership"

  • A class is defined for each tree node.
  • All table rows which are descendants of that node have that class applied.
  • Expand/collapse of node X corresponds to changing the display status of the class corresponding to node X.
Advantages
  • Single interaction with the DOM (albeit fiddling with the CSS)
  • Should result in single reflow

Problems
  • Rows will have a number of classes applied according to depth, so 1 class for children of topmost parent, 2 classes at next level, and so on. The most-numerous bottom-most nodes will have the most classes applied.
  • With a 5 child/parent ratio, would result in defining 2,000 classes per 10,000 nodes
    • These will need to be applied to virtually all nodes, so approx 10,000/10,000 will have some classes applied, with the
  • Might not work without further fiddling, because it's not clear which class's display attribute will rule when several classes are applied.
    • Maybe choices like display=none or display=default solve this? Not sure.
  • In short, this runs into geometric explosion of class applications, and presumably geometric explosion of work for the browser to do to perform operations based on the classes.
    • At the very least, it's operating in territory that is probably not well tested and optimized?

Containership specified by progressively-extended id's and wildcards

  • A unique id is applied to each node.
  • Id is composed as follows: Some prefix (say 't' for tree) followed by a dash and a number according to sibling number within parent: 't-2-21-13' would be the id for the 13th child of the 21st child of the 2nd child of the root.
  • Operations (such as display: none) could be performed on groups of nodes selected by wildcard operations on the id. To collapse node t-2, apply display: none to all nodes with ids matching 't-2-*'. (Or apply a class that includes display:none.)
Advantages
  • No geometric explosion of classes or ids
  • No impact on CSS rules per se.
Problems
  • CSS select by wildcard operation is not a native CSS operation, must be done by JS, perhaps using a library such as jQuery.
    • Just the select by itself may be slow
    • Changes like 'display:none' would be performed on individual DOM nodes one at a time, resulting in reflow for each of possibly very many nodes.

Maintain separate JavaScript nested data structure

  • On initialization, create a JavaScript tree data structure where each node in the data structure has a reference to the corresponding DOM node.
  • Expand and collapse would involve the JS code determining from the tree data structure which rows of DOM are involved, and setting those to display: visible or none.
  • The JS tree data structure could optionally hold additional info, such as the node's text, to allow speedy searching
Advantages
  • Much faster determination of which nodes are descendants
  • Search through JS data structure would be much faster than searching DOM nodes
    • Similar for "sync" (jump to node having URL) operations
Problems
  • If the table HTML is supplied from the server with neither ids or classes, how does JS know which rows are children of which?
    • Almost suggests supplying data as JSON, and let JS build it.

Alternative: Place only visible parts of the tree-grid in the DOM

Only DOM-ify the expanded parts of the tree/table

Use a JS tree-of-objects data structure to hold the entire tree's data. When the user expands a node, only at that stage add nodes to the DOM.
Advantages
  • Initial speed
  • Likely enough speed on opening each individual parent
Disadvantage
  • Still needs to allow "expand all", so back to the issues discussed in previous sections

Only DOM-ify the portion of tree/table that is visible on-screen

In this alternative,at any one time in the DOM there would be only sufficient nodes (tree rows) to provide the visible display. JS adds table rows above or below (or inserts/deletes rows) corresponding to nodes that the user is now requesting to see by virtue of scrolling or clicking on nodes.
Advantages
  • Far fewer DOM elements in play at any one time: On the order of a few hundred table rows.
Problems
  • Sophisticated code required to track UI
    • Scroll bar would have to be very clever to properly model the position within the currently-expanded "virtual height" of the tree. And to work live while tree rows are being added and during reflow.

What about Ajax?

Ajax provides the opportunity to load some of the tree data from the server on-demand. For example, when the user clicks to expand a particular node, the click event handler could request the list of children from the server, and build the child DOM node on the fly.
This may be useful for avoiding loading the entire tree up front (or for cases where the entire tree is extremely large or effectively infinite). However, it does not solve the problems involved in dealing with managing and presenting 10,000 to 100,000 nodes that actually have been acquired from the server. Ajax is potentially complementary, but not an alternative.

UI Usability and Mobile issues

  • Performance of large trees may be very slow on mobile browsers
  • Wikispaces-specific issue: Wikispaces sends differently structured pages to browsers that identify themselves as mobile, and I've not got an answer on how to control that. (Mobile browsers that identify as desktop get the expected usual page.)
  • Operation of widgets that appear small on mobile, using a finger that is large relative to a mouse, combined with slow UI feedback, makes operation of tree on mobile difficult.
  • Using entire node as expand/collapse target -- would partially address difficulty to operate small widget, but conflicts with assignment of click or tap to follow node's link.

Related links

Performance


Miscellaneous