title: Efficient Database Structure for Deep Tree Data
body: <p>For a very big data database (more than a billion rows) where there is a very deep data tree, what is the most efficient structure?  The read loading is the highest usage, but there are also changes to the tree on a regular basis.</p>
  
  <p>There are several standard algorithms to represent a data tree.  I have found this reference as part of the Mongodb manual to be an excellent summary: <a href="http://docs.mongodb.org/manual/tutorial/model-tree-structures/" rel="nofollow">http://docs.mongodb.org/manual/tutorial/model-tree-structures/</a></p>
  
  <p>My system has properties that do not map well to any of these cases.  The issue is that the depth of the tree is so great that keeping "ancestors" or a "path" is very large.  The tree also changes frequently enough that the "Nested Sets" approach is not efficient.  I am considering a hybrid of the "Materialized Paths" and "Parent References" approach, where instead of the path I store a hash that is not guaranteed to be unique, but 90% of the time it is.  Then the 10% of the time there is a collision, the parent reference resolves it.  The idea is that the 90% of the time there is a fast query for the path hash.  This idea is kind of like a bloom filter technique.  But this is all for background: the question is in the first line of this post.</p>