Иерархические данные в реляционных БД
Категории товаров, оргструктура, меню, комментарии с ответами — деревья встречаются в каждом продукте. Реляционная модель — таблицы и строки; дерево нужно смоделировать.
База: SQL — язык, JOIN и объединения, рекурсивные CTE.
Три распространённые модели
| Модель | Идея | Чтение поддерева | Вставка узла | Сложность |
|---|---|---|---|---|
Adjacency list (parent_id) | Ссылка на родителя | Рекурсивный CTE | O(1) | Низкая |
Nested sets (left, right) | Интервалы обхода | Один диапазон | O(n) сдвигов | Средняя |
| Closure table | Все пары предок–потомок | JOIN по ancestor | O(depth) строк | Выше объём |
Adjacency list (parent_id)
CREATE TABLE category (
id BIGINT PRIMARY KEY,
parent_id BIGINT REFERENCES category(id),
name TEXT NOT NULL
);
Плюсы: просто объяснить, дешёвые вставки и перенос ветки (обновить parent_id).
Минусы: "все потомки узла 42" — рекурсия. В PostgreSQL, SQL Server, Oracle — рекурсивный CTE:
WITH RECURSIVE tree AS (
SELECT id, parent_id, name, 1 AS depth
FROM category WHERE id = 42
UNION ALL
SELECT c.id, c.parent_id, c.name, t.depth + 1
FROM category c
JOIN tree t ON c.parent_id = t.id
)
SELECT * FROM tree;
Для глубоких деревьев (тысячи уровней — редкость) следите за индексом (parent_id).
Nested sets
Каждый узел получает номера left и right обхода "в глубину". Потомки узла — все строки, у которых left и right лежат внутри интервала родителя.
Плюсы: выборка поддерева без рекурсии — один WHERE left BETWEEN ….
Минусы: вставка/удаление сдвигает границы у многих строк — плохо при частых изменениях и высокой конкуренции.
Подходит для реже меняющихся каталогов (справочники, таксономии).
Closure table
Отдельная таблица (ancestor_id, descendant_id, depth) со всеми парами на пути.
Плюсы: быстрые запросы "все предки", "все потомки", гибкая глубина.
Минусы: больше строк при вставке; нужна дисциплина поддержания при переносе ветки.
Хорошо для частых сложных запросов по иерархии при умеренной частоте записи.
Материализованный путь (дополнение)
Колонка path вида /1/5/12/ — быстрый LIKE '/1/5/%', но перенос узла требует обновления всех потомков. Иногда комбинируют с parent_id.
Когда что выбирать
| Сценарий | Рекомендация |
|---|---|
| Типичный CRUD, глубина < 10 | parent_id + CTE |
| Частое чтение дерева целиком, редкие правки | Nested sets |
| Сложная аналитика по предкам/потомкам | Closure table |
| Граф "друзья друзей", не дерево | Таблица рёбер + графовая БД |
Ограничения целостности
FOREIGN KEYнаparent_id— не удалить родителя с детьми без CASCADE или переноса.- Запрет циклов: триггер или проверка при переносе (в closure — проще валидировать).
- Для nested sets — транзакция на всю операцию сдвига.