Какие существуют способы хранения и сериализации древовидных структур в базе данных?

Question

Деревья можно хранить разными способами: через связи «родитель → потомок» (adjacency list), через диапазоны в вершинах (nested sets), через путь от корня (materialized path), либо в JSON-структурах.
Adjacency list прост и понятен, но делает сложными выборки поддеревьев. Nested sets оптимизируют чтение, но требуют дорогих обновлений. Materialized path удобен для поиска потомков по шаблону пути.
JSON полезен, когда структура часто меняется или не требует сложных запросов внутри БД.
Выбор зависит от частоты чтений, обновлений и сложности запросов к дереву.

YeaHub · Accepted Answer

Хранение деревьев — частая задача при работе с каталогами, меню, сущностями с вложенностью. Существуют несколько классических моделей.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.