Hierarchical Data Storage: Design Patterns for Processing

Google publishes the taxonomy it expects merchants to classify products against as a plain text file, one category per line, each written out as its full path. The header reads, verbatim, # Google_Product_Taxonomy_Version: 2021-09-21. Under it sit lines like 3 - Animals & Pet Supplies > Pet Supplies > Bird Supplies. That is a materialized path, distributed as a flat file, by the company with the best graph infrastructure on earth, and the version string has not moved in five years.

You meet the same shape everywhere once you start collecting data from the web. A shop menu nests five levels deep. A comment thread branches into replies of replies. A crawl produces a site map that is a tree of URLs by definition, and the sitemaps protocol caps a single file at 50,000 URLs and 52,428,800 bytes, with an index file able to list 50,000 more of them. Breadcrumb trails are common enough that schema.org reports BreadcrumbList in use on more than 10 million domains, counted from Google's own web index.

Then you try to persist any of it and the awkward question arrives: how do you store a tree in tables that only know rows and columns?

There are four well-worn answers, and the trade-offs between them shifted more between 2017 and 2026 than in the twenty years before. What follows walks through all four with runnable SQL, then measures them against each other on one 100,000-node tree so the trade-offs stop being adjectives. Every claim about a product, version or limit was re-checked against that vendor's own documentation on 10 August 2026. Schema examples are MySQL 8.4 dialect unless marked otherwise; every timing was taken on PostgreSQL 16.13.

The three questions a tree has to answer

Comparisons of these patterns almost always rank them on one operation: read a whole subtree. That is the operation the patterns were invented for. It is rarely the one your application runs most.

A rendered category menu asks for the direct children of the node you are standing on. A breadcrumb asks for the ancestors of one node, in order, and nothing else. An export or a sitemap build asks for the whole subtree. A re-crawl asks to insert a leaf, and occasionally to move a branch. That is five questions. No pattern is good at all five, and the pattern that wins the subtree race can lose the children race by four orders of magnitude.

Direct children is the query that decides most real designs, and the one comparison tables skip. On the tree measured below an adjacency list answers it in 0.03 ms, while a textbook nested set takes 393 ms for the same nine rows. Nothing about storage size or the elegance of the model tells you that in advance.

So before picking a row out of the table below, count your queries. Not your data.

The four patterns at a glance

Every relational approach to trees is a variation on one idea: encode each node's position in the hierarchy so a query can reconstruct parent-child relationships. The four classic patterns differ in what they encode.

The percentages are measured, not estimated, and the measurement is further down. Keep the Direct children column in view: it is the one that moves people off nested sets once they have shipped something.

We will use the same running example throughout: a product category tree for an online shop, the kind of structure you routinely extract when you scrape a product catalog. Root is Electronics; under it sit Televisions and Portable Electronics; under those, individual product types.

Adjacency list

The adjacency list is the simplest and most intuitive model: every row stores a pointer to its parent.

CREATE TABLE category (
  id        INT UNSIGNED NOT NULL AUTO_INCREMENT,
  name      VARCHAR(100) NOT NULL,
  parent_id INT UNSIGNED DEFAULT NULL,
  PRIMARY KEY (id),
  KEY (parent_id),
  FOREIGN KEY (parent_id) REFERENCES category (id)
    ON DELETE CASCADE ON UPDATE CASCADE
);

INSERT INTO category (name, parent_id) VALUES
  ('Electronics',        NULL),  -- id 1 (root: no parent)
  ('Televisions',        1),     -- id 2
  ('Portable Electronics', 1),   -- id 3
  ('LCD',                2),      -- id 4
  ('OLED',               2),      -- id 5
  ('MP3 Players',        3),      -- id 6
  ('Headphones',         3);      -- id 7

The foreign key on parent_id gives you real referential integrity. A node with no children is a leaf; a node with no parent is the root; everything above a node is its ancestors, everything below its descendants. The explicit index on parent_id is not decorative: without it, every "children of X" query is a full scan, and that is the query you run most.

Simple operations are trivial:

-- Direct children of "Televisions"
SELECT id, name FROM category WHERE parent_id = 2;

-- All leaf nodes (no children point back to them)
SELECT c.id, c.name FROM category c
LEFT JOIN category child ON child.parent_id = c.id
WHERE child.id IS NULL;

ON DELETE CASCADE on a self-reference does what you hope, with one trap. Deleting a root removes the whole subtree; a chain of 5,000 self-referencing rows in PostgreSQL 16 vanished entirely when the root was deleted in a single statement. The trap is on the MySQL side and it is documented in one sentence: "Cascaded foreign key actions do not activate triggers." If you maintain a derived structure such as a closure table with triggers, a cascaded delete silently leaves it stale. Nothing errors. The rows just stop meaning anything.

The historical weakness of the adjacency list was fetching a whole subtree of unknown depth. You either self-joined once per level, fine for three or four fixed levels and useless beyond that, or looped in application code with one query per level.

What changed: recursive CTEs

This is the single biggest reason the old advice is out of date. Every mainstream database now supports recursive common table expressions. MySQL added them in 8.0.1, announced on 10 April 2017 with the line "MySQL now supports common table expressions, both nonrecursive and recursive." SQLite added the WITH clause in 3.8.3 on 3 February 2014. PostgreSQL, SQL Server, Oracle, MariaDB and DuckDB all have them. A recursive CTE walks the tree in one statement, to any depth:

WITH RECURSIVE subtree AS (
    SELECT id, name, parent_id, 0 AS depth
    FROM category
    WHERE id = 1                      -- start at the root you want

    UNION ALL

    SELECT c.id, c.name, c.parent_id, s.depth + 1
    FROM category c
    JOIN subtree s ON c.parent_id = s.id
)
SELECT * FROM subtree ORDER BY depth;

The depth column lets you indent the output into a readable tree, and it is worth keeping in the result rather than recomputing it.

This breaks when the data has a cycle. One row whose parent_id points at its own descendant turns that query into an infinite loop. A three-row cycle in PostgreSQL 16 ran until the statement timeout cancelled it at three seconds; left alone it would have run until the disk filled. Cycles are not exotic in scraped data. They arrive from bulk imports where a category was re-parented under one of its own children between two crawls, and they arrive from sites that link a breadcrumb back on itself.

Each engine hands you a different guard rail, and they are not interchangeable:

Two of those defaults bite in opposite directions. SQL Server stops at 100 levels and reports an error, which reads like a bug in your data when it is a bug in your default. PostgreSQL has no ceiling at all, which is why the CYCLE clause, added in PostgreSQL 14 on 30 September 2021, is the one to reach for. It flags the repeat and stops:

WITH RECURSIVE t AS (
    SELECT id, parent_id FROM category WHERE id = 1
    UNION ALL
    SELECT c.id, c.parent_id FROM category c JOIN t ON c.parent_id = t.id
) CYCLE id SET is_cycle USING path
SELECT id, parent_id, is_cycle FROM t;

With recursive CTEs available, the adjacency list is the sensible default for most workloads. It is the easiest to write, it is the only single-table pattern with real referential integrity, its writes are one row, and it answers "children of X" faster than anything else on the list. Reach for something else after you have measured a read problem, not before.

Materialized path

The materialized path, also called path enumeration, stores each node's full lineage as a string, usually slash-delimited: /1/3/6/.

CREATE TABLE comment (
  id      INT NOT NULL AUTO_INCREMENT,
  body    VARCHAR(500) NOT NULL,
  path    VARCHAR(255) NOT NULL,
  PRIMARY KEY (id),
  KEY (path)
);

Comment threads are the canonical use case, so switch examples for a moment. To read an entire thread under comment 1, you match a prefix:

SELECT * FROM comment WHERE path LIKE '/1/%' ORDER BY path;

Deleting a subtree is just as clean:

DELETE FROM comment WHERE path LIKE '/1/3/%';

The index that is not there

Here is where most write-ups on this pattern, including the earlier version of this article, quietly get it wrong. The claim is that a left-anchored LIKE can use an index, so the prefix read is cheap. In PostgreSQL, with a default index on a text column, it cannot.

On the 100,000-node tree, WHERE path LIKE '/1/2/36/%' with a plain B-tree index produced a sequential scan and took 21.3 ms. The reason is in PostgreSQL's own documentation: the text_pattern_ops family compares "strictly character by character rather than according to the locale-specific collation rules," which makes it suitable "for use by queries involving pattern matching expressions (LIKE or POSIX regular expressions) when the database does not use the standard 'C' locale." Rebuild the index and the same query becomes an index scan at 0.73 ms:

CREATE INDEX mpath_path_pattern ON mpath (path text_pattern_ops);

Twenty-nine times faster, from one operator class nobody mentions. If your database is in the C locale you do not need it, and if you are on MySQL the collation rules differ again. The point is that "the prefix is indexable" is a claim about your collation, not about the pattern.

Depth has a hard ceiling and it is a byte count, not a level count. InnoDB caps an index key at 3072 bytes on DYNAMIC or COMPRESSED row format and 767 bytes on COMPACT or REDUNDANT. With utf8mb4 at four bytes per character that is 768 characters in the best case and 191 in the worst. A VARCHAR(255) path of numeric ids runs out at roughly thirty levels of a wide tree, and it runs out silently: the insert succeeds, the string is truncated or rejected depending on your SQL mode, and the subtree quietly detaches.

The other cost is structural. Paths are denormalized strings, so nothing enforces that they point at real ancestors, and moving a branch rewrites the path of every descendant.

What changed: native path types

Rather than hand-rolling slash strings, use a purpose-built type.

PostgreSQL ltree is a first-class labelled-path type with GiST indexes and operators including @> (is-ancestor-of-or-equal), <@ (is-descendant-of-or-equal), and ~ for lquery pattern matching. Its documented limits are generous: "The length of a label path cannot exceed 65535 labels" and "Labels must be no more than 1000 characters long." It is a contrib extension, so CREATE EXTENSION ltree is required, and it is available on managed platforms; Cloud SQL for PostgreSQL ships version 1.2 on PostgreSQL 13 through 16 and 1.3 on 17. In the measurements below ltree beat the string version on subtree and level queries and lost to it on ancestor lookups, and it cost the most storage of any single-table model: 27 MB against 14 MB for the text path, because the GiST index is large.

SQL Server hierarchyid is a materialized path in binary, and Microsoft's own numbers are worth quoting because they are the best argument for the pattern: "A node in an organizational hierarchy of 100,000 people with an average fanout of six levels takes about 38 bits. This is rounded up to 40 bits, or 5 bytes, for storage." Comparison is in depth-first order, so subtree reads are range reads. The documentation is equally direct about what you do not get: "Hierarchical relationships represented by hierarchyid values aren't enforced like a foreign key relationship," and moving a node "affects n rows, where n is number of nodes in the subtree being moved." It is a path, with a path's write cost, in five bytes.

Document stores model path arrays natively. MongoDB documents five tree patterns: parent references, child references, an array of ancestors, materialized paths, and nested sets, the last described as one that "optimizes discovering subtrees at the expense of tree mutability." The MySQL equivalent of the ancestors array is a JSON column with a multi-valued index, tested by Oracle "to permit as many as 1604 integer keys per record."

Nested set

The nested set model numbers nodes with a left and right value by walking the tree depth-first: an incrementing counter on the way down (lft) and again on the way back up (rgt).

CREATE TABLE tree (
  id     INT NOT NULL AUTO_INCREMENT,
  name   VARCHAR(100) NOT NULL,
  lft    INT NOT NULL,
  rgt    INT NOT NULL,
  PRIMARY KEY (id),
  KEY (lft),
  KEY (rgt)
);

A node's descendants are exactly the rows whose lft/rgt fall inside its own range, so a whole subtree comes back with no joins and no recursion:

-- Everything under the node with lft = 2, rgt = 15
SELECT * FROM tree WHERE lft BETWEEN 2 AND 15;

A correction to the earlier version of this article. It offered a second form of that query as "descendants, relative to a parent row":

SELECT child.* FROM tree parent
JOIN tree child ON child.lft BETWEEN parent.lft AND parent.rgt
WHERE parent.id = 3;

That returns the parent as well, because parent.lft is trivially between parent.lft and parent.rgt. Run against the measured tree it returned 2,013 rows where the true descendant count is 2,012. One row of drift is exactly the kind of error that survives review and then shows up as a category counted twice in a report. The fix is child.lft > parent.lft AND child.rgt < parent.rgt.

Subtree reads really are the fastest of the five models: 0.23 ms for 2,013 ids, payload in the same row, no join. Two things spoil the story.

There is no direct answer for "the children of X." The range gives you every descendant at every depth. Getting only the first level, with nothing extra stored, means an anti-join against the same range, and it cost 393 ms against 0.03 ms for an adjacency list. The standard fix is to denormalize a depth column into each row, which brings it to 0.13 ms and leaves you maintaining a third derived value beside lft and rgt.

Writes renumber the table. Inserting one leaf under a mid-level node updated 87,093 rows in one statement and 87,090 in the next: 174,183 row updates for a single new category, taking 6.2 to 10.4 seconds. That is the median case, not a pathological one: everything numbered to the right of the insertion point shifts by two, and for a node encountered early in the depth-first walk that is most of the table.

The model also has a structural limit that surprises people mid-project. TypeORM's documentation puts it plainly: "You cannot have multiple roots in the nested set." One numbering scheme, one root. A catalogue merged from three sources has three roots, and you will be inventing a synthetic super-root to hold them.

In 2026, nested sets are a niche pick: trees that are read constantly, almost never change, and are queried by whole subtree rather than by level. A published navigation menu qualifies. A catalogue you re-crawl nightly does not.

Closure table

The closure table stores the tree's relationships explicitly, in a second table. The main table holds the nodes; a separate table holds every ancestor-descendant pair, including each node's zero-distance relationship with itself.

CREATE TABLE node (
  id   INT NOT NULL AUTO_INCREMENT,
  name VARCHAR(100) NOT NULL,
  PRIMARY KEY (id)
);

CREATE TABLE closure (
  ancestor_id   INT NOT NULL,
  descendant_id INT NOT NULL,
  depth         INT NOT NULL,        -- 0 = self, 1 = child, 2 = grandchild ...
  PRIMARY KEY (ancestor_id, descendant_id),
  KEY (descendant_id),
  FOREIGN KEY (ancestor_id)   REFERENCES node(id),
  FOREIGN KEY (descendant_id) REFERENCES node(id)
);

For a node with id 3, you insert (3,3,0) plus one row per ancestor. Reading any subtree is then a plain join, and the depth column answers the question the nested set cannot:

-- Node 3 and its entire subtree
SELECT n.* FROM node n
JOIN closure c ON n.id = c.descendant_id
WHERE c.ancestor_id = 3;

-- Direct children only
SELECT n.* FROM node n
JOIN closure c ON n.id = c.descendant_id
WHERE c.ancestor_id = 3 AND c.depth = 1;

-- Ancestors, root first
SELECT n.* FROM node n
JOIN closure c ON n.id = c.ancestor_id
WHERE c.descendant_id = 3 ORDER BY c.depth DESC;

The storage cost is predictable, which makes it budgetable. A node at depth d contributes d+1 rows, so the closure table holds n × (1 + average depth) rows. The measured tree has 100,000 nodes at an average depth of 5.69 and produced exactly 669,304 closure rows, 6.69 per node. Total on disk was 54 MB for the closure table plus 6.6 MB for the node table, against 8.7 MB for the same tree as an adjacency list. Seven times the storage, and you can compute the multiplier before you build anything.

The shape that ruins it is a chain: a comment thread of 5,000 messages nested 5,000 deep produces 12,502,500 closure rows, because growth is quadratic in depth. Wide and shallow is cheap. Narrow and deep is not.

Moving a branch is the expensive write. Re-parenting a 2,013-node subtree meant deleting 4,026 pairs and inserting 4,026 new ones, 385 ms and 467 ms across two runs. The count is the product of the subtree size and the number of ancestors that change, which is why moving a node near the root of a deep tree is much worse than moving a leaf.

Bookkeeping is the other price. The pairs must be maintained on every write, usually by triggers or an ORM, and this is where the MySQL trigger rule from earlier turns into a live bug: a cascaded delete on the node table does not fire the trigger that would have cleaned the closure rows. Maintain both tables in one transaction in application code, or drop ON DELETE CASCADE and delete explicitly.

Bill Karwin's SQL Antipatterns, Volume 1 (Pragmatic Bookshelf, October 2022, 378 pages) treats all four models in a chapter titled Naive Trees, whose stated objective is "Store and Query Hierarchies" and whose named antipattern is "Always Depend on One's Parent." That book is why the closure table is known outside academic papers, and its recommendation is conditional: pick by the operations you run.

Numbers from a 100,000-node tree

Everything above is measurable, so here it is measured. The tree is synthetic, generated from a fixed seed: 100,000 nodes, maximum depth 7, average depth 5.69, fanout widest near the root and narrowing below, which is roughly the shape a scraped shop catalogue has. It was loaded five times, once per model, into PostgreSQL 16.13 on a two-core Linux virtual machine with 8 GB of RAM and stock configuration. Read timings are the median of 25 runs after three warm-ups, from a warm cache, and each query returns matching ids rather than joined payload rows.

The materialized path's ancestor figure assumes the application splits the path string itself and issues WHERE id IN (...), which is what every library does; as pure SQL with a correlated subquery the same lookup took 170 ms. Its direct-children figure also returns the node itself unless you exclude it, which is the off-by-one that string patterns invite.

The nested set's 1.42 ms for ancestors deserves a look at the plan rather than the number. WHERE lft <= 19712 AND rgt >= 19713 is a two-sided range predicate and a B-tree can drive only one side of it, so PostgreSQL read 9,860 index entries and discarded 9,852 of them to return 8 rows. Ancestor lookups get slower the deeper into the numbering your node sits, and nothing in the schema warns you.

Writes are where the models diverge by orders of magnitude rather than by factors. Row counts here are exact and deterministic; the timings alongside them are indicative.

Measured on a single two-core machine, on one synthetic 100,000-node tree, in PostgreSQL 16.13 with default settings and a warm cache. Your absolute numbers will differ by an order of magnitude in either direction. The shape will not.

Two conclusions survive the noise. "Nested sets are fastest for reads" holds only for the whole-subtree read, and fails on the two reads a catalogue actually serves. And no read difference here is worth ten seconds per insert.

Where each pattern stops working

Cycles. Only the adjacency list can represent one, which is both the problem and the diagnosis: a path or a nested set cannot store a cycle, so a corrupt import fails loudly instead of looping. Validate parent_id on load, reject any parent already in the candidate's ancestor set, and use your engine's cycle guard on recursive reads over imported data.

More than one parent. Products in several categories are not a tree, they are a directed acyclic graph, and three of the four patterns cannot express one. The closure table can: drop the assumption of a single ancestor chain per node and the pairs table still holds. That is the strongest practical argument for it in e-commerce data, where "Wireless Headphones" sits under both Audio and Accessories on nearly every site that has both.

More than one root. The nested set is out, per TypeORM's flat statement above. The others handle it without comment.

Depth. Materialized paths hit byte limits on the index key, recursive CTEs hit SQL Server's 100 levels and MySQL's 1,000, closure tables hit quadratic growth. Adjacency lists have no depth ceiling of their own, only the recursion budget you forgot to raise.

Concurrency. Two writers renumbering a nested set at once will corrupt it unless the operation is serialised, which in practice means a table-level lock on every insert. Under a re-crawl adding a few thousand categories, that is a queue, not a database.

The ORM. A closure table maintained by an ORM is correct only while every write goes through the ORM, and bulk loads, COPY and migration scripts all bypass it. Put the maintenance in triggers, with the MySQL cascade caveat in mind, or run a job that rebuilds the closure from the adjacency list and diffs the two.

Trees that come out of a crawler

Scraped trees have quirks that a normalised in-house hierarchy does not, and the storage model has to absorb them.

Re-crawls mean churn. Categories get added, renamed and re-parented between runs, and a re-parent is the most expensive operation in three of the four models. If your nightly diff moves even a handful of branches, nested sets are out on write cost before any read benchmark runs.

The source hands you paths, not pointers. A breadcrumb trail on a product page is already a materialized path; so is a BreadcrumbList block in JSON-LD, with position giving you the level for free. The path is therefore the natural landing shape for raw extracted data, whatever you convert it to later. Keeping it alongside the resolved parent_id costs one column and settles every argument about how a node got where it is.

Sources disagree on structure. Merging category trees from several sites is easier when each node carries a stable natural key alongside its position, so normalize and deduplicate before you assign tree positions. Position is derived; identity is not. Get identity wrong and every subsequent re-parent looks like a delete plus an insert.

Depth is rarely known in advance. Design for arbitrary depth on day one, with recursive CTEs or a closure table, rather than hard-coding a fixed number of self-joins you will outgrow on the third site you add.

Extraction is the other half of the problem. When the menu is assembled by JavaScript and the category ids exist only inside an internal API response, getting the tree out of the page is harder than storing it, and that is where a web scraping service spends its time before any schema question arises. Running the whole pipeline, from crawl through extraction into a schema that stays fast as it grows, is what a data as a service arrangement covers, with the storage model chosen to fit the query patterns rather than the reverse.

When the relational answer is the wrong one

If your data is less a clean tree and more a tangled graph, with recommendation links and many-to-many memberships, a relational model of any flavour will fight you. Three escape hatches, in ascending order of commitment.

JSON columns. For small self-contained subtrees you always read as a unit, a single product's option tree or a config blob, store the branch as JSON in one row and let the application parse it. PostgreSQL's jsonpath has a recursive descent accessor, .**, which searches every nesting level, and the manual carries a warning worth heeding: lax mode unwraps arrays and "can lead to surprising results," so "we recommend using the .** accessor only in strict mode." PostgreSQL 17, released 26 September 2024, added JSON_TABLE() to turn that JSON back into rows in a FROM clause.

Graph queries inside SQL. The standard caught up. ISO/IEC 9075-16:2023, Property Graph Queries (SQL/PGQ), was published in June 2023 and is already marked for revision. Oracle exposes hierarchical traversal through CONNECT BY with START WITH, SYS_CONNECT_BY_PATH for the materialized path of a row, and NOCYCLE to survive loops. On PostgreSQL, Apache AGE adds a Cypher-style graph layer as an extension built per major version, keeping the graph beside the relational data instead of in a second system.

A graph database. GQL became a real ISO standard on 17 April 2024, as ISO/IEC 39075:2024, the first new ISO database language since SQL. Neo4j moved to calendar versioning and is shipping fast, with 2026.07.1 released on 5 August 2026 beside a maintained 5.26 LTS line. Price it before you commit: AuraDB lists a free tier with node and relationship caps, Professional from $65 per GB per month at a 1 GB minimum, and Business Critical from $146 per GB per month at a 2 GB minimum. If hierarchy is your core domain, that is money well spent. If you have one category tree and a deadline, it is a second database to operate.

What the libraries actually do

The clearest signal about which patterns survived is which libraries are still shipping, and the answer differs by ecosystem.

In Python the shift is finished and documented. django-mptt, the library that made nested sets the default way to do trees in Django, last released 0.18.0 on 26 August 2025, and its README now opens with "This project is currently unmaintained." It points readers at django-tree-queries, described as "Adjacency-list trees for Django using recursive common table expressions," whose README states the requirement precisely: "Supports PostgreSQL, sqlite3 (3.8.3 or higher) and MariaDB (10.2.2 or higher) and MySQL (8.0 or higher, if running without ONLY_FULL_GROUP_BY)." The pattern that needed a workaround lost to the one that no longer does.

Ruby did not move the same way, and the download counts say the old models still work for people. ancestry, a materialized path, reached 5.1.0 on 8 March 2026 with 38.4 million downloads; awesome_nested_set 3.9.0 on 20 December 2025 with 24.6 million; closure_tree 9.8.0 on 5 August 2026 with 8.4 million.

PHP and TypeScript sit in between. kalnoy/nestedset shipped v7.0.0 on 11 April 2026 with 14.7 million installs; staudenmeir/laravel-adjacency-list reached v1.26.1 two days later and handles both trees and multi-parent graphs through CTEs. TypeORM implements three of the four as first-class @Tree types and is candid about each: nested set is "very efficient for reads, but bad for writes," closure table "is efficient in both reading and writing," and "TreeRepository doesn't support Adjacency list."

Read that last line carefully before you take it as a verdict on the pattern. It says the ORM's tree helper does not cover the adjacency list, not that the adjacency list is worse. Plain foreign keys need no helper.

Choosing a pattern

There is no universal winner. The model follows the read/write mix, the depth, and how often the tree moves.

Default to the adjacency list. With recursive CTEs it covers most cases with the least code, the smallest storage, full referential integrity, single-row writes, and the fastest direct-children query in the measurement above. Stay here until a profiler says otherwise. The one query it loses badly is the full-tree walk, at 249 ms against 13 ms, and if you run that on every page load you have a caching problem rather than a schema problem.

Reach for a closure table when you query ancestors and descendants with equal frequency, when writes are constant, or when nodes have more than one parent. It is the only model here that handles a DAG, and its costs can be calculated in advance: n × (1 + average depth) rows, and a move that costs the subtree size times the changed ancestors.

Use a materialized path, preferring ltree or hierarchyid over hand-rolled strings, for comment threads and breadcrumb-style lineage where prefix matching is the main query and the tree grows at the leaves. Check your index operator class before you believe any prefix benchmark.

Use nested sets only for a fixed taxonomy that is read by whole subtree, never re-parented, and has exactly one root.

Then keep the hybrid in mind, because it is what most mature systems converge on: an adjacency list as the source of truth, with the foreign key doing what only a foreign key can, plus a derived path or closure table rebuilt by trigger or nightly job for the reads that need it. Writes stay one row. Reads get their index. The derived copy can be dropped and rebuilt when it drifts, which it will.

Count your queries first. The tree is the easy part.