Hierarchical Data (Adjacency List vs. Materialized Path vs. Nested Sets)
You'll learn to
- -Model tree-shaped data (folders, albums, categories) using an adjacency list, and know its query limitations
- -Compare materialized path and nested-set alternatives for when deep-hierarchy queries need to be fast
Photo albums that can contain sub-albums are a tree - the same Composite shape from Phase 1, now needing a relational representation instead of an object hierarchy. Several established techniques trade off query simplicity against query performance differently, and picking the right one depends on what the tree actually needs to do.
Adjacency List: The Simple, Default Choice
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, simple to insert into, and simple to update (moving an album to a new parent is a single-row UPDATE). The limitation: finding all descendants of an album (every sub-album, at any depth) requires either a recursive query or N round-trips walking down one level at a time - reasonable for shallow trees, but it does not scale gracefully to deep hierarchies queried frequently.
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 ancestor chain directly on each row as a string, like /1/4/17/, making "find all descendants of album 4" a single indexed prefix-match query (WHERE path LIKE '/1/4/%') instead of a recursive traversal. The cost: moving a subtree to a new parent means updating the path on every row in that subtree, not just one row - the update cost that adjacency list avoided has moved to whichever operation is now less frequent than reads.
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: Optimized for Read-Heavy, Rarely-Modified Trees
Nested sets assign each node a left and right number via a depth-first traversal, such that a node's descendants are exactly the nodes whose left/right values fall inside its own - an elegant technique for extremely fast subtree queries with no recursion or string matching, at the cost of needing to renumber a large portion of the tree on nearly every insert or move. This is worth knowing exists and naming as an option, but it is rarely the practical first choice for a tree that changes often - the update cost is usually too punishing outside of specialized, read-dominated cases.
The honest, defensible default in most interviews: start with adjacency list, name its query limitation for deep-hierarchy lookups explicitly, and mention materialized path (or nested sets, briefly) as the upgrade path if the interviewer pushes on "what if we need 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.
Design Photo Albums in the LLD Lab's Social Network act.