title: How do you sort a tree stored using the nested set model?
body: <p>When I refer to nested set model I mean what is described <a href="http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/" rel="nofollow noreferrer">here.</a></p>
  
  <p>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:</p>
  
  <pre><code>root
      finances
          budgeting
              fy08
      projects
          research
          fabrication
          release
      trash
  </code></pre>
  
  <p>I want that to be sorted so that it displays as:</p>
  
  <pre><code>root
      finances
          budgeting
              fy08
      projects
          fabrication
          release
          research
      trash
  </code></pre>
  
  <p>Notice that the fabrication appears before research.</p>
  
  <p>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.</p>
  
  <p>Regardless, I was able to figure out how to (using the nested set model):</p>
  
  <ol>
  <li>Start a new tree in SQL</li>
  <li>Insert a node as a child of another node in tree</li>
  <li>Insert a node after a sibling node in the tree</li>
  <li>Pull the entire tree with the hierarchy structure from SQL</li>
  <li>Pull a subtree from a specific node (including root) in the hierarchy with or without a depth limit</li>
  <li>Find the parent of any node in the tree</li>
  </ol>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>Could this just be the limitation of the nested set model?  Does its use inhibit in query sorting of the output?</p>