Modeling Hierarchical Data: Four Approaches Compared

1. Why hierarchical data is hard in relational databases

Hierarchical data such as product categories, organizational structures, file systems, or nested comment threads has a tree shaped structure with arbitrary depth, while relational tables are inherently flat: a row has fixed columns, not a variable number of children. This structural tension forces every model for hierarchical data into a trade-off between write and read performance.

The central question is always: which operations are frequent, and which ones are allowed to be slower in exchange? A category tree in a shop is rarely restructured but very frequently read for navigation menus and subtree queries. A comment thread, on the other hand, constantly receives new entries, while full tree queries are rarer and usually only needed for a limited depth. The four models discussed in this post, Adjacency List, Nested Sets, Path Enumeration, and Closure Table, resolve this trade-off in different ways.

None of the four models is universally "the best" for hierarchical data. Each deliberately optimizes for certain operations at the expense of others, and the right choice depends entirely on the actual access pattern of the specific application. The following sections show each model with a concrete schema and typical queries.

2. Adjacency List: the simplest model and its limits

The Adjacency List is the most intuitive model for hierarchical data: each row simply stores a reference to its direct parent node via a self-referencing foreign key column parent_id. The root of the tree has parent_id = NULL, every other node points to exactly one parent node.

-- Adjacency List: simplest modeling via parent_id
CREATE TABLE categories (
  category_id  SERIAL PRIMARY KEY,
  parent_id    INTEGER REFERENCES categories(category_id),
  name         VARCHAR(255) NOT NULL
);

-- Inserting is trivial: just set the new node's parent_id
INSERT INTO categories (parent_id, name) VALUES (3, 'Graphics Cards');

-- Direct children of a node: a simple, indexed lookup
SELECT * FROM categories WHERE parent_id = 3;

-- Entire subtree: requires a recursive CTE (see section 8)
WITH RECURSIVE subtree AS (
  SELECT * FROM categories WHERE category_id = 3
  UNION ALL
  SELECT c.* FROM categories c
  JOIN subtree s ON c.parent_id = s.category_id
)
SELECT * FROM subtree;

The advantage lies in maximum simplicity: inserting, moving, and deleting a single node are each just one fast INSERT, UPDATE, or DELETE. The limit shows up with subtree queries: without a recursive CTE or application logic that handles the recursion itself, it is impossible to determine "all descendants of a node" in a single plain query, because the depth of the tree is unknown at query time.

3. Nested Sets: tree structure via left and right values

Nested Sets encode tree structure not through a parent reference but through two numeric values per node, traditionally called lft and rgt, which result from a depth first traversal of the tree. Every node's interval [lft, rgt] fully contains the intervals of all its descendants, which turns subtree queries into a simple range comparison.

-- Nested Sets: tree structure via lft/rgt intervals
CREATE TABLE categories (
  category_id  SERIAL PRIMARY KEY,
  name         VARCHAR(255) NOT NULL,
  lft          INTEGER NOT NULL,
  rgt          INTEGER NOT NULL
);

-- Entire subtree of a node: a single range comparison,
-- NO recursion needed
SELECT child.*
FROM categories AS node, categories AS child
WHERE child.lft BETWEEN node.lft AND node.rgt
  AND node.category_id = 3;

-- All ancestors of a node: also a single range comparison
SELECT ancestor.*
FROM categories AS node, categories AS ancestor
WHERE node.lft BETWEEN ancestor.lft AND ancestor.rgt
  AND node.category_id = 17;

-- Inserting a new node requires shifting ALL
-- lft/rgt values to the right, expensive on large trees:
-- UPDATE categories SET rgt = rgt + 2 WHERE rgt >= :insert_position;
-- UPDATE categories SET lft = lft + 2 WHERE lft >= :insert_position;

The big advantage of Nested Sets: subtree and ancestor queries are extremely fast, because they require no recursion and no multi level joins, just a simple range comparison on indexed integer columns. The downside is massive for write operations: every insert or move of a node requires updating the lft/rgt values of all nodes to the right across the entire tree, which causes locking and performance issues on large, frequently changed trees.

4. Path Enumeration: the path as a string column

Path Enumeration stores, for every node, the full path from the root as a string, typically with a separator between the ancestor ids. A node with path 1.3.17 means: root id 1, then child id 3, then child id 17, with its own id at the end of the path.

-- Path Enumeration: full path as a string per node
CREATE TABLE categories (
  category_id  SERIAL PRIMARY KEY,
  name         VARCHAR(255) NOT NULL,
  path         VARCHAR(500) NOT NULL   -- e.g. '1.3.17'
);

CREATE INDEX idx_categories_path ON categories (path);

-- All descendants of a node with path '1.3': prefix search
SELECT * FROM categories WHERE path LIKE '1.3.%';

-- All ancestors of a node with path '1.3.17': split the path into segments
-- and check against the category_id of each segment (simplified example)
SELECT * FROM categories
WHERE category_id = ANY (string_to_array('1.3.17', '.')::int[]);

-- Inserting is simple: derive the own path from the parent's path
INSERT INTO categories (name, path) VALUES ('Graphics Cards', '1.3.17.42');

The advantage of this model: inserting is just as simple as with Adjacency List, and descendant queries are possible via an indexed prefix search without recursion. The downside is moving a subtree: if a node with many descendants is moved elsewhere in the tree, the path string of every single descendant must be updated, similarly expensive as with Nested Sets. Additionally, the maximum column length implicitly limits the maximum tree depth.

5. Closure Table: every ancestor-descendant relationship explicit

The Closure Table takes a different approach than the previous three models: instead of encoding the hierarchy within the node table itself, a separate table stores every ancestor-descendant relationship as its own row, including the distance between the two nodes. A node is also its own ancestor with distance zero.

-- Closure Table: every ancestor-descendant relationship as its own row
CREATE TABLE categories (
  category_id  SERIAL PRIMARY KEY,
  name         VARCHAR(255) NOT NULL
);

CREATE TABLE category_paths (
  ancestor_id    INTEGER NOT NULL REFERENCES categories(category_id),
  descendant_id  INTEGER NOT NULL REFERENCES categories(category_id),
  depth          INTEGER NOT NULL,
  PRIMARY KEY (ancestor_id, descendant_id)
);

-- Entire subtree of a node: a simple join, no recursion
SELECT c.* FROM categories c
JOIN category_paths cp ON cp.descendant_id = c.category_id
WHERE cp.ancestor_id = 3;

-- All ancestors of a node: same join, opposite filter direction
SELECT c.* FROM categories c
JOIN category_paths cp ON cp.ancestor_id = c.category_id
WHERE cp.descendant_id = 17;

-- Inserting a new leaf node under parent node 3:
-- copy all ancestor relationships of the parent plus one new row for itself
INSERT INTO category_paths (ancestor_id, descendant_id, depth)
SELECT ancestor_id, 42, depth + 1 FROM category_paths WHERE descendant_id = 3
UNION ALL
SELECT 42, 42, 0;

The advantage of the Closure Table: both subtree and ancestor queries are simple, non-recursive joins, and moving a subtree only touches the rows concerning the moved node and its descendants, not the whole tree as with Nested Sets. The downside is storage: the number of rows in the closure table grows quadratically with the depth of a subtree, a node with a hundred descendants potentially creates thousands of relationship rows.

6. Write operations compared: insert, move, delete

With hierarchical data, the four models differ most strongly on write operations. Adjacency List and Path Enumeration are equally cheap for simply inserting a new leaf node, a single INSERT is enough. Nested Sets, on the other hand, requires updating all rightward lft/rgt values across the entire tree on every insert, which becomes noticeable with thousands of nodes.

Moving a subtree, for example when a category with many subcategories moves into a different branch, shows the biggest difference: with Adjacency List, a single UPDATE of the moved node's parent_id is enough, all descendants stay unchanged because they remain correctly referenced relative to their direct parent. With Path Enumeration and Nested Sets, however, every single descendant must be updated. The Closure Table sits in between: only the relationship rows of the moved subtree need to be recomputed, not the entire table.

7. Read operations compared: subtree, depth, ancestors

The picture almost completely reverses for read operations. Adjacency List needs either a recursive CTE or several application logic round trips for every subtree or ancestor query, which is noticeably slower for deep trees than a single join. Nested Sets, Path Enumeration, and Closure Table each solve exactly this problem, each in its own way, with a single, non-recursive query.

A node's depth in the tree is not directly stored with Nested Sets and must be counted via the number of enclosing intervals, while Closure Table explicitly carries depth in its depth column, making it trivially queryable. Path Enumeration yields depth indirectly through the number of separators in the path string. For applications that frequently ask "all nodes at level 3," Closure Table, or an additional depth field in the other models, is the most practical solution.

8. When recursive CTEs are enough and when they are not

Recursive common table expressions elegantly solve the Adjacency List read problem without changing the data model: a WITH RECURSIVE query runs until no more child nodes are found, returning the complete subtree in a single statement. For moderate tree depths of a few dozen levels and moderate data volumes, this approach is often entirely sufficient and considerably easier to maintain than Nested Sets or Closure Table.

The limits of recursive CTEs show up with very frequent subtree queries under high load, because every query must run the recursion again without benefiting from precomputed structures. Very deep trees, say several hundred levels, can also hit configurable recursion limits on some database engines. For systems with rare structural changes but very frequent, performance critical subtree queries, the extra write cost of Nested Sets or Closure Table pays off, while recursive CTEs on Adjacency List remain the most pragmatic starting point for most use cases.

9. All four models compared

The following table summarizes the costs of the four modeling strategies for hierarchical data.

10. Summary

No model for hierarchical data is universally superior, each shifts the effort between write and read operations. Adjacency List is unbeatably cheap for writes but demands recursive CTEs for subtree queries. Nested Sets delivers extremely fast reads via a simple range comparison, but pays for it with expensive write operations across the whole tree.

Path Enumeration stays close to Adjacency List for inserts but makes moving a subtree expensive because every descendant must shift. Closure Table offers the most balanced trade-off between read and write cost, at the price of extra storage. The right choice for hierarchical data follows from the actual ratio of write to read operations in the specific application, not from a general ranking.

11. FAQ: Modeling Hierarchical Data