How do you sort a tree stored using the nested set model?

Question

When I refer to nested set model I mean what is described here.

I need to build a new system for storing "categories" (I can't think of better word for it) in a user defined hierarchy. Since the nested set model is optimized for reads instead of writes, I decided to use that. Unfortunately during my research and testing of nested sets, I ran into the problem of how do I display the hierarchical tree with sorted nodes. For example if I have the hierarchy:

root
    finances
        budgeting
            fy08
    projects
        research
        fabrication
        release
    trash

I want that to be sorted so that it displays as:

root
    finances
        budgeting
            fy08
    projects
        fabrication
        release
        research
    trash

Notice that the fabrication appears before research.

Anyway, after a long search I saw answer such as "store the tree in a multi-dimensional array and sort it" and "resort the tree and serialized back into your nested set model" (I'm paraphrazing...). Either way, the first solution is a horrible waste of RAM and CPU, which are both very finite resources... The second solution just looks like a lot of painful code.

Regardless, I was able to figure out how to (using the nested set model):

1. Start a new tree in SQL
2. Insert a node as a child of another node in tree
3. Insert a node after a sibling node in the tree
4. Pull the entire tree with the hierarchy structure from SQL
5. Pull a subtree from a specific node (including root) in the hierarchy with or without a depth limit
6. Find the parent of any node in the tree

So I figured #5 and #6 could be used to do the sorting I wanted, and it could also be used to rebuild the tree in sorted order as well.

However, now that I've looked at all of these things I've learned to do I see that #3, #5, and #6 could be used together to perform sorted inserts. If I did sorted inserts it always be sorted. However, if I ever change the sort criteria or I want a different sort order I'm back to square one.

Could this just be the limitation of the nested set model? Does its use inhibit in query sorting of the output?

Answer 1

I think this is indeed a limitation of the nested set model. You can not easily sort the child nodes within their respective parent node, because the ordering of the result set is essential to reconstruct the tree structure.

I think it is probably the best approach to keep the tree sorted when inserting, updating or deleting nodes. This even makes queries very fast, which is one of the main goals of this data structure. If you implement stored procedures for all operations, it is very easy to use.

You can also reverse the sort order of a presorted tree. You just have to use ORDER BY node.rgt DESC instead of ORDER BY node.lft ASC.

If you really need to support another sort criteria, you could possible implement it by adding a second lft and rgt index to each node and keep this sorted by the other criteria on every insert/update/delete.