MySQL – Storing Hierarchies with a Closure Table

Relational tables are flat and trees are not, so storing a hierarchy is a genuine design decision. This lesson covers the three approaches worth knowing — the adjacency list, the recursive CTE that rescued it in MySQL 8, and the closure table — using a menu category tree.

The adjacency list

Every row points at its parent. It is where everyone starts, and it is a good default:

CREATE TABLE menu_category (
    id        BIGINT AUTO_INCREMENT PRIMARY KEY,
    name      VARCHAR(60) NOT NULL,
    parent_id BIGINT NULL,
    CONSTRAINT fk_menu_category_parent FOREIGN KEY (parent_id) REFERENCES menu_category (id)
);

INSERT INTO menu_category (id, name, parent_id) VALUES
    (1,'Menu',NULL),(2,'Food',1),(3,'Drinks',1),
    (4,'Pizza',2),(5,'Sides',2),(6,'Cold',3),(7,'Hot',3),
    (8,'Speciality Pizza',4),(9,'Build Your Own',4);

SELECT c.id, c.name, p.name AS parent FROM menu_category c LEFT JOIN menu_category p ON p.id = c.parent_id ORDER BY c.id;

+----+------------------+--------+
| id | name             | parent |
+----+------------------+--------+
|  1 | Menu             | NULL   |
|  2 | Food             | Menu   |
|  3 | Drinks           | Menu   |
|  4 | Pizza            | Food   |
|  5 | Sides            | Food   |
|  6 | Cold             | Drinks |
|  7 | Hot              | Drinks |
|  8 | Speciality Pizza | Pizza  |
|  9 | Build Your Own   | Pizza  |
+----+------------------+--------+

Cheap to store, trivial to modify — moving a subtree is one UPDATE of one parent_id — and the foreign key keeps it honest. That self join walks exactly one level, which is the problem: "everything under Food" has no fixed number of joins, because you do not know the depth in advance.

The recursive CTE

MySQL 8 answers that directly:

WITH RECURSIVE subtree AS (
    SELECT id, name, 0 AS depth FROM menu_category WHERE id = 2
    UNION ALL
    SELECT c.id, c.name, s.depth + 1
    FROM   menu_category c JOIN subtree s ON c.parent_id = s.id
)
SELECT name, depth FROM subtree ORDER BY depth, name;

Any depth, one query, no extra tables to maintain. For most applications this is where the story ends — an adjacency list plus a recursive CTE is simple, correct, and fast enough. See CTEs.

What it costs is that the walk happens every time. Each level is a separate join step, so reading a deep subtree on a hot path — a category page rendering on every request — does real work repeatedly. That is the case the closure table exists for.

The closure table

Store one row for every ancestor-descendant pair, including each node paired with itself at depth 0:

CREATE TABLE category_closure (
    ancestor_id   BIGINT NOT NULL,
    descendant_id BIGINT NOT NULL,
    depth         INT    NOT NULL,
    PRIMARY KEY (ancestor_id, descendant_id),
    KEY idx_closure_descendant (descendant_id)
);

INSERT INTO category_closure (ancestor_id, descendant_id, depth)
WITH RECURSIVE walk AS (
    SELECT id AS ancestor_id, id AS descendant_id, 0 AS depth FROM menu_category
    UNION ALL
    SELECT w.ancestor_id, c.id, w.depth + 1
    FROM   walk w JOIN menu_category c ON c.parent_id = w.descendant_id
)
SELECT ancestor_id, descendant_id, depth FROM walk;

SELECT COUNT(*) AS closure_rows FROM category_closure;

+--------------+
| closure_rows |
+--------------+
|           25 |
+--------------+

Nine categories, 25 closure rows. That ratio is the trade: storage grows with the number of ancestor-descendant pairs, not with the number of nodes.

What you buy is that both directions become a single indexed lookup with no recursion at all. The whole subtree under Food:

SELECT c.name, cl.depth
FROM   category_closure cl JOIN menu_category c ON c.id = cl.descendant_id
WHERE  cl.ancestor_id = 2
ORDER  BY cl.depth, c.name;

+------------------+-------+
| name             | depth |
+------------------+-------+
| Food             |     0 |
| Pizza            |     1 |
| Sides            |     1 |
| Build Your Own   |     2 |
| Speciality Pizza |     2 |
+------------------+-------+

And the breadcrumb trail — every ancestor of a node — which the adjacency list makes just as awkward in the other direction:

SELECT c.name, cl.depth
FROM   category_closure cl JOIN menu_category c ON c.id = cl.ancestor_id
WHERE  cl.descendant_id = 8
ORDER  BY cl.depth DESC;

+------------------+-------+
| name             | depth |
+------------------+-------+
| Menu             |     3 |
| Food             |     2 |
| Pizza            |     1 |
| Speciality Pizza |     0 |
+------------------+-------+

Both are WHERE ancestor_id = ? or WHERE descendant_id = ? against an index. Depth costs nothing. WHERE depth = 1 gives direct children only, and depth > 0 excludes the self-row.

The cost: writes

The closure table is derived data, so every structural change has to maintain it. Adding a leaf means inserting one row per ancestor:

INSERT INTO menu_category (id, name, parent_id) VALUES (10, 'Deep Dish', 8);

INSERT INTO category_closure (ancestor_id, descendant_id, depth)
SELECT cl.ancestor_id, 10, cl.depth + 1 FROM category_closure cl WHERE cl.descendant_id = 8
UNION ALL SELECT 10, 10, 0;

Moving a subtree is worse: delete every pair linking the moved nodes to their old ancestors, then insert the cross product of the new ancestors against the moved subtree. It is a handful of statements and it must be done inside a transaction — a half-updated closure table is a tree that disagrees with itself, and nothing will tell you.

Which to choose

Start with the adjacency list. Add a recursive CTE when you need depth. Move to a closure table only when subtree reads are demonstrably hot and the tree changes rarely — a product catalogue, an org chart, a threaded comment tree. Those are exactly the conditions that make the trade pay: many reads, few writes.

Two other schemes exist and are worth recognising rather than choosing. Materialised path stores '/1/2/4/8/' in a column, making descendant lookups a LIKE 'prefix%' — simple, and it inherits every problem of storing structure in a string. Nested sets store left/right numbers giving very fast reads and requiring renumbering much of the table on any insert. Both are largely historical now that recursive CTEs exist.

What to remember

• Adjacency list first; it is simple and the foreign key keeps it correct.
• A recursive CTE walks it to any depth, and is enough for most applications.
• A closure table makes subtree and ancestor reads a single indexed lookup.
• It pays for that on every structural write, and it is derived data that can drift — maintain it in a transaction.