Michael Gilfix Online

I recently found myself posed with a design problem that necessitated storing a hierarchical structure in a relational database (no, a directory such as LDAP wasn't an option). A desirable solution would be implemented entirely in SQL, without dipping into stored procedure specifics. A bit of research turned up three techniques:

• Adjacency lists: Effectively each node (row) gets a parent column that refers to its parent. The tree is constructed by traversing through parent links. Here's a good tutorial: http://www.sqlsummit.com/AdjacencyList.htm.
  
• Nested sets: An excellent and clever approach that has yielded much fame for Mr. Joe Celko. Each node in the hierarchy has an interval that represents the range of its children, with smaller numbers in a level being to the left and larger numbers moving to the right. http://www.intelligententerprise.com/001020/celko.jhtml?_requestid=235427.
  
• Right child index: Each node gets a positive integer index and each node contains a column that references its rightmost child. In each level, nodes are organized from smallest index to largest. http://www.codeproject.com/cs/database/persisting_trees.asp#af.
  

The adjacency list is cheap for writes but expensive for queries. Nested sets and the right child index are optimized for reads at the expense of writes. The nested sets approach is particularly quick for queries, taking full advantage of database indexing capabilities -at the cost of updating the index. The right child index approach seems like it could offer a middle ground, but it's unclear how much savings since this is still an optimized for read approach. In addition to execution time, the latter two approaches also offer significant latency savings, as the adjacency list approaches requires multiple queries to follow the chain of parents up the tree.

The best part about all these approaches is that they only require basic SQL.