These forums are read-only and for archival purposes only!
Please join our new forums at discourse.kohanaframework.org
Materialized Path plugin for Kohana ORM
  • Привет, ребята! Пару дней назад я спрашивал про плагин, который позволяет работать с деревьями, важным критерием выбора был быстрый select. Мне предложили orm_mptt, но изучив его я понял, что он мне не совсем подходит.
    Представляю на ваш суд свой плагин Kohana_ORM_MP, который реализует хранение деревьев на базе Materialized Path - http://github.com/theshock/kohana-orm-mp

    Из недостатков отмечу ограниченную (30-40 элементов) глубину (так как ключ в базе (поле "path") не может быть дольше 255 символов), но в большинстве случаев этой глубины хватает с избытком.

    Код с примером и инструкцией - на гитхабе: http://github.com/theshock/kohana-orm-mp
  • А чем MPTT не подошел, если не секрет? :)
  • 1. Не очень люблю Нестед Сетс. Не нравится сама идеология
    2. Показался медлительным. Когда добавлял много элементов - винт секунд 20 шуршал и мучался. Эксперименты со своим плагином не проводил. Но один важный для меня момент - сортировка, уверен, будет лучше
    3. Не совсем согласен с апи. Например, метод сортировки мне нравится больше мой - через set_position а не вставкой после другого узла. Вот если во время сортировки человек кинул элемент в конец массива - я должен вставлять его после последнего элемента. Если в начало - перед первым. Если в середину - как хочу. У меня просто указал set_position и все
    4. Поменьше строк в базе данных. У меня 3 (path, level, position). В мптт - 5 (lft, rgt, lvl, scope, parent_id).
    5. Код огромен, в 4 раза больше, чем у меня, недостаёт изящества. Метод move - 100 строк, два экрана. Иногда проскакивает быдлокод:
    public function __get($column)
    {
    switch ($column)
    {
    case 'parent':
    return $this->parent();
    case 'parents':
    return $this->parents();
    case 'children':
    return $this->children();
    case 'first_child':
    return $this->children(FALSE, 'ASC', 1);
    case 'last_child':
    return $this->children(FALSE, 'DESC', 1);
    case 'siblings':
    return $this->siblings();
    case 'root':
    return $this->root();
    case 'roots':
    return $this->roots();
    case 'leaves':
    return $this->leaves();
    case 'descendants':
    return $this->descendants();
    case 'fulltree':
    return $this->fulltree();
    default:
    return parent::__get($column);
    }
    }


    Вместо, скажем:
    public function __get($column)
    {
    if (in_array($column, array(
    'root', 'roots', 'parent', 'parents', 'fulltree', 'children', 'siblings', 'leaves', 'descendants'
    )) return $this->$column();

    switch ($column) {
    case 'first_child':
    return $this->children(FALSE, 'ASC', 1);
    case 'last_child':
    return $this->children(FALSE, 'DESC', 1);
    default:
    return parent::__get($column);
    }
    }


    Но вообще я придираюсь, да. Неплохой плагин на самом деле. Недостатки - мелочёвские. Мой тоже не лишён их, наверное.
  • Не знаю, может это просто модуль так написан, но когда я работал с MPTT (я приспособил Sprig-овский модуль для ORM), все было достаточно быстро. Кстати говоря, parent_id это в MPTT совсем лишнее, странно, почему он там находится, scope нужен только если нужно хранить в одной таблице несколько деревьев.

    MP лично у меня вызывает сомнения не столько в самом ограничении, сколько в том, что нельзя заранее сказать, какое оно, это ограничение. Если часто добавлять/удалять элементы, то его максимальная длина будет еще и уменьшаться (из-за увеличения длины id).

    А в целом - методы разные нужны, методы разные важны :) Спасибо за модуль.
  • Ограничение указать можно - $max_level. 32 - по-умолчанию, которое способно вырержать путь индексов из 7 цифр.
    scope - что значит "несколько деревьев"? с разными корнями?
  • Конечно, индекс из 7 и более цифр на практике можно увидеть довольно редко, но в MySQL INT влезает больше, и есть риск, что когда-нибудь поля path не хватит. Поэтому, наверное, стоит установить ограничение так жестко, чтобы исключить и эту возможность.

    p.s.: Несколько деревьев - это и есть несколько независимых (не пересекающихся) деревьев, с разными корнями.
  • Понял.
  • Values in VARCHAR columns are variable-length strings. The length can be specified as a value from 0 to 255 before MySQL 5.0.3, and 0 to 65,535 in 5.0.3 and later versions.


    С документации. Так что ограничение вложености где-то 5.9к. FYI
  • Кстати говоря, parent_id это в MPTT совсем лишнее, странно, почему он там находится

    Удобно получить непосредственного родителя. Чем вычислять через комбинацию условий lft/rgt/level
  • xobb, path обычно индексируется как unique-key, и может быть максимум 1000 байт. В УТФ это 255 символов (как показала практика). Можно попробовать использовать не мультибайтовую кодировку для этого поля. тогда, по идее, можно повысить максимальную длину.
  • Не могу установить пример. Напишите, пожалуйста, инструкцию, как это сделать. Куда заливать файлы, какие модули требуется включить для работы, и т.п.
  • Не очень люблю Нестед Сетс. Не нравится сама идеология.

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

    Тормознутость - тоже поспорю. Для меня лично имеет значение лишь скорость выборки конечного дерева из базы данных, а нисколько не скорость перемещения. Но я ни за что не поверю, что в какие-то моменты у вас время манипуляции с деревом составляло 2,5с. Это, вероятно, бывает при количестве элементов в дереве, превышающим 5-6-значное число и с уровнем вложенности равным 10. И то сомневаюсь. Да даже предположим на секундочку проект, в котором мы будем использовать эти библиотеки. В большинстве случаев, я думаю, мы дерево будем кешировать, что все-таки оттолкнет вопрос производительности (а у них разница минимальна) на последний план.

    Что касается, например, большего количества полей в таблице вложенных множеств - я не вижу так же в этом особенного недостатка. Подчас существует необходимость вычислить предка в дереве. Так вот в таком случае эта информация уже есть в дереве. И ее не нужно вычислять заново - достаточно просто выбрать ее.

    Кроме того, кстати, ORM_MPTT от @biakaveron - не единственная MPTT-библиотека и на ней свет клином не сошелся ни разу. @biakaveron прости, но это так - есть более интересное решение от @kiall - вот оно https://github.com/kiall/kohana3-orm_mptt (там, правда, тоже не все гладко - встречаются некоторые отхождения от правил кодинга коханы, но для человека вкрадчивого, например, для вас - эта проблема будет решаемой, я думаю).
    Отличительной чертой данной библиотеки является возможность хранения полного пути в базе данных (как и у вашего подхода, кстати).

    А вот в чем действительно проблема - так это в количестве возможных вложенных элементов. Думаю, большинство со мной согласится, что возможности применения MPTT в том виде, в котором они есть сейчас, гораздо обширнее. У вас есть существенное ограничение на количество элементов в дереве. В частном случае да, это не проблема. Но когда вам понадобится организовать древовидные комментарии к каждой новости, я думаю, это вылезет серьезным препятствием.

    Лично мое отношение к materialized path (русского названия пока в общепринятой терминологии пока не встречал) двоякое: с одной стороны, способ довольно изящный и стройный. С другой - какой-то колокольчик все-равно звенит у виска, не позволяя всецело взять этот подход на вооружение.
  • тоже использовал ORM mptt и как раз была реализация для древовидных комментариях. Поэтому ограничение в 32 уровня хватит для этого с головой, так как я не представляю себе ветку в 32 уровня иерархии, и как это все будет отображаться на сайте. Мы вообще ограничили 5-ю уровнями.
  • @Alexeyco
    А чего обижаться-то? Я в свое время эту библиотеку набрасывал под свои нужды, так что неудивительно, что она кому-то покажется не такой удобной :)
  • @ANT
    А как организовано комментирование, скажем, в ЖЖ. Видели? Отображение и все такое... Лично я стараюсь не подстраивать функционал на сайтах под костыли и ограничения библиотек, которые (никому, кстати, не интересно) изобилуют уникальные способы реализации чего угодно. Любое ограничение - пища для троллей, т.к. это все-таки минус в функционал. Конкурентам достаточно преодолеть этот минус и ХОБАНА - у них уже половина твоих посетителей.
  • А почему репозиторий прикрыли?

  • На самом деле, проблема materialized path не только в косяках с вложенностью. Проблемы еще в том, чтобы избавиться от рекурсии. Более подробно описана проблема здесь. И получается, нам либо надо вводить какое-то эфемерное доп. поле, либо изголяться и записывать путь не 1.2.3, а 00000000001.00000000002.00000000003... Ибо ООП, конечно, вещь охеренная. Но не когда на кону производительность. Хоть, конечно, и можно структуру скешировать.

    Как вам кажется, предложенный мной вариант (через sprintf('%011d', $id); нормальный? Потому, что я лично внедря это, не узрел каких-то серьезных ударов по производительности.

    P.S. И получается, кол-во уровней вложенности у нас с 32 уменьшается до 20... В принципе, канает, конечно...

  • Слушайте, люди добрые... я все-таки не понимаю этого алгоритма в конкретно этой реализации. Если строить пути именно так - то это никуда не годится, это не materialized path. Если даже не брать во внимание "косяк" в работе, например, с сортировкой (ссылка на проблему и ее обсуждение выше), то вырисовывается второй непроглядный пипец, состоящий в том, что в путях используются (почему-то) id элементов, а не их порядковые номера. А должны использоваться как раз порядковые номера. При переносе и удалении веток надо пересчитывать пути.

    Автор и все, кто будет использовать данный модуль в своих проектах, очень сильно рискуют, т.к. это все работать не будет (попытайтесь поперемещать туда-сюда ноды и вы увидите, о чем я).

    Другой вариант реализации, так сказать, "малой кровью" существует. Давайте поговорим о нем.

    Итак, что же сейчас

    | id | path      | position | name    |
    |----|-----------|----------|---------|
    | 1  | .1.       | 1        | Garden  |
    | 2  | .1.2.     | 1        | Fruits  |
    | 3  | .1.2.3.   | 1        | Apples  |
    | 4  | .1.2.4.   | 2        | Oranges |
    | 5  | .1.5.     | 2        | Flowers |
    | 6  | .1.5.6.   | 1        | Orchids |
    | 7  | .1.5.7.   | 2        | Roses   |
    | 8  | .1.8.     | 3        | Bananas |

    Видим: Bananas "лежит" не там, где должен - переложим его в "fruits" - в самый конец.

    | id | path      | position | name    |
    |----|-----------|----------|---------|
    | 1  | .1.       | 1        | Garden  |
    | 2  | .1.2.     | 1        | Fruits  |
    | 3  | .1.2.3.   | 1        | Apples  |
    | 4  | .1.2.4.   | 2        | Oranges |
    | 8  | .1.2.8.   | 3        | Bananas |
    | 5  | .1.5.     | 2        | Flowers |
    | 6  | .1.5.6.   | 1        | Orchids |
    | 7  | .1.5.7.   | 2        | Roses   |

    Все вроде бы ничего, но есть одно НО... Оно существенное. Предположим, мы "двигаем" Bananas так, чтобы он шел первым в списке фруктов

    | id | path      | position | name    |
    |----|-----------|----------|---------|
    | 1  | .1.       | 1        | Garden  |
    | 2  | .1.2.     | 1        | Fruits  |
    | 8  | .1.2.8.   | 1        | Bananas |
    | 3  | .1.2.3.   | 2        | Apples  |
    | 4  | .1.2.4.   | 3        | Oranges |
    | 5  | .1.5.     | 2        | Flowers |
    | 6  | .1.5.6.   | 1        | Orchids |
    | 7  | .1.5.7.   | 2        | Roses   |

    И как, скажите-ка мне, выбрать все это великолепие? Как должен выглядеть SQL-запрос? Здесь без рекурсии не обойтись, либо можно конечно обойтись и без нее - с применением лошадиного алгоритма и оператора eval. Но это полнейший бред, на мой взгляд. Запрос SELECT * FROM table_name ORDER BY path выдаст нам массив, в котором Bananas будет в конце списка фруктов.

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

    | id | path      | position | name    |
    |----|-----------|----------|---------|
    | 1  | .1.       | 1        | Garden  |
    | 2  | .1.1.     | 1        | Fruits  |
    | 8  | .1.1.1.   | 1        | Bananas |
    | 3  | .1.1.2.   | 2        | Apples  |
    | 4  | .1.1.3.   | 3        | Oranges |
    | 5  | .1.2.     | 2        | Flowers |
    | 6  | .1.2.1.   | 1        | Orchids |
    | 7  | .1.2.2.   | 2        | Roses   |

    В этом случае поле position становится избыточным, и его можно убрать... Оно никак не снижает производительность (не могу придумать такую ситуацию).

    Либо можно его оставить, но писать в базу путь, не включающий id текущего элемента. То есть:

    | id | path      | position | name    |
    |----|-----------|----------|---------|
    | 1  |           | 1        | Garden  |
    | 2  | .1.       | 1        | Fruits  |
    | 8  | .1.2.     | 1        | Bananas |
    | 3  | .1.2.     | 2        | Apples  |
    | 4  | .1.2.     | 3        | Oranges |
    | 5  | .1.       | 2        | Flowers |
    | 6  | .1.5.     | 1        | Orchids |
    | 7  | .1.5.     | 2        | Roses   |

    В таком случае можно выбрать все дерево без рекурсии запросом SELECT * FROM table_name ORDER BY path, position

    Ситуация с сортировкой (решил-таки разобрать подробнее)

    Предположим, мы убрали из пути id текущего элемента (см. верхнюю таблицу). И элемент Flowers у нас имеет id не 5, а 21... И еще у нас в таблице тусят помимо фруктов и цветов овощи.

    | id | path      | position | name       |
    |----|-----------|----------|------------|
    | 1  |           | 1        | Garden     |
    | 2  | .1.       | 1        | Fruits     |
    | 8  | .1.2.     | 1        | Bananas    |
    | 3  | .1.2.     | 2        | Apples     |
    | 4  | .1.2.     | 3        | Oranges    |
    | 9  | .1.       | 2        | Vegetables |
    | 10 | .1.9.     | 1        | Cucumbers  |
    | 11 | .1.9.     | 2        | Potatoes   |
    | 12 | .1.9.     | 3        | Tomatoes   |
    | 21 | .1.       | 3        | Flowers    |
    | 6  | .1.21.    | 1        | Orchids    |
    | 7  | .1.21.    | 2        | Roses      |

    Ух, большая таблица вышла. Погодите чутка, уже не много осталось. Так вот... Придумайте-ка, пожалуйста, SQL-запрос, который все это великолепие корректно выберет.

    И посему, есть по крайней мере 2 способа исправить данную ситуацию и разрулить все ошибки: 1. Вместо ID писать в путь порядковый номер (position) 2. Вместо путей .1.2.3. писать .000001.000002.000003. - ведь при сортировке SQL расположит числа 1, 2, 11 так: 1, 11, 2...

    В ближайшее время я внесу изменения в данную библиотеку. Следите за новостями.

  • Если кому интересен данный плагин и данный подход, я поправил указанные мной ошибки. Вроде бы все работает, но нужно тестировать.

    Вы можете скачать модуль отсюда

    Отличия:

    • код отрефакторен по стандартам Kohana

    • указанные мной ошибки с формированием путей исправлены

    • добавлена документация в соответствии с последней спецификацией Kohana userguide

    Если нужна информация по вопросам установки: см. доки, которые прилагаются.

    В ближайших планах на версию 0.3:

    • добавление в дистрибутив юниттестов

    • доработка возможности хранить в одной таблице несколько деревьев (scope arrays)

    Автору и зачинщику - уважуха и указание в копирайтах (хоть лицензия и не была указана в исходном модуле, а на письма он не откликается).

  • А пока я с головой ушел в решение проблем несовершенства бытия - кто-то может мне ответить на вопрос - как сильно различается производительность при выборке по полю VARCHAR в отличие от выборки по полю INT?

  • Если полю VARCHAR присвоить индекс UNIQUE KEY, то - значительно быстрее, чем просто INT :)

  • Если дерево в таблице одно - тогда это очень хорошая весть... А если несколько - придется кешировать.

  • а на письма он не откликается

    На какие письма? =) Если что, мой емейл [email protected]

    Вы смотрели конкретно эту реализацию на "боевом" примере?

  • Да... Почитайте эпичные треды чуть выше и поймете, в чем камень преткновения. Если мы используем рекурсию - проблем ноль, но если мы решаем ее не использовать - лезут грабли те еще (см выше).

    Но если юзать рекурсию, то примерно на нескольких сотнях записей операции перемещения и добавления узлов в середину дерева будут вызывать тупняки сервера, по сравнению с которыми MPTT покажется ангельской забавой. Чтобы допилить этот модуль до вменяемого состояния, я сейчас думаю над различными алгоритмами. Но все-таки, как бы постепенно не пришла мне в голову мысль, что лучше использовать родной MPTT, а не выдумывать. Соблазн велик. Выигрыш довольно незначителен, что бы кто на хабре нам ни рисовал.

  • То была корректная реализация, которая правильно работает =) Посмотрите внимательно "load_tree". Мы сортируем по "position". Потом берём самых "высоких" родителей, заносим их в массив. Потом их детей заносим в _children. Это делается не рекурсией, а циклом со сложностью o(2n). При этом поле path у нас unique key.

    Работать с Materialized Path, как будто это Nested Sets - неправильно.

    Попробуйте взять ваш пример, мой код и вывести код так, как в примере. Вы будете приятно удивлены)

    function r_render(array $category) {
        $result = "";
        foreach ($category as $child) {
            $sub_list = r_render($child->children);
            $result  .= "{child->title} {$sub_list}";
        }
        return "{$result}";
    }
    echo r_render(ORM::factory('Category')->roots);
    
  • Какую рекурсию, о чём вы?

  • Лицензия - MIT или LGPL.

  • Ну вообще, как у коханы, BSD. Но если вы против, я тогда грохну репозиторий и плюну :)

    Безусловно, все что вы говорите (с одной стороны) так. Но получается что. Получается внутри Model_Tree::load_tree() мы делаем одну итерацию, при выводе на экран - другую. А ведь массив объектов моделей сильно больше занимает в оперативе, чем просто массив. Это, конечно, в теории все прикольно, но на деле не очень.

    Какую рекурсию? Ну... можно попробовать вставить что-то в середину дерева и увидите, какую рекурсию. А если мы что-то перемещаем, то вообще все весело (если при этом уровней много). Безусловно, что когда мы манипулируем MPTT, там тоже есть каскадные запросы и на запредельных количествах узлов оно все начинает жутко тормозить, но все-таки, конечная, "живая" реализация сильно быстрее, чем сферические бенчмарки.

    Вот если бы получилось процесс переноса нод (и выборки заодно) облегчить и убрать дикое количество каскадных запросов. А еще убрать $model->_primary_key из формирования путей и вставить туда $model->position, то было бы, о чем говорить. Вот я и думаю - стоит ли игра свеч.

    Кстати, это я еще не придираюсь к тому, что у вас совершенно не масштабируемая библиотека вышла. Используются напрямую $this->id вместо $this->{$this->_primary_key} (аналогично поля path и position), несоответствие стандартам оформления исходного кода от Kohana, отсутствие описания методов, отсутствие гайдов, юниттестов. Так что хз.

  • BSD? Ну пусть будет BSD =)

  • И что? Если создать новую ноду:

    1. Получаем родительскую ноду

    2. Вставляем новую ноду, даём ей position = parent.children.length + 1, path = parent.path + this.id

    Если надо поменять позицию внутри дерева - допустим, с 15 на 5 - всех, у кого позиция >= 5 - плюсуем на единицу, а этой - ставим 5.

    Если надо перенести дерево - тут да, придётся перенесённому дереву поменять path на новый и родителю перенесённого дерева изменить position. Но это редкая операция.

    Что еще?

  • Нет, не редкая... К сожалению. У вас запросы формируются каскадно. То есть, на каждого нового потомка по одному запросу. Этого вполне достаточно, чтобы библиотеку назвать "грузной".

    Но лично я располагаю довольно небольшим количеством времени на реализацию древовидных структур и разработку архитектуры для этого, так что, как я уже говорил, вполне возможно, я сдамся.

  • Ну с немаштабируемой, наверное, согласен. Рад, что вы форкнули её.

    Выборка не имеет каскадных запросов.

    Куча запросов есть только в перемещении. По одному на каждый элемент. Но можно сократить до 2-3 запросов, хотя в результате будет менее красивый код. Могу рассказать как, если интересует.

    Чем вам поможет $model->position, вместо $model->id? По-моему будет только хуже.

  • А в Nested Sets перемещение дерева не будет разве за собой тянуть кучу запросов?

  • Да что там думать - через REPLACE. Я уже начитался о теории MP.

    Поможет выбрать все дерево одним запросом. Если почитать эпичный тред - станет понятно, почему надо формировать деревья с position, а путь писать через 00001.00002.00003.

    А высший класс - это делать, чтобы было автоопределение. То есть, подстановка нулей только в случае необходимости (братьев больше 10, 100, 1000). Надеюсь, я понятно излагаю - очень высокая температура, мысли все еле-текут, а спать не хочется.

  • А в Nested Sets перемещение дерева не будет разве за собой тянуть кучу запросов?

    Дак запросов будет, собственно говоря, не куча. Можно посмотреть, хотя бы MPTT от @biakaveron

  • Какой именно тред?

  • Ну хорошо. У нас есть такие данные:

    Garden
        Fruits
            Apples
            Oranges
            Bananas
    Garage
        Cars
            Mersedes
            BMW
        Bicycles
            X3B
    Flowers
        Orchids
        Roses

    И посмотрим на два варианта хранения в базе.

    С id в пути:

    | id | path      | position   | name         |
    |----|-----------|------------|--------------|
    | 1  | .1.       | 1          | Garden       |
    | 2  | .1.2.     |   1        |   Fruits     |
    | 3  | .1.2.3.   |     1      |     Apples   |
    | 4  | .1.2.4.   |     2      |     Oranges  |
    | 5  | .1.2.5.   |     3      |     Bananas  |
    | 6  | .6.       | 2          | Garage       |
    | 7  | .6.7.     |   1        |   Cars       |
    | 8  | .6.7.8.   |     1      |     Mersedes |
    | 9  | .6.7.9.   |     2      |     BMW      |
    | 10 | .6.10.    |   2        |   Bicycles   |
    | 11 | .6.10.11. |     1      |     X3B      |
    | 12 | .12.      | 3          | Flowers      |
    | 13 | .12.13.   |    1       |   Orchids    |
    | 14 | .12.14.   |    2       |   Roses      |

    С position в пути:

    | id | path      | position   | name         |
    |----|-----------|------------|--------------|
    | 1  | .1.       | 1          | Garden       |
    | 2  | .1.1.     |   1        |   Fruits     |
    | 3  | .1.1.1.   |     1      |     Apples   |
    | 4  | .1.1.2.   |     2      |     Oranges  |
    | 5  | .1.1.3.   |     3      |     Bananas  |
    | 6  | .2.       | 2          | Garage       |
    | 7  | .2.1.     |   1        |   Cars       |
    | 8  | .2.1.1.   |     1      |     Mersedes |
    | 9  | .2.1.2.   |     2      |     BMW      |
    | 10 | .2.2.     |   2        |   Bicycles   |
    | 11 | .2.2.1.   |     1      |     X3B      |
    | 12 | .3.       | 3          | Flowers      |
    | 13 | .3.1.     |    1       |   Orchids    |
    | 14 | .3.2.     |    2       |   Roses      |

    Отступов в position и name, естественно в реальной базе нету. Добавил, чтобы легко схватывалось, какова сейчас структура

    Хорошо. Давай теперь перенесём цветы повыше, над гаражом.

    С id в пути:

    | id | path      | position   | name         |
    |----|-----------|------------|--------------|
    | 1  | .1.       | 1          | Garden       |
    | 2  | .1.2.     |   1        |   Fruits     |
    | 3  | .1.2.3.   |     1      |     Apples   |
    | 4  | .1.2.4.   |     2      |     Oranges  |
    | 5  | .1.2.5.   |     3      |     Bananas  |
    | 12 | .12.      | 2          | Flowers      | ↑
    | 13 | .12.13.   |    1       |   Orchids    |
    | 14 | .12.14.   |    2       |   Roses      |
    | 6  | .6.       | 3          | Garage       | ↓
    | 7  | .6.7.     |   1        |   Cars       |
    | 8  | .6.7.8.   |     1      |     Mersedes |
    | 9  | .6.7.9.   |     2      |     BMW      |
    | 10 | .6.10.    |   2        |   Bicycles   |
    | 11 | .6.10.11. |     1      |     X3B      |

    Что у нас поменялось? position у двух полей.

    С position в пути:

    | id | path      | position   | name         |
    |----|-----------|------------|--------------|
    | 1  | .1.       | 1          | Garden       |
    | 2  | .1.1.     |   1        |   Fruits     |
    | 3  | .1.1.1.   |     1      |     Apples   |
    | 4  | .1.1.2.   |     2      |     Oranges  |
    | 5  | .1.1.3.   |     3      |     Bananas  |
    | 12 | .2.       | 2          | Flowers      | ↑
    | 13 | .2.1.     |    1       |   Orchids    |
    | 14 | .2.2.     |    2       |   Roses      |
    | 6  | .3.       | 3          | Garage       | ↓
    | 7  | .3.1.     |   1        |   Cars       |
    | 8  | .3.1.1.   |     1      |     Mersedes |
    | 9  | .3.1.2.   |     2      |     BMW      |
    | 10 | .3.2.     |   2        |   Bicycles   |
    | 11 | .3.2.1.   |     1      |     X3B      |

    Тут мы видим, что меняется path у двух веток. Дальше. Давайте теперь перенесём Flowers в Garden.

    С id в пути:

    | id | path      | position   | name         |
    |----|-----------|------------|--------------|
    | 1  | .1.       | 1          | Garden       |
    | 2  | .1.2.     |   1        |   Fruits     |
    | 3  | .1.2.3.   |     1      |     Apples   |
    | 4  | .1.2.4.   |     2      |     Oranges  |
    | 5  | .1.2.5.   |     3      |     Bananas  |
    | 12 | .1.12.    |   2        |   Flowers    | ↑
    | 13 | .1.12.13. |     1      |     Orchids  |
    | 14 | .1.12.14. |     2      |     Roses    |
    | 6  | .6.       | 2          | Garage       |
    | 7  | .6.7.     |   1        |   Cars       |
    | 8  | .6.7.8.   |     1      |     Mersedes |
    | 9  | .6.7.9.   |     2      |     BMW      |
    | 10 | .6.10.    |   2        |   Bicycles   |
    | 11 | .6.10.11. |     1      |     X3B      |

    Что у нас поменялось? path у каждого элемента перенесённого дерева и position у родителя и всех братьев, что шли после родителя.

    С position в пути:

    | id | path      | position   | name         |
    |----|-----------|------------|--------------|
    | 1  | .1.       | 1          | Garden       |
    | 2  | .1.1.     |   1        |   Fruits     |
    | 3  | .1.1.1.   |     1      |     Apples   |
    | 4  | .1.1.2.   |     2      |     Oranges  |
    | 5  | .1.1.3.   |     3      |     Bananas  |
    | 12 | .1.2.     |   2        |   Flowers    | ↑
    | 13 | .1.2.1.   |      1     |     Orchids  |
    | 14 | .1.2.2.   |      2     |     Roses    |
    | 6  | .2.       | 2          | Garage       |
    | 7  | .2.1.     |   1        |   Cars       |
    | 8  | .2.1.1.   |     1      |     Mersedes |
    | 9  | .2.1.2.   |     2      |     BMW      |
    | 10 | .2.2.     |   2        |   Bicycles   |
    | 11 | .2.2.1.   |     1      |     X3B      |

    Что у нас поменялось? path всех узлов и position родителей всех деревьев после перенесённого включительно.

    Не влезло в одно сообщение, сейчас еще будет

  • Теперь добавим элемент в начало списка

    С id в пути:

    | id | path      | position   | name         |
    |----|-----------|------------|--------------|
    | 15 | .15.      | 1          | Kitchen      |  ←
    | 1  | .1.       | 2          | Garden       |
    | 2  | .1.2.     |   1        |   Fruits     |
    | 3  | .1.2.3.   |     1      |     Apples   |
    | 4  | .1.2.4.   |     2      |     Oranges  |
    | 5  | .1.2.5.   |     3      |     Bananas  |
    | 12 | .1.12.    |   2        |   Flowers    |
    | 13 | .1.12.13. |     1      |     Orchids  |
    | 14 | .1.12.14. |     2      |     Roses    |
    | 6  | .6.       | 3          | Garage       |
    | 7  | .6.7.     |   1        |   Cars       |
    | 8  | .6.7.8.   |     1      |     Mersedes |
    | 9  | .6.7.9.   |     2      |     BMW      |
    | 10 | .6.10.    |   2        |   Bicycles   |
    | 11 | .6.10.11. |     1      |     X3B      |

    Что у нас поменялось? Добавлен элемент. У всех родителей деревьей инкрементировалась позиция (1 лёгкий запрос)

    С position в пути:

    | id | path      | position   | name         |
    |----|-----------|------------|--------------|
    | 15 | .15.      | 1          | Kitchen      |  ←
    | 1  | .2.       | 2          | Garden       |
    | 2  | .2.1.     |   1        |   Fruits     |
    | 3  | .2.1.1.   |     1      |     Apples   |
    | 4  | .2.1.2.   |     2      |     Oranges  |
    | 5  | .2.1.3.   |     3      |     Bananas  |
    | 12 | .2.2.     |   2        |   Flowers    |
    | 13 | .2.2.1.   |      1     |     Orchids  |
    | 14 | .2.2.2.   |      2     |     Roses    |
    | 6  | .3.       | 3          | Garage       |
    | 7  | .3.1.     |   1        |   Cars       |
    | 8  | .3.1.1.   |     1      |     Mersedes |
    | 9  | .3.1.2.   |     2      |     BMW      |
    | 10 | .3.2.     |   2        |   Bicycles   |
    | 11 | .3.2.1.   |     1      |     X3B      |

    Что у нас поменялось ? Path у всех элементов.

    И самое главное - выборка. Как выбрать элемент с id=14 и всех его детей?

    С id в пути (один запрос):

    SELECT * WHERE path LIKE '%.14.%' ORDER BY position

    С position в пути (два запроса):

    SELECT * WHERE id = 14
    SELECT * WHERE path LIKE '{14_path}.%' ORDER BY path

    А еще вопрос, как будет база себя вести при апдейте unique поля, например, когда мы меняем местами path = '.1.' и path = '.2.'. (Это случается просто если поменять местами первых и второй элемент в дереве)

    UPDATE `path` = '.2.' WHERE `path` = '.1.'

    Выскочит ошибка, что path = '.1.' уже существует и только потом выполнится запрос

    UPDATE `path` = '.1.' WHERE `path` = '.2.'

    И да, зачем сортировать по полю path? Оно не содержит данных о порядке! Только вложенность!

  • Тогда все, что у вас получается, это не materialized path

  • Категорично и не аргументированно. Суть MP в хранении полного пути в отдельном поле и моя реализация полностью подходит под это условие.

    Смотрите, например, здесь: http://phpclub.ru/faq/Tree/Mp . Хранится никак не позиция

    Вариант с position - это только частный случай MP и, как видите, совсем не эффективный.

  • Все-равно, запросы в базу при операции переноса и вставку в дерево от того, что мы будем спорить, сами собой не уменьшатся.

  • Ну от использования position вместо id они явно только увеличатся. =) Ещё предложения?)

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

In this Discussion