Skip to content
Tutorials Center
My learning

Topics

Lesson 81 of 125 ยท Designing Databases

Hierarchical Data: Adjacency, Nested Sets, Closure Tables

Model trees such as categories and org charts in SQL. Compare the adjacency list, nested sets and closure table, and query descendants, ancestors and depth.

Trees are everywhere in real data: product categories, folders, comment threads, org charts, bills of materials. A relational table is flat, so the first design question is how to store "this row belongs under that row". The second is how to ask useful questions afterwards: show me everything under Electronics, show me the path from Smartphones up to the root, how deep is this node?

There are three classic designs. The adjacency list stores each node's parent. Nested sets store a numeric interval for every node. A closure table stores every ancestor and descendant pair in a separate table. Each one makes some questions cheap and others expensive, and this lesson shows you the trade-offs with runnable code. You already met the adjacency list in self joins and recursive CTEs; here we compare it with the alternatives.

All examples use the same small tree of shop categories:

flowchart TD
  S["Store"] --> E["Electronics"]
  S --> B["Books"]
  E --> P["Phones"]
  E --> L["Laptops"]
  P --> SP["Smartphones"]
  P --> FP["Feature phones"]
  B --> F["Fiction"]
  B --> SC["Science"]

The category tree used in this lesson: nine nodes, three levels below the root.

Design 1: the adjacency list

The simplest design adds a parent_id column that points back to the same table. The root has NULL as its parent. Inserting, renaming and moving a node each touch exactly one row, which is why this is the default choice.

Reading a whole subtree needs a recursive CTE. The anchor picks the starting node, and the recursive member walks down one level per step:

SQL Adjacency list: walk a subtree

Press Run (or Ctrl + Enter) to see the result here.

The query returns Electronics and everything below it. depth counts the steps from the starting node, and path accumulates the names; ordering by path puts every parent directly before its children. Walking up is the mirror image: start at a leaf and join on c.id = s.parent_id.

The adjacency list is excellent for writes and for "direct children" queries (WHERE parent_id = 3). Its weakness is that every subtree or ancestor question needs recursion. All modern databases support recursive CTEs, and for trees of a few thousand nodes they are fast enough, but they can't use a simple index range scan the way the next designs can.

Design 2: nested sets

Nested sets give every node two numbers, lft and rgt. Imagine walking around the tree like a path drawn around its outline: you number each node when you enter it (lft) and again when you leave it (rgt), counting up by one at every step. A node's descendants are exactly the nodes whose numbers lie inside its interval.

flowchart LR
  A["Store 1..18"] --> B["Electronics 2..11"]
  A --> C["Books 12..17"]
  B --> D["Phones 3..8"]
  B --> E["Laptops 9..10"]
  D --> F["Smartphones 4..5"]
  D --> G["Feature phones 6..7"]
  C --> H["Fiction 13..14"]
  C --> I["Science 15..16"]

Each node shows its (lft..rgt) interval. A child's interval always sits inside its parent's.

Now "everything under Electronics" is a plain range filter, with no recursion and no loop:

SQL Nested sets: descendants, ancestors, leaves

Press Run (or Ctrl + Enter) to see the result here.

Look at the last query. The number of descendants needs no join at all: a node with interval lft..rgt has (rgt - lft - 1) / 2 descendants, because each descendant uses two numbers. A leaf is any node where rgt = lft + 1. Depth is the number of intervals that contain the node, counted with a self join.

Nested sets make reads superb, and a single BETWEEN can use an index on lft. Writes are the price. Inserting a new node means shifting the lft and rgt of every node to its right, so a busy tree turns into many row updates and lock contention. Moving a subtree is worse. Use nested sets for trees that are read often and changed rarely, such as a product catalog that editors update a few times a day.

Not every lft/rgt pair is valid. If a bug leaves gaps, duplicates or overlapping intervals, subtree queries silently return wrong rows. Many teams add a check query that validates the numbering after any maintenance job.

Design 3: the closure table

A closure table keeps the tree in a second table with one row for every ancestor and descendant pair, including each node paired with itself at distance 0. A tree of nine nodes with three levels gives more rows than nodes, but each row is tiny: just two ids and a distance.

SQL Closure table: build it and query it

Press Run (or Ctrl + Enter) to see the result here.

The first result is 25 pair rows: nine self pairs plus sixteen real ancestor-descendant pairs. After that, subtrees, breadcrumbs, depth and "is X under Y?" are plain joins on the primary key. Because the pair table has its own index, these queries stay fast even for deep trees and huge subtrees.

Writes cost more than with an adjacency list but far less than with nested sets. To add a leaf under a parent, copy all of the parent's ancestor rows with the distance increased by one, and add the self pair:

SQL
INSERT INTO category_closure (ancestor_id, descendant_id, distance)
SELECT ancestor_id, :new_id, distance + 1
FROM category_closure
WHERE descendant_id = :parent_id
UNION ALL
SELECT :new_id, :new_id, 0;

Moving a subtree means deleting the old paths that connect it to its former ancestors and inserting new ones, which you should do in one transaction. Wrap this logic in a stored procedure or in application code so that nobody updates the two tables inconsistently.

Choosing a design

Question Adjacency list Nested sets Closure table
Direct children / parent Trivial Needs a join Filter on distance 1
Whole subtree Recursive CTE One range filter One join
Ancestors / breadcrumb Recursive CTE One range filter One join
Insert a node One row Renumber many rows A few rows
Move a subtree One row Renumber many rows Delete and insert paths
Extra storage None Two integers per node Many pair rows

Start with the adjacency list. It matches how people think, enforces integrity with a plain foreign key, and recursive CTEs handle most real trees. Reach for nested sets when the tree is huge, almost static and read constantly. Choose a closure table when you need fast reads and regular edits. Some databases also offer native tree features (PostgreSQL has the ltree extension, SQL Server has hierarchyid, Oracle has CONNECT BY), which are worth a look once you know which engine you will live on; see PostgreSQL and SQL Server and Oracle.

Whichever you pick, protect the tree: forbid a node from becoming its own ancestor (a cycle), and decide what happens to children when a parent is deleted (cascade or restrict).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which design stores only a parent_id column and needs a recursive CTE to read a whole subtree?

    The adjacency list stores one parent pointer per row. Following that pointer an unknown number of times is exactly what a recursive CTE does.
  2. 2. In a nested-sets table, a node has lft = 3 and rgt = 8. How many descendants does it have?

    Every descendant uses two numbers (its own lft and rgt), so the count is (rgt - lft - 1) / 2 = (8 - 3 - 1) / 2 = 2.
  3. 3. What does a closure table store?

    The closure table lists every ancestor and descendant pair, including each node with itself at distance 0, so subtree and ancestor queries become simple joins.
  4. 4. Which design makes inserting a node in the middle of a busy tree most expensive?

    Nested sets must shift the lft and rgt numbers of every node to the right of the insertion point, which can touch a large part of the table.

Summary

  • The adjacency list (parent_id) is simplest and best for writes; subtrees and ancestors need a recursive CTE.
  • Nested sets give each node a lft..rgt interval; descendants and ancestors are range filters and subtree size is (rgt - lft - 1) / 2, but writes renumber many rows.
  • A closure table stores every ancestor-descendant pair with a distance; reads are plain joins and edits touch a handful of rows.
  • Start with an adjacency list, and move to nested sets or a closure table only when read performance or query complexity demands it.
  • Guard against cycles and decide what happens to children when a parent is deleted.

Next: Versioning, Audit Tables and Slowly Changing Dimensions, where rows keep their history instead of being overwritten.