How to store a tree in SQL: adjacency list, materialized path, ltree or closure table

Store a tree as a parent_id column that references the same table, and read it with a recursive query. That is the adjacency list, and it is the right default for categories, folders, org charts and comment threads. Add a second structure only when a measured read is too slow: a materialized path (or PostgreSQL's ltree) when you render whole subtrees in order and nodes rarely move, a closure table when you query ancestors and descendants constantly and nodes do move. Skip nested sets.

We checked this against the 100 schemas in the drawDB schema gallery. They contain 39 real trees in 30 schemas, and every one of them is an adjacency list. Only one, the Reddit comment tree, adds a materialized path on top. None uses a closure table, nested sets or ltree. The interesting failures are elsewhere: 23 of the 37 parent columns outside MySQL have no index, 16 category-style trees delete with SET NULL, and not one schema stops a node from being moved under its own descendant.

What does a tree look like in the gallery?

We counted every foreign key that points back at its own table. There are 77 of them across 50 schemas, but only half are trees:

• 24 containment hierarchies in 19 schemas: categories, folders, org charts, sales territories, Notion pages and blocks, nested filter groups.
• 15 reply threads in 14 schemas: comments, Slack thread replies, GitHub review comments, Twitter replies.
• 38 other self-references, which are links rather than trees: a fork's upstream repository, a reposted post, a reversing ledger entry, a renewed lease, a quoted message. Each row points at one other row, and nobody walks the chain to arbitrary depth.

Most of the trees are shallow on purpose. Five of the 15 comment threads (Instagram, YouTube, Facebook, TikTok and Notion's comments) are capped at two levels: a reply to a reply attaches to the same top-level comment. That is a product decision, and the YouTube schema states the payoff in its own notes: a thread page becomes two indexed reads instead of a recursive walk. If your product can live with two levels, you don't need any of the techniques below.

How do you store a tree with an adjacency list?

One nullable self-referencing column, plus three constraints most implementations skip:

CREATE TABLE "categories" (
  "id" BIGINT GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,
  "parent_id" BIGINT REFERENCES "categories" ("id") ON DELETE RESTRICT,
  "name" VARCHAR(120) NOT NULL,
  CONSTRAINT "chk_categories_not_own_parent" CHECK ("parent_id" <> "id"),
  CONSTRAINT "uq_categories_sibling_name" UNIQUE NULLS NOT DISTINCT ("parent_id", "name")
);

• parent_id is nullable. NULL marks a root. All 77 self-references in the gallery are nullable, because the first row of any tree has nothing to point at.
• The unique constraint does double duty. It keeps sibling names unique, which is exactly the rule a filesystem enforces, and because it leads with parent_id its index also serves the foreign key. No separate index on parent_id is needed.
• NULLS NOT DISTINCT covers the roots. Without it, two top-level categories called "Books" are allowed, because SQL treats every NULL as distinct from every other. The clause is new in PostgreSQL 15. On older versions, or in MySQL, add a partial unique index on name where parent_id IS NULL; the soft delete post covers the same NULL trap per database.
• The CHECK blocks the one-node cycle: a category cannot be its own parent. Longer cycles need a trigger, shown further down.

The Dropbox schema uses this exact shape for its folder tree, with a composite unique index on (parent_id, name):

Productivity

Dropbox-style file storage & sync database schema

How a cloud drive models its data: a folder tree, versioned files, content-addressed blocks that deduplicate identical uploads to a single copy, shares and expiring public links, per-device sync cursors, trash retention and quota accounting.

How do you query a tree with a recursive CTE?

Start from a node and join children onto the rows found so far. In PostgreSQL 14 and later, add the CYCLE clause so a corrupt row can't send the query into an endless loop:

WITH RECURSIVE subtree AS (
  SELECT id, parent_id, name, 0 AS depth
  FROM categories
  WHERE id = 1
  UNION ALL
  SELECT c.id, c.parent_id, c.name, s.depth + 1
  FROM categories c
  JOIN subtree s ON c.parent_id = s.id
)
CYCLE id SET is_cycle USING visited
SELECT repeat('  ', depth) || name AS outline
FROM subtree
WHERE NOT is_cycle
ORDER BY visited;

visited is the array of ids on the way down, so ordering by it returns the tree depth-first, each child directly under its parent. The PostgreSQL docs recommend exactly this over adding a separate SEARCH DEPTH FIRST clause, which would compute the same path twice.

Walking up instead of down gives you a breadcrumb:

WITH RECURSIVE crumbs AS (
  SELECT id, parent_id, name, 0 AS up
  FROM categories
  WHERE id = 3
  UNION ALL
  SELECT c.id, c.parent_id, c.name, b.up + 1
  FROM categories c
  JOIN crumbs b ON c.id = b.parent_id
)
SELECT string_agg(name, ' > ' ORDER BY up DESC) AS breadcrumb
FROM crumbs;

That returns Electronics > Audio > Headphones. Every step of the walk down is a lookup by parent_id, which is why that column needs an index; every step up is a primary key lookup and is already fast.

The same query works almost everywhere, with different safety limits. MySQL has supported WITH RECURSIVE since 8.0 and aborts after 1,000 iterations by default. SQL Server drops the RECURSIVE keyword and stops at 100 levels unless you add OPTION (MAXRECURSION n). PostgreSQL has no limit at all, which is why the CYCLE clause matters there. A real category tree is rarely ten levels deep, so hitting any of these limits almost always means the data has a cycle.

Do you need an index on parent_id?

Yes, and this is the most common gap in the gallery. Of the 37 tree columns outside MySQL, 23 are not the leading column of any index: 17 of the 24 containment hierarchies and 6 of the 15 comment threads. MySQL is excluded because InnoDB creates the index automatically. PostgreSQL, SQLite and SQL Server don't.

Without the index, every level of a recursive walk down is a sequential scan of the whole table, and so is every delete of a parent, since the database must look for children before it can cascade or refuse. The best practices audit found the same gap across all 2,061 foreign keys in the gallery; self-references just make it worse, because the scan repeats once per level. If your tree has no unique constraint that leads with parent_id, add the index:

CREATE INDEX "idx_categories_parent" ON "categories" ("parent_id");

What should happen when you delete a parent?

Decide per tree, because the three options mean very different things:

• CASCADE deletes the subtree. Right when children are part of the parent: replies under a deleted comment, blocks inside a deleted page, files in a deleted folder. 11 of the 15 comment threads and 6 of the 24 hierarchies do this.
• RESTRICT refuses. Right for taxonomies, where children are independent records that someone has to re-home first: departments, sales regions, product categories. Only 2 hierarchies in the gallery do this, the SQL Server department tree in HR & payroll and the geographic areas in property listings.
• SET NULL promotes the children to roots. 16 of the 24 hierarchies use it, and for most of them it is the wrong choice. Deleting "Audio" would make "Headphones" and "Speakers" top-level categories that appear in the main navigation, with nobody having decided that.

We'd change most of those 16 to RESTRICT. SET NULL is the right rule for the 38 link-style references, where a deleted original should leave the repost or the renewed lease standing, not for a hierarchy.

How do you stop a node from being moved under its own descendant?

With a trigger. A foreign key can't see more than one level, so nothing in the schema stops you from setting Electronics' parent to Headphones, after which both nodes vanish from every query that starts at a root. Not one of the 39 trees in the gallery guards against this; most applications check it in the UI and hope. The database can check it on every move:

CREATE FUNCTION categories_reject_cycle() RETURNS trigger
LANGUAGE plpgsql AS $$
BEGIN
  IF NEW.parent_id IS NOT NULL AND EXISTS (
    WITH RECURSIVE ancestors AS (
      SELECT id, parent_id FROM categories WHERE id = NEW.parent_id
      UNION ALL
      SELECT c.id, c.parent_id
      FROM categories c
      JOIN ancestors a ON c.id = a.parent_id
    )
    SELECT 1 FROM ancestors WHERE id = NEW.id
  ) THEN
    RAISE EXCEPTION 'category % cannot move under its own descendant %', NEW.id, NEW.parent_id;
  END IF;
  RETURN NEW;
END $$;

CREATE TRIGGER "trg_categories_reject_cycle"
  BEFORE UPDATE OF "parent_id" ON "categories"
  FOR EACH ROW EXECUTE FUNCTION categories_reject_cycle();

The trigger walks up from the new parent and fails if it meets the node being moved. It costs one primary key lookup per level, so it's cheap on any realistic tree. One caveat: two concurrent moves can each pass the check against the old tree and together form a cycle. If users can drag nodes around at the same time, serialize moves, for example with pg_advisory_xact_lock on the tree's owner id at the start of the transaction.

When should you use a materialized path?

When you read whole subtrees in display order far more often than you move nodes. The Reddit schema is the gallery's one example. Each comment keeps its parent_comment_id and also stores path, the zero-padded ids of all its ancestors joined with dots, plus depth:

CREATE TABLE "comments" (
  "id" BIGINT GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,
  "post_id" BIGINT NOT NULL,
  "parent_comment_id" BIGINT REFERENCES "comments" ("id") ON DELETE CASCADE,
  "path" VARCHAR(512) COLLATE "C" NOT NULL,
  "depth" SMALLINT NOT NULL DEFAULT 0,
  "body" TEXT NOT NULL
);

CREATE INDEX "idx_comments_post_path" ON "comments" ("post_id", "path");
CREATE INDEX "idx_comments_parent" ON "comments" ("parent_comment_id");

Rendering a thread is now WHERE post_id = $1 ORDER BY path, a single index scan that comes back already in reading order, and a subtree is a prefix match:

SELECT id, depth, body
FROM comments
WHERE post_id = 1
  AND path LIKE '0000000012.0000000087%'
ORDER BY path;

Three details make this work. The padding must be fixed-width and wide enough for your largest id, or '9' sorts after '10'. The column uses the C collation, because PostgreSQL can only use a B-tree index for a LIKE prefix match under the C locale or with a pattern operator class. And the parent pointer stays, because writing a reply only ever needs the parent: read the parent's path, append your own id.

The cost is moves. Moving a node means rewriting the path of every descendant. Comments never move, which is exactly why Reddit can afford it.

Social

Reddit database schema

How a forum models its data: subreddits and subscriptions, link and text posts, arbitrarily deep comment trees stored as materialised paths, narrow vote tables, karma, flairs, and an append-only moderation log with removal reasons.

Should you use ltree in PostgreSQL?

If you are on PostgreSQL and want a path, yes: ltree is a materialized path with a real type, operators and GiST indexing, so you don't hand-roll padding and collation.

CREATE EXTENSION IF NOT EXISTS ltree;

CREATE TABLE "regions" (
  "id" BIGINT GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,
  "name" VARCHAR(120) NOT NULL,
  "path" LTREE NOT NULL UNIQUE
);

CREATE INDEX "idx_regions_path" ON "regions" USING GIST ("path");

<@ means "is a descendant of" and @> means "is an ancestor of", both served by the GiST index:

SELECT name, nlevel(path) - 1 AS depth
FROM regions
WHERE path <@ '1.4'
ORDER BY path;

Use ids as labels, not names, so renaming a node changes one row instead of its whole subtree. A move is still a subtree rewrite, but now it's one statement. This moves node 4 and everything under it beneath node 9:

UPDATE regions
SET path = '1.9' || subpath(path, nlevel('1.4') - 1)
WHERE path <@ '1.4';

What you give up is portability: no other database has ltree, so the design doesn't carry over to MySQL, SQL Server or SQLite. Cybertec's comparison is a good read on where it beats WITH RECURSIVE and where it doesn't.

When is a closure table worth it?

When you constantly ask "everything above this node" or "everything below it", nodes do move, and you need it to work in every database. A closure table stores one row for every ancestor-descendant pair, including each node paired with itself at depth 0:

CREATE TABLE "category_paths" (
  "ancestor_id" BIGINT NOT NULL REFERENCES "categories" ("id") ON DELETE CASCADE,
  "descendant_id" BIGINT NOT NULL REFERENCES "categories" ("id") ON DELETE CASCADE,
  "depth" INTEGER NOT NULL CHECK ("depth" >= 0),
  PRIMARY KEY ("ancestor_id", "descendant_id")
);

CREATE INDEX "idx_category_paths_descendant" ON "category_paths" ("descendant_id");

Reading a subtree is a plain join with no recursion. Adding a node copies its parent's ancestor rows and adds the self row:

INSERT INTO category_paths (ancestor_id, descendant_id, depth)
SELECT ancestor_id, 12, depth + 1
FROM category_paths
WHERE descendant_id = 6
UNION ALL
SELECT 12, 12, 0;

Moving a subtree is two statements: delete the rows that connect the subtree to its old ancestors, then insert the cross product of the new parent's ancestors and the subtree's descendants. Moving node 5 under node 7:

DELETE FROM category_paths p
USING category_paths sub, category_paths sup
WHERE sub.ancestor_id = 5
  AND sup.descendant_id = 5
  AND sup.ancestor_id <> 5
  AND p.descendant_id = sub.descendant_id
  AND p.ancestor_id = sup.ancestor_id;

INSERT INTO category_paths (ancestor_id, descendant_id, depth)
SELECT sup.ancestor_id, sub.descendant_id, sup.depth + sub.depth + 1
FROM category_paths sup
CROSS JOIN category_paths sub
WHERE sup.descendant_id = 7
  AND sub.ancestor_id = 5;

Keep parent_id on the node table and run those statements in the same transaction that changes it. The closure table is a derived index of the tree, and like any cache it drifts as soon as one code path forgets to update it. Its size also grows with depth: a balanced tree of a million nodes, ten levels deep, holds around ten million path rows. That is why we'd reach for it last, after an index on parent_id and, on PostgreSQL, ltree.

What about nested sets?

Each node stores a lft and rgt number, and a subtree is every node whose numbers fall between its parent's. Reads are one range scan. Writes are the problem: inserting a single leaf shifts the numbers of every node to its right, so a write touches a large share of the table and blocks every other writer. Nested sets made sense before databases had recursive queries. MySQL got WITH RECURSIVE in 8.0, and none of the 100 gallery schemas uses nested sets.

Model it before you build it

Notion's schema has more trees than any other in the gallery: pages nest inside pages, blocks inside blocks, filter groups inside filter groups, and comments under an opening comment. All four are adjacency lists with CASCADE, because a deleted page takes its contents with it.

Productivity

Notion workspace database schema

How a docs-and-databases workspace models its data: nested pages, a document stored as an ordered block tree, user-defined databases whose rows are pages, views with filters and sorts, inherited permissions and block-anchored comments.

Open any of these schemas in the drawDB editor, add the CHECK, the index and the RESTRICT rule to your own tree, and export the DDL for your database. Every schema in the gallery is public domain, so fork whichever tree is closest to yours.

Frequently asked questions