Открыть список
Как стать автором
Обновить
204,33
Рейтинг
Auriga
Аурига — это люди

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

Блог компании AurigaАлгоритмыC#
Tutorial


Привет, меня зовут Антон, и я разработчик. Сына я родил, дом построил купил, осталось вырастить дерево. Так как агроном из меня не очень, пришлось дерево кодить. Наш проект состоит из нескольких микросервисов на .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, надо добавить прямую ссылку на идентификатор родительского элемента. Это позволит быстрее перемещаться по иерархии и находить родительские и дочерние узлы, и, кроме того, повысит надежность алгоритма.
Теги:.netnested setsalgorithms
Хабы: Блог компании Auriga Алгоритмы C#
Всего голосов 18: ↑18 и ↓0 +18
Просмотры2K

Комментарии 4

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Похожие публикации

Лучшие публикации за сутки

Информация

Дата основания
Местоположение
Россия
Сайт
auriga.com
Численность
501–1 000 человек
Дата регистрации

Блог на Хабре