Sorting out SQL Trees
I recently came upon a problem that had a surprisingly pleasant solution. I had set of elements that look like this:
| Element | Bucket |
The "Bucket" for each element was a member of a hierarchical (and editable) tree. Usually, people represent a tree like this in SQL using the "adjency list model", where the table is repeatedly joined with itself on ID=parentID to produce the tree. The schema for that table looks like this:
| Bucket | ID | parentID | Order |
My hierarchy also has order, so that each child of a given parent has a sequential order.
The problem I had was that I wanted to sort my elements in an order based on the order of the tree so that I could have a report that looked like this:
1. Bucket
Element
Element
1.1 Bucket2
Element
Element
The dumb way to do this was to create a temporary table in my host language (recursively joining the "Buckets" table) and then joining that with my elements for ordering. The temporary table would look like this:
| Bucket | Order |
Where the order in this table was the preorder traversal of the tree.
The better way to do this is to use what Joe Celko calls "the nested set model" for representing a tree. The basic idea here is that you create a table that looks like this:
| Bucket | Left | Right |
Then you preorder traverse your tree. When you first hit a node, you set the node's "Left" property to the counter and then increment the counter. When you return to a node, you set the node's "Right" property to the counter and then increment. This is a more complicated data structure to maintain in SQL, but it has some nice properties that Celko elaborates on in his book and in this article. Each leaf node has the property that "Left" = "Right" + 1, and you can select all of the children of a node by selecting every node with a"Left" greater than the node and "Right" less than the node.
But the property that Celko doesn't mention is that this representation is perfect for sorting! If you sort by the "Left" property, you get a preorder tree traversal.