древовидные структуры, почему вложенные множества , а не

[Maxik]

древовидные структуры, почему вложенные множества , а не

например обычная система координат.
Суть в следующем:
Каждый пункт как бы находится в двухмерной системе координат.
Координата X это глубна в дереве. Координата Y это строка в дереве.
Мне кажется это удобнее и нагляднее чем вложенные множества.
А если хранить указатель на родительский объект, то алгоритм становится более устойчив к сбоям. Ведь родительский идентификатор запоминается сразу, а для установки координат (в вложеных множествах процедура весьма похожая) надо обновить всю таблицу. По этому в случае сбоя. всегда можно пересчитать все дерево.

В общем если не сложно, дайте рецензию на эту тему.
Если алгоритм не ясен, то могу расписать подробнее.

 

[DimbIch]

мда туго понял.....
а можно подробнее ??

 

[Maxik]

Ну вы же представляете обычную школьную систему координат.
Теперь мы хотим описать дерево. При том обычное двухмерное, типа форума.
Каждое сообщение этого форума имеет две определяющие величины. Удаленность от начала форума сверху, и удаленность от края. Пример:
сообщение 1.1
сообщение 2.1
--сообщение 3.2
--сообщение 4.2
сообщение 5.1
--сообщение 6.2
--сообщение 7.2
--сообщение 8.2
----сообщение 9.3
----сообщение 10.3
----сообщение 11.3
--сообщение 12.2
--сообщение 13.2
сообщение 14.2

Видите в чем смысл?

 

[su1d]

Maxik, про'google'яйся насчёт "tropashko" и предложенного им метода хранения деревьев Materialized Path with Nested Intervals.
кажется это именно оно самое и есть.

только там своих недостатков куча, и метод пока малоприменим.

 

[Maxik]

Автор оригинала: su1d
Maxik, про'google'яйся насчёт "tropashko" и предложенного им метода хранения деревьев Materialized Path with Nested Intervals.
кажется это именно оно самое и есть.

только там своих недостатков куча, и метод пока малоприменим.

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

Но на самом деле проблема только в то как ограничить выбор ветки по родительскому идентификатору. Для выбора нужно будет ограничить по У сверху и снизу. Но это не сложно.

 

[su1d]

не.. недостаток в том, что слишком быстро кончается integer.
в первом предложенном способе знаменатель возрастает со степенью двойки, что позволяет иметь не более 16 (32) уровней вложенности.

второй способ -- последовательности Фейри уже получше, и у самого Тропашко даже получилось создать дерево на 1М нод.

однако, он пошёл дальше и предложил кодировать дерево через преобразования Мёбиуса, что вроде как уже имеет право на жизнь, хотя даже там числа растут как последовательность Фибоначчи, что тоже налагает существенные ограничения на кол-во нод в дереве.

в общем, самый надёжный и единственно бесконечный способ кодирования -- Adjacency list, где хранится ссылка на родителя. все остальные методы так или иначе накладывают ограничения на макс. кол-во нод в дереве, и Целковские вложенные множества ещё самые добрые, т.к. там зависимость возрастает лишь как 2n.

 

[Popoff]

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

можно ссылку?

 

[_RVK_]

Maxik
Ты лучше раскажи в чем приемущества твоего метода, поред Nested Sets. Новое должно быть лучше старого хотя бы по некоторым критериям.

 

[su1d]

Автор оригинала: Popoff
можно ссылку?

держи: ссылка

 

[SelenIT]

Меня посещала та же (насколько я понял) идея, что у Maxikа (2 координаты - номер строки и уровень вложенности). Основной плюс вижу в удобстве и быстроте построения дерева при выводе.

У меня такая мысль возникла после того, как мне пришлось чинить один старый проект, где дерево >1000 узлов строилось сложной рекурсивной ф-цией по Adjacency List с отдельным запросом к БД для каждого узла (выполнялось это ~12-15 секунд).

 

[su1d]

SelenIT, а как в такой системе выбрать "всех потомков узла Х" ?
всех его предков?
его непосредственных детей?
и т.п.

 

[SelenIT]

В принципе можно, где-то примерно так:

Все потомки: уровень вложенности больше чем у данного элемента, номер в интервале между номером данного элемента и номером ближайшего элемента с не большим, чем у данного эл-та, уровнем вложенности.

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

Предки: группировка по разности уровней вложенности текущего элемента и заданного, разность положительна, выбрать элементы с наибольшим номером, меньшим номера данного, сортировка по разности.

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

 

[su1d]

Все потомки

слишком много JOIN'ов потребуется (2-3 как минимум). БД просто грохнется на больших объёмах.
сравни с выборкой BETWEEN x AND y для Вложенных Множеств или Вложенных Интервалов.

Непосредственные потомки

значит ещё хранить и уровень вложенности? или опять кучу джойнов?

Но можно делать это средствами php при самом выводе

не самое лучшее решение: таскать от БД-сервера к БД-клиенту миллионы записей для того, чтобы вывести 20 из них.

 

[SelenIT]

su1d

слишком много JOIN'ов потребуется (2-3 как минимум).

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

значит ещё хранить и уровень вложенности?

Конечно. И вовсе не "еще и", это и есть сама вторая координата . Тот же запрос, что и для вывода всех потомков + одно дополн. условие. А вот как раз в Nested Sets для этого, AFAIK, нужно или дополн. поле, или дополн. сложности.

миллионы записей

Я и не утверждаю, что эта модель пригодна для такого случая. А вот выбрать 100-150 записей одним простым и быстрым запросом может оказаться быстрее, чем 20 записей более сложным. Все зависит от конкретной ситуации.

 

[su1d]

угу, самой пригодной моделью "для всего" похоже так до сих пор и является лишь Adjacency List (ParentID), а остальные так или иначе накладывают какие-либо ограничения.

на малых объёмах данных и Вложенные Множества оч хороши и удобны... интерес как раз в том, чтобы найти модель, не сильно ограничивающую объёмы, но и предоставляющую более удобный механизм доступа к записям, чем это делается с Adjacency List.

 

[SelenIT]

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

 

[Screjet]

Почему бы не завести сервисную таблицу/записи с описанием сетей/нитей, например.

 

[su1d]

Screjet, в смысле? по-моему, структура дерева, чуть более сложная, чем parentID, и так должна храниться отдельно от данных.

 

[SelenIT]

Screjet, нельзя ли пояснить, что такое описание нитей? Это случайно не Materialized Path?

 

[Screjet]

Что есть:

Помимо родителя нод "знает" индекс своей нити. Индекс нити формируется вместе с корневым нодом. А обратный путь содержит последовательность родителей (Нужен только для определения последовательности).

Если необходимо выбрать все элементы какой либо папки, выбираю всю нить с ИД элеметнов больше ИД папки.

Единственная проблема была с перемещением элеметнов, когда какаято структура перемещается в более позднюю папку/нод. Решил методом переиндексации перемещаемых элементов, т.е. считывал перемещаемый нод/нить в буфер, удалял перемещаемые элементы и вставлял заново в той же структуре, но с новой нитью (по ходу обновляя все связные таблицы если есть). В итоге ИД пермещаемых элементов всегда больше ИД родителя.
Такая операция довольно ресурсоемкая, но опыт показывает, что реорганизация структуры происходит довольно редко.

Может несколько примитивно, но все мои требования удовлетворяет.