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:


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 ( 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




SQL Server

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