Trees in the database: Advanced data structures

alberton.info

19 points·nreece··5 comments

As an exercise in masochism, I created my own threaded comment system for a social news site I built. This question took me a long time to figure out.

Eventually I found Jow Celko's Trees and Hierarchies in SQL for Smarties. http://www.amazon.com/dp/1558609202/

Highly recommended if you're modeling trees in your database.

A brilliant illustration, clear yet concise, too bad there still isn't a clear winner.

Just a simple observation on an otherwise brilliant presentation. I had success modelling an organization chart in the past, just by simply adding a reportsTo field in the employee Database! It removed a lot of unnecessary tables in the database.

Assuming you have lot's of little tree's in different area's one quick read optimization is have (parent node) and (root node). Writes become a pain but being able to grab most tree's from the DB and update them in code often brings significant speedups.

I do that one a lot, since I've yet to need to stick a multi-million node tree in a database. Careful attention to the tree re-assembly algorithm results in an O(n) re-assembly, regardless of the order of the incoming nodes. With a bit more work the same algorithm cost can give you detection of invalid trees; unless you really can't afford to load in whole trees at a time this is as fast as anything else. Ordering of the tree can be provided by either a sort at query time or an ordering parameter in the worst case. (If you use an ordered child representation and append children to their parents in the order you receive them, and you sort the tree nodes by, say, date, then the resulting tree will have all children sorted by date too, with one simple ORDER BY clause. This works great for a comment tree, for instance.)

I consider this the go-to representation.

Reply on news.ycombinator.com