Trees in SQL: Adjacency List, Materialized Path, and When to Use a Graph Database

Trees Are Everywhere, SQL Was Not Designed for Them

Hierarchical data structures appear in almost every domain. Comment threads with replies to replies. Category hierarchies five levels deep. Organizational charts with unlimited reporting depth. File system paths. Product taxonomies. Bill of materials trees. SQL was designed for flat sets, not recursive trees. The strategies for modeling trees in relational databases are therefore a collection of trade-offs, each optimizing for different access patterns.

The Adjacency List

The adjacency list is the simplest tree representation: each row has a parent_id that references the same table. A categories table has id, name, and parent_category_id. A comments table has id, text, and parent_comment_id. This model is intuitive to understand and easy to write. The downside is querying. Finding all descendants of a given node requires recursive CTEs or multiple application-level queries.

SQL:1999 added recursive common table expressions specifically for this problem. WITH RECURSIVE traverses the tree in a single SQL query: start with the root, union with all children, repeat until no more children exist. The result is a flat set of all descendants. Modern databases execute recursive CTEs efficiently. For most tree workloads with moderate depth (comment threads, category hierarchies), the adjacency list with recursive CTEs is the right answer.

The adjacency list is correct for trees where writes are frequent and read patterns are flexible. The recursive CTE is the SQL tool that makes it practical. Learn it once and tree queries become straightforward.

Materialized Paths

Materialized paths store the full ancestry of each node as a string column: '/electronics/phones/smartphones/iphone'. Finding all nodes under '/electronics/' becomes a simple prefix query: WHERE path LIKE '/electronics/%'. This is dramatically faster than recursive queries and does not require CTEs. Text indexes can accelerate prefix lookups.

The cost is write complexity. When a node moves in the tree, every descendant's path must be updated. Renaming a category from '/phones/' to '/mobile-phones/' requires a bulk UPDATE of every descendant row. For trees that change infrequently but are read constantly, materialized paths are excellent. For trees that restructure often, the write cost is prohibitive.

Nested Sets

The nested set model assigns left and right numbers to each node such that every descendant has values strictly between its ancestor's left and right numbers. Finding all descendants of category 5 (with left=10, right=25) is just WHERE left > 10 AND right < 25. No recursion. No prefix matching. Just a range query that any index handles efficiently.

The insert cost destroys this model's practical appeal. Adding a node requires renumbering every other node in the tree to maintain the invariant. On a tree with millions of nodes, inserting a single new category locks the entire table during renumbering. Joe Celko documented nested sets in SQL for Smarties in 1995 and they became famous as the 'theoretically perfect but practically painful' tree option.

When to Use a Graph Database

Neo4j, launched in 2007, stores data as nodes and edges natively. Queries like 'find friends of friends who like jazz and live within 50 miles' are trivial to express in Cypher and execute in milliseconds. The same query in SQL requires multiple self-joins on a users table, which the query optimizer handles poorly beyond three hops.

Relational databases CAN model graphs using self-referencing junction tables. They SHOULD use graph databases when the primary query patterns involve traversal more than three relationships deep. Fraud detection (finding fraudulent networks across transactions), recommendation engines (finding what similar users like), and knowledge graphs are natural graph database workloads. Social friend graphs with simple depth-1 queries are fine in relational. Social friend graphs with influence analysis across the full network are not.

• Adjacency list + recursive CTE: best default for trees. Simple writes, flexible queries, supported everywhere.
• Materialized path: best for read-heavy trees with infrequent restructuring. Fast prefix queries.
• Nested sets: theoretically elegant, practically painful. Avoid unless you have a very specific read optimization need.
• Graph databases: correct tool for traversal-heavy query patterns beyond 3 hops. Not a replacement for relational, a complement.

When SQL Beats Graph Databases on Graph Problems

Graph databases are often proposed as the solution for any problem involving relationships. The recommendation is frequently premature. PostgreSQL with recursive CTEs handles most tree and graph problems efficiently, especially when nodes have few connections (sparse graphs) and traversal depth is bounded (under 10 levels). Social friend recommendations at 1-2 hops, organization chart reporting chains, category hierarchies, comment thread nesting: all of these work well in PostgreSQL. The case for a graph database emerges when the query pattern requires unbounded depth traversal, complex multi-hop path finding, or relationship-heavy analytics across millions of edges.

The operational consideration reinforces this: running a separate graph database doubles your operational complexity. Two connection pools, two backup strategies, two monitoring setups, two query languages to maintain expertise in. For most applications, the graph workload is a small fraction of total data access. Solving it with PostgreSQL extensions (if possible) or accepting the SQL recursive CTE complexity keeps the operational model simple.

Practical Tree Patterns by Use Case

Comment threads with variable depth and frequent insertions: adjacency list with parent_comment_id. Recursive CTEs for reading nested threads. The write pattern (new comments append at the bottom) keeps insertion simple. The read pattern (fetch thread structure for display) benefits from the flexibility of recursive traversal.

Category trees for e-commerce (maximum 5-6 levels deep, read 1000x more than written): materialized paths. The category hierarchy changes infrequently (products are moved between categories rarely). The read benefit, fast prefix queries for all subcategories without recursive CTEs, outweighs the write cost of updating paths when categories move.

Organizational charts in enterprise HR systems (frequent reorganizations, must support complex reporting queries): adjacency list for primary storage, with a materialized hierarchy table refreshed on change for reporting. The combination gives write flexibility (adjacency list handles frequent changes easily) with read performance (flat table for analytics).

Graph Database Selection Criteria

• Neo4j: mature, full ACID, Cypher query language, best for production workloads requiring transactional guarantees on graph data.
• Amazon Neptune: managed graph database supporting both Gremlin and SPARQL. Best when you are already committed to AWS and want managed operations.
• TigerGraph: analytical graph database optimized for 10+ hop traversals. Best for fraud detection and recommendation engines at large scale.
• PostgreSQL with pgRouting or Apache AGE: add graph query capabilities to existing PostgreSQL infrastructure. Best for teams that already run PostgreSQL and have limited graph workloads.
• The choice between graph and relational should be driven by query patterns, not by whether the data has relationships. All data has relationships.

When SQL Beats Graph Databases on Graph Problems

Graph databases are often proposed as the solution for any problem involving relationships. The recommendation is frequently premature. PostgreSQL with recursive CTEs handles most tree and graph problems efficiently, especially when nodes have few connections (sparse graphs) and traversal depth is bounded (under 10 levels). Social friend recommendations at 1-2 hops, organization chart reporting chains, category hierarchies, comment thread nesting: all of these work well in PostgreSQL. The case for a graph database emerges when the query pattern requires unbounded depth traversal, complex multi-hop path finding, or relationship-heavy analytics across millions of edges.

The operational consideration reinforces this: running a separate graph database doubles your operational complexity. Two connection pools, two backup strategies, two monitoring setups, two query languages to maintain expertise in. For most applications, the graph workload is a small fraction of total data access. Solving it with PostgreSQL extensions (if possible) or accepting the SQL recursive CTE complexity keeps the operational model simple.

Practical Tree Patterns by Use Case

Comment threads with variable depth and frequent insertions: adjacency list with parent_comment_id. Recursive CTEs for reading nested threads. The write pattern (new comments append at the bottom) keeps insertion simple. The read pattern (fetch thread structure for display) benefits from the flexibility of recursive traversal.

Category trees for e-commerce (maximum 5-6 levels deep, read 1000x more than written): materialized paths. The category hierarchy changes infrequently (products are moved between categories rarely). The read benefit, fast prefix queries for all subcategories without recursive CTEs, outweighs the write cost of updating paths when categories move.

Organizational charts in enterprise HR systems (frequent reorganizations, must support complex reporting queries): adjacency list for primary storage, with a materialized hierarchy table refreshed on change for reporting. The combination gives write flexibility (adjacency list handles frequent changes easily) with read performance (flat table for analytics).

Graph Database Selection Criteria

• Neo4j: mature, full ACID, Cypher query language, best for production workloads requiring transactional guarantees on graph data.
• Amazon Neptune: managed graph database supporting both Gremlin and SPARQL. Best when you are already committed to AWS and want managed operations.
• TigerGraph: analytical graph database optimized for 10+ hop traversals. Best for fraud detection and recommendation engines at large scale.
• PostgreSQL with pgRouting or Apache AGE: add graph query capabilities to existing PostgreSQL infrastructure. Best for teams that already run PostgreSQL and have limited graph workloads.
• The choice between graph and relational should be driven by query patterns, not by whether the data has relationships. All data has relationships.