Привет, меня зовут Антон, и я разработчик. Сына я родил, дом
Что такое 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, надо добавить прямую ссылку на идентификатор родительского элемента. Это позволит быстрее перемещаться по иерархии и находить родительские и дочерние узлы, и, кроме того, повысит надежность алгоритма.
