18.08.2015 10:40
ZentSoft 23 3745 Источник
Лучше совсем не помышлять об отыскании каких бы то ни было истин, чем делать это без всякого метода. (Рене Декарт)

image

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

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

Мы представляем на суд разработчиков метод Cartesius который основан на представлении иерархической структуры на координатной плоскости где каждый узел имеет свою координату в виде двух параметров ord и dep.

Итак приступим. Возьмем для примера следующую иерархию вин.

  • Вина
    • Белые сорта вин
      • Французские белые вина
        • Chardonnay
        • Colombard
        • Folle blanche
        • Ugni blanc
        • Muscadelle
        • Sauvignon
      • Итальянские белые вина
        • Castelli Romani Bianco
        • Tusculum Bianco
    • Красные сорта вин
      • Французские красные вина
        • Cabernet
          • Franc
          • Sauvignon
        • Carmenere
        • Beaujolais nouveau
      • Итальянские красные вина
        • Bardolino
        • Syrah Cabernet
        • Castelli Romani Rosso

Расставим всю эту иерархию на координатной плоскости и получим координаты каждого узла иерархии.

image

Ось Y, которая идет сверху вниз, будем именовать ord (от слова order — порядок), а ось X будем именовать dep (от слова depth — глубина).

Теперь каждый узел имеет свои координаты. Например, Bardolino (ord 20, dep 3), Chardonnay (ord 3, dep 3), Sauvignon (ord 16, dep 4) и т.д.

Создадим SQL таблицу и занесем эти данные в нее. (в данной статье все примеры разработаны под СУБД MySQL).

CREATE TABLE IF NOT EXISTS `tree` (
  `id` int(11) NOT NULL auto_increment,
  `name` varchar(255) collate utf8_bin NOT NULL,
  `ord` int(11) unsigned NOT NULL,
  `dep` int(11) NOT NULL,
  PRIMARY KEY  (`id`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8 COLLATE=utf8_bin;

INSERT INTO `tree` (`id`, `name`, `ord`, `dep`) VALUES
(1, 'Вина', 0, 0),
(2, 'Белые сорта вин', 1, 1),
(3, 'Французские белые вина', 2, 2),
(4, 'Chardonnay', 3, 3),
(5, 'Colombard', 4, 3),
(6, 'Folle blanche', 5, 3),
(7, 'Ugni blanc', 6, 3),
(8, 'Muscadelle', 7, 3),
(9, 'Chenin', 8, 3),
(10, 'Итальянские белые вина', 9, 2),
(11, 'Castelli Romani Bianco', 10, 3),
(12, 'Tusculum Bianco', 11, 3),
(13, 'Красные сорта вин', 12, 1),
(14, 'Французкие красные вина', 13, 2),
(15, 'Cabernet', 14, 3),
(16, 'Franc', 15, 4),
(17, 'Sauvignon', 16, 4),
(18, 'Carmenere', 17, 3),
(19, 'Beaujolais nouveau', 18, 3),
(20, 'Итальянские красные вина', 19, 2),
(21, 'Bardolino', 20, 3),
(22, 'Syrah Cabernet', 21, 3),
(23, 'Castelli Romani Rosso', 22, 3);

Получим следующую таблицу:
id
 name
 ord
 dep
1
 Вина
 0
 0
2
 Белые сорта вин
 1
 1
3
 Французкие белые вина
 2
 2
4
 Chardonnay
 3
 3
5
 Colombard
 4
 3
6
 Folle blanche
 5
 3
7
 Ugni blanc
 6
 3
8
 Muscadelle
 7
 3
9
 Chenin
 8
 3
10
 Итальянские белые вина
 9
 2
11
 Castelli Romani Bianco
 10
 3
12
 Tusculum Bianco
 11
 3
13
 Красные сорта вин
 12
 1
14
 Французкие красные вина
 13
 2
15
 Cabernet
 14
 3
16
 Franc
 15
 4
17
 Sauvignon
 16
 4
18
 Carmenere
 17
 3
19
 Beaujolais nouveau
 18
 3
20
 Итальянские красные вина
 19
 2
21
 Bardolino
 20
 3
22
 Syrah Cabernet
 21
 3
23
 Castelli Romani Rosso
 22
 3


Итак, у нас есть два параметра ord и dep, а также название и id каждого узла.

Добавим еще один узел под названием сartesius_plug с максимальным значением ord в данном случае 23 и значением dep равным 0. Этот узел всегда будет иметь максимальный ord. Зачем мы это сделали вам станет чуть позже. 

INSERT INTO tree (`id`, `name`, `ord`, `dep`) 
VALUES ('24', ' сartesius_plug', '23', '0');

Определим наиболее распространенные задачи с которыми встречаются разработчики.
  • Вывести все дерево
  • Вывести узел и всех его потомков
  • Вывести узел и потомков первого уровня
  • Вывести узел и всех его предков
  • Добавить узел
  • Удалить узел


Вывести все дерево

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

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

Заметьте, что в нашем примере корневой узел Вина (ord 0, dep 0) только один, но их может быть сколько угодно.

В результате получаем
Name
 ord
 dep
Вина
 0
 0
Белые сорта вин
 1
 1
Французские белые вина
 2
 2
Chardonnay
 3
 3
Colombard
 4
 3
Folle blanche
 5
 3
Ugni blanc
 6
 3
Muscadelle
 7
 3
Chenin
 8
 3
Итальянские белые вина
 9
 2
Castelli Romani Bianco
 10
 3
Tusculum Bianco
 11
 3
Красные сорта вин
 12
 1
Французские красные вина
 13
 2
Cabernet
 14
 3
Franc
 15
 4
Sauvignon
 16
 4
Carmenere
 17
 3
Beaujolais nouveau
 18
 3
Итальянские красные вина
 19
 2
Bardolino
 20
 3
Syrah Cabernet
 21
 3
Castelli Romani Rosso
 22
 3


Из этих данных лего создать XML или JSON. Если у кого-то возникнет интерес можем привести пример построения json-a из этих данных на языке Perl, одним циклом.

Вывести узел и всех его потомков

Предположим, нам необходимо вывести узел “Красные сорта вин” (ord 12, dep 1) и всех его потомков. Следовательно нам необходимо вывести узлы у которых ord >= 12 и который меньше ord-а точки разрыва.

Что такое точка разрыва? Точка разрыва – это узел, который следующим требованиям:
  1. ord должен быть больше ord-а узла потомков которого необходимо вывести
  2. dep должен быть меньше или равно dep-у узла потомков которого необходимо вывести
  3. Он должен иметь минимальный ord из множества узлов отвечающих двум предыдущим условиям

Например, для узла “Французские белые вина” точкой разрыва будет узел “Итальянские белые вина”, его ord больше ord-а узла “Французские белые вина”, dep равен dep-у “Французские белые вина” и, наконец, имеет минимальный ord из множества узлов, который следуют за узлом “Французские белые вина”, то есть первый узел, который следует за потомками узла “Французские белые вина”.

image

Итак, узел “Красные сорта вин” имеет id=13. SQL запрос будет выглядеть следующим образом:
SELECT name, ord, dep FROM tree 
                WHERE ord>=(SELECT ord FROM tree WHERE id=13)
                AND ord<(SELECT MIN(ord) FROM tree  
                               WHERE ord>(SELECT ord FROM tree WHERE id=13)  
                               AND dep<=(SELECT dep FROM tree WHERE id=13)) 
                ORDER BY ord

В выше приведенном запросе
SELECT MIN(ord) FROM tree  
                    WHERE ord>(SELECT ord FROM tree WHERE id=13)  
                      AND dep<=(SELECT dep FROM tree WHERE id=13)

дает нам ord точки разрыва, которой в данном случае является сartesius_plug который имеет ord 23.

Получим результат:
name
 ord
 dep
Красные сорта вин
 12
 1
Французские красные вина
 13
 2
Cabernet
 14
 3
Franc
 15
 4
Sauvignon
 16
 4
Carmenere
 17
 3
Beaujolais nouveau
 18
 3
Итальянские красные вина
 19
 2
Bardolino
 20
 3
Syrah Cabernet
 21
 3
Castelli Romani Rosso
 22
 3


Пришло время объяснить назначение узла сartesius_plug. Заметьте, что у узла “Красные сорта вин” потомки доходят до конца иерархии. Соответственно мы не смогли бы найти точку разрыва для этого узла. Тут нам на помощь приходит сartesius_plug, который всегда имеет максимальный ord и в данном случае будет являться точкой разрыва для узла “Красные сорта вин”.

Если необходимо вывести только потомков, без узла родителя, достаточно взять узлы ord-ы которых больше, но не равны ord-у узла “Красные сорта вин”
SELECT name, ord, dep FROM tree 
                WHERE ord>(SELECT ord FROM tree WHERE id=13)
                AND ord<(SELECT MIN(ord) FROM tree  
                               WHERE ord>(SELECT ord FROM tree WHERE id=13)  
                               AND dep<=(SELECT dep FROM tree WHERE id=13)) 
                ORDER BY ord


Вывести узел и потомков первого уровня

Для вывода узла и потомков только первого уровня достаточно добавить к предыдущему запросу условие ограничивающее глубину: 
dep >= (SELECT dep FROM tree WHERE id=13)
dep <= (SELECT dep+1 FROM tree where id=13)


SQL запрос будет выглядеть следующим образом:
SELECT id, name, ord, dep FROM tree
                       WHERE ord >= ( SELECT ord FROM tree WHERE id=13 ) 
                       AND ord < ( SELECT MIN( ord ) FROM tree 
                            WHERE ord > ( SELECT ord FROM tree WHERE id=13 ) 
                            AND dep <= ( SELECT dep FROM tree WHERE id=13 ) ) 
                      AND dep >= (SELECT dep FROM tree WHERE id=13)
                      AND dep <= (SELECT dep+1 FROM tree where id=13) 
 ORDER BY ord

Результат:
name
 ord
 dep
Красные сорта вин
 12
 1
Французские красные вина
 13
 2
Итальянские красные вина
 19
 2



Вывести узел и всех его предков

Для решения этой задачи достаточно взглянть на координатную плоскоть. Предками узла “Французкие красные вина” являются вершины желтых столбцов. Таким образом узлы, ord которых меньше ord –а узла “Французкие красные вина” и которые имеют максимальный ord, сгруппированные по dep-у, и, наконец, dep должен быть меньше или равен dep-у узла “Французкие красные вина”.

SQL запрос будет выглядеть следующим образом:
SELECT (SELECT name FROM tree WHERE ord=MAX(a.ord)) AS name
FROM tree a WHERE a.ord<=(SELECT ord FROM tree WHERE id=14) 
AND dep <= (SELECT dep FROM tree WHERE id = 14) 
GROUP BY a.dep ORDER BY a.ord

image

Результат:
  • Вина
  • Красные сорта вин
  • Французские красные вина


Добавить узел

Для добавления нового узла нужно выполнить следующие действия.

А. Если добавляется после какого либо узла например после узла “Tusculum Bianco”
  1. Определяем точку разрыва для “Tusculum Bianco”
  2. Прибавляем к ord-ам, которые больше или равны ord-у точки разрыва единицу
  3. Вставляем новый узел с ord-ом равным ord-у точки разрыва и dep-ом равным dep-у узла “Tusculum Bianco”

B. Если добавляется в качестве потомка например к узлу “Tusculum Bianco”
  • Прибавляем к ord-ам, которые больше ord-а узла “Tusculum Bianco” единицу
  • Вставляем новый узел с ord-ом равным ord-у узла “Tusculum Bianco” + 1 и dep-ом равным dep-у узла “Tusculum Bianco”+1

Лучше всего это делать при помощи процедуры. Ниже приведен код универсальной процедуры.
CREATE DEFINER=`root`@`localhost` PROCEDURE `sp_add`(
                                                     IN relativ_menu int,
                                                     IN direct tinyint,
                                                     IN name_menu varchar(255) charset utf8
                                                    )
BEGIN

DECLARE relativ_menu_ord INT;
DECLARE relativ_menu_dep INT;

    IF (direct=0) THEN

        SELECT ord, dep INTO relativ_menu_ord, relativ_menu_dep FROM tree WHERE id = relativ_menu;
        UPDATE tree SET ord=ord+1 WHERE ord>=relativ_menu_ord;
        INSERT INTO tree (name, ord, dep) VALUES (name_menu, relativ_menu_ord, relativ_menu_dep);

    ELSEIF (direct=1) THEN

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

        SELECT dep INTO relativ_menu_dep FROM tree WHERE id =relativ_menu;
        UPDATE tree SET ord=ord+1 WHERE ord>=relativ_menu_ord;
        INSERT INTO tree (name, ord, dep) VALUES (name_menu, relativ_menu_ord, relativ_menu_dep);

    ELSEIF (direct=2) THEN

        SELECT ord, dep INTO relativ_menu_ord, relativ_menu_dep FROM tree WHERE id =relativ_menu;
        UPDATE tree SET ord=ord+1 WHERE ord>relativ_menu_ord;
        INSERT INTO tree (name, ord, dep) VALUES (name_menu, relativ_menu_ord+1, relativ_menu_dep+1);

    END IF;

END$$

где direct=0 добавление до выбранного узла, direct=1 добавление после выбранного узла, direct=2 добавление потомка к выбранному узлу 

CALL sp_add (12, 0, 'node_name')

Удалить узел

Для удаления узла нужно выполнить следующие действия:

А. Если удаляется один единственный узел например “Cabernet”:
  1. Определяем точку разрыва для “Cabernet”
  2. Отнимаем от ord-ов, которые больше ord-а “Cabernet” единицу
  3. Отнимаем единицу от dep-ов у узлов ord-ы которых больше ord-а “Cabernet” и меньше ord-а точки разрыва
  4. Удаляем узел

B. Если удаляется узел и все его потомки например “Cabernet”:
  1. Определяем точку разрыва для “Cabernet”
  2. Определяем количество удаляемых узлов т.е. сам узел плюс все его потомки.
  3. Удаляем узлы у которых ord-ы больше или равно ord-у удаляемого нода и меньше ord-а точки разрыва
  4. Отнимаем от ord-ов которые больше или равны ord-у точки разрыва число удаляемых узлов которое определили в пункте 2

Лучше всего это делать при помощи процедуры. Ниже приведен код универсальной процедуры.

CREATE DEFINER=`root`@`localhost` PROCEDURE `sp_del`(IN id_menu int, IN direct tinyint)
BEGIN

DECLARE min_ord INT;
DECLARE max_ord INT;
DECLARE count_id INT;
DECLARE menu_ord INT;
DECLARE menu_dep INT;
DECLARE id_node_pr INT;

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

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

IF (direct=0) THEN

    UPDATE tree SET dep=dep-1 WHERE ord > menu_ord AND ord < max_ord;
    UPDATE tree SET ord=ord-1 WHERE ord > menu_ord;
    DELETE FROM tree WHERE id=id_menu;

ELSEIF (direct=1) THEN

    SELECT COUNT(id) INTO count_id FROM tree WHERE ord >= menu_ord AND ord < max_ord;

    DELETE FROM tree WHERE ord >= menu_ord AND ord < max_ord;

    UPDATE tree SET ord=ord-count_id WHERE ord >= max_ord;

END IF;

END$$

где direct=0 удаление одного узла, direct=1 удаление узла и всех его потомков

CALL sp_del(15,0)
CALL sp_del(15,1)

Ну и в завершении общий дамп
CREATE TABLE IF NOT EXISTS `tree` (
`id` int(11) NOT NULL auto_increment,
`name` varchar(255) collate utf8_bin NOT NULL,
`ord` int(11) unsigned NOT NULL,
`dep` int(11) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_bin AUTO_INCREMENT=50;

— — Dumping data for table `tree`
— INSERT INTO `tree` (`id`, `name`, `ord`, `dep`) VALUES
(1, 'Вина', 0, 0),
(2, 'Белые сорта вин', 1, 1),
(3, 'Французские белые вина', 2, 2),
(4, 'Chardonnay', 3, 3),
(5, 'Colombard', 4, 3),
(6, 'Folle blanche', 5, 3),
(7, 'Ugni blanc', 6, 3),
(8, 'Muscadelle', 7, 3),
(9, 'Chenin', 8, 3),
(10, 'Итальянские белые вина', 9, 2),
(11, 'Castelli Romani Bianco', 10, 3),
(12, 'Tusculum Bianco', 11, 3),
(13, 'Красные сорта вин', 12, 1),
(14, 'Французские красные вина', 13, 2),
(15, 'Cabernet', 14, 3),
(16, 'Franc', 15, 4),
(17, 'Sauvignon', 16, 4),
(18, 'Carmenere', 17, 3),
(19, 'Beaujolais nouveau', 18, 3),
(20, 'Итальянские красные вина', 19, 2),
(21, 'Bardolino', 20, 3),
(22, 'Syrah Cabernet', 21, 3),
(24, 'сartesius_plug ', 23, 0),
(23, 'Castelli Romani Rosso', 22, 3);

DELIMITER $$
— — Procedures
— CREATE DEFINER=`root`@`localhost` PROCEDURE `sp_add`(
IN relativ_menu int,
IN direct tinyint,
IN name_menu varchar(255) charset utf8
)
BEGIN

DECLARE relativ_menu_ord INT;
DECLARE relativ_menu_dep INT;

IF (direct=0) THEN

SELECT ord, dep INTO relativ_menu_ord, relativ_menu_dep FROM tree WHERE id = relativ_menu;
UPDATE tree SET ord=ord+1 WHERE ord>=relativ_menu_ord;
INSERT INTO tree (name, ord, dep) VALUES (name_menu, relativ_menu_ord, relativ_menu_dep);

ELSEIF (direct=1) THEN

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

SELECT dep INTO relativ_menu_dep FROM tree WHERE id =relativ_menu;
UPDATE tree SET ord=ord+1 WHERE ord>=relativ_menu_ord;
INSERT INTO tree (name, ord, dep) VALUES (name_menu, relativ_menu_ord, relativ_menu_dep);

ELSEIF (direct=2) THEN

SELECT ord, dep INTO relativ_menu_ord, relativ_menu_dep FROM tree WHERE id =relativ_menu;
UPDATE tree SET ord=ord+1 WHERE ord>relativ_menu_ord;
INSERT INTO tree (name, ord, dep) VALUES (name_menu, relativ_menu_ord+1, relativ_menu_dep+1);

END IF;

END$$

CREATE DEFINER=`root`@`localhost` PROCEDURE `sp_del`(IN id_menu int, IN direct tinyint)
BEGIN

DECLARE min_ord INT;
DECLARE max_ord INT;
DECLARE count_id INT;
DECLARE menu_ord INT;
DECLARE menu_dep INT;
DECLARE id_node_pr INT;

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

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

IF (direct=0) THEN

UPDATE tree SET dep=dep-1 WHERE ord > menu_ord AND ord < max_ord;
UPDATE tree SET ord=ord-1 WHERE ord > menu_ord;
DELETE FROM tree WHERE id=id_menu;

ELSEIF (direct=1) THEN

SELECT COUNT(id) INTO count_id FROM tree WHERE ord >= menu_ord AND ord < max_ord;

DELETE FROM tree WHERE ord >= menu_ord AND ord < max_ord;

UPDATE tree SET ord=ord-count_id WHERE ord >= max_ord;

END IF;

END$$

DELIMITER;

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


  1. 4dmonster
    18.08.2015 13:46
    #8540801
    +2

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


    1. ZentSoft
      18.08.2015 14:15
      #8540869

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


      1. 4dmonster
        18.08.2015 14:20
        #8540887

        Сами пишите:

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


        Вот на хабре.


        1. ZentSoft
          18.08.2015 14:41
          #8540951

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

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

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

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


          1. 4dmonster
            18.08.2015 14:47
            #8540965

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

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


            1. ZentSoft
              18.08.2015 15:08
              #8541025

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

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

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

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

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


              1. 4dmonster
                18.08.2015 15:25
                #8541063

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

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

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

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


                1. ZentSoft
                  18.08.2015 15:41
                  #8541091

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

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

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


                  Все дерево

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


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


                  1. 4dmonster
                    18.08.2015 15:51
                    #8541099
                    +1

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

                    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;

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


                    1. ZentSoft
                      18.08.2015 16:15
                      #8541125

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

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


                      1. 4dmonster
                        18.08.2015 16:33
                        #8541165

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

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


                        1. ZentSoft
                          18.08.2015 22:20
                          #8541603
                          -1

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

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

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


                  1. vintage
                    19.08.2015 15:12
                    #8542213
                    +1

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

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


      1. AlexLeonov
        18.08.2015 14:37
        #8540939
        +2

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

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


        1. ZentSoft
          18.08.2015 14:45
          #8540959
          -1

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

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


          1. AlexLeonov
            18.08.2015 17:41
            #8541303
            +1

            image

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


  1. 4dmonster
    18.08.2015 13:48
    #8540809

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


  1. Reposlav
    18.08.2015 14:52
    #8540983
    +1

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

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


  1. lleo_aha
    19.08.2015 09:18
    #8541785
    +2

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


    1. ZentSoft
      19.08.2015 10:44
      #8541863

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

      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$$


  1. dezconnect
    19.08.2015 10:12
    #8541839
    +1

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


  1. bebop
    21.08.2015 10:44
    #8544405

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

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

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


  1. vlivyur
    21.08.2015 10:59
    #8544437

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