Как стать автором
Обновить

Комментарии 23

Не смог с ходу определить, чем данный метод лучше вложеных множеств?
Не совсем понял как хранить в таблице вложенные множества и самое главное извлекать легкими sql запросами нужную информацию.
Сами пишите:
Существует много методов от самых примитивных до очень сложных и возможно слишком сложных. Мы не будем описывать их в этой статье. При желании вы можете найти множество прекрасных обзорных статей в интернете “Google forever”.


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

Если просто взглянуть на таблицу то иерархию увидеть очень сложно. В нашем методе иерархия видна так сказать невооруженным взглядом.

В принципе преимущество метода в его прозрачном представлении.

Упомянутый Вами метод на хабре очень напоминает Joe Celko, однако могу ошибаться не успел прочесть внимательно.

Да, это он и есть. (только ещё level добавили для ускорения)

А зачем нужно, что бы иерархия была видна с первого взгляда на служебные поля?
Ну например чтобы внести в базу небольшую иерархию ничего кроме кроме командной строки не нужно. Посмотрев на таблицу Вы сразу понимаете какой insert должны сделать.

Если закралась ошибка то найти ее не составляет труда. Все ясно видно прямо на таблице.

Вывод «всего дерева» (Cartesius) — это самый простой запрос который можно придумать. Быстрее него я не знаю что может работать. Сравните эту задачу с Joe Celko.

В принципе это только мое частное мнение, что все вышесказанное преимущества. Может кому-то удобен метод Joe Celko.

Однако меня неудобства метода Joe Celko и побудили создать свой, совершенно отличный.

Как-то слишком надуманно.

Мелкую иерархию и для вложенных можно внести.
Найти, тоже.
А в чём проблема вывести дерево я не понял.

Однако меня неудобства метода Joe Celko и побудили создать свой, совершенно отличный.

А тут у вас казус Архимеда.
Мелкую иерархию и для вложенных можно внести.

Можно не спорю. Вопрос, что легче.

А в чём проблема вывести дерево я не понял.


Все дерево

Метод Joe Celko

SELECT node.category_id, node.name, (COUNT(parent.name) - 1) AS depth
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft 


Метод CARTESIUS

SELECT category_id, name, ord, dep FROM z_nested_category WHERE ord < (SELECT MAX(ord) FROM z_nested_category) ORDER by ord 


Сравните запросы

Вот из статьи поссылке:
SELECT node.id, node.name, node.level
FROM ns_tree AS node,
ns_tree AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND parent.id = 1
ORDER BY node.lft;

Простой запросик.
А в варианте Картезиус — подзапросы.
В запросе на все дерево ( Joe Celko) одна таблица ns_tree участвует 2 раза

FROM ns_tree AS node, ns_tree AS parent

А в варианте Картезиус — подзапросы.

SELECT MAX(ord) FROM z_nested_category

Если заметите выполняется один раз непосредственно перед основным запросом. Т.е почти нагрузки не несет.
При желании его можно убрать и просто отсекать один последний элемент ответа (сartesius_plug). Тогда запрос будет
SELECT category_id, name, ord, dep FROM z_nested_category  ORDER by ord 

Думаю проще трудно придумать.
Но в скорости выполнения это почти ничего не даст потому как
SELECT MAX(ord) FROM z_nested_category

запрос ничтожно маленький.
Это для вывода ветки дерева по её ID.
Вывести всё дерево как у вас:

SELECT node.id, node.name, node.level
FROM ns_tree AS node
ORDER BY node.lft;
Ваша правда. Однако чтобы мы получим в результате. Примерно что-то вроде

name		left		right
node_0		1		14
node_0_1	2		7
node_0_1_1	3		4
node_0_1_2	5		6
node_0_2	8		11
node_0_2_1	9		10
node_0_3	12		13


Теперь вывод для Cartesius

name		ord		dep
node_0		0		0
node_0_1	1		1
node_0_1_1	2		2
node_0_1_2	3		2
node_0_2	4		1
node_0_2_1	5		2
node_0_3	6		1


Вопрос в том из чего построить json xml или другую многомерную структуру легче?

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

Мне апеллировать параметрами «последовательности» и «уровнем вложенности» легче чем треком червя по левой и правой стороне узлов дерева.
«Последовательность» и «уровень вложенности» это то, что видно, когда просто смотришь на дерево.

Из второго результата мне и построить многомерный массив, json или xml намного легче (одним прогоном цикла). Причем без выворота мозга:).

Опят таки дело вкуса. Может кому-то с треком червя удобнее. Не спорю.
Для сравнения, запрос на более предназначенных для таких вещей СУБД:
-- запрос имён узлов всего поддерева --
SELECT name , parent FROM ( TRAVERSE child FROM node )

Не совсем понял как хранить в таблице вложенные множества

Пожалуй это главное в вашем посте
Согласен. Я просто не совсем понял
чем данный метод лучше вложеных множеств

image

Моим студентам эта картинка обычно помогает понять, что такое метод вложенных множеств. Без всяких дурацких правил обхода узлов.
А почему бы не использовать дробные координаты?
Тогда добавление/удаление узла не затронет координаты других?
В одной из статей на хабре по nested sets упоминалось, что дробные числа имеют ограниченную точность. Хотя как по мне, это довольно надуманный аргумент, так как в подавляющем большинстве задач этой точности должно хватить, а на больших данных, возможно, уже стоит смотреть в сторону нереляционных СУБД.

Упс, это был ответ на комментарий выше от 4dmonster.
Кстати, в предложенных примерах операций нет ещё операции «перенести ветку с потомками в другую ветку»
Вот процедура переноса:

sp_move
CREATE  PROCEDURE `sp_move`(
                                                      IN id_move_menu INT,
                                                      IN id_menu INT,
                                                      IN direct INT
                                                     )
BEGIN

DECLARE menu_ord INT;
DECLARE menu_dep INT;
DECLARE move_ord INT;
DECLARE move_dep INT;
DECLARE count_id INT;
DECLARE max_ord INT;
DECLARE rezult_ord INT;
DECLARE rezult_dep INT;
DECLARE max_ord_n INT;
DECLARE point_to_plus_ord INT;


    SELECT COUNT(id) INTO count_id FROM tree
            WHERE ord >= (SELECT ord FROM tree WHERE id =id_move_menu)
            AND ord < (SELECT MIN(ord) FROM tree WHERE ord>(SELECT ord FROM tree WHERE id=id_move_menu) AND dep<=(SELECT dep FROM tree WHERE id=id_move_menu));

 		SELECT ord, dep INTO move_ord, move_dep FROM tree WHERE id = id_move_menu;

 		SELECT MIN(ord) INTO max_ord FROM tree WHERE ord>(SELECT ord FROM tree WHERE id=id_move_menu) AND dep<=(SELECT dep FROM tree WHERE id=id_move_menu);

 		UPDATE tree SET m_i = 1 WHERE ord >= move_ord AND ord < max_ord;

 		UPDATE tree SET ord = ord-count_id WHERE ord >= max_ord AND m_i = 0;

 		SELECT ord, dep INTO menu_ord, menu_dep FROM tree WHERE id=id_menu;

    IF (direct=5) THEN
 		    SET point_to_plus_ord=menu_ord;
    ELSEIF (direct=6) THEN
 		    SELECT MIN(ord) INTO max_ord FROM tree WHERE ord>(SELECT ord FROM tree WHERE id=id_menu) AND dep<=(SELECT dep FROM tree WHERE id=id_menu) AND m_i=0;
        SET point_to_plus_ord=max_ord;
     ELSEIF (direct=7) THEN
             SET point_to_plus_ord=menu_ord+1;
     END IF;

     UPDATE tree SET ord = ord+count_id WHERE ord >= point_to_plus_ord AND m_i = 0;

     IF (direct=5 || direct=6) THEN
 		 UPDATE tree SET ord=ord-move_ord+point_to_plus_ord, dep=dep-move_dep+menu_dep WHERE m_i = 1;
     ELSEIF (direct=7) THEN
         UPDATE tree SET ord=ord-move_ord+point_to_plus_ord, dep=dep-move_dep+menu_dep+1 WHERE m_i = 1;
    END IF;

    UPDATE tree SET m_i=0 WHERE m_i=1;

END$$



IN id_move_menu INT — id узла который будет переноситься
IN id_menu INT — id узла куда переноситься
IN direct INT — (5-поставить над id_menu) (6-поставить под id_menu) (7-поставить как потомка id_menu)

Процедура выдрал из строго проекта — там frontend-e использовалось «ExtJ дерево» поэтому по задаче потребовалось «над», «под», «как ребенок».
Но логика как делается move в процедуре есть.

Если будут вопросы, пишите отвечу.
PostgreSQL, ltree, with recursive? не, не слышали…
Согласен, что такая структура наглядна + эффективна при запросах на селект.

Однако, вставка\изменение\удаление крайне неэффективна.
При большом размере таблицы вставка записи в начало иерархии займёт огромное время + если СУБД блокировочная, то это будет эксклюзивная блокировка всей таблицы = полная недоступность её для читателей данных на всё это время.

Т.е. для условно-постоянной информации такое решение, возможно, подойдет но не более того.
Нет нужды при удалении перенумеровывать все ветки, ну будет дырка — не беда. Нужна процедура для пересчёта по-порядку и запускать её иногда.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории