Problem RestatementProblem
Atlassian asked: design a service to store a hierarchical tree of nodes (think Confluence pages under pages, or folders) and expose APIs to:
- Add a node under a parent.
- Return all descendants (children, grandchildren, and so on) of a node.
APIs
POST /nodes{ parent_id?, name }→{ node_id }GET /nodes/{id}/descendants?depth=&cursor=→ a list or nested treeGET /nodes/{id}/ancestorsPOST /nodes/{id}/move{ new_parent_id }DELETE /nodes/{id}?cascade=true
Deep Dive — Choosing how to store the treeDeep dive
The API has to add a node, list all descendants, and move a subtree. No single representation is good at all three, so the choice is about which operation you are willing to make slow.
Adjacency list alone
Each row stores its parent_id.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
A["Get all descendants of page 4"] --> L1["Query children of 4"]
L1 --> L2["Query children of each child"]
L2 --> L3["...once per level"]
L3 --> N["A 12-level tree = 12 round trips, fanning out"]
N --> DEEP["Deep Confluence spaces make this unusable"]Adds and moves are perfect — one row changes — and the descendants query is the one the API is built around. Without recursive CTE support it is a query per level; with one, it is still a traversal proportional to the subtree at query time.
Materialised path
Every row stores its full path, /1/4/9/. Descendants become WHERE path LIKE '/1/4/%', which an index answers in one shot.
The read problem disappears, and the write problem appears: moving a subtree rewrites the path of every node inside it. Moving a busy space with 50,000 pages is a 50,000-row update, and it must be atomic or the tree is briefly inconsistent. Paths also have a length limit, which deep trees eventually find.
Adjacency list as the truth, closure table for the queries
Keep parent_id as the source of truth and maintain a separate table of every (ancestor, descendant, depth) pair:
| Model | Get descendants | Add node | Move subtree |
|---|---|---|---|
| Adjacency list | Recursive, per level | O(1) | O(1) |
| Materialised path | Indexed prefix scan | O(1) | Rewrite the whole subtree |
| Nested sets | Very fast range scan | Renumber many rows | Very slow |
| Closure table | Simple indexed join | One row per ancestor | Rewrite pairs for the subtree |
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
ADJ["nodes(id, parent_id) - source of truth"] --> CT[("closure(ancestor, descendant, depth)")]
Q1["All descendants of 4"] --> CT
CT --> FAST["One indexed join - any depth, one query"]
Q2["All ancestors of 9 - breadcrumbs"] --> CT
ADD["Add node under 4"] --> INS["Insert one row per ancestor - depth of the tree, not its size"]
MOVE["Move subtree"] --> REW["Delete and reinsert pairs for that subtree only"]- Both directions for free. The same table answers descendants and ancestors, so breadcrumbs cost one query instead of walking parents upward.
- Adds are cheap — one row per ancestor, which is the tree's depth, typically under twenty.
- Moves are bounded by the size of the moved subtree rather than the whole path space, and the adjacency list stays authoritative, so a closure table that drifts can always be rebuilt from it.
The cost is a derived table to maintain inside the same transaction. That is the trade: extra write complexity for read queries that are a single indexed join at any depth.
Schema (adjacency + closure table)Data model
CREATE TABLE nodes (
node_id BIGINT PRIMARY KEY,
parent_id BIGINT NULL REFERENCES nodes(node_id), -- NULL = root (forest allowed)
name TEXT NOT NULL
);
CREATE TABLE node_paths ( -- every ancestor/descendant pair, including self (depth 0)
ancestor_id BIGINT NOT NULL,
descendant_id BIGINT NOT NULL,
depth INT NOT NULL,
PRIMARY KEY (ancestor_id, descendant_id)
);
CREATE INDEX ON node_paths (descendant_id);3.1 Add a node (in one transaction)
INSERT INTO nodes (node_id, parent_id, name) VALUES (:id, :parent, :name);
-- the new node is a descendant of every ancestor of its parent, plus itself
INSERT INTO node_paths (ancestor_id, descendant_id, depth)
SELECT ancestor_id, :id, depth + 1 FROM node_paths WHERE descendant_id = :parent
UNION ALL SELECT :id, :id, 0;3.2 Get all descendants
SELECT n.* , p.depth FROM node_paths p JOIN nodes n ON n.node_id = p.descendant_id
WHERE p.ancestor_id = :id AND p.depth > 0
ORDER BY p.depth, n.name;One indexed query, no recursion. To return a nested tree as JSON, fetch the rows with parent_id and build the tree in memory (O(n)).
3.3 Move a subtree
In one transaction: delete the pairs linking the subtree's nodes to their old outside ancestors, then insert pairs linking them to the new parent's ancestors (a cross join of new ancestors × subtree nodes), and update parent_id. Reject moves that would create a cycle (the new parent is inside the subtree).
Alternative Without a Closure TableTrade-offs
With only parent_id, use a recursive CTE:
WITH RECURSIVE sub AS (
SELECT node_id, parent_id, name, 1 AS depth FROM nodes WHERE parent_id = :id
UNION ALL
SELECT n.node_id, n.parent_id, n.name, s.depth + 1 FROM nodes n JOIN sub s ON n.parent_id = s.node_id
) SELECT * FROM sub;This works well for moderate trees, since each level is one indexed step (index on parent_id). Deep trees mean many steps.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
API["Hierarchy API"] --> DB[("nodes + node_paths")]
API --> C[("Cache - subtree results")]
DB -->|"change events"| INV["Invalidate cached subtrees of affected ancestors"]
INV --> CScale and Edge CasesScale
- Huge subtrees: paginate descendants (a cursor by depth, name, id), or return only a few levels at a time (
depthparameter), as file explorers do. - Caching: cache subtree results, and invalidate the caches of all ancestors when a node is added, moved or deleted (the closure table tells you exactly which).
- Delete: cascade (delete the subtree, found via the closure table) or re-parent the children, as the product decides.
Wrap-UpWrap-up
Keep parent_id for simple structure, and add a closure table of all ancestor–descendant pairs with depth, so "all descendants" and "all ancestors" are single indexed queries, adds insert one row per ancestor, and moves rewrite only the subtree's outside links (with a cycle check). Paginate or depth-limit large subtrees, and cache results with ancestor-based invalidation. A recursive CTE on parent_id is the simpler alternative for moderate trees.