Оптимизация модели 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 может пригодится подход с оптимизацией.
Если интересны какие-то детали или просто хочется поболтать, заходите к нам в чат.
