Производительность Nested Sets (множественные хозяева)

[fisher]

да, ясно
имхо это самый эффективный способ для неглубоких деревьев

 

[Sad Spirit]

Автор оригинала: pachanga
Именно по причине "Fatal error: Maximum execution time of" мы отказались от использования nested sets.

Сколько элементов было в дереве? Какая СУБД юзалась?

 

[Screjet]

Сколько элементов было в дереве?

Скорее более важен уровень вложенности.

 

[syfisher]

Sad Spirit

>32000. MySQL 4.0, InnoDb. Вставка в batch режиме. Мы так и не дождались окончания работы (работал очень долго). Возможно дело было в InnoDB, но факт - мы перешли на MatherializedPath.

 

[kvf77]

syfisher

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

 

[pachanga]

Народ мы не против nested sets, но факт остается фактом - materialized path в любом случае быстрее на операциях изменения структуры.

 

[Sad Spirit]

Автор оригинала: syfisher
Sad Spirit

>32000. MySQL 4.0, InnoDb. Вставка в batch режиме. Мы так и не дождались окончания работы (работал очень долго). Возможно дело было в InnoDB, но факт - мы перешли на MatherializedPath.

"Вставка в batch режиме" --- это типа 32000 вызовов процедур, в каждой из которых обновляется в среднем 50% записей в таблице?..

Считаем:

\sum_{i=1}^{32000}\frac{i}{2}=256008000

итак, 256 млн. старых версий строк... Насколько я не знаю мыскль, каждую старую версию он сносит в некий сегмент отката.

Интуитивно понятно, что если заранее рассчитать дерево в приложении, то всё пойдёт гораздо веселее, т.к. понадобится тока 32000 операций вставки.

-~{}~ 03.10.05 16:50:

Автор оригинала: pachanga
materialized path в любом случае быстрее на операциях изменения структуры.

ню-ню. по остальным операциям вы так же считали?

 

[pachanga]

Скажу честно, я не великий спец по БД, как скажем Sad Spirit, поэтому когда на большом проекте nested sets начал проседать и сроки поджимали, нам было проще переключиться на materialized path.

Честно говоря, я с огромным любопытством выслушаю, как можно ускорить nested sets на практике, используя MySQL. (все никак не найду времени прочитать Joe Celko's Trees and Hierarchies in SQL for Smarties где приводятся различные способы улучшения данного алгоритма)

 

[Нечто]

Дико извиняюсь, что вмешиваюсь, но почему-то никто не сказал про adjacency list.
На больших деревьях с частым обновлением и переносами - очень удобно. Скорость при выборке ветки средняя, т.к. делается join на каждый уровень вложенности. Ряды в результате получаются нестандартные, но обрабатывать нетрудно.

 

[kvf77]

Нечто

может потому что тема звучит "Производительность Nested Sets"?

 

[pachanga]

Нечто
Ну если ты покажешь способ выборки целой ветки дерева одним запросом(с использованием ANSI SQL 92) , я сегодня же переключусь на adj. list

 

[ONK]

pachanga, если есть в наличии дополнительная таблица связей узлов с их потомками, то проблема исчезает.

 

[pachanga]

...а поддерживать такую таблицу синхронизованной ведь тоже надо. Т.е преимущества adj.list тогда просто сводятся на нет.

 

[Screjet]

pachanga
Неправда. Поддерживать оч. просто. Один раз написал либу и более туда не заглядываю. Недостаток = перемещение нитей: практически таблицу связей нужно переписывать заново.

 

[pachanga]

Так об этом я и говорю, достоинство adj.list и состоит в том, что это решение самое нормализованное с точки зрения БД. Однако если приходится применять еще одну таблицу для поддержки информации об иерархии, то это преимущество исчезает.

-~{}~ 04.10.05 14:04:

Не знаю, как в других БД но вот в Oracle есть в SQL поддержка работы с деревьями, которые в виде adj.list, там даже есть такая роскошь как сортировка сиблингов по некоторому аттрибуту, а это порой очень ценная вещь... но это Oracle

 

[ONK]

Screjet, в отличии от Nested Sets всю таблицу перестраивать не надо, только информацию о узлах, связанных с перемещаемым узлом.
Главный недостаток, это большой объём хранимых данных.
Я дополнительно поддерживаю ещё и таблицу хранения связей каждого узла с его предками. Благодаря этому даже самые сложные операции по модификацией дерева укладываются в 3 - 4 быстрых SQL запроса, а выборка дерева в 1 SQL запрос (в любом направлении).
И того получаем 3 таблицы, хотя таблицы связей можно объединить в одну (путём добавления ещё одного столбца), но от этого будет только путаница, трудноуловимые ошибки при разработке API и дополнительное повышение объёма хранимых данных.

 

[Screjet]

ONK

relation {
  ParentID,
  NodeID,
  Level
}

Что еще может понадобиться?

 

[kvf77]

Screjet

я так понял человек нам рассказывает о helper table только и всего - в связи с этим - зайди на яндекс там по-русски есть статья - но по моему мнению крайне непродуктивный подход - слишком много избытояных данных

 

[ONK]

Screjet

таблица всех потомков каждого узла m:m
descendants {
  NodeID,
  ChildID
}
таблица всех предков каждого узла m:m
parents {
 NodeID,
 ParentID
}

tree{
  NodeID,
  ParentID,
  data,,....
}

Таблица предков мне нужна для достраивания цепочки дерева (со стороны корня) от произвольного узла в скриптах отображения информации и быстрого получения данных для модификации дерева в скриптах управления деревом.
Недостатком метода является избыточность хранимых данных.

 

[Нечто]

Я получаю ветку от узла до корня при одной таблице с помощью user variables MySQL. К сожалению, это не стандарт.