Hierarchies in Backend Design · Lesson 1

Four ways to store a tree

You already know one cell of this matrix. This lesson gives you the other fifteen — and the reason the matrix, not the model, is the thing to memorise.

1. The frame: models are answers, operations are the question

Nobody picks a tree model by liking it. You pick it by ranking four operations, plus one guarantee:

1. Read subtree — every descendant of X, any depth. (Render a folder tree, sum a budget.)
2. Read ancestors — the path from root to X. (Breadcrumbs, permission inheritance.)
3. Insert leaf — the common write.
4. Move subtree — reparent X and everything under it. (The drag-and-drop.)

+ Integrity — can the database stop you from producing a broken tree, or does that live in application code and hope?

Write these five on the whiteboard before you argue about models. Half of hierarchy design disagreements are two people silently optimising different rows.

2. The four models

Adjacency list

Each row points at its parent. The default, and the one your ORM assumes.

node(id, parent_id REFERENCES node(id), name)

Reading a subtree needs a recursive common table expression (recursive CTE) — the SQL construct that repeatedly joins a result back onto itself until it stops producing rows:

WITH RECURSIVE sub AS (
  SELECT id, parent_id FROM node WHERE id = $1      -- anchor
  UNION ALL
  SELECT n.id, n.parent_id                          -- recursive term
  FROM node n JOIN sub ON n.parent_id = sub.id
) SELECT * FROM sub;

That is one query, and it is fine — the cost is one index lookup per level, and it walks the whole subtree. The trap is not the CTE. The trap is that ORMs rarely express it, so people write a loop instead. (Exercise 2.)

Integrity: the foreign key guarantees "my parent exists". It does not prevent a cycle — A.parent = B, B.parent = A satisfies every constraint and hangs your traversal.

Materialised path (a.k.a. path enumeration)

Each row stores its own full path. In Postgres, ltree gives you this as a first-class indexed type.

node(id, parent_id, path ltree, name)   -- 'root.marketing.q3'
CREATE INDEX ON node USING GIST (path);
SELECT * FROM node WHERE path <@ 'root.marketing';   -- whole subtree, one index scan

Subtree reads collapse to a prefix match. Ancestor reads too. The price is on move: every descendant's path is now wrong, so you rewrite them all — write amplification proportional to subtree size. That is your 50 000 rows.

Integrity: path is denormalised — a derived copy of a truth that lives in parent_id. Nothing in the database forces the two to agree. Every code path that writes one must write the other, in the same transaction.

Nested set

Each row stores two numbers from a depth-first walk of the tree: lft and rgt. A node's descendants are exactly the rows whose numbers fall between them.

node(id, lft INT, rgt INT, name)
SELECT * FROM node WHERE lft BETWEEN $lft AND $rgt;   -- subtree, one range scan

Reads are the fastest of the four. But inserting a single leaf shifts the numbering of roughly half the tree, and it must happen under a write lock or two concurrent inserts corrupt the numbering irreparably. A corrupted nested set is also the hardest of the four to repair, because the structure is the numbering — there is no surviving parent_id to rebuild from.

Nested set is the right answer for a near-static, read-dominated tree — a published taxonomy, a book's table of contents. In a web app where users write concurrently, it is almost always the wrong answer. Know it so you can name it and reject it with a reason.

Closure table

Store the transitive closure explicitly: one row for every ancestor–descendant pair, including each node to itself at depth 0.

node(id, name)
node_closure(
  ancestor_id   REFERENCES node(id) ON DELETE CASCADE,
  descendant_id REFERENCES node(id) ON DELETE CASCADE,
  depth INT,
  PRIMARY KEY (ancestor_id, descendant_id))

Both directions are one indexed lookup. Inserting a leaf writes depth + 1 rows. Moving a subtree deletes and reinserts |subtree| × |new ancestor path| rows — the largest write of the four, but ordinary rows in an ordinary table, no locking scheme required.

Integrity: the strongest of the four. Both columns are real foreign keys, so no edge can reference a node that does not exist, and cascading deletes clean the closure automatically. Storage cost is n × average depth rows — for a 1M-node tree of depth 6, ~6M closure rows. Cheap. For a depth-40 tree, reconsider.

3. The matrix

Try to fill it from memory before reading — you have two cells already.

Notice what the matrix says that "read-heavy vs write-heavy" does not: the expensive write is move, specifically, and only move. Insert is cheap in three of four models. A product where users create deeply nested things but rarely drag them (most products) can happily pay materialised path's move cost.

4. The question that outranks the matrix: is depth bounded?

The decision flow

This is where your two flavours of hierarchy diverge, and it is the single highest-leverage distinction in the topic.

A type hierarchy — campaign → ad set → ad — is not a tree problem. Depth is three, forever, fixed in the schema. Three tables, two foreign keys, ordinary joins. Every tree model above is overhead you would be paying for flexibility the domain forbids. The interesting questions for type hierarchies are about API shape and consistency boundaries, not storage — that's Lesson 2.

A value hierarchy — folder → folder → folder — is recursive and homogeneous. Users choose the depth, which means depth is unbounded, which means every traversal is a loop of unknown length. That is what the four models exist for.

The mistake this catches: reaching for ltree to model campaign → ad set → ad, or reaching for three tables and hardcoded joins when users can nest folders arbitrarily. Both are common; both are visible from the first sentence of the requirements.

5. The hybrid most products land on

Keep parent_id as the source of truth. Add path (or a closure table) as a derived read index, written in the same transaction.

-- truth
node(id, parent_id REFERENCES node(id), name)
-- derived, maintained by trigger or repository code, rebuildable at any time
node(..., path ltree) + GIST index

You get materialised path's read performance and adjacency list's insert cost. You still pay |subtree| writes on move. What you buy for that price is recoverability: because parent_id remains authoritative, a drifted or corrupted path column is a bug you fix with one UPDATE, not a data-loss incident. Nested set has no equivalent escape hatch, which is most of why it lost.

Truth versus derived data

The generalisation is worth naming properly, because it recurs everywhere. parent_id is the single source of truth: the one representation the database enforces, and the one every other copy is computed from. path is derived data — its only justification is speed, and its defining property is that you can delete it and lose nothing. That question — if I dropped this column, could I rebuild it from what remains? — is the test that separates a legitimate denormalisation from a second, competing source of truth.

A second source of truth is the thing you are avoiding. Nested set has no parent_id underneath it, so its lft/rgt pair is the truth — nothing to rebuild from, which is why a corrupted nested set is an incident and a drifted path column is a one-line UPDATE. Same asymmetry drives caches, search indexes, read models and materialised views; a future lesson on the outbox pattern makes it explicit for data that lives in another service.

Exercises

Exercise 1 — Recall (free)

Without scrolling up: you are moving a subtree of 50 000 nodes, from depth 3 to depth 7, in a closure table. Roughly how many closure rows are written, and why is that number bigger than the materialised path's 50 000?

Exercise 2 — Bug hunt: click the offending line

This is the ORM-shaped subtree read. Click the line where it goes wrong.

async function loadSubtree(nodeId: string): Promise<Node[]> {  const node = await db.node.findUnique({ where: { id: nodeId } });  const children = await db.node.findMany({ where: { parentId: nodeId } });  const out: Node[] = [node!];  for (const child of children) {    out.push(...(await loadSubtree(child.id)));  }  return out;}

Exercise 3 — Bug hunt: click the offending line (or declare it clean)

A move under a materialised-path design. One of these two snippets is correct; this one may not be.

async function moveNode(id: string, newParentId: string) {  const parent = await db.node.findUniqueOrThrow({ where: { id: newParentId } });  await db.node.update({    where: { id },    data: { parentId: newParentId, path: `${parent.path}.${id}` },  });}

UPDATE node SET path = $newParentPath || subpath(path, nlevel($oldPath) - 1)
WHERE path <@ $oldPath;

Exercise 4 — Bug hunt: click the offending line (or declare it clean)

Inserting a leaf into a closure table.

async function insertLeaf(id: string, parentId: string) {  await db.$transaction(async (tx) => {    await tx.node.create({ data: { id, parentId } });    await tx.$executeRaw`      INSERT INTO node_closure (ancestor_id, descendant_id, depth)      SELECT ancestor_id, ${id}, depth + 1        FROM node_closure WHERE descendant_id = ${parentId}      UNION ALL SELECT ${id}, ${id}, 0`;  });}

Exercise 5 — Execution: three scenarios

Pick a model and give the one sentence that decides it. Then compare.

1. An ad platform integration: campaign → ad set → ad. Millions of ads, read constantly for reporting, written by a sync job.
2. A file manager. Users nest folders arbitrarily, drag them around all day, and every page load renders a subtree.
3. A published product category taxonomy. Depth 5, 20 000 nodes, edited by three staff via an admin tool once a week, queried on every storefront request.

Retention

Fluency fades; storage strength is what survives to the design review. Two things to do:

• Tomorrow, from memory: draw the 4×5 matrix on paper. Do not open this file first. Check after.
• Next time you read any schema with a parent_id: ask which of the four operations that codebase actually performs, and whether the model matches. This is the interleaving that makes it stick.