Как хранить деревья или как мы меняли инструмент «Структура компании»

Привет, меня зовут Степан Золотухин, я разработчик в Битрикс24. Моя команда работает над такими продуктами, как Почта, Маркетинг, Структура компании, Подписание, CRM-Формы.

Мы делаем очень много клевых и интересных фич, но в этой статье я расскажу о том, как мы работаем с «деревьями» на примере нашего продукта «Структура компании».

Немного теории

Древовидные структуры встречаются повсюду: файловые системы, меню в веб-приложениях, товары в интернет-магазинах, связи между друзьями в соцсетях, различные организационные диаграммы. Древовидные структуры обычно хранятся базах данных, и от того, каким способом данные представлены в таблицах, зависит гибкость самой структуры и скорость обработки запросов к дереву.

Для того чтобы поместить дерево в базу данных, нужно «упаковать» древовидную структуру со всеми уровнями и связями между узлами в таблицу.

Существует четыре основных способа это сделать, но у каждого есть свои плюсы и минусы. Опишу кратко эти способы, учитывая такие критерии, как Поиск, Добавление, Удаление, Изменение.

Adjacency List (Список смежности):

• Поиск: Легко найти прямых потомков узла (простым фильтром по PARENT_ID). Для глубоких запросов требуется рекурсивный обход или несколько последовательных запросов, что замедляет работу с большими деревьями.

• Добавление: Добавить узел просто, достаточно указать его PARENT_ID.

• Удаление: Удаление требует дополнительных операций для обработки потомков.

• Изменение: Изменение родителя (перемещение) требует обновления только одного поля.

Closure Table (Таблица замыканий/связей):

• Поиск: Мгновенно можно получить всех потомков любого узла, включая глубоко вложенные.

• Добавление: Добавление нового узла требует обновления нескольких записей в таблице путей.

• Удаление: Требует удаления всех записей из таблицы путей, связанных с узлом и его потомками.

• Изменение: Перемещение узла требует пересчета путей для всех потомков.

Nested Sets (Вложенные множества):

• Поиск: Быстрое получение всех потомков или предков благодаря диапазонам LEFT_MARGIN и RIGHT_MARGIN (наименование колонок могут быть индивидуальными).

• Добавление/удаление: Любое изменение требует пересчета значений для всего дерева.

• Изменение: Очень дорогостоящее для больших деревьев.

Materialized Path (Материализованный путь):

• Поиск: Легко находить всех потомков и проверять принадлежность узла к поддереву с помощью запросов LIKE.

• Добавление: Новый узел добавляется путем расширения пути родителя минимальными операциями.

• Удаление: Удаление узла и его потомков выполняется одним запросом по фильтру пути.

• Изменение: Перемещение узла требует обновления пути у него и всех его потомков, что может быть ресурсоемким.

Как мы хранили деревья раньше

«Структура компании» существует в продукте уже давно — это наглядный способ отобразить структуру отделов, подчиненность сотрудников, руководителей, удобный способ найти нужного сотрудника и его контакты. 

Для реализации дерева в «Структуре компании» мы использовали стандартный механизм, встроенный в Битрикс24 и основанный на модуле iblock. Проще говоря, мы строили древовидные структуры на инфоблоках.

Модуль iblock использовал подход Nested Sets через таблицу (b_iblock_section). В основе его реализации лежат два поля:

o   LEFT_MARGIN (левый край)

o   RIGHT_MARGIN (правый край)

Каждому узлу дерева присваивались числовые значения, которые обозначали границы диапазона для этого узла. Эти значения указывали, где начинается и заканчивается узел внутри дерева, включая всех его потомков.

Пример хранения структуры

1. Корневой узел «Компания» охватывает весь диапазон (1–10), включающий все узлы в дереве.

2. Узел «Отдел IT» имеет потомка «Поддержка», который находится внутри диапазона (6–9).

Почему использовался этот подход?

Nested Sets отлично подходит для задач, связанных с построением иерархий, где:

1. Нужно быстро находить потомков узла. Например, запросить все подразделения внутри конкретного отдела.

2. Необходимо эффективно обрабатывать вложенные запросы (например, сколько людей в каждом отделе).

Любые модификации такого дерева требуют пересчета границ у всех связанных узлов — это довольно ресурсоемкая задача, особенно на больших деревьях. Но мы рассчитывали на то, что структуры компаний у наших пользователей будут относительно статичными — для таких условий Nested Sets подходил идеально.  

Почему мы решили поменять подход, использующий Nested Sets?

Предыдущая версия «Структуры компании» была основана на инфоблоках. Но когда мы получили список задач по обновлению инструмента для нового релиза и проанализировали текущую реализацию, стало очевидно, что существующий легаси-код значительно усложнит разработку нового функционала.

Расскажу немного подробнее о тех задачах, которые нам предстояло решить. 

Среди пользователей Битрикс24 много крупных компаний, холдингов и их организационная структура часто не вписывается в типовой шаблон. Например, в компании может быть два руководителя отдела с четко разделенными ролями и компетенциям. Или у одного руководителя может быть несколько заместителей со своими зонами ответственности. 

Основываясь на запросах пользователей, наши продакты сформулировали такие задачи к новому релизу:

• Заместители

• Видимость отделов в зависимости от прав доступа

• Ролевая модель прав

• Права на редактирование своего отдела и отделов в подчинении у руководителя

• Права доступа у HR на управление структурой

• Совместители

• Новый визуальный конструктор структуры

Большое количество имевшихся решений и множество точек взаимодействия с инфоблоками мешали бы внедрению необходимого функционала для новой концепции. И мы решили полностью переписать продукт. 

Учитывая кадровую специфику крупных компаний, нам нужно было предоставить пользователям возможность динамично редактировать роли сотрудников и перемещать целые отделы внутри компании без значительных затрат по времени. Однако в Nested Sets такие операции требовали серьезных вычислительных ресурсов, особенно для крупных организаций, что усложнялось спецификой событийной модели продукта.

В связи с этим, учитывая новые требования, мы пересмотрели подход к хранению дерева структуры компании.

Посмотрев на запросы и список предполагаемых фич, мы проанализировали возможности Nested Sets и выявили несколько ограничений.

1. Сложности с изменением структуры:
   Для того чтобы добавить, удалить или переместить отделы, приходилось пересчитывать значения LEFT_MARGIN и RIGHT_MARGIN для всех связанных узлов.

2. Проблемы производительности:
   В больших организациях перенос отдела, включающего десятки дочерних узлов, требовал массового пересчета границ для большого количества элементов. Это становилось узким местом, вызывая задержки, а в случае высокой нагрузки — даже сбои, которые разваливали связи между блоками.

3. Ограниченная гибкость:
   Требовались новые фичи, такие как фильтрация, поиск и редактирование структуры в реальном времени. Однако адаптация Nested Sets в наших условиях для этих задач усложнила бы разработку.

Как мы меняли «Структуру компании»

Для хранения структуры и для смежных задач, связанных с работой сотрудников компании, мы добавили в Битрикс24 новый модуль humanresources, куда и поместили новый механизм хранения дерева. Перебрав все варианты с учетом продуктовых требований, за саму схему хранения решено было использовать Closure Table совместно с Adjacency List.

Этот подход позволил нам объединить лучшие стороны обоих методов: он упрощает такие операции, как добавление, удаление отделов, перемещение сотрудников между отделами, а также позволяет быстро и эффективно выполнять более сложные запросы, например, получение всех сотрудников в определенном отделе или построение полного иерархического дерева компании.

Детали реализации на примерах SQL без PHPДля хранения структуры компании теперь мы используем таблицы:

•  b_hr_structure_node для хранения узлов дерева с колонкой PARENT_ID (Adjacency List).

• b_hr_structure_node_path для хранения всех возможных путей между узлами (Closure Table).

Это дало нам ощутимое ускорение сложных операций с деревом. 

С помощью таблицы b_hr_structure_node_path мы можем эффективно выполнять сложные запросы. 

Например, для построения дерева визуальной структуры мы можем запросить все подразделения корневого узла (Компании):

SELECT n.* FROM b_hr_structure_node_path p JOIN b_hr_structure_node n ON p.CHILD_ID = n.ID WHERE p.PARENT_ID = 1;

Для получения всех вышестоящих подразделений можно использовать следующий запрос:

SELECT p.PARENT_ID FROM b_hr_structure_node_path p WHERE p.CHILD_ID = 5 ORDER BY p.DEPTH DESC;

Детали реализации на PHP + ORM.

Как мы можем получить всех сотрудников отдела с подотделами

$nodeMemberQuery =    Model\NodeMemberTable::query()       ->setSelect(['*'])       ->registerRuntimeField(          'ncn',          new Reference(             'ncn',             Model\NodePathTable::class,             Join::on('this.NODE_ID', 'ref.CHILD_ID'),          ),       )->where('ncn.PARENT_ID', $nodeId)       ->addOrder('ncn.DEPTH') ;

Вставка нового подразделения с пересчетом всех родителей и подотделов

$list = <<<SQL SELECT new_parent.PARENT_ID, child.CHILD_ID, new_parent.DEPTH + child.DEPTH AS depth FROM (    SELECT PARENT_ID, (DEPTH + 1) as DEPTH    FROM b_hr_structure_node_path    WHERE CHILD_ID = $targetNodeId    UNION ALL    SELECT $nodeId as PARENT_ID, 0 as depth ) AS new_parent JOIN (    SELECT CHILD_ID, DEPTH    FROM b_hr_structure_node_path    WHERE PARENT_ID = $nodeId OR CHILD_ID = $nodeId ) AS child ON new_parent.PARENT_ID != child.CHILD_ID SQL; $query = $helper->getInsertIgnore(    “b_hr_structure_node_path”,    '(PARENT_ID, CHILD_ID, DEPTH) ',    $list ); $connection->queryExecute($query);

 Благодаря используемому подходу добились следующего: 

1. Реализовали запросы любой сложности, включая:

   • Построение полного пути от подразделения к корню и обратно.

   • Поиск всех потомков или предков подразделения.

2. Ускорили массовые операции:

   • Изменение структуры или перемещение узлов не требует пересчета всех индексов дерева.

3. Добавили поддержку новых функций:

   • Поддержка произвольного уровня вложенности.

   • Возможность работы с несколькими структурами в рамках одного проекта.

   • Множественные руководители и заместители.

Результаты и планы

На уровне продукта и пользовательского опыта мы смогли в течение нескольких месяцев реализовать все задачи, поставленные продактами на новый релиз. 

Прежде всего мы изменили дизайн и восприятие самой структуры компании, создали визуальный конструктор структуры. Если раньше добавлять сотрудников можно было только через отдельную форму, а само изображение структуры компании было практически статичным, то сейчас это визуальный конструктор, позволяющий вносить изменения в структуру движениями мышки. 

Мы добавили новые фичи для управления отделами, разрешили добавлять несколько руководителей в один отдел и отображать это в визуальной структуре. 

В наших дальнейших планах: добавить в структуру компании функциональные группы (команды с участием сотрудников из разных отделов), показывать акционеров и их доли в компании, создавать организационную структуру для холдингов (объединять структуры разных компаний). Новые подходы к хранению деревьев помогут нам быстро реализовать эти возможности.