Storing a Hierarchy and Returning All Descendants

0) Problem Restatement

Atlassian asked: design a service to store a hierarchical tree of nodes (think Confluence pages under pages, or folders) and expose APIs to:

1. Add a node under a parent.
2. Return all descendants (children, grandchildren, and so on) of a node.

1) APIs

• POST /nodes { parent_id?, name } → { node_id }
• GET /nodes/{id}/descendants?depth=&cursor= → a list or nested tree
• GET /nodes/{id}/ancestors
• POST /nodes/{id}/move { new_parent_id }
• DELETE /nodes/{id}?cascade=true

2) Four Ways to Store a Tree

3) Schema (adjacency + closure table)

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).

4) Alternative Without a Closure Table

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.

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 --> C

5) Scale and Edge Cases

• Huge subtrees: paginate descendants (a cursor by depth, name, id), or return only a few levels at a time (depth parameter), 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.

6) Wrap-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.