Designing and Optimizing Hierarchical Tree Data in SQL: A Practical Comparison of 4 Models - ITFROMZERO - Share tobe shared! A practical comparison of four hierarchical data models in SQL—Adjacency List, Path Enumeration, Nested Sets, and Closure Table—with real-world benchmarks and query optimization tips.

Table of Contents

Context & Real-World Challenges

Whether you’re building an e-commerce platform, a forum system, or handling database schema design for chat apps, you will inevitably deal with hierarchical data. The tricky part is that relational database management systems (RDBMS) are fundamentally designed to handle flat, two-dimensional tables, whereas tree structures branch out freely and nest across multiple levels.

Picking the wrong model early on usually leads to two familiar issues. On the milder end, your application fires off dozens of N+1 queries just to render a multi-level navigation menu. In worse cases, the database suffers deadlocks and CPU spikes to 100% when a user drags and drops a parent category. On MySQL or PostgreSQL, just as with designing polymorphic relationships in SQL, the table architecture you choose determines whether your system runs smoothly or crashes when data grows to hundreds of thousands of records.

There are four widely adopted approaches: Adjacency List, Path Enumeration (Materialized Path), Nested Sets, and Closure Table. There is no silver bullet for every use case. Ultimately, the choice comes down to whether you prioritize read performance or write/update overhead.

Sample Schema Setup

To make comparisons straightforward, let’s model a tech category tree: Electronics > Phones > iOS / Android and Electronics > Laptops.

1. Adjacency List

The most intuitive and familiar approach. Each row simply includes a parent_id column referencing the primary key of its parent node.

CREATE TABLE categories_adj (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    parent_id INT NULL,
    CONSTRAINT fk_parent FOREIGN KEY (parent_id) REFERENCES categories_adj(id) ON DELETE CASCADE,
    INDEX idx_parent (parent_id)
);

INSERT INTO categories_adj (id, name, parent_id) VALUES
(1, 'Electronics', NULL),
(2, 'Phones', 1),
(3, 'Laptops', 1),
(4, 'iOS', 2),
(5, 'Android', 2);

2. Path Enumeration (Materialized Path)

An idea borrowed from Unix directory paths (e.g., /var/log/nginx/). Each node stores the full path from the root node to itself.

CREATE TABLE categories_path (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    path VARCHAR(255) NOT NULL, -- Standard format: 1/2/4/
    INDEX idx_path (path)
);

INSERT INTO categories_path (id, name, path) VALUES
(1, 'Electronics', '1/'),
(2, 'Phones', '1/2/'),
(3, 'Laptops', '1/3/'),
(4, 'iOS', '1/2/4/'),
(5, 'Android', '1/2/5/');

3. Nested Sets

This model numbers nodes based on a pre-order tree traversal. Each node holds two integer coordinates: lft (left) and rgt (right). Every descendant node has an index pair that falls completely within the parent node’s (lft, rgt) range.

CREATE TABLE categories_nested (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    lft INT NOT NULL,
    rgt INT NOT NULL,
    INDEX idx_lft_rgt (lft, rgt)
);

INSERT INTO categories_nested (id, name, lft, rgt) VALUES
(1, 'Electronics', 1, 10),
(2, 'Phones', 2, 7),
(3, 'Laptops', 8, 9),
(4, 'iOS', 3, 4),
(5, 'Android', 5, 6);

4. Closure Table

Decouples entity data from hierarchy relationships into two separate tables. A secondary table, category_relations, stores every ancestor-descendant pair along with a depth level.

CREATE TABLE categories_closure (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(100) NOT NULL
);

CREATE TABLE category_relations (
    ancestor_id INT NOT NULL,
    descendant_id INT NOT NULL,
    depth INT NOT NULL,
    PRIMARY KEY (ancestor_id, descendant_id),
    INDEX idx_descendant (descendant_id),
    CONSTRAINT fk_ancestor FOREIGN KEY (ancestor_id) REFERENCES categories_closure(id) ON DELETE CASCADE,
    CONSTRAINT fk_descendant FOREIGN KEY (descendant_id) REFERENCES categories_closure(id) ON DELETE CASCADE
);

INSERT INTO categories_closure (id, name) VALUES
(1, 'Electronics'), (2, 'Phones'), (3, 'Laptops'), (4, 'iOS'), (5, 'Android');

-- Record relationships (including self-referencing relationship at depth 0)
INSERT INTO category_relations (ancestor_id, descendant_id, depth) VALUES
(1,1,0), (2,2,0), (3,3,0), (4,4,0), (5,5,0),
(1,2,1), (1,3,1), (1,4,2), (1,5,2),
(2,4,1), (2,5,1);

Query Execution & Data Manipulation

Real-world performance differences become most apparent in two scenarios: retrieving an entire subtree and inserting/moving nodes.

Query 1: Retrieve the entire subtree under “Phones” (id = 2)

Adjacency List: Starting with MySQL 8.0 and PostgreSQL, we can use recursive Common Table Expressions (CTEs). The query runs in a single pass without requiring multiple round-trip loops from the application layer:

WITH RECURSIVE SubTree AS (
    SELECT id, name, parent_id, 1 AS level
    FROM categories_adj WHERE id = 2
    UNION ALL
    SELECT c.id, c.name, c.parent_id, st.level + 1
    FROM categories_adj c
    INNER JOIN SubTree st ON c.parent_id = st.id
)
SELECT * FROM SubTree;

Path Enumeration: Use the LIKE operator with a fixed prefix to leverage a B-Tree index:
```
SELECT * FROM categories_path
WHERE path LIKE '1/2/%';
```
Nested Sets: Boasts the fastest read speeds among all four models. The query is simply an arithmetic filter using the composite index (lft, rgt):
```
SELECT child.*
FROM categories_nested parent
JOIN categories_nested child ON child.lft BETWEEN parent.lft AND parent.rgt
WHERE parent.id = 2;
```

Closure Table: Requires only a simple two-table JOIN without recursive calculations:

SELECT c.*
FROM categories_closure c
JOIN category_relations r ON c.id = r.descendant_id
WHERE r.ancestor_id = 2;

Query 2: Inserting or Moving a Subtree

This is where write costs diverge significantly:

Adjacency List: Adding a child node requires only a single independent INSERT statement (execution time around 1ms). Moving a subtree also requires just a single UPDATE parent_id statement. Extremely fast and safe.
Path Enumeration: Adding a new node only requires fetching the parent’s path string and appending the new ID. However, when moving a parent node to a new location, you must update the path strings of the entire subtree underneath using string manipulation functions.
Nested Sets: Extremely expensive writes. Inserting a new node into the middle of the tree forces the database to re-index and increment the lft and rgt values (+2) of all subsequent nodes:
```
-- Must be wrapped in a transaction with locks
UPDATE categories_nested SET rgt = rgt + 2 WHERE rgt > 4;
UPDATE categories_nested SET lft = lft + 2 WHERE lft > 4;
INSERT INTO categories_nested (name, lft, rgt) VALUES ('HarmonyOS', 5, 6);
```
On a table with 500,000 records, these two UPDATE statements scan through hundreds of thousands of rows, easily causing wide-scope table locks and I/O bottlenecks.

Closure Table: When adding a new node, you insert one row into the categories table and replicate the parent’s relationships for the new node:

INSERT INTO categories_closure (id, name) VALUES (6, 'HarmonyOS');
INSERT INTO category_relations (ancestor_id, descendant_id, depth)
SELECT ancestor_id, 6, depth + 1
FROM category_relations
WHERE descendant_id = 2
UNION ALL
SELECT 6, 6, 0;

This operation only appends new rows to the auxiliary table without modifying existing data rows.

Summary Comparison Table

Criteria	Adjacency List	Path Enumeration	Nested Sets	Closure Table
Fetch Subtree	Good (Recursive CTE)	Fast (Index LIKE)	Blazing Fast (BETWEEN)	Very Fast (JOIN)
Fetch Ancestor Chain	Good (Recursive CTE)	Requires string parsing / CTE	Very Fast	Very Fast (depth > 0)
Add New Node	Blazing Fast (1 INSERT)	Fast (1 INSERT)	Very Slow (Re-indexing lft/rgt)	Fast (Insert a few auxiliary rows)
Move Subtree	Very Easy (Update 1 row)	Complex (String updates)	Highly Complex & deadlock-prone	Clean (Delete & rewrite relations)
Integrity Constraints	Very Strict (Foreign Key)	Weak (Relies on text strings)	Weak (Relies on arithmetic logic)	Very Strict (Foreign Key)
Storage Overhead	O(N) – Minimal	O(N) – Low	O(N) – Low	O(N * depth) – Highest disk usage

Performance Testing & Monitoring

To ensure system stability in production environments, you should use EXPLAIN ANALYZE to inspect indexes and execution plans.

1. Index Traps with Path Enumeration

A classic mistake with LIKE is placing a leading wildcard: LIKE '%/2/%'. This invalidates the B-Tree index, forcing the database into a full table scan. On a 500,000-row table, execution time can spike from 3ms to over 800ms.

To take advantage of an Index Range Scan, always preserve a fixed prefix:

-- Good: Utilizes Index Range Scan (Execution time: ~2-3ms)
EXPLAIN ANALYZE SELECT * FROM categories_path WHERE path LIKE '1/2/%';

-- Bad: Full Table Scan due to missing index prefix (Execution time: ~800ms)
EXPLAIN ANALYZE SELECT * FROM categories_path WHERE path LIKE '%/2/%';

2. Risk of Infinite Recursion with Adjacency List

Recursive CTEs build temporary tables in memory. MySQL’s system variable cte_max_recursion_depth defaults to a cap of 1,000 iterations. If bad data creates a circular reference due to an application bug (node A points to parent B, while node B points back to A), the query will consume resources and hang until hitting the timeout threshold:

-- Check current recursion limit
SHOW VARIABLES LIKE 'cte_max_recursion_depth';

-- Increase the limit for the current session if the tree is legitimately deeper
SET SESSION cte_max_recursion_depth = 5000;

3. Practical Rules of Thumb for Choosing a Solution

Adjacency List + Recursive CTE: Best suited for 80% of modern applications running on MySQL 8.0+ or PostgreSQL. Features a minimalist table schema, data integrity guaranteed via foreign keys, and performs exceptionally well on trees under 10–15 levels deep.
Closure Table: Well worth the investment when building multi-level comment systems (Reddit-style) or complex role-based access trees. It allows querying the distance between any two nodes and moving branches swiftly without locking tables.
Nested Sets: Reserve strictly for largely static data with read/write ratios exceeding 99:1. A textbook example is administrative boundary hierarchies (Country > Province > District > Ward). Administrative boundaries rarely change, whereas querying all descendants occurs constantly.
Path Enumeration: An ideal pick when you need to render breadcrumbs immediately in the UI without incurring extra JOINs or recursive queries.