Хранение деревьев — частая задача при работе с каталогами, меню, сущностями с вложенностью. Существуют несколько классических моделей.

1. Adjacency List (способ «родитель → ребёнок»)

Определение:
Adjacency list — модель, в которой каждая запись хранит ссылку на своего родителя.

1.1. Структура таблицы

id
parent_id  -- может быть NULL для корня
name

1.2. Плюсы

• простая структура;

• легко обновлять (менять родителя);

• интуитивно понятно.

1.3. Минусы

• сложные выборки поддеревьев, требуется рекурсия;

• чтение дерева без CTE может быть дорогим.

1.4. Пример запроса (Postgres, рекурсивный CTE)

WITH RECURSIVE tree AS (
    SELECT id, parent_id, name FROM nodes WHERE id = 1
    UNION ALL
    SELECT n.id, n.parent_id, n.name
    FROM nodes n
    JOIN tree t ON t.id = n.parent_id
)
SELECT * FROM tree;

2. Nested Sets (вложенные множества)

Определение:
Nested sets — модель, в которой каждая вершина хранит два индекса: left и right.
Поддерево — это диапазон left < x < right.

2.1. Структура

id
lft
rgt
name

2.2. Плюсы

• быстрые выборки поддеревьев;

• идеально для часто читаемых деревьев.

2.3. Минусы

• обновления дороги: перестраивается большая часть дерева;

• сложно реализовать без вспомогательных функций.

2.4. Пример выборки поддерева

SELECT * FROM nodes WHERE lft BETWEEN 10 AND 30;

3. Materialized Path (материализованный путь)

Определение:
Materialized path — модель, где каждая запись хранит путь от корня к узлу в виде строки.

3.1. Структура

id
path     -- например, '1.5.9.'
name

3.2. Плюсы

• простая реализация;

• быстрая выборка потомков (LIKE '1.5.%');

• легко перемещать узлы (обновление пути).

3.3. Минусы

• зависимость от строковых операций;

• возможны дорогие массовые обновления при изменении пути.

3.4. Пример выбора поддерева

SELECT * FROM nodes WHERE path LIKE '1.5.%';

4. JSON / JSONB структуры

Определение:
JSON-иерархия — способ хранить дерево как вложенные JSON-объекты.

4.1. Плюсы

• гибкость;

• нет жёсткой схемы;

• удобно, если дерево часто меняется или не слишком велико.

4.2. Минусы

• сложно делать SQL-запросы по структуре;

• трудно поддерживать целостность;

• хуже подходит для больших деревьев.

4.3. Пример

SELECT data->'children' FROM tree WHERE id = 1;

5. Сравнение подходов

Когда выбирать adjacency list:

• когда дерево часто изменяется;

• когда глубина небольшая;

• когда подходит рекурсивный CTE.

Когда использовать nested sets:

• когда важны быстрые запросы чтения;

• когда структура меняется редко.

Когда materialized path:

• удобен для древовидных каталогов;

• хорош, когда запросы — в основном чтение поддерева.

Когда JSON:

• когда дерево — часть модели, но не основной объект хранения;

• когда нет сложных запросов внутри БД.

Краткий вывод

• Если дерево часто обновляется → adjacency list.

• Если дерево читается гораздо чаще, чем модифицируется → nested sets.

• Если удобен путь как строка → materialized path.

• Если структура гибкая или вспомогательная → JSON.