skip to content

What is a closure table for storing hierarchical data, what rows does it contain, and what does it cost to insert or move a node?

level: middleimportance: should knowfreq 48%

answer

  1. one row per ancestor-descendant pair
  2. self-row depth 0
  3. both directions indexable
  4. insert = depth+1 rows
  5. move = ancestors × subtree rows

basics

~20 s

A closure table is a separate table holding one row for every ancestor-descendant pair, including each node paired with itself, usually with the distance between them. Any ancestor or descendant query becomes one indexed lookup. Writes cost many rows: inserting a node adds one row per ancestor, and moving a subtree rewrites all pairs crossing the moved boundary.

solid answer

~60 s

A closure table materializes the **transitive closure** of the tree in its own table: columns `ancestor_id`, `descendant_id` and typically `depth`, with the primary key on the pair. Every ancestor-descendant relationship gets a row, plus a self-row at depth 0 for each node so that "the subtree including me" is a single predicate. The payoff is reads. "All descendants of X" is `WHERE ancestor_id = X`; "all ancestors of X" is `WHERE descendant_id = X`; "is X under Y" is one index probe. No recursion, and both directions are indexable, which no single path column gives you. The cost is writes and storage. Inserting a leaf writes `depth + 1` rows (copy the new parent's ancestor rows, plus the self-row). Moving a subtree means deleting every pair that links the moved nodes to their old ancestors and inserting the cross product of new ancestors × moved nodes — O(ancestors × subtree size). Storage is O(n × average depth), not O(n). Usually the adjacency list stays as the source of truth and the closure table is derived, maintained by triggers or by the same service transaction.

code

sql · 14 lines
sql
CREATE TABLE node (
    id        BIGINT PRIMARY KEY,
    parent_id BIGINT NULL REFERENCES node(id),
    name      VARCHAR(200) NOT NULL
);

CREATE TABLE node_closure (
    ancestor_id   BIGINT NOT NULL REFERENCES node(id),
    descendant_id BIGINT NOT NULL REFERENCES node(id),
    depth         INT    NOT NULL,
    PRIMARY KEY (ancestor_id, descendant_id)
);

CREATE INDEX idx_closure_desc ON node_closure(descendant_id, ancestor_id);

go deeper

for a junior

Know the shape — a pairs table with ancestor, descendant and depth — and that it makes subtree and ancestor queries a single indexed lookup.

for a middle

Be able to write the insert statement, state the row counts for insert and move, and explain why both directions are indexable unlike a path column.

for a senior

Discuss maintenance strategy (triggers vs service transaction vs rebuild), lock footprint of large subtree moves, and the degenerate-depth storage blowup.

for a principal

Position it as one point on a read/write cost curve, justify it from measured access patterns, and cover derivation from a single source of truth plus a reconciliation strategy.

## The idea A tree stored as parent pointers records only direct edges; every question about *indirect* relationships needs traversal. A **closure table** removes traversal by storing the answers ahead of time. It is a second table whose rows are pairs: for every node A and every node B that is a descendant of A (at any distance), there is a row `(ancestor_id = A, descendant_id = B, depth = distance)`. By convention every node also has a self-row `(X, X, 0)`. So a three-level chain root → mid → leaf produces nine rows: three self-rows at depth 0, root→mid and mid→leaf at depth 1, and root→leaf at depth 2 — and that is the whole point: `root→leaf` is stored explicitly, so answering "is leaf under root" costs one index probe instead of two joins. The primary key is `(ancestor_id, descendant_id)`, and a second index on `(descendant_id, ancestor_id)` makes upward queries equally fast. That symmetry is the closure table's distinguishing advantage: a materialized path column can answer "descendants of X" with a prefix `LIKE`, but "ancestors of X" requires string surgery or a separate structure, whereas a closure table indexes both directions natively. ## Reads - Whole subtree: `SELECT n.* FROM node n JOIN closure c ON n.id = c.descendant_id WHERE c.ancestor_id = :x` - Ancestor path: swap the columns, and `ORDER BY depth DESC` to get root-first. - Direct children only: add `AND depth = 1`. - Containment test: `EXISTS (SELECT 1 FROM closure WHERE ancestor_id = :y AND descendant_id = :x)`. - Leaves under X: descendants of X that appear as an ancestor only in their own self-row. All of these are plain joins with index access and no recursion, which also means the optimizer can cost them normally and combine them with other predicates — a recursive CTE is much more opaque to a planner and often materializes the whole traversal before filtering. ## Writes, in detail **Insert a new node N under parent P.** The correct row set is: every ancestor row of P, re-pointed at N with depth incremented, plus N's self-row. As one statement: ``` INSERT INTO closure(ancestor_id, descendant_id, depth) SELECT ancestor_id, :n, depth + 1 FROM closure WHERE descendant_id = :p UNION ALL SELECT :n, :n, 0; ``` That writes depth(P) + 2 rows. For a shallow tree this is trivial; for a deep one it is still bounded by depth, not by table size. **Delete a subtree rooted at S.** Delete every closure row whose descendant is in S's descendant set: one nested query, and the pairs disappear along with the nodes. **Move subtree S under a new parent P.** This is the expensive operation and the one interviewers probe. Two steps: (1) delete every row linking a node *outside* the subtree to a node *inside* it — those are the stale ancestor links; (2) insert the cross product of P's ancestor rows (including P itself) with S's descendant rows, with depth summed. If S has *d* descendants and P has *a* ancestors, the move writes roughly *a × d* rows. Moving a large subtree near the root of a deep tree is genuinely costly, and doing it under a transaction holds locks on all those rows — worth knowing before you promise a drag-and-drop category editor. ## Storage Row count is the sum over all nodes of (depth + 1). For a balanced tree of *n* nodes and depth *log n* that is O(n log n); for a degenerate chain of depth *n* it is O(n²), which is the pathological case — a comment thread that becomes a 10 000-deep reply chain will blow up a closure table. Bound your depth, or reconsider the structure. ## Keeping it consistent The closure table is derived data, so it can drift. Options: maintain it in triggers on the node table (consistent by construction, invisible to callers, harder to debug); maintain it in the service layer inside the same transaction (explicit, but every write path must remember); or rebuild it periodically from the adjacency list (simplest, but tolerates windows of staleness). Whichever you pick, keep the adjacency list — `parent_id` — as the source of truth, because it is the smallest correct representation and lets you regenerate the closure at any time. A reconciliation job that recomputes the closure and diffs it against the stored one is a cheap safety net. ## When to choose it Choose a closure table when reads dominate and both directions matter — permission inheritance ("does this user's group sit under any group granted X?"), org charts with frequent "everyone under this manager" reports, category trees rendered on every page. Avoid it when the tree is churned constantly by subtree moves, when depth is unbounded, or when a materialized path would do because you only ever ask downward questions and can accept string-prefix matching. And avoid it entirely if a recursive CTE over an indexed adjacency list already meets your latency budget — the closure table is an optimization with real maintenance cost, not a default.

  • Why does a closure table include a row where a node is its own ancestor at depth 0?
    It makes "the subtree including the root itself" a single uniform predicate rather than a query plus a union with the node row. It also makes the insert rule uniform: copying the parent's ancestor rows works because the parent's self-row supplies the direct parent-child edge. Without self-rows, every containment query needs an extra OR branch and the insert needs a special case.
  • How would you keep the closure table from drifting out of sync with the parent_id column?
    Make every structural write go through one place — either database triggers on insert, delete and parent update, or a single service method that writes both tables inside the same transaction. Triggers are stronger because they cannot be bypassed by ad-hoc SQL or a second application. Either way, keep the adjacency list as the source of truth so the closure can be rebuilt from scratch, and run a periodic reconciliation job that recomputes it and reports differences.

The adjacency list is a chain of "who's my boss" notes; the closure table is the full org directory listing every person under every manager, precomputed — instant to look up, but the whole directory section gets reprinted when a department is reorganized.

saying these in an interview costs you the question

  • Thinking the closure table replaces parent_id rather than deriving from it
  • Claiming a move is cheap because "you just update the closure rows"
  • Storing only ancestor and descendant without depth, then being unable to get direct children or order the ancestor path
  • Ignoring the O(n × depth) storage blowup in deep or unbounded trees
  • Maintaining the closure in application code on only some write paths

context

resolving links…