Оптимизация модели Nested Set в PHPixie

Всего 2 часа назад я дописал последний тест к новому типу связи для PHPixie ORM — Nested Set. Я долго думал использовать ли этот подход или же Closure Table для хранения деревьев в SQL базах. Но в результате Closure Table проиграл ввиду квазиквадратических размеров к которым растет таблица связей (при 20 нодах в худшем случае уже можно получить 190 записей). Так что следующей задачей стала оптимизация классического Nested Set подхода, и результат мне очень даже понравился.



Одной из главных проблем в использовании Nested Set является стоимость вставки ноды. Чем левее позиция вставки тем больше записей надо сдвинуть вправо. Например есть у нас вот такое дерево:

Допустим нам надо вставить подкатегорию Fay в Pixies, результат получится таким:

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

Я нашел элегантный способ как решить эту проблему всего лишь чуть-чуть изменив стандартный Nested Set. Идея его проста, хотя имплементация заметно сложнее в некоторых местах. Ко всем нодам следует добавить идентификатор поддерева в котором они находятся, например id корня. В каждом поддереве нумерацию left и right начинаем сначала. Вышеприведенный пример с таким подходом выглядел бы вот так:

При вставке нам надо изменять только ноды находящиеся в том же поддереве:

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

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

Использование в PHPixie

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

Во первых добавьте 4 INTEGER поля к таблице в которой хранятся элементы: left, right, rootId, depth (конечно-же имена полей полностью настраиваемыми, это лишь дефолтные). Затем добавьте связь в /bundes/app/assets/config/orm.php

return array(
     'relationships' => array(
          //....
         array(
             'model' => 'category' //имя модели,
             'type' => 'nestedSet'
         )
     )
);

Дальше все просто:

$fairies->children->add($sprites);
$fairies->children->add($pixies);

//ну или так
$pixies->parent->set($fairies);

//поместить категорию в корень
$pixies->parent->remove();

//подгрузить все дерево с БД
//заметьте условие where('depth', 0),
//без него в результате мы бы получили все категории
//а не только те что сверху (то есть кучу дубликатов)

$categories = $orm->query('category')->where('depth', 0)->find(array('children'));

Кстати PHPixie сама будет следить за удалением сущностей и исправлять индексы.

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