Here are some notes on "SQL Server 2008 Hierarchies and HierarchyID" I took while attending an advanced class on SQL Server taught by Paul Nielsen (from http://www.sqlserverbible.com).

Please note that, although these notes were taken during the class, I might have added some of my own (mis)interpretation :-). Always check your facts on Books Online (I try to provide links when applicable). As with anything else you get from a blog, never use any of this in production before you thoroughly validate it a test environment. Please keep in mind that some of those will be hard to follow without some pre-requisite knowledge and the right context. Reading the post from top to bottom will help.


Hierarchies

  • Use cases: Hierarchy, graphs (many to many), XML indexing
  • Adjacency Lists: Species trees, directory folders, simple org charts
  • Dual parent adjacency list: Genealogies
  • Multiple Cardinality: Bill of materials, complex org charts
  • See http://technet.microsoft.com/en-us/library/bb677290.aspx

Adjacency pairs

  • Case: ManagerID in person table (AdventureWorks, 2005 or earlier)
  • Usually implemented as column pointing to PK on same table
  • Easy to find one level up or down, easy to reparent (replace manager)
  • Can leverage Recursive CTEs, user-defined functions

Bill of Materials

  • Case: Keeping track of all parts, subparts required to build a device
  • Case: Classes are pre-requisites to multiple other classes
  • m:m adjacency pairs
  • Typically implemented as an associative table
  • Can leverage user-defined functions

Materialized Path

  • Absolute path for row stored in database
  • Usually implemented as a text column in the table, using some sort of delimiter.
  • Example: 1 - 1.1 - 1.1.1 - 1.1.2 - 1.2 - 1.3 - 1.3.1
  • Example: /A - /B - /B/C - /B/D - /B/D/E - /B/D/F - /G
  • Easy to store as primary key, search all levels, difficult to reparent, fast queries
  • User-defined function to calculate materialized path (could be used in index)
  • You could also have the parent ID in parallel (use both at once)

HierarchyID

  • Like a materialized path: easy to search all levels, difficult to reparent
  • Easier to use as compound key
  • Example: /1/ - /1/1/ - /1/1/1/ - /1/2/
  • Compact design: CLR Data Type (SQLTypes library – SQLHierarchyID)
  • Used by SQL Server 2008 in the “hid” field in XML Indexing
  • See http://msdn.microsoft.com/en-us/magazine/cc794278.aspx

HierarchyID - Methods

HierarchyID – Indexing

  • Index by Node – Index on (HierarchyID)
  • Index by Level – Index on (Level[persisted], HierarchyID)

Hierarchy – Demo – Adjacency Pairs

Hierarchy – Demo – Materialized Path

  • Creating a column, storing the hierarchy
  • Querying in multiple ways, using functions
  • Storing the Level in an index, querying by level

Hierarchy – Demo – HierachyID

  • Using AdventureWorks2008, which uses OrganizationalNode, which is a HierarchyID
  • Looking at it as binary, .ToString.
  • Querying based on a string (no need to convert to binary)
  • Query a node to @Manager, querying all nodes under @Manager using .IsDescendentOf
  • How to insert – Use HierarchyID::GetRoot() or manager.GetDescendant(...)

Read more at http://technet.microsoft.com/en-us/library/cc721270.aspx
(includes other topics, search for HierarchyID)