Tree of nested sets - определение кол-ва затронутых записей до выполнения запроса

Rin · 11 Окт 2007

Tree of nested sets - определение кол-ва затронутых записей до выполнения запроса

Вопрос по деревьям модели вложенных множеств.
Как известно, перед вставкой записи в дерево (запросом INSERT) необходимо сделать смещение левого или правого поддерева.
Для вставки записи в конец списка дочерних узлов запросы будут следующими:

Код:

-- справа:
UPDATE ?#:table
   SET ns_left  = IF (ns_left > ?i:ns_left, ns_left + ?i:delta, ns_left),
       ns_right = ns_right + ?i:delta
WHERE ns_right >= ?i:ns_right;

-- слева:
UPDATE ?#:table
   SET ns_right = IF (ns_right < ?i:ns_right, ns_right - ?i:delta, ns_right),
       ns_left  = ns_left - ?i:delta
 WHERE ns_left < ?i:ns_right;

?#:table -- название таблицы дерева
?i:ns_left, ?i:ns_right -- числовые значения родительского узла
?i:delta -- значение равно 2.

Возможно ли определить кол-во затронутых записей (~ формулы для 2-х случаев: слева и справа), которые будут обновлены ДО выполнения запроса UPDATE в БД? Было бы неплохо добавить LIMIT в sql запросы а так же принимать решение для выбора правого или левого обновления.

Popoff · 11 Окт 2007

Rin
В моём модуле:
http://popoff.donetsk.ua/text/work/libs/mysql/tree/
реализована функциональность, когда система автоматически выбирает, следует ли делать смещение слева или справа от вставляемой вершины. Посмотрите и сделайте себе также.

Rin · 12 Окт 2007

Popoff
Спасибо, гляну.
А кол-во затронутых записей до выполнения запроса пробовали вычислять?

Popoff · 12 Окт 2007

Пробовал.

Rin · 14 Окт 2007

Видимо, без SQL запроса не обойтись, вот решение.

Код:

SELECT -- COUNT(*) AS total,
       SUM(ns_left  <  ?i:ns_right) AS limit_left,
       SUM(ns_right >= ?i:ns_right) AS limit_right,
       IF (SUM(ns_right >= ?i:ns_right) > COUNT(*) / 2, "left", "right") AS method
  FROM ?#:table

Popoff · 14 Окт 2007

Rin
Считаю, Вам необходимо почитать об основах представления деревьев в виде вложенных множеств. Вот здесь есть неплохая подборка ссылок:
http://phpclub.ru/faq/Tree/NsLink
В особенности рекомендую статьи на английском языке, как наиболее полные и точные.

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

Wicked · 15 Окт 2007

1) я правильно понимаю, что речь идет про случай, когда, у нодов left и right могут уходить в минуса?

2) если это так, то мне непонятно, зачем считать таким извратным способом, перебирая все элементы. Имхо достаточно знать, к какому краю рутового элемента ближе вставляемый элемент. А это в чистом виде что больше, (?i:ns_right - ns_left) или (ns_right - ?i:ns_right) при условии where level = $root.
Надеюсь, это то, что имел в виду товарищ Popoff.

3)

?i:delta -- значение равно 2.

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

4)

?i:ns_left, ?i:ns_right -- числовые значения родительского узла

зачем?
Вам никогда не доводилось вставлять запись не в конец родительской записи, а, например, в серидину, или в начало? Имхо left-позиция, с которой после вставки будет начинаться вставленный элемент, более уместна. Соотв-но, у Вас эта left-позиция ограничена только right'ом родительского элемента, тогда как она может принимать left любого из своих намечаемых сиблингов.

Popoff · 15 Окт 2007

Wicked

Имхо достаточно знать, к какому краю рутового элемента ближе вставляемый элемент. А это в чистом виде что больше, (?i:ns_right - ns_left) или (ns_right - ?i:ns_right) при условии where level = $root.
Надеюсь, это то, что имел в виду товарищ Popoff[/b.]

Ну да. Для того, кто разобрался, что означают циферки в дереве, это очевидно

Rin · 15 Окт 2007

Popoff
>Считаю, Вам необходимо почитать об основах представления деревьев в виде вложенных множеств

В 2003-м я написал класс TreeNS, для которого сейчас делаю рефакторинг. А мой ник стоит вторым после Вашего на странице идеальная библиотека.

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

файл mysql.tree.php

Код:

  $count=mysql_query_single("select count(*) from ".$table);
  if($is_left)
  {
    $is_right=mysql_query_single("select count(*) from ".$table." where i_left>=".$r_tree['i_left'])<$count/2;

Вот Ваше решение. Без дополнительных SQL запросов задача не решается.

Wicked

>я правильно понимаю, что речь идет про случай, когда, у нодов left и right могут уходить в минуса?

да

>(?i:ns_right - ns_left) или (ns_right - ?i:ns_right) при условии where level = $root.

Поясните, что есть что.

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

В моей библиотеке есть возможность множественной вставки записей для одного родительского узла в один запрос INSERT. Сейчас, для упрощения, когда ?i:delta = 2, мы рассматриваем вставку только одной записи.

>Вам никогда не доводилось вставлять запись не в конец родительской записи, а, например, в серидину, или в начало?

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

Wicked · 15 Окт 2007

Rin

>(?i:ns_right - ns_left) или (ns_right - ?i:ns_right) при условии where level = $root.

Поясните, что есть что.

ns_left, ns_right where level = $root -- я понял, что написал немного неправильно, т.к. в nested sets наличие единственного рутового элемента необязательно. Поправлюсь, что я имел в виду что-то типа min(ns_left), max(ns_right) where 1 -- т.е. границы диапазона, который содержит все дерево. Поскольку ноды дерева на этом диапазоне распределены дискретно равномерно, то оценить кол-во элементов, которые предстоит проапдейтить при левой или при правой вставке, довольно просто расстоянием от точки вставки до концов этого диапазона. Вот и вся идея.

Вот Ваше решение. Без SQL запроса задача не решается.

Формально - да.
Но сразу скажу, что с точки зрения производительности у него решение таки получше, т.к. count вычисляется по индексам, а у Вас происходит fullscan.
Также нужно принимать во внимание, что есть такая замечательная штука как кэширование. И в данном случае требования к актуальности этих данных позволяют кэшировать число (середину диапазона) достаточно вольно.

Popoff · 15 Окт 2007

Rin
В таком случае вынужден признать Ваш вопрос странным %)
Либо непонятно сформулированным %)

Без дополнительных SQL запросов задача не решается.

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

Rin · 15 Окт 2007

Да, я про индексы я забыл.

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

Код:

-- при вставке записей
SELECT IF (?i:ns_right - MIN(ns_left) < MAX(ns_right) - ?i:ns_right, "left", "right") AS method
  FROM ?#:table
-- при удалении записей
SELECT IF (?i:ns_left - MIN(ns_left) < MAX(ns_right) - ?i:ns_right, "left", "right") AS method
  FROM ?#:table

Я проверил, все работает корректно.

-~{}~ 15.10.07 13:31:

>т.к. в nested sets наличие единственного рутового элемента необязательно

обязательно

Wicked · 15 Окт 2007

ну пусть будет обязательно. Тогда неясен Ваш вопрос

)

>(?i:ns_right - ns_left) или (ns_right - ?i:ns_right) при условии where level = $root.
Поясните, что есть что.

Rin · 18 Окт 2007

Ладно, тема исчерпана.

Выложил на всеобщее обозрение:
TreeNS: класс для манипуляции с данными иерархического типа модели вложенных множеств

Tree of nested sets - определение кол-ва затронутых записей до выполнения запроса

Rin

*

Popoff

popoff.donetsk.ua

Rin

*

Popoff

popoff.donetsk.ua

Rin

*

Popoff

popoff.donetsk.ua

Wicked

Новичок

Popoff

popoff.donetsk.ua

Rin

*

Wicked

Новичок

Popoff

popoff.donetsk.ua

Rin

*

Wicked

Новичок

Rin

*