Ответ.

Работа с деревьями и иерархиями — частый кейс при программировании в SQL: каталоги товаров, оргструктура, меню. Изначально большинство СУБД поддерживало только ссылку на родителя (ParentId), но со временем появились альтернативные методы — вложенные множества и пути (Path), а также рекурсивные запросы через CTE.

Проблема традиционного Parent-Child подхода — низкая скорость при обходе больших иерархий; выборки уровня глубже 2-3 приводят к лавинообразному числу JOIN. Более сложные техники (Nested Sets, Path Enumeration) ускоряют массовые обходы, но затрудняют вставки/удаления.

Решение — выбор оптимальной модели хранения под конкретную задачу:

• Для редких изменений и массового чтения: Nested Sets (сохраняем границы left/right в узлах для быстрого поиска потомков)
• Для частых изменений: Adjacency List + рекурсивные CTE
• Для быстрого поиска пути — Path и хранение полного пути в строке

Пример рекурсивного поиска под-дерева через CTE:

WITH RecursiveTree AS (
  SELECT id, parent_id, name, 0 as level
  FROM categories
  WHERE parent_id IS NULL
  UNION ALL
  SELECT c.id, c.parent_id, c.name, rt.level + 1
  FROM categories c
  INNER JOIN RecursiveTree rt ON c.parent_id = rt.id
)
SELECT * FROM RecursiveTree;

Ключевые особенности:

• Выбор структуры хранения под сценарий (Parent-Child, Nested Sets, Path)
• Использование рекурсивного CTE для произвольных глубин
• Оценка частоты изменений и чтения для подбора оптимального метода

Вопросы с подвохом.

Можно ли заменить хранение деревьев одной денормализованной таблицей с одним уровнем ссылок, если глубина фиксирована?

Только если глубина мала и всегда фиксирована (2-3 уровня) — далее JOIN'ы становятся неуправляемыми, усложняется обработка изменений.

---

А CTE не "провиснет" при больших деревьях — нет ли ограничений по стеку, глубине рекурсии?

Да, в большинстве СУБД выставлены лимиты по глубине рекурсии (например, 100/32767). Для деревьев в 1000+ уровней потребуется ручное управление глубиной или кастомные алгоритмы обхода/разделения.

---

Nested Sets — решение всех проблем?

Нет, nested sets мгновенно ищут всех потомков, но вставка/удаление требует массового обновления всех индексов слева/справа — это медленно при большом числе частых изменений.

Пример вставки (упрощённо):

UPDATE tree SET lft = lft + 2 WHERE lft > @parent_right;
UPDATE tree SET rgt = rgt + 2 WHERE rgt >= @parent_right;
INSERT INTO tree(id, name, lft, rgt) VALUES(@new_id, @name, @parent_right, @parent_right + 1);

Типовые ошибки и анти-паттерны

• Ожидание, что Parent-Child легко масштабируется — при deep tree быстрый рост затрат
• Вложенные множества для обновляемых данных (вставки/удаления) — дорого
• Неучет лимитов CTE/Stack Overflow в больших деревьях

Пример из жизни

Негативный кейс

Большой интернет-магазин хранил дерево категорий в adjacency list и строил меню вложенными подзапросами. При 6+ уровнях меню главный запрос выполнялся несколько минут, а любое изменение дерева приводило к cascade update. Плюсы:

• Простой код
• Поддержка стандартной SQL-схемы

Минусы:

• Медленный обход, сложно строить агрегаты и отчёты

Позитивный кейс

Перешли на Nested Sets для статичных деревьев (категорий), а для путей в меню — на Path. Использовали CTE для динамических сценариев. Поиск потомков стал мгновенным, изменения делали батчами. Плюсы:

• Быстрый поиск любого уровня вложенности
• Гибкость, разные модели для разных задач

Минусы:

• Требуется контроль целостности границ при изменениях (Nested Sets)
• Увеличение сложности синхронизации при миграциях