Ответ.

Работа с иерархическими структурами — классика реляционных баз данных. Примеры: каталоги, древовидные меню, организационные структуры.

История вопроса: Базы данных — табличная модель. Для древовидных данных существует несколько подходов, каждый со своими плюсами и минусами.

Проблема: Стандартная модель parent_id приводит к медленным рекурсивным SELECT'ам. Реальные задачи (поиск всех потомков, пути, пересчёт поддеревьев) требуют оптимизации.

Решение:

Adjacency List — простая ссылка на parent_id.
Materialized Path — строка, отражающая полный путь.
Nested Sets — хранение левых/правых границ (left/right), что позволяет легко вытаскивать поддеревья.
Closure Table — отдельная таблица связей (from->to), отражающая все отношения в дереве.

Пример кода для Materialized Path (PostgreSQL):

CREATE TABLE categories (
    id SERIAL PRIMARY KEY,
    name TEXT,
    path TEXT
);

-- Пример хранения path: '1/2/5/' (корень/подкатегория/текущий)
SELECT * FROM categories WHERE path LIKE '1/2/%'; -- все потомки 2

Пример кода для Nested Sets:

CREATE TABLE nested_categories (
    id SERIAL PRIMARY KEY,
    name TEXT,
    lft INT NOT NULL,
    rgt INT NOT NULL
);

-- Дочерние узлы
SELECT * FROM nested_categories WHERE lft > 2 AND rgt < 15;

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

Adjacency List удобна для простых древовидных структур (низкая вложенность).
Materialized Path — быстрое извлечение поддеревьев, легко реализуется.
Nested Sets — мгновенное получение всех потомков, быстрое чтение, но сложная модификация.

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

Можно ли просто использовать вложенный SELECT с parent_id для поиска всех потомков на произвольную глубину?

Это работает только для малых глубин. Для рекурсивного поиска требуется либо рекурсивный CTE (WITH RECURSIVE), либо более сложные схемы, т.к. простые JOIN приводят к огромному числу обращений и плохой производительности.

Пример:

WITH RECURSIVE cte AS (
    SELECT id, parent_id, name FROM categories WHERE id = 1
    UNION ALL
    SELECT c.id, c.parent_id, c.name
    FROM categories c
    INNER JOIN cte ON c.parent_id = cte.id
)
SELECT * FROM cte;

Почему молекулярное дерево (Nested Sets) быстро извлекает поддерево, но медленно добавляет/удаляет узлы?

При изменении дерева приходится менять lft/rgt сразу у многих строк (шаг изменения — все значения, большие чем вставка/удаление). Для чтения подход идеален, для частых изменений используйте другие методы.

Когда использовать Closure Table, а не parent_id или materialized path?

Closure Table идеально работает для многократных запросов к потомкам любых уровней и регулярного пересчёта связи. Минус — требует больше места.

Пример:

CREATE TABLE closure (
    ancestor INT,
    descendant INT,
    depth INT
);

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

Хранение иерархии только через parent_id, когда требуется быстрый поиск вложенных структур.
Ручное пересчитывание путей или lft/rgt без вспомогательных функций.
Отсутствие индексации ключевых столбцов (parent_id/path/lft/rgt).

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

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

В интернет-магазине категории реализованы через parent_id. Все вложенные ставятся вручную, поиск подкатегорий — вложенными SELECT'ами.

Плюсы:

Простота, не требуется расширенной поддержки.

Минусы:

Производительность падает даже на 3-4 уровнях вложенности.
Операции перемещения узлов — неочевидны, приводят к логическим ошибкам.

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

Используется materialized path или closure table. Все запросы на вложенные категории мгновенны, пересчёт — групповыми скриптами.