Trees in SQL: adjacency lists, paths & closure tables

Four queries for a breadcrumb

A company's docs tool shows a breadcrumb above every document: Company › Legal › Contracts › Suppliers. The folders live in one table, folders(id, name, parent_id), and the page asks for the current folder, then its parent, then that folder's parent, until parent_id comes back null: four queries in a row, each waiting for the one before.

That table is an adjacency list: each row stores only its link to the row above, in a parent_id column that references the same table. It is good at changes: a new folder is one INSERT, and moving Contracts, with everything inside it, to Engineering is an UPDATE of one row. A foreign key on parent_id makes the database refuse a parent that does not exist.

What it is bad at is any question that spans levels. "Search only inside Legal" has to walk down, and the code cannot know in advance how far.

Walking the tree in one statement

A recursive CTE (common table expression) repeats a join until it runs out of rows. Legal and everything under it is WITH RECURSIVE sub AS (SELECT id FROM folders WHERE id = 2 UNION ALL SELECT f.id FROM folders f JOIN sub ON f.parent_id = sub.id) SELECT id FROM sub. The first SELECT is the anchor, the second the recursive step, run in rounds:

1. The anchor returns Legal (2).
2. Round 1 joins Legal against folders on parent_id and finds Contracts (3) and Policies (6).
3. Round 2 starts from Contracts and Policies and finds Suppliers (4) and Customers (5).
4. Round 3 starts from Suppliers and Customers, finds no children, and the walk stops.

Each round joins on parent_id, so that column wants an index; without one, each round reads the whole table. PostgreSQL does not create one for a foreign key, MySQL's InnoDB does. Walking up gives the breadcrumb. One statement replaces four round trips, though the database still works through the tree one level per round. PostgreSQL, MySQL 8.0 and SQLite all have WITH RECURSIVE.

A move that makes a loop

An adjacency list accepts a shape no tree can have. A user drags Legal into Suppliers, which is inside Legal. The foreign key is satisfied, and Legal is now its own ancestor, cut off from Company. The next walk down from Legal circles until something stops it: a recursion cap where the engine has one (MySQL and SQL Server do, PostgreSQL does not), or a statement timeout.

Guard both sides. The walk carries a depth with a ceiling the data never reaches and the ids visited so far, refusing a row already on the list; PostgreSQL 14 added a CYCLE clause that keeps that list for you. The write refuses a move whose target is inside the branch being moved. Two moves that are each valid alone, Contracts into Engineering and Engineering into Contracts at the same moment, can still make a loop together; that race is a Transactions & isolation levels question.

Writing the ancestry into each row

The breadcrumb runs on every page view and "only inside Contracts" on every scoped search. Both get cheaper if each row carries its ancestry. A materialized path stores it as a string: Company is /1/, Legal /1/2/, Contracts /1/2/3/, Suppliers /1/2/3/4/.

Suppliers' breadcrumb is now in its row: one WHERE id IN (1, 2, 3, 4) fetches the names, and the code puts them in the path's order, since IN returns rows in no particular order. Contracts and everything under it is a prefix match, WHERE path LIKE '/1/2/3/%', which an index can serve as one range read. Keep the trailing slash: LIKE '/1/2/3%' also matches folder 30's /1/2/30/. In PostgreSQL that index needs text_pattern_ops unless the database uses the C collation; without a usable index every search reads every path, which a query plan shows (Indexing & query optimisation). Sorted by path, each folder comes right before its contents; siblings follow id order only if the segments have a fixed width: as text, /1/10/ sorts before /1/2/, hence /0001/0002/.

Writes pay for it. Moving Contracts to Engineering rewrites the path of Contracts and of every folder below it, three rows here and 3,001 if Contracts held 3,000 folders, in one UPDATE that swaps the /1/2/ prefix for /1/7/. The path also caps the depth, because the column and an index key have size limits.

One row per ancestor

Permissions strain the path. Access is inherited downward, so "which folders can Ana see?" needs everything below each of her grants, on Contracts and Engineering: a prefix match per grant, on ids inside a string that no foreign key checks and no join on keys can use.

A closure table stores the ancestry as rows: one for each pair of a folder and one of its ancestors, the folder itself included, with the distance between them. In folder_paths(ancestor, descendant, depth), Suppliers has four: Company at depth 3, Legal at 2, Contracts at 1, itself at 0.

Each question is now a join on keys. Contracts and everything under it is WHERE ancestor = 3; Suppliers' breadcrumb is WHERE descendant = 4 ORDER BY depth DESC; Ana's folders are her grants joined to folder_paths on ancestor. A primary key on (ancestor, descendant) and an index on descendant let each one run as an index range read.

The table pays in rows: one per folder per level above it, plus its own. The seven folders above make 19 (1 + 2 + 2 + 3 + 3 + 4 + 4), and 50,000 folders at an average depth of 5 make 300,000; a chain of n folders makes n(n+1)/2. A new folder under Contracts adds 4: its own row at depth 0, and a copy of each of Contracts' 3 rows with the new folder as descendant and the depth one higher. Moving Contracts to Engineering deletes the 6 rows that tie its three folders to Legal and Company and inserts 6 that tie them to Engineering and Company; the 5 rows inside the branch stay.

Nested sets, left and right numbers from a depth-first walk, also read fast, but one insert renumbers every folder after it in the walk.

Often two of them

No encoding wins outright: the adjacency list costs the least to keep and the most to read across levels, the closure table the reverse, the path in between. Many systems combine them. parent_id, with its foreign key, stays the source of truth, and a path or closure table is derived from it in the same transaction as every insert and move, so it can be rebuilt from parent_id if it drifts. The docs tool, with rare moves and ancestry checked on every request, suits a closure table; a shallow tree queried rarely needs only the recursive CTE. Deletes need care too: with ON DELETE CASCADE on parent_id, deleting Legal silently takes its four subfolders, and with SET NULL Contracts and Policies become top-level folders nobody created; the default (NO ACTION) refuses while children exist, usually the safer start.

Threads are trees too

The Comment System Challenge asks for "threaded (nested) comments". Replies almost never move and a thread is read far more often than written, which favours parent_id plus a path of fixed-width comment ids: write that into the PostgreSQL node's title and label the API's read edge with its query, one thread ordered by path. A long thread is paged by its top-level comments, with the cursor from Pagination: offset, keyset & cursors. The brief also offers Neo4j, which a reply tree does not need; Graph databases describes the case where connections stop being a tree.

The order comes from the path. Ids from a sequence grow roughly with time, so sorting by the path puts each reply under its parent, and replies to the same comment in about the order they were posted. Sort by created_at alone and a reply to the first comment, posted an hour later, lands at the bottom of the thread, far from what it answers.