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

image

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



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

image

Припустимо нам треба вставити підкатегорію Fay в Pixies, результат буде таким:

image

Як бачимо змінити доведеться все ноди в дереві. А тепер уявіть що ви таким способом зберігаєте дерево коментарів до статей. Кожен раз коли хтось додає новий коментар у вас відбувається апдейт купи записів, крім того треба обов'язково робити це все в транзакції при чому бажано заборонити зміни цих рядків паралельними запитами. Якщо всього цього не зробити, то навіть кілька активних користувачів коментують одночасно можуть легко зламати всю індексацію. Та й продуктивність системи очевидно теж сильно страждає.

Я знайшов елегантний спосіб, як вирішити цю проблему лише трохи змінивши стандартний Nested Set. Ідея його проста, хоча імплементація помітно складніше у деяких місцях. До всіх нодам слід додати ідентифікатор піддерева у якому вони знаходяться, наприклад id кореня. У кожному поддереве нумерацію left і right починаємо спочатку. Вищенаведений приклад з таким підходом виглядав би ось так:

image

При вставці нам треба змінювати тільки ноди, що знаходяться у тому ж поддереве:

image

Як бачимо піддерево 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 може стане в нагоді підхід з оптимізацією.
Якщо цікаві якісь деталі або просто хочеться поговорити, заходьте до нас в чат.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.