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

В одном своём проекте на 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 реализованы таким образом, что выполняется метод первого поведения, в котором он существует. Чтобы совместно использовать несколько поведений, надо вызвать модифицирующие дерево методы для каждого подключенного поведения, а для выбирающих из базы методов — наиболее быстрый. Для этого был написан Trait, который выполняет эти функции. Заодно это избавляет от необходимости указывать 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 MB
    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 MB
    Nested Intervals amount=3 noPrepend noIns.  3644        1,271 ms    5,993 ms    48.9 MB
    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 MB

Тест 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 MB
    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 MB
    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 MB
    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 MB
    
Тест 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

Комментарии (6)


  1. SamDark
    05.09.2015 12:04
    +8

    Отличный набор, но надо юнит-тестов как у creocoder.


    1. PaulZi
      05.09.2015 18:34

      Постараюсь сделать.


      1. SamDark
        05.09.2015 20:51
        +1

        Как сделаете — добавляйте в новости на yiifeed.com.


  1. greabock
    05.09.2015 12:06
    +1

    А как же ct?


    1. SamDark
      05.09.2015 14:31

      ct?


    1. PaulZi
      05.09.2015 18:34
      +1

      Честно говоря ни разу не применял шаблон Closure Table, но вообще надо будет сделать потестить.