Знаете ли вы работу с деревьями в базах данных

Что проверяют

Умеете ли вы хранить и читать иерархии: категории, оргструктуру, комментарии с ответами. Путать это с B-деревьями индексов не стоит, вопрос про модель данных. Следом обычно просят написать запрос «все потомки узла» или выбрать схему под частые переносы веток.

Как отвечать

Назовите основные схемы и их цену:

• список смежности: колонка ParentId со ссылкой на ту же таблицу. Проще всего писать и переносить узлы, но поддерево читается рекурсией;
• материализованный путь: строка вида /1/7/42/, поддерево находится через LIKE '/1/7/%' по индексу. Перенос ветки переписывает пути всех потомков;
• вложенные множества: у узла есть границы lft и rgt, поддерево это один запрос по диапазону. Зато вставка сдвигает границы у значительной части таблицы;
• таблица замыканий: отдельная таблица всех пар «предок, потомок, глубина». Быстро читается в обе стороны, но занимает больше места;
• hierarchyid в SQL Server: встроенный тип с методами GetAncestor, IsDescendantOf, GetLevel. В PostgreSQL похожую роль играет расширение ltree.

Список смежности читается рекурсивным CTE: в SQL Server это WITH с якорной частью и UNION ALL, в PostgreSQL WITH RECURSIVE. SQL Server по умолчанию ограничивает рекурсию сотней уровней, лимит меняется подсказкой OPTION (MAXRECURSION n).

Со стороны C#: в EF Core самоссылка описывается свойствами Parent и Children, но Include не загружает дерево произвольной глубины. Рабочий приём: одним запросом взять плоский список узлов и собрать дерево в памяти через словарь по Id, либо выполнить рекурсивный CTE через FromSql. С EF Core 8 провайдер SQL Server поддерживает HierarchyId.

Где спотыкаются

Рассказывают про B-деревья и AVL вместо хранения иерархий. Вопрос звучит похоже, но ответ мимо.

Строят дерево ленивой загрузкой: обращение к Children на каждом уровне порождает N+1 запросов.

Не защищаются от циклов в списке смежности. Узел, ставший собственным предком, гоняет рекурсивный CTE по кругу, пока его не остановит лимит.