Привет, Хабр!
Большинство разработчиков знает, что такое Nested Sets, их сильные и слабые стороны. Сегодня я хочу представить на суд общественности реализацию модификации этой методики, которая частично решает недостатки оригинального алгоритма, правда имеет и свои отрицательные стороны.

Какие же плюсы и минусы у оригинальных Nested Sets:
+ быстрая выборка родителей и детей простым запросом;
+ быстрая выборка соседних узлов простым запросом;
+ быстрая выборка пустых узлов простым запросом;
+ моментальное получение количества всех детей в узле по формуле;
+ возможность не рекурсивного построения дерева одним циклом;
— очень медленная вставка и обновление.

Каковы же причины медленной вставки/обновления? Так как, значения границ узлов идут непрерывно, то любая вставка, особенно в начало дерева, требует перерасчёта границ всех последующих узлов. Если таблица достаточно большая, то это процесс может затянуться на десятки секунд и даже дольше. На анимации:

Nested Intervals

Первая мысль, которая пришла в голову, рассматривая картинку с визуальным представлением Nested Sets: «так границы же можно не двигать, если представить корневой узел как отрезок на поле вещественных чисел». То есть, если представить, что границы корневого узла имеют значения 0.0 и 1.0, то можно добавлять узлы в любое место не двигая другие, надо просто взять вещественное число между целевыми узлами. Но, так как мы прекрасно знаем, вещественные числа в компьютере имеют свои пределы, то от этой идеи я быстро отказался, в пользу целых чисел.

С целыми числами суть та же, только границы корневого узла сделаем от нуля до INT_MAX. Тогда при вставке нового узла мы просто берём любые два незанятых значения между целевыми узлами, и больше ничего не трогаем, всё было бы быстро и круто, если бы не одно «но» — что делать если свободных значений больше нет? Очевидно, что нужно двигать все значения границ до ближайшего свободного значения, «расчищая» себе пространство для вставки. Только вот поиск такой «дырки» — задача затратная, поэтому результат в таком случае может выйти даже медленнее, чем в классических nested sets.


Немного погуглив, я понял, что не изобрёл велосипед, и эта идея уже давно имеет название Nested Itervals. Только вот реализаций я так и не нашёл, т. к. на большинстве ресурсов данную методику рассматривали в негативном ключе, мол «одно лечим, другое калечим». И это не безосновательно, но мне стало очень интересно, захотелось протестировать в чём данный алгоритм лучше, а в чём хуже, и на сколько.

Реализация

Я начал писать Behavior для Yii2, реализующий идею Nested Intervals. Первая сложность возникла при написании методов вставки — как получить границу соседнего узла или родителя при insertBefore() и insertAfter() и границу первого/последнего узла при prependTo() и appendTo()? Если в Nested Sets она очевидна — +1/-1 к границе текущего узла, то здесь без дополнительно запроса к базе никак. Но благо, что выборки у нас быстрые.

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

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

Но вот перемещение из другого дерева — задача оказалась трудно решаемая, т. к. перемещаемых узлов может оказаться очень много, и вставлять их по одному обычным алгоритмом выходит слишком долго. Сначала я вообще хотел отказаться от этой возможности, списав на сложность реализации. Но чуть позже, осознал необходимость метода optimize(), который бы равномерно распределял границы существующих узлов по диапазону. После этого, возникла идея перемещать узлы другого дерева путём оптимизации исходного дерева с заготовлением «окна» под перемещаемые узлы. Всё это работает очень медленно (на данный момент есть оптимизация этого метода только под MySQL), но стоит отметить, что операция по перемещению из других деревьев требуется редко, куда чаще требуется движения в рамках одного дерева.

Зато реализовывать выборки было достаточно легко — главные методы получения родителей и детей идентичны классическим nested sets. Чуть посложнее с выборками предыдущего/следующего соседа — требуется два запроса: получение родителя, и непосредственный поиск в диапазоне с лимитом. А вот совсем плохо стало с получением пустых узлов getLeaves(), т. к. пришлось его делать с помощью left join, что наверняка скажется на производительности.

Оптимизация вставки

Выполнив первый ряд тестов на производительность, результаты мягко говоря не впечатлили. Дело оказалось в том, что сначала я реализовал выбор границ вставляемого узла просто разбив отрезок на три части. Из-за этого промежуток для новых узлов стремительно сокращался. Так как диапазон 32 битного PHP составляет [0 — 2147483647] (операции с большими числами конвертируются во float), то выполнив вставку через appendTo() всего 19-ти узлов в корень, на 20-й узел уже не останется места (2147483647/3^19 = ~1.9), и приходится выполнять медленные операции по поиску незанятых мест и перемещения. Так дело, конечно, не пойдёт. Нужны какие-то оптимизации по распределению места. Для этого в Behavior есть аж 5 опций:

• Первая и главная amountOptimize — этот параметр определяет на какое количество узлов запланировать разбиение доступного для вставки отрезка. То есть, при значении 20, мы сможем вставить 20 дочерних узлов, и они равномерно займут диапазон родителя, а дальше — как получится.
  В качестве значения можно использовать массив, тогда значение будет разным для каждого уровня.
  
• noPrepend, noAppend, noInsert — эти параметры помогают оптимизировать резервирование места между границами, и положение первого узла. Если у вас, используется в основном только операция appendTo() (например, комментарии), то вы можете выставить noPrepend = true и noInsert = true, и тем самым значительно снизите вероятность возникновения тяжёлого случая с расчисткой пространства под новый узел. Более наглядно влияние этих параметров показано на картинках.
  

  amountOptimize=3
  amountOptimize=3 noPrepend=true
  amountOptimize=3 noAppend=true
  amountOptimize=3 noInsert=true
  amountOptimize=3 noInsert=true noPrepend=true
  amountOptimize=3 noInsert=true noAppend=true

  
  Стоит отметить, что если вы задаёте noPrepend = true — это не значит, что вы не сможете выполнить вставку prependTo(), просто с большой долей вероятности множество таких операций будут выполняться медленно.
  
• И последний параметр reserveFactor, определяет размер промежутков между границами. При единичке размер промежутка равен размеру вставляемого узла. Если сценарий использования Behavior предполагает большого числа операций insertBefore() и insertAfter(), то этот параметр лучше увеличить

После всех этих манипуляций тесты стали гораздо более «вкусными».

64 бита

Если вы задействуете BIGINT колонки для хранения left и right атрибутов и используете 64-битный PHP, то сможете воспользоваться бесплатной оптимизацией в виде более широкого диапазона. Просто задайте параметр range = [0, 9223372036854775807]. Это позволит сделать более редкими случаи с недостатком места под новые узлы.

Тесты на производительность

В качестве эталона для сравнения, был взят самый популярный Behavior, реализующий Nested Sets от уважаемого Alexander Kochetov (Creocoder) creocoder/yii2-nested-sets. Так же было интересно сравнить результаты с Adjacency List с сохранением возможности сортировки. Подходящей библиотеки я для этого не нашёл, поэтому взял и написал сам (да ещё и с поддержкой JOINов, но сейчас не об этом).

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

Тесты 3-5 имитируют вставку 20 узлов в разное место большой таблицы:

Следующий тест удаляет 20 узлов из начала дерева:

Тест 7 очень показательный, т. к. хорошо имитирует использование Behavior для комментариев. В цикле 1000 узлов добавляется в случайно выбранный узел, с ограничением уровней. Тест 8 аналогичный, но с ещё более жесткими условиями — разрешено не только добавление, но и любая другая операция.

Следующие два теста на перемещение узлов в дереве:

После написания Behavior мне захотелось узнать, какую выгоду даст использование Trait вместо поведений. Поэтому я портировал его Trait со статическими атрибутами. Дальнейшие тесты на выборки велись также и в вариантах с Trait. Но результаты применения примесей мягко говоря не впечатлили, особенно учитывая то, насколько более уродлив стал код из-за них.
Простая выборка всех элементов Model::find()->all():

Выборка потомков:

Выборка предков:

Выборка соседних и пустых узлов:

Выводы

Nested Intervals — имеет право на жизнь. У него есть как преимущества, так и недостатки:
+ быстрая вставка (при условии хорошего подбора оптимизирующих параметров);
+ быстрое удаление узла с потомками;
+ такая же скорость как у Nested Sets в выборке предков и потомков;
+ так же, осталась возможность не рекурсивного построения дерева одним циклом;
— медленное получение соседних узлов;
— медленное получение пустых узлов;
— нет возможности моментально подсчитать количество потомков в узле.

Реализация для Yii2

Хочу отметить, что методы немного отличаются от предложенных в поведении Creocoder. Во-первых я изменил именование методов на геттеры getParents() getDescendants(), это позволяет реализовывать доступ к связанным узлам, аналогично Relations, что позволяет не делать вторичных запросов к базе:

$node = Node::findOne(['name' => 'test']);
$children = $node->children; // relation
$children = $node->getChildren()->all(); // query

Кроме того, я не стал протаскивать Yii-шные параметры к save($runValidation, $attributeNames), вместо этого я реализовал методы, как указание на действие (прямо как ->asArray()->):

$node = new Node();
$node->makeRoot()->save(false);
$node->insertAfter($node2)->save();

Реализация Nested Intervals на GitHub.
Реализация Adjacency List на GitHub.