ZentSoft 18 авг 2015 в 10:40

Cartesius — метод хранения и извлечения древовидных структур в реляционных базах данных или SQL деревья без червей и тараканов

9 мин

9.9K

MySQL * SQL *

Из песочницы

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

4dmonster 18 авг 2015 в 10:46

Не смог с ходу определить, чем данный метод лучше вложеных множеств?

ZentSoft 18 авг 2015 в 11:15

Не совсем понял как хранить в таблице вложенные множества и самое главное извлекать легкими sql запросами нужную информацию.

4dmonster 18 авг 2015 в 11:20

Сами пишите:

Существует много методов от самых примитивных до очень сложных и возможно слишком сложных. Мы не будем описывать их в этой статье. При желании вы можете найти множество прекрасных обзорных статей в интернете “Google forever”.

Вот на хабре.

ZentSoft 18 авг 2015 в 11:41

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

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

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

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

4dmonster 18 авг 2015 в 11:47

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

А зачем нужно, что бы иерархия была видна с первого взгляда на служебные поля?

ZentSoft 18 авг 2015 в 12:08

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

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

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

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

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

4dmonster 18 авг 2015 в 12:25

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

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

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

А тут у вас казус Архимеда.

ZentSoft 18 авг 2015 в 12:41

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

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

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

Все дерево

Метод 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

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

4dmonster 18 авг 2015 в 12:51

Вот из статьи поссылке:

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;

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

ZentSoft 18 авг 2015 в 13:15

В запросе на все дерево ( 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

запрос ничтожно маленький.

4dmonster 18 авг 2015 в 13:33

Это для вывода ветки дерева по её ID.
Вывести всё дерево как у вас:

SELECT node.id, node.name, node.level
FROM ns_tree AS node
ORDER BY node.lft;

ZentSoft 18 авг 2015 в 19:20

Ваша правда. Однако чтобы мы получим в результате. Примерно что-то вроде

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 намного легче (одним прогоном цикла). Причем без выворота мозга:).

Опят таки дело вкуса. Может кому-то с треком червя удобнее. Не спорю.

vintage 19 авг 2015 в 12:12

Для сравнения, запрос на более предназначенных для таких вещей СУБД:

-- запрос имён узлов всего поддерева --
SELECT name , parent FROM ( TRAVERSE child FROM node )

AlexLeonov 18 авг 2015 в 11:37

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

Пожалуй это главное в вашем посте

ZentSoft 18 авг 2015 в 11:45

Согласен. Я просто не совсем понял

чем данный метод лучше вложеных множеств

AlexLeonov 18 авг 2015 в 14:41

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

4dmonster 18 авг 2015 в 10:48

А почему бы не использовать дробные координаты?
Тогда добавление/удаление узла не затронет координаты других?

Reposlav 18 авг 2015 в 11:52

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

Упс, это был ответ на комментарий выше от 4dmonster.

lleo_aha 19 авг 2015 в 06:18

Кстати, в предложенных примерах операций нет ещё операции «перенести ветку с потомками в другую ветку»

ZentSoft 19 авг 2015 в 07:44

Вот процедура переноса:

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 в процедуре есть.

Если будут вопросы, пишите отвечу.

dezconnect 19 авг 2015 в 07:12

PostgreSQL, ltree, with recursive? не, не слышали…

bebop 21 авг 2015 в 07:44

Согласен, что такая структура наглядна + эффективна при запросах на селект.

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

Т.е. для условно-постоянной информации такое решение, возможно, подойдет но не более того.

vlivyur 21 авг 2015 в 07:59

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий