Pull to refresh

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

Reading time 9 min
Views 9.5K
Лучше совсем не помышлять об отыскании каких бы то ни было истин, чем делать это без всякого метода. (Рене Декарт)

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;
Tags:
Hubs:
+3
Comments 23
Comments Comments 23

Articles