Nested Sets

The expression nested sets might not be familiar to you, but the concept behind it is quite common to all of us, it is a hierarchical structure. A hierarchical representation of elements allows the humans to locate them relatively to each other.

There are several data structures to represent a hierarchy of elements, the one being the topic of this article has different names in fact:

• Nested sets
• Modified Preorder Traversal Tree (translation: Route preordonnance modified tree).

Another model is the adjacent model. It is the most used model because of its simplicity, each node is linked to its closest parent. Unfortunately with this model we have to use recusivity to browse through a complete tree structure. This can be a problem when the tree structure becomes bigger.

Maintenance of a tree (adding, changing, deleting nodes) based on the adjacent model, however, is very fast and simple to implement.

Nested Sets allow an optimized traversal of the complete tree structure (because it is preordered) and, in contrast, the maintenance is heavier and less easy.

So it is a matter of choosing the right solution for each case. In the case of Nested Sets, here are some possible applications:

• Forum / sites / store categories ...
• Navigation menus
• Organizational chart

The common denominator in those few applications is that the structure is rarely modified, but it is browsed intensively !

It would be illogical to use this model for example in the case of a forum at the level of the hierarchy of the messages (threads). The structure is often being modified, so in this case the adjacent model would be better.

The functionning of the Nested Sets is that each node of the tree structure holds a reference of the "left" node and of the "right" node. It is used to describe the traversal of the tree an also the different hierachical levels. For example, we can say that each not that has a difference larger than 1 between its "left" and "right" references has at least one child. We can even calculate the total number of children with this formula : ("right" - "left" - 1) / 2 .

Figure 1 — Preordered traversal of a tree structure

Another advantage of this structure is that it is possible to fetch the whole structure or only a part of it with one single database query, without having to use recursivity. Which, in the case of a frequent display of the tree, allows to use the minimum of ressources.

The difficulty lies in the maintenance of the tree, for example, adding a node in the structure requires an update of all the nodes downstream of it. The same goes for other maintenance operations.

I was asked to develop a class for the access and the maintenance of a Nested Sets structure. A library of PHP function already exists, created by Rolf Brugger (edutech), called nstrees library (under GNU/GPL).

Based on this, I developed a PHP class for all these operations and some others. Here are some improvements:

• The use of a class allows management of several independent trees.
• Deleting a node: Keep and unindent children.
• Breadcrumbs Path, the description of the path to a node in form of an array that is not dependant on the design of the database (field name) : nstGetBreadcrumbsPath.
• Fetching of all the fields related to a node: nstNodeAllAttributes.
• Every methods and properties are commented.
• Explanation about how the traversal of the tree works internally (comments).

Source code of this class : nstrees.class.phps
Source code of an use example : nstreestest.phps

Additional References

• Storing Hierarchical Data in a Database