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:
- 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.
- 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.
- 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.
- 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.
- 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
- 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
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.