Nested Sets model or some other model for representing hierarchy? <p>I have a project where I hope to store hierarchical information (specifically, categories and subcategories) in what is basically a flat database system (in short, it's a collection of XML records). I'd like to store information about categories and subcategories in the system:</p> <ul> <li>Animals <ul> <li>Invertebrates</li> <li>Vertebrates</li> </ul></li> <li>Weather</li> <li>Buildings <ul> <li>Skyscrapers</li> <li>Historic buildings</li> </ul></li> </ul> <p>...and so forth.</p> <p><em>Everything</em> in the system, for better or worse, is stored as an XML record; this is just how the storage system works.</p> <p>Which means that each category in the system is also stored as an XML record, like so:</p> <pre><code>&lt;record id="12345"&gt; &lt;attribute name="Skyscrapers" /&gt; &lt;attribute type="Category" /&gt; &lt;/record&gt; </code></pre> <p>So I am wondering how to implement a hierarchy under these constraints.</p> <p>I'm used to data storage in a relational database. In those cases I pretty much always use the <a href="http://en.wikipedia.org/wiki/Nested_set_model" rel="nofollow">nested set model</a>. It seems like this wouldn't be a good choice in this case because:</p> <ol> <li>Each time you insert an item, you have to change the <code>right</code> and/or <code>left</code> values for many of the nodes. I can't do a bulk update on the XML files, so I'd have to update each one individually. </li> <li>Although there are search functions that let me filter by "less-than" or "greater-than" (so I could in theory pull only the relevant child nodes or parent nodes of a given category), I can't order the XML records by attributes. So I'd have to retrieve all of the documents, transform them into a list of objects that can be sorted (in this case with Python) and then sort them using a <code>lambda</code> function. </li> </ol> <p>Since my data storage model isn't significantly different than storing data using NoSQL I was wondering if anyone using that storage mechanism has come up with a good trick for handling and storing hierarchical data.</p>