Набір Yii2 Behavior для зберігання дерев в БД і їх спільного використання


Привіт, Хабр!

В одному своєму проекті на Yii2 мені захотілося поєднати Adjacency List і Nested Sets. Причому так, щоб у разі відключення поведінки Nested Sets, функціонал залишався повністю працездатний. Потім я зрозумів, що Nested Sets мені не потрібен, т. к. в базі все одно доводилося зберігати повний шлях, тому на заміну я вирішив застосувати Materialized Path. Наявний на GitHub Behavior (matperez/yii2-materialized-path) був недостатньо функціональний, тому довелося написати свій, а так як я нещодавно вже писав свої поведінки для Adjacency List і Nested Intervals, я вирішив, чому б не зробити набір таких поводжень з єдиним API, і можливістю довільно підключати їх до моделі одночасно, використовуючи перевагу кожного.


Список поводжень
Adjacency List
+ самопідтримуюча цілісність структура
+ швидкі модифікації, оскільки не вимагає ніяких перерахунків і оновлень нащадків
+ швидке отримання безпосередніх батьків і дітей
— складність і повільність отримання усіх предків і нащадків

Найпростіший вид зв'язку, найчастіше для його реалізації не докладають жодних поводжень, а просто прописують зв'язку з батьком і дітьми. Але варто доповнити Adjacency List полем сортування вузлів (
insertBefore()
/
insertAfter()
), то тут вже без готового поведінки стає складно. Та й отримати усіх предків/нащадків одними зв'язками вже важкувато.
Всі ці проблеми вирішує поведінку. Крім того, у нього є деякі фішки — він дозволяє робити настроюється кількість join-ів таблиці саму з собою для скорочення і прискорення запитів на отримання предків/нащадків.
Дивитися на GitHub

Materialized Path
Методика зберігання повного шляху в кожному елементі (прямо як шлях у файловій системі).
+ швидке отримання усіх предків і нащадків
+ швидка вставка нових елементів
— неоптимальний зберігання шляху, можливі обмеження на його довжину,
— у загальному вигляді необхідно додаткове поле depth для одержання безпосередніх дітей (у реалізаціях під конкретну базу ця вимога не потрібно)
— при зміні шляху елемента, потрібне оновлення всіх нащадків

Чим же мені не підійшов matperez/yii2-materialized-path, крім необхідності єдиного API і відсутність деяких методів? У першу чергу тим, що оновлення дітей при зміні path у нього йде php-рекурсією, що породжує купу запитів до бази, що дуже погано. У реалізованому мною поведінці це виробляється одним запитом, правда, довелося пожертвувати певною сумісністю з базами даних — потрібна підтримка функцій
CONCAT()
та
LENGTH()
(в більшості БД вони є — mysql, pqsql, mssql). Ще з переваг — у моєму behavior передбачено два режими побудови шляху — по первинному ключу або по іншому полю, причому не обов'язково унікальному.
Дивитися на GitHub

Nested Sets
+ швидкі вибірки предків, нащадків, сусідніх і порожніх вузлів
+ моментально отримання кількості нащадків у вузлі
+ не рекурсивне побудова дерева
— дуже повільні модифікації дерева, особливо на початку великих баз (вставка одного елемента може запросто тривати більше 30 секунд в великій базі)

Для Yii2 вже є відмінне розширення від Creocoder, але мені довелося його переписати для підтримки єдиного API, про який трохи нижче. Цей API дає ряд переваг.
Дивитися на GitHub

Nested Intervals
+ швидкі вибірки предків, нащадків
+ не рекурсивне побудова дерева
+ швидка вставка за умови оптимізації параметрів
— повільні переміщення вузлів

Цей алгоритм не дуже популярний, хоча він дуже швидкий за умови вибору правильних параметрів. Більш детально про nested intervals можна почитати в цієї статті.
Дивитися на GitHub

Єдиний API
Всі перераховані вище поведінки мають загальне API, завдяки чому можуть бути замінені без переписування коду.
У API є одна велика перевага — подвійний доступ до зв'язаних об'єктів через стандартний для Yii2 механізм Relations:
$parent = $model->getParent()->orderBy(['title' => SORT_DESC])->one(); // якщо викликати зв'язок методом, поверне ActiveQuery
$title1 = $model->parent->title; // якщо викликати властивістю, поверне сам об'єкт
$title2 = $model->parent->title . '(2)'; // повторний виклик НЕ генерує другий запит до бази

Є та особливість — методи
makeRoot(), prependTo(), appendTo(), insertBefore(), insertAfter()
— не виробляють сама дія, а лише дають вказівку на його тип, тому після них треба не забути виконати
save()
:
$node = new Node;
$node->title = 'root';
$node->makeRoot()->save();

Це зроблено для того, щоб не протягати за собою параметри
save($runValidation = true, $attributeNames = null)
.

Trait для одночасного використання декількох поводжень
Behavior в Yii2 реалізовані таким чином, що виконується метод першого поведінки, в якому він існує. Щоб спільно використовувати кілька поводжень, треба викликати модифікуючі дерево методи для кожного підключеного поведінки, а для обирають з бази методів — найбільш швидкий. Для цього був написаний Договорі, який виконує ці функції. Заодно це позбавляє від необхідності вказувати PhpDoc кожен раз.
Дивитися на GitHub

Приклад:
use paulzi\adjacencylist\AdjacencyListBehavior;
use paulzi\nestedsets\NestedSetsBehavior;
use paulzi\autotree\AutoTreeTrait;

class Node extends \yii\db\ActiveRecord
{
use AutoTreeTrait;

public function behaviors() {
return [
['class' => AdjacencyListBehavior::className()],
['class' => NestedSetsBehavior::className()],
];
}
}

Тепер:
$node->parents; // буде використовувати nested sets
$node->parent; // буде використовувати adjacency list
$node->children; // буде використовувати adjacency list
$node->descendants; // буде використовувати nested sets
$node->insertAfter($node2)->save() // виконається для двох поводжень відразу

Максимально ефективні поєднання:
Adjacency List + Materialized Path
Adjacency List + Nested Sets
Adjacency List + Nested Intervals

Порівняння продуктивності
З таблиці думаю видно, в чому переваги і недоліки кожного з behavior:
Таблиця продуктивностіЗапитів DB час Виконання Пам'ять

Тест 1. Заповнення 3 рівня по 12 дітей
Adjacency List 5811 1,567 ms 9,591 ms 71.3 MB
Nested Sets 7697 6,672 ms 25,019 ms 105.9 MB
Nested Intervals amount=24 5813 1,765 ms 10,442 ms 78.7 MB
Nested Intervals amount=12 noPrepend noIns. 5813 1,750 ms 10,223 ms 78.7 MB
Materialized Path (identity pr. key mode) 7696 3,169 ms 13,726 ms 92.5 МБ
Materialized Path (attribute mode) 5811 1,690 ms 9,504 ms 71.6 MB

Тест 2. Заповнення 6 рівня по 3 дітей
Adjacency List 3642 982 ms 5,812 ms 44.5 MB
Nested Sets 4736 5,447 ms 17,859 ms 65.0 MB
Nested Intervals amount=10 3644 1,275 ms 5,976 ms 48.9 МБ
Nested Intervals amount=3 noPrepend noIns. 3644 1,271 ms 5,993 ms 48.9 МБ
Materialized Path (identity pr. key mode) 4735 1,316 ms 6,920 ms 57.3 MB
Materialized Path (attribute mode) 3642 1,129 ms 5,507 ms 44.6 МБ

Тест 3. Вставити в початок <4% (20 в 19657 вузлів)
Adjacency List 100 36 ms 190 ms 4.6 MB
PaulZi 100 15,768 ms 16,712 ms 4.7 MB
Nested Intervals 82 21 ms 150 ms 4.7 MB
Materialized Path (identity pr. key mode) 120 98 ms 355 ms 4.8 MB
Materialized Path (attribute mode) 100 74 ms 334 ms 4.6 MB

Тест 4. Вставка в середину >46% <50% (20 в 19657 вузлів)
Adjacency List 100 24 ms 150 ms 4.6 MB
Nested Sets 100 8,212 ms 8,799 ms 4.7 MB
Nested Intervals 82 269 ms 593 ms 4.7 MB
Materialized Path (identity pr. key mode) 120 35 ms 196 ms 4.9 MB
Materialized Path (attribute mode) 100 287 ms 494 ms 4.6 MB

Тест 5. Вставка в кінець >96% (20 в 19657 вузлів)
Adjacency List 100 31 ms 214 ms 4.5 MB
Nested Sets 100 487 ms 899 ms 4.7 MB
Nested Intervals 83 46 ms 187 ms 4.7 MB
Materialized Path (identity pr. key mode) 120 34 ms 229 ms 4.8 MB
Materialized Path (attribute mode) 100 470 ms 718 ms 4.6 MB

Тест 6. Видалення з початку <4% (20 з 19657 вузлів)
Adjacency List parentJoin=0 childrenJoin=0 60 169 ms 257 ms 3.8 MB
Adjacency List parentJoin=3 childrenJoin=3 60 87 ms 162 ms 3.8 MB
Nested Sets 100 16,480 ms 16,902 ms 4.7 MB
Nested Intervals 60 164 ms 250 ms 4.2 MB
Materialized Path (identity pr. key mode) 60 87 ms 201 ms 4.0 MB
Materialized Path (attribute mode) 60 122 ms 219 ms 4.0 MB

Тест 7. appendTo() випадковий вузол (5 рівнів, 1000 вузлів)
Adjacency List 4001 1,062 ms 5,976 ms 46.1 MB
Nested Sets 5003 5,428 ms 17,334 ms 64.8 МБ
Nested Intervals amount=10 8497 23,301 ms 41,060 ms 120.7 MB
Nested Intervals x64 amount=10 7092 11,330 ms 23,618 ms 97.5 MB
Nested Intervals amount=200,25 noPrep noIns 4009 1,431 ms 6,490 ms 50.2 MB
Nested Intervals x64 a=250,30 noPrep noIns 4003 1,421 ms 6,615 ms 50.0 MB
Materialized Path (identity pr. key mode) 5003 1,621 ms 8,184 ms 57.8 МБ
Materialized Path (attribute mode) 4002 1,269 ms 6,169 ms 46.2 MB

Тест 8. Довільна операція у випадковий вузол (5 рівнів, 1000 вузлів)
Adjacency List 4383 1,330 ms 6,147 ms 53.0 MB
Nested Sets 5003 9,577 ms 24,334 ms 64.8 МБ
Nested Intervals amount=10 7733 8,123 ms 24,031 ms 107.2 MB
Nested Intervals x64 default amount=10 5663 3,761 ms 14,084 ms 75.6 MB
Nested Intervals amount=200,25 4175 1,548 ms 7,223 ms 52.8 MB
Nested Intervals x64 a=250,30 reserve=2 4003 1,541 ms 6,753 ms 50.0 MB
Materialized Path (identity pr. key mode) 5392 3,211 ms 11,771 ms 65.0 MB
Materialized Path (attribute mode) 4377 2,902 ms 10,132 ms 53.2 МБ

Тест 9. Переміщення вузлів на початку <4% (20 з 19657 вузлів)
Adjacency List 112 39 ms 261 ms 4.5 MB
Nested Sets 140 218 ms 566 ms 5.5 MB
Nested Intervals 160 180 ms 573 ms 6.0 MB
Materialized Path (identity pr. key mode) 128 38 ms 307 ms 4.9 MB
Materialized Path (attribute mode) 128 159 ms 495 ms 4.9 MB

Тест 10. Переміщення вузлів з кінця в початок <4% >96% (20 з 19657 вузлів)
Nested Sets 140 16,991 ms 17,845 ms 5.5 MB
Nested Intervals 160 16,972 ms 17,854 ms 6.0 MB
Materialized Path (identity pr. key mode) 132 49 ms 319 ms 4.9 MB
Materialized Path (attribute mode) 132 205 ms 502 ms 4.9 MB
Adjacency List 112 33 ms 217 ms 4.5 MB

Тест 11. Вибір всіх вузлів (19657 шт.)
Adjacency List 1 33 ms 890 ms 179.1 MB
Nested Sets 1 40 ms 1,208 ms 215.2 MB
Nested Intervals 1 42 ms 1,247 ms 225.3 MB
Materialized Path (identity pr. key mode) 1 46 ms 1,240 ms 209.0 MB
Materialized Path (attribute mode) 1 44 ms 1,106 ms 209.0 MB

Тест 12. Вибір дітей і нащадків (для 819 вузлів в середині дерева з 19657 вузлів)
Adjacency List parentJoin=0 childrenJoin=0 2562 720 ms 1,969 ms 36.9 MB
Adjacency List parentJoin=3 childrenJoin=3 2461 704 ms 1,966 ms 35.3 MB
Nested Sets 1641 522 ms 1,585 ms 25.0 MB
Nested Intervals 1641 579 ms 1,657 ms 25.0 MB
Materialized Path (identity pr. key mode) 1641 569 ms 1,626 ms 23.4 MB
Materialized Path (attribute mode) 1641 793 ms 6,552 ms 44.7 MB

Тест 13. Вибірка батьків (для 819 вузлів в середині дерева з 19657 вузлів)
Adjacency List parentJoin=0 childrenJoin=0 3180 948 ms 2,304 ms 51.2 MB
Adjacency List parentJoin=3 childrenJoin=3 1641 486 ms 1,495 ms 30.8 MB
Nested Sets 821 3,238 ms 3,979 ms 20.7 MB
Nested Intervals 821 3,292 ms 4,147 ms 22.0 MB
Materialized Path (identity pr. key mode) 821 292 ms 902 ms 21.2 MB
Materialized Path (attribute mode) 821 582 ms 4,574 ms 24.7 MB

Тест 14. Вибірка сусідніх вузлів (для 819 вузлів в середині дерева з 19657 вузлів)
Adjacency List parentJoin=0 childrenJoin=0 1641 535 ms 1,442 ms 23.7 MB
Adjacency List parentJoin=3 childrenJoin=3 1641 508 ms 1,421 ms 23.6 MB
Nested Sets 1641 513 ms 1,428 ms 24.5 MB
Nested Intervals 1641 19,681 ms 21,326 ms 27.5 MB
Materialized Path (identity pr. key mode) 1641 730 ms 1,695 ms 24.3 MB
Materialized Path (attribute mode) 1641 1,892 ms 2,964 ms 24.3 MB

Тест 15. Вибірка порожніх вузлів (для 819 вузлів в середині дерева з 19657 вузлів)
Adjacency List parentJoin=0 childrenJoin=0 1833 568 ms 1,743 ms 32.6 MB
Adjacency List parentJoin=3 childrenJoin=3 1732 556 ms 1,891 ms 31.3 MB
Nested Sets 821 305 ms 908 ms 18.4 MB
Nested Intervals 821 10,450 ms 11,166 ms 18.8 MB
Materialized Path (identity pr. key mode) 821 7,968 ms 8,434 ms 18.5 MB
Materialized Path (attribute mode) 821 14,349 ms 19,105 ms 21.3 MB

Посилання на GitHub
Adjacency List
Materialized Path
Nested Sets
Nested Intervals
Auto Tree Trait

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

0 коментарів

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