Как отрисовать дерево Nested sets имея все записи?

Question

[Arman]

ДД.
Использую https://github.com/creocoder/yii2-nested-sets
Если через рекурсию то получается легко отрисовать запрашивая потомков друг за другом с ограничением "depth = 1", но выходит кучу запросов.
Хотелось бы получить все записи одним запросом и как-то их отрисовать, обычно видел что используют parent_id, но тут такого нет.

Или можно как-то сделать связи, чтоб 2-3 запросами он построил связи? Сейчас под 30-40 запросов, чтоб отрисовать все.

Или может отказаться от этого, но тогда что лучше? Нужно сделать список разделов из 3-4 уровней с 50-60 элементов

Answer 1

[Максим Тимофеев]

$myModel = MyModel::find()->orderBy('lft')->all();
Далее рекурсия в php. 1 запрос. Вся хитрость в сортировке по lft. Тогда у Вас уже есть правильная упорядоченная структура, остается ей только вложенность сделать базируясь на depth.
Как вариант можете тут глянуть:
https://github.com/yiiext/nested-set-behavior/blob...
там внизу самом пример php есть. Он для yii1, но по сути все так же

Comments

[Arman]

спасибо, интересное решение, тоже думал в эту сторону, но код уж очень начал усложнятся, решил пока оставить на одном запросе и рекурсии

[Александр Леон-Булатов]

Спасибо большое!
Мне именно этот совет и помог!

Единственное, что я изменил это запрос сортировки по двум полям.
И в общем напишу как у меня получилось сделать:

Этот код в файле модели

protected function generateTree()
    {
        $collection = static::find()->orderBy('order_num DESC')->all();
        
        $level = 0;
        
        if (sizeof($collection) > 0) {
            
            foreach ($collection as $n => $item) {
                
                if($item->depth == $level)
                        echo \yii\helpers\Html::endTag('li')."\n";
                else if($item->depth > $level)
                        echo \yii\helpers\Html::beginTag('ul')."\n";
                else
                {
                        echo \yii\helpers\Html::endTag('li')."\n";

                        for( $i = $level-$item->depth; $i; $i-- )
                        {
                                echo \yii\helpers\Html::endTag('ul')."\n";
                                echo \yii\helpers\Html::endTag('li')."\n";
                        }
                }

                echo \yii\helpers\Html::beginTag('li');
                echo \yii\helpers\Html::encode($item->faq_category_name);
                $level = $item->depth;
            }
            
            for ( $i = $level; $i; $i--) {
                    echo \yii\helpers\Html::endTag('li')."\n";
                    echo \yii\helpers\Html::endTag('ul')."\n";
            }   
        }
    }

[Arman]

Александр Булатов, lft ASC и должен сортировать модели, зачем order_num?

[Максим Тимофеев]

Arik, +1 order_num явно лишний

[Александр Леон-Булатов]

Согласен.
Удалил.

Уважаемые знатоки, а не подскажите как мне сделать так, чтобы скрипт добавлял только к подсписку css-класс ?

А то никак логически не получается без рекурсии.

[Максим Тимофеев]

Александр Булатов, подсписок это что?

[Александр Леон-Булатов]

Максим Тимофеев, лучше напишу html код, чтобы визуально ответить:

<ul class="Список">
    <li>Пункт</li>
    <li>Пункт</li>
    <li>
        <ul class="Подсписок">
            <li>Пункт в подсписке</li>
            <li>Пункт в подсписке</li>
            <li>Пункт в подсписке</li>
        </ul>
    </li>
</ul>

[Максим Тимофеев]

Александр Булатов, Ну так есть же depth.

if($depth == 0){
echo 'class="Список"';
}else{
echo 'class="Подсписок"';
}

[Александр Леон-Булатов]

Максим Тимофеев, к сожалению не получается.
И кстати, если поставить сортировку по атрибуту lft то получается вот такой список:

<ul class="foo">
    <li>Пункт 1</li>
    <li>Пункт 2</li>
    <li>Пункт 3</li>
    <li>Пункт 4</li>
    <li>Пункт 5</li>
    <li>Пункт 6</li>
    <li>Пункт 7</li>
    <li>Пункт 8</li>
    <li>Пункт 9</li>
    <li>Пункт 10</li>
    <li>Пункт 11</li>
    <li>Пункт 12</li>
    <li>Пункт 13</li>
    <li>Пункт 14</li>
    <li>Пункт 15</li>
    <li>Пункт 16</li>
</ul>
</li>
<li class="foo">Пункт 17</li>
<li class="foo">Пункт 18</li>
<li class="foo">Пункт 19</li>
<li class="foo">Пункт 20</li>
<li class="foo">Пункт 21

А при сортировке по атрибуту order_num вот такой список, правильный:

</li>
<li class="foo">Пункт 1
    <ul class="Подсписок">
        <li>Пункт подсписка 1</li>
        <li>Пункт подсписка 2</li>
    </ul>
</li>
<li class="foo">Пункт 2
    <ul class="Подсписок">
        <li>Пункт подсписка 1</li>
        <li>Пункт подсписка 2</li>
    </ul>
</li>
<li class="foo">Пункт 3
    <ul class="Подсписок">
        <li>Пункт подсписка 1</li>
    </ul>
</li>
<li class="foo">Пункт 4
    <ul class="Подсписок">
        <li>Пункт подсписка 1</li>
        <li>Пункт подсписка 2</li>
    </ul>
</li>
<li class="foo">Пункт 5
    <ul class="Подсписок">
        <li>Пункт подсписка 1</li>
        <li>Пункт подсписка 2</li>
        <li>Пункт подсписка 3</li>
        <li>Пункт подсписка 4</li>
        <li>Пункт подсписка 5</li>
        <li>Пункт подсписка 6</li>
        <li>Пункт подсписка 7</li>
        <li>Пункт подсписка 8</li>
        <li>Пункт подсписка 9</li>
    </ul>

И если добавить код, который Вы написали, то добавит эти классы ко всем элементам, а нужно только к <li>
верхнего уровня.

Не могли бы Вы, Максим, код привести в пример полностью?

[Александр Леон-Булатов]

Максим Тимофеев, хочу дополнить, у меня в базе несколько деревьев.
Там где одно дерево, я проверил только что, что и в правду работает в этом случае метод описанный выше Вами:

if($depth == 0){
echo 'class="Список"';
}else{
echo 'class="Подсписок"';
}

А там, где много деревьев, не работает таким образом. Не знаете почему так может быть?

При этом отсортировывает корректно только по order_num.

[Максим Тимофеев]

Александр Булатов, откуда ж я знаю, надо смотреть что там в базе у Вас. Видимо каша какая-то. Вы же должны выбирать 1 дерево, соответственно lft и depth должны отрабатывать. Видимо Вы деревья используете не по назначению. ХЗ. Только догадки могут быть.

[Александр Леон-Булатов]

Понял. Ладно буду копать)

[Александр Леон-Булатов]

Максим Тимофеев, спасибо за то, что уделяли время на мой вопрос.
Вот спустя небольшое время размышлений меня осенило, что нужно запрос составлять вот так:

static::find()->orderBy('tree ASC, lft ASC')->all()

и тогда всё работает на ура без рекурсии!

А потом меня ещё осенило. Ведь в документации по этому NestesSets так и написано, что если у вас много деревьев то нужно ещё и по атрибуту tree сортировку делать, если хотите сделать без рекурсии список!

Answer 2

[Arman]

Остановился на таком обходе

$f = function ($f, $categories, $lft = 0, $rgt = null, $depth = 1) {

    if (!$categories) {
        return '';
    }
    $result = '';

    foreach ($categories as $k => $category) {

        $catId = $category->id;
        $catLft = $category->lft;
        $catRgt = $category->rgt;
        $catDepth = $category->depth;

        if ($catDepth != $depth || $catLft < $lft + 1 || ($rgt !== null && $catRgt > $rgt)) {
            continue;
        }

        $result .= $f($f, $categories, $catLft, $catRgt, $catDepth + 1);
    }

    return $result;
};

Answer 3

[ThunderCat]

вроде ничего необычного, делаете запрос и выбираете все записи, затем на пхп делаете рекурсивную функцию и строите дерево, тут вместо parent_id насколько я понял используется указание lft - элемент слева - видимо родитель, и rgt - элемент потомок. Функция ищется поисковиком за минуту, по запросу рекурсия дерево нестед сетс.

Answer 4

[Дмитрий]

Доброе утро.
В ActiveRecord можно делать связи с одной модели на другую. Если Вы об этом, то вот здесь смотрите (Работа со связными данными).

Answer 5

[PaulZi]

Если интересно в моём nested sets расширении есть метод populateTree(), который как раз позволяет запросить из базы одним запросом потомков и актуализировать их связи.

Comments

[Arman]

благодарю.
Буквально вчера читал ваши статьи на хабре об этих расширениях =).
Я мало работал с деревьями, в основном обходил такое рекурсией, а тут разные примеры показали, разобрал что да как и оказалось что рекурсию иногда можно избежать, не знаю насколько это правильно, так, по сути все кишки дерева "наружу" выходят

[PaulZi]

Arik: сама рекурсия не так страшна, если речь, конечно, не о >10k элементов. Nested Set, как показали выше (по ссылке на расширение yii1), можно в принципе обойти без рекурсии, однако читабельность такого кода несколько ниже.

[Евгений]

Когда пытаюсь вызвать метод populateTree() для корневой категории, то он только её и возвращает. Почему так может быть?

[PaulZi]

Евгений, потому что populateTree() загружает дерево из БД в связи `children`, и возвращает сам узел. Таким образом, можно обойти всё дерево обращением, например, $root->children[0]->children[0]->title, при этом обращений к БД более не будет.

[Евгений]

Понятно. Спасибо. Было бы неплохо если был бы метод который бы возвращал бы всё дерево в виде массива.

[PaulZi]

Евгений, для этого есть getDescendants()

Answer 6

[Алексей]

Вот такая функция возвращает всё дерево в виде многомерного массива с добавлением parent_id каждому элементу для удобства. Работает с любым количеством деревьев и любой степенью вложенности.
Далее из этого массива можно что угодно нарисовать.
Если в вашей таблице используется под уровни 'depth' вместо 'lvl', поменяйте
$l = $node['lvl']; на $l = $node['depth']; Соответственно также $r = $node['root']; на $r = $node['tree'], если вместо 'root' в базе 'tree'.
Если таблица без использования множества деревьев, тогда $r = 1;
Используется один запрос к базе. Перебор уровня вложенности можно менять с помощью $level.

$category = CategoryMenu::find()->orderBy('root, lft')->indexBy('id')->asArray()->all();

function getTree($category, $level = 0) {
   $tree = []; $_id = [];
   foreach ($category as $id=>&$node) {
      $l = $node['lvl']; $p = $l-1; $r = $node['root']; $_id[$r][$l] = $id;
      if ($l == $level) {
         $tree[$id] = &$node;
      } elseif ($l > $level) {
         $category[$_id[$r][$p]]['childs'][$id] = &$node;
         $node['parent_id'] = $category[$_id[$r][$p]]['id'];
      }
   }
   return $tree;
}