Nested Sets, Materialized Paths, and Closure Tables

Learning outcomes

Adjacency lists are flexible, but some workloads need very fast subtree or ancestor queries. Alternative hierarchy representations—nested sets, materialized paths, and closure tables—trade additional storage or write complexity for cheaper reads.

Nested sets

Each node receives left/right bounds:

Mechanical   lft=1  rgt=8Bearing      lft=2  rgt=3Seal         lft=4  rgt=5Alignment    lft=6  rgt=7

A descendant has bounds inside its ancestor's interval.

Subtree query

SELECT child.*FROM category parentJOIN category child  ON child.lft BETWEEN parent.lft AND parent.rgtWHERE parent.category_id = ?;

Subtree reads can be very efficient.

Nested-set write cost

Inserting or moving nodes may require renumbering many left/right values. This makes nested sets better for read-mostly, relatively static trees.

Materialized path

Store a path:

/mechanical/bearing/mechanical/seal/electrical/sensor

or an ID path:

/12/18/44/

Path-prefix queries

Descendants of node path /12/18/ are rows whose path begins with that prefix.

Materialized-path advantages

• simple path rendering;
• fast subtree prefix queries with suitable indexing;
• easy depth calculation in some designs;
• human-readable paths if codes are used.

Materialized-path disadvantages

Moving a subtree requires updating path values for the node and all descendants. Path encoding also needs escaping/delimiter rules if user-facing codes appear in the path.

Closure table

Store every ancestor/descendant relationship:

CategoryClosure(  ancestor_id,  descendant_id,  depth)

Each node usually includes a self-row at depth 0.

Closure example

ancestor   descendant   depthA          A            0A          B            1A          C            2B          B            0B          C            1C          C            0

Ancestor query

SELECT ancestor_id, depthFROM category_closureWHERE descendant_id = ?ORDER BY depth DESC;

Descendant query

SELECT descendant_id, depthFROM category_closureWHERE ancestor_id = ?;

Closure-table cost

For a chain of N nodes, closure rows can approach \(N(N+1)/2\). Balanced trees are less extreme, but storage still exceeds one row per node.

Closure-table write maintenance

Inserting a node requires closure rows linking all ancestors to the new node. Moving a subtree is more complex because old transitive relationships must be removed and new ones inserted.

Why closure tables are powerful

• ancestor queries are simple;
• descendant queries are simple;
• depth is explicit;
• cycle detection can be easier;
• recursive SQL may be unnecessary for common reads.

Comparison

Hybrid designs

A system may keep adjacency parent_id as the canonical structure and maintain a materialized path or closure table as a derived acceleration structure. That adds synchronization duties but preserves a simple source representation.

WorkshopHub choice examples

• Failure categories changing occasionally: adjacency list or materialized path.
• Large read-heavy equipment taxonomy: closure table may help.
• Mostly static publication taxonomy: nested sets can work.
• Frequently reorganized teams: adjacency list is often preferable.

Practice: choose a hierarchy model

Summary and next lesson

Hierarchy models make different tradeoffs. Adjacency lists optimize simplicity and moves; nested sets optimize static subtree reads; materialized paths optimize path/prefix access; closure tables precompute transitive reachability. The final lesson expands beyond trees into general graph-like relationships.

References

• Joe Celko, Trees and Hierarchies in SQL for Smarties.
• Bill Karwin, SQL Antipatterns.
• Database vendor documentation for recursive queries and path/index support.