Optimized Nested Sets

[su1d]

Optimized Nested Sets

набрёл тут на одном форуме на интересный пост:
предлагают оптимизировать алгоритм Вложенных Множеств таким образом, чтобы при вставке одной новой записи зараннее создавать "дырки" для нескольких будущих:

            Albert (100,1200)
            /            \
          /                \
    Bert (200,300)    Chuck (400,1100)
                      /    |      \
                    /      |        \
                  /        |          \
                /          |            \
              /            |              \
Donna (500,600)  Eddie (700,800)  Fred (900,1000)

идея неплохая, хоть и имеет свою цену: придётся отказаться от подсчёта кол-ва потомков по формуле: (right - left + 1) >> 1


что мы будем думать по этому поводу, господа?

 

[Макс]

su1d
хмм, я пока даже не представляю как в этом случае написать запросы для переноса узла (с потомками) к другому родителю.
Старая структура позволяет делать сравнительно сложные расчеты - ну например кол-во узлов между двумя любыми узлами, зная только данные об этих 2-х узлах (это использовалось в методе moveAll())

Нагрузку при вставке узла это конечно снимет, но усложнит выборки некоторые.

ЗЫ
Кстати, ты не думал внести в таблицу еще одно поле - tree_id (идентификатор дерева) и хранить таким образом несколько маленьких деревьев вместо одно большого ?
(например древовидный форум. каждый тред - отдельное дерево в таблице. Тогда добавление нового сообщения в тред, не затронит другие треды)

 

[Sad Spirit]

Nested intervals?

 

[pachanga]

Самое интересное, что новая книга Joe Celko: SQL Tree Ierarchies(как-то так) содержит решение данной проблемы, вот где бы ее найти....

Оригинальная идея здесь:
http://searchdatabase.techtarget.co...i537290,00.html (требует регистрации)

 

[su1d]

Целко "работает на настоящем SQL" (© Целко), поэтому вовсю использует хранимые процедуры и объединения и суб-запросы. всяко, там всегда можно воткнуть лишний SELECT COUNT(*) -- никто ничего и не заметит. на мускуле же придётся поизвращаться.


я тут подумал децл над алгоритмом.

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

- так или иначе, нужна будет функция балансировки дерева, реиндексирующая всё дерево, выравнивая "расстояния" между нодами. в принципе, её можно будет хоть по крону запускать, т.к. работать она будет довольно-таки долго уже на паре десятков тысяч нод. что плохо, похоже придётся LOCK'ать (только на запись, и то хорошо) всю таблицу на время работы.

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

 

[pachanga]

Автор оригинала: su1d
Целко "работает на настоящем SQL" (© Целко), поэтому вовсю использует хранимые процедуры и объединения и суб-запросы. всяко, там всегда можно воткнуть лишний SELECT COUNT(*) -- никто ничего и не заметит. на мускуле же придётся поизвращаться.

Согласен, но к Celko я питаю глубокое уважение

я тут подумал децл над алгоритмом.

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

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

- так или иначе, нужна будет функция балансировки дерева, реиндексирующая всё дерево, выравнивая "расстояния" между нодами. в принципе, её можно будет хоть по крону запускать, т.к. работать она будет довольно-таки долго уже на паре десятков тысяч нод. что плохо, похоже придётся LOCK'ать (только на запись, и то хорошо) всю таблицу на время работы.

Что-то типа...

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

MoveAll - в смысле перенести некоторую подветку полностью в иное место?

 

[csa]

как насчет такой идеи:
1. вводим поле active=on|off
2. выборку делаем по записям с active=on
3. обновление дерева (вставку/удаление) - по active=off
4. после завершения обновления дерева лочим всю таблицу, сносим active=on, меняем active=off на on, освобождаем таблицу

лочить обновление дерева можно пользовательскими локами (SELECT/RELEASE LOCK)
все апдейты идут в фоне, локи таблицы должны быть непродолжительными,
хотя тут придется перестраивать все индексы при удалении active=on..

-~{}~ 01.04.04 19:10:

но такой путь оставляет все преимущества классической модели

 

[pachanga]

Автор оригинала: csa
как насчет такой идеи:
1. вводим поле active=on|off
2. выборку делаем по записям с active=on
3. обновление дерева (вставку/удаление) - по active=off
4. после завершения обновления дерева лочим всю таблицу, сносим active=on, меняем active=off на on, освобождаем таблицу

но такой путь оставляет все преимущества классической модели
....

как-то не очень элегантно...

как вариант мы так же подумываем над тем, чтобы на время тяжелых batch insert операций(типа полный каталог предприятия на 1C) отключать расстановку l и r, а после операции расставить l и r, используя parent_id(для удобства мы храним parent_id)

никаких других мыслей пока нет?

-~{}~ 06.04.04 18:30:

Кстати, только что наткнулся:

http://groups.google.com/groups?q=g:thl434721241d&dq=&hl=en&lr=&ie=UTF-8&[email protected]

 

[csa]

Автор оригинала: pacha
как-то не очень элегантно...

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

 

[pachanga]

Вот тут еще интересная инфа(причем наш человек писал):

http://www.dbazine.com/tropashko4.shtml
http://arxiv.org/html/cs.DB/0401014

-~{}~ 07.04.04 17:22:

Автор оригинала: Sad Spirit
Nested intervals?

Не пытался заимплементить?

 

[Sad Spirit]

Автор оригинала: pacha
Не пытался заимплементить?

Пока нет, щас я деревья использую только для более-менее статичных структур, Nested Sets хватает.

Кроме того, если я и буду реализовывать, то на процедурном языке (о чём, собственно, и в статье сказано).

 

[pachanga]

Кстати, можно ли в одном запросе по выборке nested set дерева учитывать некоторую сортировку детей внутри родителя?

 

[Sad Spirit]

Автор оригинала: pacha
Кстати, можно ли в одном запросе по выборке nested set дерева учитывать некоторую сортировку детей внутри родителя?

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

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

 

[pachanga]

Жесткое задание узлов и сортировка целой ветки средствами php - нехорошо....

Я так понимаю, что под страшным sql имеется в виду нечто с mysql несовместимое?

 

[Sad Spirit]

Автор оригинала: pacha
Я так понимаю, что под страшным sql имеется в виду нечто с mysql несовместимое?

сорри, я прогнал, забыл про очевидную вещь: чтобы получить на клиенте структуру дерева, результат запроса должен быть отсортирован по полю "левое значение".

сортировать надо уже построенное дерево, выходит так.

 

[pachanga]

Нехорошо однако....

Это особенно полезно для тех случаев, когда выборка лимитированнная.
Получается, если нельзя так сделать, то дерево всегда необходимо получать целиком. php умрет если дерево размером 100k

Однозначно должен быть выход

 

[csa]

Автор оригинала: pacha
Однозначно должен быть выход

другая модель

 

[pachanga]

а подробнее?

 

[csa]

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

 

[Bred Vilchec]

Кстати, использовать рекурсию в деревьях на таблицах
id - parent_id не обязательно. Нужно добавить еще одно поле - level, куда записывать уровень вложения (конечно избыточность, но по сравнению с Nested Sets...). Например, одну из самых обычных задач - получение всех родителей данной ветки можно решить многократным объединением таблицы самой с собой. Получается всего два быстрых запроса:
1. Получает для данного id объекта его level
2. По level'у скрипт циклом собирает второй запрос, например вот так:

SELECT 
u0.user_id AS user_0, 
u1.user_id AS user_1
FROM 
users_tree AS u0, users_tree AS u1 
WHERE u0.user_id = '4' AND u1.user_id = u0.parent_id AND u1.parent_id=0

Хотя знающие люди говорят, что level не обязателен, что можно например, 50 раз объединять таблицу саму с собой для получения потомков/родителей (лишние значения будут просто NULL) и это кстати не будет тормозить БД (ей практически безразлично 3 или 53 раза join'иться). Однако что-то мне это не очень нравится, вдруг например вложенность бужет больше чем мы предполагаем? ну и лишние по размеру запросы порождают больший трафик..

Вообщем без рекурсии вполне можно обойтись. Я немножко погонял свой способ на тестах, оказалось, что например родители объекта с level == 30 в таблице с 1 000 000 записей вибираются менее чем за 0,1 секунду, что очень даже.