Xponent

Xponent developed a radically new type of treeview for XMLMax that completely eliminates the memory and performance problems that result from loading a treeview with a large number of nodes. The architecture does not implement or build upon any existing treeview technology, including ones that do not hold the entire XML in memory. Conventional treeview controls hold the entire treeview in memory, such that the number of nodes that may be added is strictly a function of the amount of available memory. As nodes are added and available memory decreases, so does performance. The reason is that the treeview control must re-calibrate the entire branch of the tree to which a node is added or inserted. As the branch becomes larger, the time required to add or insert a node increases logarithmically.

Existing Solutions

A widely used strategy that has been around for at least ten years loads the treeview with only the nodes in the first hierarchy under the root, but none of their child nodes, which are dynamically loaded and unloaded upon demand when a parent node is expanded or collapsed. This design requires that the entire document must be read before any data can be displayed and thereby precludes incremental loading. Moreover, this design requires that the displayed elements are initially collapsed because child elements are not loaded until the user expands an element. This may detract from the usability of the treeview for some users. It also presents the problem of preserving the collapsed-expanded state of an element; when a user collapses or expands specific fragments they expect to see them in the same state when they navigate back to them.

A variation of the above design is to read the XML only for the number of elements that can be visually displayed in the container, a value known as the Visiblecount. The known implementation of this design must still initially display elements collapsed, which requires reading the first(or next) Visiblecount elements at the same level. As the thickness (the number of nodes at a given level) of the XML increases, at some point the performance and memory problems occur. This is because the parser still has to read far enough into the raw XML to get enough elements at the same level to fill the screen. For example, if the first Visiblecount elements in the XML each contain 1,000 child elements and each child contains 100 elements, then between one and two million elements, depending on the Visiblecount, would have to be read before the data is displayed.

The Ultimate Treeview

Xponent's treeview works by reading the first VisibleCount nodes in the XML file and displaying them fully expanded. Thus, it reads only a short distance into the raw XML before it populates the treeview. The maxiumn number of XML nodes added to the treeview depends upon the size of the treeview, font size, and other user interface factors, but should not exceed forty nodes in a maximized window. Because so few nodes are in the treeview at a given time, the amount of memory needed to display and navigate any XML is strictly a factor of the content of the XML. Between ten and fifty thousand XML nodes are held in a memory buffer. Thus, the memory requirement is the size in bytes of the XML contained in the buffer, plus a small amount of overhead. It would be unusual for the memory requirement to exceed twenty megabytes unless the XML content includes large text nodes. Each time the tree is navigated, such as page down, page up or a scroll, it is cleared and the next VisibleCount nodes are added to the tree. This completely eliminates both the memory and performance problems, but it introduces a number of new ones.

This design requires a treeview to which any number of nodes may be added at any depth, which required the creation of a custom treeview. Xponent's treeview does not inherit or use any treeview or list-based control or class.

Even with such a custom treeview, a number of issues must be addressed. Mechanisms are needed for:

• Locating the child nodes of an element when it is expanded or collapsed.
• Tracking the expansion state of each element such that it is re-displayed in its prior state.
• Tracking the hierarchical depth of each node so that it may be properly indented in the treeview.
• Fast, bi-directional paging and scrolling from any location in the XML.

Xml data present the addtional problem of determining when XML end elements need to be added to the treeview. To address these issues, Xponent designed a buffering and caching system based on accessing and tracking byte offsets into the raw XML. The only drawbacks of the design are:

• The content of the XML is not scrolled while the scrollbar is dragged.
  This is because the treeview is cleared with each navigation event. In the case of a scroll drag event, it is not re-populated until the thumb is dropped.
• There may be a brief delay when the end of a buffer is reached.
  This is because the buffer must be cleared and re-loaded. The delay ranges from a small fraction of one second to two seconds. The delay for a given datasource is constant and does not vary with how far the treeview is scrolled. Thus, dragging the thumb from the beginng of the tree to the end should not take more than two seconds. Paging and scrolling within the range of the current buffer takes a small fraction one second so there is no noticeable delay. Buffer size ranges from ten to fifty thousand nodes

Submitted by Bill Conniff, Founder of Xponent, on May 26, 2009 Permalink