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

[confguru]

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

Есть вопрос насколько оптимально хранить дерево в
Nested Sets причем если у каждого пользователя оно
должно быть свое и принадлежать только ему
структура примерно такая

id | user_id | cleft | cright | clevel

user_id - текущий пользователь
id - вяжется отдельная таблица

Какие могут быть подводные камни?

 

[Groove]

может быть стоит просто сделать дерево не с одной, а с множеством вершин и каждая из них будет отправной точкой (корнем) дерева каждого пользователя?
ты так делаешь?

 

[kvf77]

admin

думаю, что никаких - у меня так часто данные храянтся. главное правильно индексы расставить и не забывать при операциях вставки, удаления и других, которые изменяют структуру дерева, указывать КАКОЕ ИМЕННО дерево ты меняешь - а то полетят все к чертовой матери - если есть конкретные вопросы - задавай

-~{}~ 15.09.05 14:24:

Groove

ну тебе же написали - у каждого юзверя оно свое - читай внимательно

 

[python]

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

 

[confguru]

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

И как вариант обмен ветками между пользователями..

 

[kvf77]

python

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

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

 

[ONK]

admin, помоему проблем быть не должно. К подводным камням можно отнести необходимость качественного отлова всех багов в коде модификации таблици, иначе будут возникать трудноуловимые ошибки в индексах. Ещё размер дерева для каждого пользователя должен быть не слишком большим, инче модификация дерева будет тормозить.

 

[python]

kvf77
уже понял это из сообщения админа...


admin
так вроде Nested Sets быстрее всего по выборке или есть альтернатива?

 

[kvf77]

python

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

 

[python]

kvf77
да понятно всё про вставку, я первый свой вопрос задал потому что именно о выборке думал. и во втором тоже про выборку написано.

 

[ONK]

python, в Nested Sets много деревьев лучше тем, что при модификации любой ветви дерева производится перестройка индексов каждой записи всего дерева. То есть разделив одно большое дерево на сгруппированные, часто используемые части (очень удачно группировать по принадлежности пользователю) мы получаем значительную экономию процессорных ресурсов при модификации данных.

 

[kvf77]

python

не бывает первого без второго
что толку от быстрой выборки, если частая вставка все затормозит конкретно?

еще раз: выбор алгоритма зависит от цели и данных, нет лучше или хуже

 

[python]

ONK, kvf77
спасибо большое, я правда понял. сразу после сообщения админа

не будем спорить, понятно что можно придумать различные частные случаи задач итд, вопроыафывфывфывс был чисто "теоретический", а именно "разве есть алгоритм быстрее Nested Sets именно при выборке записей".

ЗЫ "фываыфваыфа" - это не специально, по моему у меня клавиатура сломалась...

 

[pachanga]

Немного оффтоп, но все же...в конце-концов мы остановились на materialized path вместо использования nested sets, т.к операции по модификации структуры дерева в случае с nested sets немного удручают по скорости(ну конечно, если не заморачиваться с различными сложными модификациями этого алгоритма). Хотя опять же, все зависит от задачи.

 

[kvf77]

pachanga

если ты все это делаешь в админке, то какая разница сколько времени это занимает? думается занимает около секунды, ну две, ты же не меняешь структуру 50 раз в минуту?

у меня всегда возникал резонный вопрос к оптимизаторам - вы вообще оптимизируете ради оптимизации что ли? надо ж разделять где и что вы оптимизируете и зачем.

 

[su1d]

kvf77
по достижении определённого размера дерева на влож.множ-вах, любое изменение структуры может окончиться с "Fatal error: Maximum execution time of ## seconds exceeded in ...", что не есть хорошо.

 

[kvf77]

su1d

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

 

[pachanga]

kvf77

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

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

 

[fisher]

pachanga:
materialized path - это каждый узел хранит полный путь в виде всех родителей по порядку с разделителем?

 

[pachanga]

fisher

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