Tree/Ni

Материал из PhpWiki.

Перейти к: навигация, поиск

Содержание

Вложенные интервалы (Nested Intervals)

Содержание
  • Готовые библиотеки для работы с вложенными интервалами
  • Часто задаваемые вопросы
  • Как устроен Nested Intervals
  • Смотрите так же
Идеи - как устроен Nested Intervals

popoff

Вложенные интервалы являются попыткой улучшить Вложенные множества. Однако, улучшения в одном месте привели к осложнениям в другом месте.

su1d

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

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

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

Макс

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

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

pachanga

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

su1d

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

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

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

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

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

pachanga

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

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

Смотрите так же

На английском языке:

  • Trees in SQL: Nested Sets and Materialized Path (By Vadim Tropashko)
    • http://www.dbazine.com/oracle/or-articles/tropashko4
  • Relocating Subtrees in Nested Intervals Model (By Vadim Tropashko)
    • http://www.dbazine.com/oracle/or-articles/tropashko5
  • Integer Labeling in Nested Intervals Model (By Vadim Tropashko)
    • http://www.dbazine.com/oracle/or-articles/tropashko6
  • Nested Intervals with Farey Fractions (By Vadim Tropashko)
    • http://arxiv.org/html/cs.DB/0401014
  • Nested Intervals Tree Encoding with Continued Fractions (By Vadim Tropashko)
    • http://arxiv.org/abs/cs.DB/0402051
  • Nested set model with large gaps and spreads in the numbering
    • http://groups.google.com/group/... http://groups.google.com/group/comp.databases.theory/browse_thread/thread/6bbc3a2f326b05b7/3d38f1ca2393c43e#3d38f1ca2393c43e http://groups.google.com/group/...

Оружейный шкаф сейф сапсан.

Реклама