Hierarchical Data Models
Tree data in SQL is modeled as adjacency lists, nested sets, materialized paths, or closure tables — each trading write complexity against subtree query speed.
Definition
Hierarchical modeling strategies store parent-child structures with different query-write trade-offs. Adjacency lists store parent_id per row and need recursive queries. Nested sets encode preorder intervals for instant subtrees at expensive writes. Materialized paths store the ancestor chain as a string; closure tables store all ancestor-descendant pairs explicitly.
Context and scope
Chosen for org charts, category trees, comment threads, and BOM structures. Recursive CTEs changed the calculus by making adjacency lists cheap to query.
Common misconceptions
- Nested sets are the fastest structure — they are fastest for subtree reads and among the worst for moves and inserts
- Adjacency lists cannot answer subtree queries — recursive CTEs traverse them fine; only fixed-depth SQL without recursion struggles
- Closure tables are always overkill — for deep trees with frequent subtree analytics they beat everything on reads
Anti-patterns
- Choosing nested sets for a tree that moves nodes constantly and rewriting half the table per move
- Storing paths with a separator that appears in user data and corrupting ancestor matching
- Fetching entire trees to compute depths in application code instead of carrying depth in the model
Related concepts
Related examples
Authoritative source
What it is
Trees challenge relational rows because subtree membership is transitive. Four encodings dominate: parent pointers, interval numbers, path strings, and pair tables. Each makes one operation cheap — moving a node, counting a subtree, finding ancestors — and pays elsewhere.
How it works
Adjacency lists keep writes trivial and delegate traversal to recursive CTEs with cycle detection. Nested sets assign left and right numbers so a subtree is a numeric range, but node insertion renumbers siblings. Materialized paths support prefix matching and indexing. Closure tables store every ancestor pair, making depth and subtree queries index lookups while multiplying storage by tree depth.
When to choose
Frequently moved trees want adjacency lists. Read-dominant, stable trees with heavy subtree analytics want nested sets or closure tables. Mixed workloads often combine adjacency for writes with a closure table maintained by triggers.
Pitfalls
Moves in nested sets renumber broad ranges, and bulk imports become a rebuild. Path strings break when separators collide with data or when sibling renames rewrite descendant paths. Closure tables double storage per level and need disciplined maintenance on every structural write.