Do you know the Choices for Storing Hierarchical Data inside a Relational Database?

Good Overviews

In most cases you are making the decision between fast read occasions (e.g. nested set) or fast write occasions (adjacency list). Usually you finish track of a mix of the choices below that best meet your needs. The next provides some thorough reading through:

• Yet another Nested Times versus. Adjacency List comparison: the very best comparison of Adjacency List, Materialized Path, Nested Set and Nested Interval I have found.
• Models for hierarchical data: 35mm slides with good explanations of tradeoffs and example usage
• Representing hierarchies in MySQL: excellent summary of Nested Occur particular
• Hierarchical data in RDBMSs: very indepth and well-organized group of links I have seen, although not much in the manner on explanation

Options

Ones I know of and general features:

1. Adjacency List:
   • Posts: ID, ParentID
   • Simple to apply.
   • Cheap node moves, card inserts, and removes.
   • Costly to locate level (can store like a calculated column), ancestry &lifier descendants (Bridge Hierarchy coupled with level column can solve), path (Lineage Column can solve).
   • Use Common Table Expressions in individuals databases that support these to traverse.
2. Nested Set (a.k.an altered Preorder Tree Traversal)
   • First referred to by Joe Celko - covered thorough in the book Trees and Hierarchies in SQL for Smarties
   • Posts: Left, Right
   • Cheap level, ancestry, descendants
   • In comparison to Adjacency List, moves, card inserts, removes more costly.
   • Takes a specific sort order (e.g. produced). So sorting all descendants inside a different order requires additional work.
3. Nested Times
   • Mixture of Nested Sets and Materialized Path where left/right posts are floating point decimals rather than integers and scribe the road information. Within the later growth and development of this concept nested times gave rise to matrix encoding.
4. Bridge Table (a.k.a. Closure Table: good quality ideas about using triggers for maintaining this method)
   • Posts: ancestor, descendant
   • Stands aside from table it describes.
   • May include some nodes in several hierarchy.
   • Cheap ancestry and descendants (although not with what order)
   • For complete understanding of the hierarchy must be coupled with an alternative choice.
5. Flat Table
   • An adjustment from the Adjacency List that contributes an amount and Rank (e.g. ordering) column to every record.
   • Costly move and remove
   • Cheap ancestry and descendants
   • Good Use: threaded discussion - forums / blog comments
6. Lineage Column (a.k.a. Materialized Path, Path Enumeration)
   • Column: lineage (e.g. /parent/child/grandchild/etc...)
   • Limit to how deep the hierarchy could be.
   • Descendants cheap (e.g. LEFT(lineage, #) = '/enumerated/path')
   • Ancestry tricky (database specific queries)

Database Specific Notes

MySQL

• Use session variables for Adjacency List

Oracle

• Use CONNECT BY to traverse Adjacency Lists

PostgreSQL

• ltree datatype for Materialized Path

SQL Server

• General summary
• 2008 offers HierarchyId data type seems to assist with Lineage Column approach and expand the depth that may be symbolized.