Storing Tree Relationships in a Table

Relational tables are flat; trees are not. Storing hierarchical data — categories, org charts, comment threads, filesystem-like structures — in a relational database means choosing how to flatten the tree, and each of the standard flattenings buys query speed in one direction by paying for it in another. There are three classic models, and the right one depends entirely on which operations dominate: reading down, reading up, or restructuring.

Adjacency list

The obvious encoding: every row points at its parent.

CREATE TABLE tree (
    node_id   INT PRIMARY KEY,
    parent_id INT NULL REFERENCES tree (node_id)
);

Immediate children and the immediate parent are one cheap query each. The trouble starts the moment you want a whole subtree or a full ancestor chain: each level is another self-join, so query cost grows with tree depth. Modern databases soften this with recursive CTEs, which walk the tree in a single statement:

WITH RECURSIVE subtree AS (
    SELECT node_id FROM tree WHERE node_id = 42
    UNION ALL
    SELECT t.node_id
    FROM tree t JOIN subtree s ON t.parent_id = s.node_id
)
SELECT * FROM subtree;

Pros: simplest possible schema; writes are trivial — moving a node is a one-column update; referential integrity comes free from the foreign key.
Cons: deep traversals are recursive by nature, and without CTE support they degrade into N queries for N levels.

Path enumeration

Instead of storing one edge per row, store the entire path from the root:

CREATE TABLE tree (
    node_id INT PRIMARY KEY,
    path    VARCHAR(255)  -- '1.4.42' = node 42 under 4 under 1
);

Now ancestry is string manipulation. All ancestors of a node are encoded in its own row — split the path and you have them. All descendants are a prefix match:

SELECT * FROM tree
WHERE path LIKE '1.4.%';   -- everything under node 4

The cost lands on writes: moving a subtree means rewriting the path of every node inside it, and the database can't guarantee the paths stay consistent — the structure lives in a string the engine doesn't understand.

Pros: ancestor and subtree reads are fast and index-friendly; depth is just the number of separators.
Cons: moves and re-parenting rewrite many rows; no integrity enforcement; the path column imposes a depth limit you will meet eventually.

Nested sets

The clever one. Do a depth-first walk of the tree and stamp each node with a number on the way in (left_value) and on the way out (right_value). A node's descendants are exactly the nodes whose interval sits inside its own.

CREATE TABLE tree (
    node_id     INT PRIMARY KEY,
    left_value  INT,
    right_value INT
);

-- entire subtree of node 42, no recursion, no string ops
SELECT child.*
FROM tree child, tree parent
WHERE parent.node_id = 42
  AND child.left_value BETWEEN parent.left_value AND parent.right_value;

Subtree reads become pure range scans — beautiful for read-heavy trees. But the numbering is global: inserting a single node shifts the left/right values of, on average, half the table. Every structural change is a renumbering exercise.

Pros: subtree and leaf queries are fast range scans; aggregates over subtrees are easy.
Cons: inserts, deletes, and moves are expensive and fiddly; the encoding is easy to corrupt and hard to repair by hand.

Choosing

The decision reduces to your read/write mix. Mostly-static, read-heavy trees (product categories, geographies) tolerate nested sets' write pain and enjoy the fast reads. Trees that restructure constantly (drag-and-drop org charts) want the adjacency list's one-column moves, with recursive CTEs doing the traversal work. Path enumeration sits in the middle and is often the pragmatic pick when you mostly ask "give me everything under X" and rarely move things.

There's no free lunch among the three — each stores the same information and merely chooses which query gets to be an index lookup and which becomes a rewrite of half the table. Pick by profiling the questions you'll actually ask, not by elegance of the encoding.