Как спроектировать базу данных для хранения древовидной организационной структуры сотрудников
Что проверяют
Знаете ли вы способы хранить деревья в реляционной базе и их цену на чтение и запись. Таблицу со ссылкой на руководителя называют почти все, интервьюер ждёт следующего шага: как получить всех подчинённых на любую глубину и что делать при переносе целого отдела.
Как отвечать
Сначала уточните требования: глубина, частота изменений, главные запросы (цепочка до директора, всё поддерево). Затем варианты:
- список смежности:
ManagerIdс внешним ключом на ту же таблицу. Перенос поддерева это одно обновление. Поддерево читается рекурсивным CTE: в SQL Server этоWITHбез словаRECURSIVEи с лимитом глубины 100 по умолчанию (OPTION (MAXRECURSION n)), в PostgreSQL нуженWITH RECURSIVE; - материализованный путь: строка вида
/1/5/12/, поддерево ищется по префиксу. В SQL Server для этого есть типhierarchyid, EF Core поддерживает его начиная с восьмой версии, в PostgreSQL аналог даёт расширениеltree; - closure table: таблица всех пар «предок, потомок» с глубиной. Любое поддерево одним запросом, но перенос отдела переписывает много строк;
- nested sets: быстрое чтение и дорогие вставки, на меняющейся структуре почти не применяется.
Для оргструктуры на десятки тысяч человек обычно хватает списка смежности с индексом по ManagerId. В EF Core связь описывается навигациями Manager и Subordinates, но Include на произвольную глубину не работает: дерево читают рекурсивным запросом через FromSql или загружают плоско и собирают в памяти.
Где спотыкаются
Не защищаются от циклов. Если назначить руководителя подчинённым его же подчинённого, рекурсивный запрос упрётся в лимит, поэтому проверка нужна при каждом переназначении.
Смешивают людей и подразделения. Обычно дерево строится из отделов, а сотрудник привязан к отделу и должности, иначе увольнение руководителя ломает всю ветку.
Забывают про историю и исключения: переводы с датами, совместительство и матричное подчинение, при котором у сотрудника два руководителя и структура уже не дерево.