Skip to content
LLD Learn/Intermediate Modeling Patterns
Browsing as a guest. Sign in to save your progress and earn XP as you complete chapters.

Hierarchical Data (Adjacency List vs. Materialized Path vs. Nested Sets)

4 min read

You'll learn to

  • -Store a tree (folders, albums, categories) as an adjacency list, and say what it makes hard
  • -Compare materialized path and nested sets using the same small example tree
  • -Count the rows a move touches under each model, and state a sensible default

Photo albums that can contain sub-albums form a tree: the same Composite shape from Phase 1, now needing a relational representation instead of an object hierarchy. Several established techniques trade query simplicity against speed in different ways, and the right one depends on what the tree must do.

An Analogy: A Family Tree on Paper

You can write a family tree in three ways. You could list each person with only their parent's name. That is easy to write and easy to correct, but to find all of someone's descendants you must keep asking "who are your children?" down every level. You could write each person's full ancestry on their card, so every descendant of a person can be found by looking at the cards. Or you could number every person along a walk around the tree so a person's descendants all have numbers inside their range. These are the three models below.

Use one example tree throughout: the album Travel (id 1) contains Italy (id 4), which contains Rome (id 17).

Adjacency List: The Simple, Default Choice

Each row stores only its immediate parent. The rows for the example are (1, Travel, parent none), (4, Italy, parent 1) and (17, Rome, parent 4).

Each row just points at its immediate parent
CREATE TABLE albums (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    parent_album_id INTEGER,          -- NULL for a top-level album
    FOREIGN KEY (parent_album_id) REFERENCES albums(id)
);

This is simple to understand, to insert into, and to change. Moving Italy under another album is a one-row update. The limitation: finding every descendant of an album, at any depth, needs a recursive query or several round trips walking down one level at a time. A recursive CTE (common table expression, a query that refers to itself) is how SQL does it. That is fine for shallow trees, but it does not scale gracefully for deep hierarchies queried often.

A recursive CTE, needed to find all descendants under adjacency list
WITH RECURSIVE album_tree AS (
    SELECT id, name, parent_album_id FROM albums WHERE id = :root_album_id
    UNION ALL
    SELECT a.id, a.name, a.parent_album_id
    FROM albums a
    JOIN album_tree t ON a.parent_album_id = t.id
)
SELECT * FROM album_tree;

Materialized Path: Trading Update Cost for Read Speed

Materialized path stores the full chain of ancestors on each row as text. Travel is /1/, Italy is /1/4/ and Rome is /1/4/17/. Finding all descendants of Italy is then a single prefix match, path LIKE '/1/4/%', with no recursion. The cost appears when you move a subtree. If Italy has 120 sub-albums, moving it changes the path of Italy and all 120, so 121 rows, where the adjacency list changed one.

Materialized path - fast descendant queries, costlier moves
CREATE TABLE albums (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    path TEXT NOT NULL          -- e.g. '/1/4/17/' - this row's full ancestor chain
);
-- all descendants of album 4, in one simple, indexable query:
SELECT * FROM albums WHERE path LIKE '/1/4/%';

Nested Sets: Fast Reads, Costly Writes

Nested sets number every node twice while walking around the tree. Travel is (1, 6), Italy is (2, 5) and Rome is (3, 4). A node's descendants are exactly the nodes whose two numbers fall inside its own range. Italy's range is 2 to 5, and Rome's 3 and 4 fall inside it. The subtree query is extremely fast with no recursion or string matching. The price is renumbering a large part of the tree on almost every insert or move. It is worth knowing and naming, but it is rarely the first choice for a tree that changes often.

The defensible default in most interviews is to start with an adjacency list, name its limitation for deep descendant lookups out loud, and offer materialized path (or nested sets, briefly) as the upgrade path if the interviewer pushes on fast descendant queries at scale.

Interview Signal is part of Pro

See a real weak answer next to a real strong one for this exact topic.

Quiz is part of Pro

Test what you just read with a short quiz, and bank the XP.

Ready to Build This?

Design Photo Albums in the LLD Lab's Social Network act.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!