Source: https://explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/
Overview
The article compares two classic techniques for modeling hierarchical data in relational databases—adjacency lists (parent pointers) and nested sets (lft/rgt intervals)—using PostgreSQL. It demonstrates their respective strengths for read-heavy vs write-heavy workloads and shows how to convert between the models.
Key points
- Adjacency list basics: each node stores a
parent_id. Recursive queries (CTEWITH RECURSIVE) can traverse the tree to fetch descendants/ancestors. Inserts are cheap; reads require recursion at runtime. - Nested sets basics: each node stores
lftandrgtvalues. Reading a subtree becomes a simple range query (WHERE lft BETWEEN ...), but inserts/updates require shifting large ranges to keep intervals consistent. - Performance trade-offs:
- Adjacency lists are intuitive and simple to maintain but need recursive queries for reporting.
- Nested sets deliver blazing-fast subtree reads and ordering but suffer from costly updates when the tree changes often.
- Conversion: the author shows how to derive nested-set values from an adjacency list using recursive traversal and
row_number(), then comparing EXPLAIN plans for sample queries. - Practical advice: choose adjacency lists when data mutates frequently or depth is limited; choose nested sets for mostly static hierarchies where read performance dominates. PostgreSQL’s recursive CTEs make adjacency lists more viable than in older SQL dialects.
Takeaways
- There is no universal winner; pick the structure aligned with your read/write profile.
- PostgreSQL’s recursive queries narrow the gap, making adjacency lists attractive unless subtree reads must be instant.
- Understanding how to convert between models lets you optimize later without losing data.