A tree in a table of rows

How do you store something with branches in a structure that only knows about rows?

An organisation chart, a product taxonomy, a threaded conversation, a chart of accounts — all trees, all of them things a business genuinely has. A table is a flat set of rows with no nesting whatsoever.

The first instinct is that this is an impedance problem to be solved once and forgotten. But the interesting thing is that it has never settled on one solution: four different approaches are in wide use, none has won, and that persistence is a clue. If one were simply better, the others would have died. So the question underneath is not how do you store a tree in rows, but why does the answer keep depending on what you intend to ask.

Begin with the most direct idea. A tree is a set of nodes where each node has one parent. So give each row a parent_id pointing at another row. Done — the whole structure is encoded, nothing is lost.

Now test it against a real question. Give me everything under Engineering. What does the database have to do? Find Engineering's children. Then their children. Then theirs. It cannot know when to stop, because the depth is data, not schema. So the query is not one operation but a repeated one — which SQL could not express at all until recursive common table expressions arrived in the SQL:1999 standard, and which even now costs one pass per level of depth.

Pause on why. In an adjacency list you have stored the edges of the tree. But the question asks about reachability — the ancestor relation, which is the transitive closure of those edges. You stored one thing and are querying another, and the gap between them is exactly the recursion you have to pay for at every read.

Which suggests the obvious remedy: store the thing you actually ask about. That is a closure table — a second table with one row for every ancestor-descendant pair, plus the depth between them, and conventionally a self-row at depth zero for each node. Now "everything under Engineering" is a single equality join, no recursion at all. A thousand nodes at average depth five yields roughly five thousand closure rows: real storage, but modest.

What did that cost? Ask what happens when someone moves a team. In the adjacency list, one row changes. In the closure table, every pair involving any node in the moved subtree has to be recomputed — potentially thousands of rows for one drag of a mouse. The cost did not disappear. It moved from read time to write time.

That is the pattern, and once you see it the other two options are easy to place. Materialised path stores each node's ancestry as a string like /1/7/22/, so a subtree is a prefix match — fast reads, and the same rewrite-the-subtree cost on a move, plus a limit on depth from the column width. Nested sets, from Joe Celko's work, number the nodes by a traversal and store a left and right value per node, so a subtree is everything between them — excellent for reading whole subtrees, and notoriously expensive to write, since inserting one node can renumber a large part of the table.

So the honest answer to the original question is: you do not store the tree. You choose which derived relation to make cheap, and pay for it in the operation you made expensive. Reads and writes are the two currencies, and there is no scheme that is cheap in both, because the recursion is intrinsic to the shape.

One caveat about generality. All four schemes assume a genuine tree — one parent per node, no cycles. Real hierarchies often violate this: a person reports to two managers, a product sits in two categories. Adjacency lists degrade gracefully into a general graph; nested sets and materialised paths do not, and a closure table can represent a directed acyclic graph but its row count grows much faster. Discovering that your "tree" is really a graph, after choosing a scheme, is a common and painful surprise.

Three refinements.

First, the misconception that this is a limitation of relational databases. It is not. A tree stored in a document as nested objects has made the same trade in the other direction — reading a subtree is trivial, but asking "which node has this identifier, anywhere in the forest" or reparenting across documents becomes the hard operation. Relational storage merely makes the choice explicit rather than implicit.

Second, the schemes are not exclusive. Keeping the adjacency list as the source of truth and maintaining a closure table beside it — by trigger, or rebuilt in a batch — is common and sensible. The adjacency list stays canonical and easy to correct; the closure table is a derived index that can be rebuilt from scratch if it drifts.

Third, choose by the query you actually run. A navigation menu showing one level at a time wants adjacency and nothing more. Rolling costs up a chart of accounts, or checking permission inheritance on every request, wants a precomputed closure. Deciding by preference rather than by workload is how a taxonomy ends up doing a seven-level recursive walk on every page load.

• Recursive common table expressions, and where they stop scaling.
• Directed acyclic graphs: what breaks when a node legitimately has two parents.
• Keeping a closure table consistent with its adjacency source under concurrent writes.

Every term the collection defines is gathered in the glossary.