Выращивание Nested sets в условиях .Net

Привет, меня зовут Антон, и я разработчик. Сына я родил, дом построил купил, осталось вырастить дерево. Так как агроном из меня не очень, пришлось дерево кодить. Наш проект состоит из нескольких микросервисов на .Net Core, в PostgreSQL базе хранятся сущности, которые образуют иерархические связи. Расскажу о том, какую структуру лучше выбрать для хранения таких данных, почему именно Nested sets, на какие грабли можно наступить, и как с этим потом жить.

Что такое Nested sets

Как растет дерево в саду все знают, а в случае Nested sets дерево растет так: для каждого узла хранится два поля Left и Right, они целочисленные. Логика здесь такая – Left меньше чем Right, и, если у узла есть дочерние, то все значение Left и Right дочерних узлов должны быть между соответствующих значений родительского.

Как они растут у нас

У нас под хранение иерархий выделен отдельный микросервис. Фронтеду приходится часто рисовать полное дерево, а также поддеревья элементов в детализированном представлении, тогда как вставлять и переносить элементы надо сравнительно реже. Для такого случая Nested sets подходят как нельзя лучше. Хранится в такой таблице:

Id – это идентификатор соответствующей сущности, по нему можно получить полную информацию из подходящего микросервиса. TreeId – идентификатор корневого элемента. В проекте деревья в основном небольшие, но их много. Для чтения из базы используется EntityFramework, класс один к одному соответствует структуре таблицы.

Как прочитать

При таком способе хранения получить элементы поддерева просто – запрашиваем все узлы, у которых Left больше Left родительского, а Right соответственно меньше. Также проверяем, что все узлы относятся к одному и тому же дереву – по колонке TreeId. Это операция, которая необходима чаще других, и выполняется она быстро. К примеру, так:

dataContext.Nodes.Where(_ =>                          _.Left > node.Left &&                          _.Right < node.Right &&                          _.TreeId == node.TreeId);  

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

dataContext.Nodes.Where(_ =>                          _.Left < node.Left &&                          _.Right > node.Right &&                          _.TreeId == node.TreeId); 

Как вырастить новые ветки

Перейдем к сложной части – пересадка, т.е. добавление узлов или перенос из одного поддерева в другое. Разберем, как сделать перенос, т.к. по сути эта операция включает в себя все, что нужно для добавления дочернего элемента.

Первое, что нужно сделать для успешной вставки – разрешить только одну операцию вставки или обновления. Для этого воспользуемся блокировкой. Блокировать всю таблицу не имеет смысла, так как узлы могут переходить только в рамках одного дерева, так что достаточно заблокировать только это дерево. Для этого выполним такой SQL запрос:

select * from "Nodes" where "TreeId" = <TreeId> for update; 

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

Следующим шагом подготовим место для пересадки – создадим промежуток между Left и Right. Посчитаем, сколько место необходимо – это разность между Right и Left корневого элемента перемещаемого поддерева. Добавим эту разность ко всем дочерним элементам узла, который станет новым родителем. Здесь можем поймать Exception, и вот почему. Для ускорения поиска и чтения в таблице заведены два B-Tree индекса, на поля Left и Right, и если одновременно менять значения этих полей, EntityFramework может выдать ошибку циклической зависимости, т.к. два индекса могут пересчитываться одновременно на одной строке. Ошибка будет типа InvalidOperationException с таким сообщением:

Unable to save changes because a circular dependency was detected in the data to be saved: ‘Node [Modified] < — Index { ‘Right’, ‘TreeId’ } Node [Modified] < — Index { ‘Left’, ‘TreeId’ } Node [Modified]’.

Чтобы обойти, просто сделаем два отдельных цикла – в одном изменим Left, в другом Right, и, конечно, сохранять изменения будем после каждого из них.

             var nodesToMove = await dataContext.Nodes                  .Where(n =>                      n.Right >= parentNodeRight &&                      n.TreeId == parentNode.TreeId)                  .OrderByDescending(n => n.Right)                  .ToListAsync();                foreach (var n in nodesToMove)              {                  n.Left += distance;              }                await dataContext.SaveChangesAsync();                foreach (var n in nodesToMove)              {                  n.Right += distance;              }                await dataContext.SaveChangesAsync();  

Далее сама пересадка – расстояние переноса будет равно разности между Left нового родителя и Left корня поддерева. Добавим это значение к Left и Right всех узлов перемещаемого поддерева.

             var nodes = await dataContext.Nodes                  .Where(n =>                      n.Left >= node.Left &&                      n.Right <= node.Right &&                      n.TreeId == node.TreeId)                  .ToListAsync();                foreach (var n in nodes)              {                  n.Left += distance;                  n.Right += distance;  

И последнее, что надо сделать – закрыть промежуток так, где было перемещенное поддерево. Запросим все узлы правее этого поддерева – это будут элементы, у которых Right больше либо равно Left корня поддерева, и передвинем их на освободившееся место. Для этого отнимем от Left и Right всех этих узлов разность между Right и Left корня. Здесь тоже придется сделать два отдельных цикла:

             var nodesToMove = await dataContext.Nodes                .Where(n => n.Right >= gap.Left && n.TreeId == gap.TreeId)                .ToListAsync();              nodesToMove = nodesToMove                  .Where(n => n.Right >= gap.Right)                  .OrderBy(n => n.Right)                  .ToList();                foreach (var n in nodesToMove)              {                  if (n.Left >= gap.Right)                  {                      n.Left -= distance;                  }              }                await dataContext.SaveChangesAsync();                foreach (var n in nodesToMove)              {                  n.Right -= distance;              }                await dataContext.SaveChangesAsync(); 

Заключение

Посмотрим, что у нас выросло. Мы получили дерево с возможностью быстрого чтения дочерних и родительских элементов. Если в вашем проекте нужно часто читать данные и получать поддеревья, Nested sets – отличный выбор. Надо быть готовым к тому, что с операциями вставки и обновления могут возникнуть проблемы, но они вполне решаемые. Если же добавлять и переносить приходится часто, лучше подумать о применении какого-то другого алгоритма, либо рассмотреть некие гибридные варианты. Например скрестить Nested sets и Adjacency List. Для этого в каждый узел, помимо Left и Right, надо добавить прямую ссылку на идентификатор родительского элемента. Это позволит быстрее перемещаться по иерархии и находить родительские и дочерние узлы, и, кроме того, повысит надежность алгоритма.