Дерево NESTED SETS - подскажите пожалуйста логику расставления ключей

@nepster · Регистрация: 19.09.2009

Author24 — интернет-сервис помощи студентам

Сел за изучение дерева NESTED SETS , но совершенно не понял логику проставления ключей

MySQL

-- ----------------------------
-- Table structure for `tree`
-- ----------------------------
DROP TABLE IF EXISTS `tree`;
CREATE TABLE `tree` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(128) NOT NULL DEFAULT '',
  `left_key` int(10) unsigned NOT NULL DEFAULT '0',
  `right_key` int(10) unsigned NOT NULL DEFAULT '0',
  `level` int(10) unsigned NOT NULL DEFAULT '0',
  PRIMARY KEY (`id`),
  KEY `left_key` (`left_key`,`right_key`,`level`)
) ENGINE=InnoDB AUTO_INCREMENT=13 DEFAULT CHARSET=utf8;
 
-- ----------------------------
-- Records of tree
-- ----------------------------
INSERT INTO `tree` VALUES ('1', 'Овощи', '0', '0', '2');
INSERT INTO `tree` VALUES ('2', 'Картошка', '0', '0', '3');
INSERT INTO `tree` VALUES ('3', 'Капуста', '0', '0', '3');
INSERT INTO `tree` VALUES ('4', 'Буряк', '0', '0', '3');
INSERT INTO `tree` VALUES ('5', 'Фрукты', '0', '0', '2');
INSERT INTO `tree` VALUES ('6', 'Банан', '0', '0', '3');
INSERT INTO `tree` VALUES ('7', 'Киви', '0', '0', '3');
INSERT INTO `tree` VALUES ('8', 'Яблоко', '0', '0', '3');
INSERT INTO `tree` VALUES ('9', 'Ягоды', '0', '0', '2');
INSERT INTO `tree` VALUES ('10', 'Арбуз', '0', '0', '3');
INSERT INTO `tree` VALUES ('11', 'Другое', '0', '0', '2');
INSERT INTO `tree` VALUES ('12', 'Еда', '0', '0', '1');

Сделал тестовую табличку.

Подскажите пожалуйста, как проставляются ключи так, что бы на выходе (прикрепленный файл)

И как в php к примеру можно получить:

Код

*еда
***овощи 
******Картошка
******Капуста
******Буряк
***фрукты 
******Банан
******Киви
******Яблоко
***ягоды 
******Арбуз
***другое

Подскажите пожалуйста логику расставления ключей, а то вообще не могу понять как столб =)

Vovan-VE · 31.10.2012, 19:26

Длинная кривая стрелка - направление рекурсивного обхода всех узлов.
Движемся (на изображении) в одну сторону - left_key, в другую - right_key.

DrobyshevAlex · 31.10.2012, 20:04

http://www.getinfo.ru/article610.html
вот тут графически изображено дерево и проставлены ключи и расписано что они означают

Vovan-VE · 01.11.2012, 19:43

Не по теме:

Сообщение от DrobyshevAlex

вот тут графически изображено дерево и проставлены ключи

Только нарисовано оно там не совсем очевидно.

DrobyshevAlex · 01.11.2012, 20:14

Не по теме:

Ну я по той статье всё понял, если всю читать, может просто глядя на картинку не знаю что это и не очень понятно :)

__PION__ · 12.02.2014, 08:02

ребяты, я вот тоже думаю переходить или нет на nested, смущают 2 вопроса:
1) так и не понял (как раз изучал статью по ссылке), что означают поля left_key и right_key, что они вообще делают?
2) со сменой (изменение родителя, а не простое перемещение) родителя кое-как понятно, но в каталоге (менюшке,.. да и в любом практически дереве) бывает необходимость не смены родителя, а простое смещение нодов друг относительно друга. Как это сделать ума не приложу, видимо из-за того, что ни... не пойму для чего вышеуказанные ключи и как сработают в нужной задаче по перестановке последовательности нодов внутри родителя. например -
1. Авто
1.1 Тойота
1.2 Лада
2. Недвижимость
2.1 Квартиры
2.2 Дома
2.3 Участки
Нужно поменять местами 1.2 и 1.1
или поменять местами родителей 2 -> 1
Как поведут себя ключи не пойму, кто знает подскажите

Добавлено через 3 минуты
забыл такой момент, щас использую обычную таблицу, где дерево строится ч/з родительское id. В чем преимущество nested'a перед таким вот написанием?

@vlaik · 07.07.2014, 05:43

Тоже сел за изучение nested sets, но в плане перемещения веток полная каша в голове. Уже кучу статей нашел, и везде одно и то же написано так, что вообще ничего не понять.

С ключами вроде ясн , уровень вложенности - и ежу понятно

Но вот никак не въеду я c перемещением веток, вроде самая развернутая статья http://www.getinfo.ru/article610.html:

Берем пример с картинки:

Дерево NESTED SETS - подскажите пожалуйста логику расставления ключей

"Из неё можно увидеть, что узел может перемещаться только в две разные области: вышестоящих и нижестоящих узлов." - вроде как отсюда следует, что если мы перемещаем узел с id=9 (left_key=25 и right_key=30), то, если опираться на картинку:
вышестоящий узел - это любой узел, у которого left_key меньше значения left_key перемещаемого узла (т.е. меньше 25)
Нижестоящий узел - это любой узел, у которого left_key больше значения left_key перемещаемого узла (т.е. больше 25)
И далее написано:
"1. Перемещение вверх по дереву (в область вышестоящих узлов), включает в себя:
Перенос ветки (узла) в подчинение нижестоящему(????) по дереву узлу;
Перенос ветки (узла) вверх без изменения родительского узла (изменение порядка узлов); "

Окей. К примеру хотим перенести узел с id=9 в узел c id=5, т.е. переносим в область вышестоящих узлов, т.е. в подчинение не нижестоящему (как в цитате из статьи), в вышестоящему узлу... Либо идет речь что нижестоящий по дереву - это и есть более вышестоящий в иерархии?

Короче вся проблема сводится не к тому, как перенести определенный узел, а к тому, как сделать проверку куда он переносится. Так как от этого зависит порядок перестроения всего дерева.

Не совсем понятно как проводить проверку, как сравнивать ключи чтобы понимать какие узлы должны быть обновлены

@Airclaim · 19.02.2016, 22:16

Вопрос к гуру.

Как найти красивое решение для построения в базе данных MySQL таблицы через NESTED SETS?

Есть дерево,как пример
root
.Книги
..Книги художественные
...Исторические
...До 1917
..Книги документальные
...Книги о войне
...Воспоминания
.Письма
..Письма личные
..Письма исторические
...Письма писателей
и так далее....

Как построить Дерева каталогов NESTED SETS?

Читал, читал, а все же знаний не хватает.
Понимаю, что такое надо применить.
http://www.php.su/articles/?cat=phpdb&page=013
http://www.poiu.ru/lessons/index.php-18.htm

Кто подскажет как создать таблицу запросов?
Вывод должен быть таким.
id pid numleft numright numlevel title

Vovan-VE 13208 / 6596 / 1041 Регистрация: 10.01.2008 Сообщений: 15,069
	31.10.2012, 19:26	2
	Длинная кривая стрелка - направление рекурсивного обхода всех узлов. Движемся (на изображении) в одну сторону - left_key, в другую - right_key. Миниатюры 2

DrobyshevAlex 1178 / 1128 / 94 Регистрация: 31.05.2012 Сообщений: 3,060
	31.10.2012, 20:04	3
	http://www.getinfo.ru/article610.html вот тут графически изображено дерево и проставлены ключи и расписано что они означают 1

Vovan-VE
	01.11.2012, 19:43 #4
	Не по теме: Сообщение от DrobyshevAlex вот тут графически изображено дерево и проставлены ключи Только нарисовано оно там не совсем очевидно. 1

DrobyshevAlex
	01.11.2012, 20:14 #5
	Не по теме: Ну я по той статье всё понял, если всю читать, может просто глядя на картинку не знаю что это и не очень понятно :) 1

__PION__ 960 / 801 / 85 Регистрация: 21.07.2010 Сообщений: 3,522
	12.02.2014, 08:02	6
	ребяты, я вот тоже думаю переходить или нет на nested, смущают 2 вопроса: 1) так и не понял (как раз изучал статью по ссылке), что означают поля left_key и right_key, что они вообще делают? 2) со сменой (изменение родителя, а не простое перемещение) родителя кое-как понятно, но в каталоге (менюшке,.. да и в любом практически дереве) бывает необходимость не смены родителя, а простое смещение нодов друг относительно друга. Как это сделать ума не приложу, видимо из-за того, что ни... не пойму для чего вышеуказанные ключи и как сработают в нужной задаче по перестановке последовательности нодов внутри родителя. например - 1. Авто 1.1 Тойота 1.2 Лада 2. Недвижимость 2.1 Квартиры 2.2 Дома 2.3 Участки Нужно поменять местами 1.2 и 1.1 или поменять местами родителей 2 -> 1 Как поведут себя ключи не пойму, кто знает подскажите Добавлено через 3 минуты забыл такой момент, щас использую обычную таблицу, где дерево строится ч/з родительское id. В чем преимущество nested'a перед таким вот написанием? 0

@vlaik 1 / 1 / 1 Регистрация: 05.11.2012 Сообщений: 88
	07.07.2014, 05:43	7
	Тоже сел за изучение nested sets, но в плане перемещения веток полная каша в голове. Уже кучу статей нашел, и везде одно и то же написано так, что вообще ничего не понять. С ключами вроде ясн , уровень вложенности - и ежу понятно Но вот никак не въеду я c перемещением веток, вроде самая развернутая статья http://www.getinfo.ru/article610.html: Берем пример с картинки: "Из неё можно увидеть, что узел может перемещаться только в две разные области: вышестоящих и нижестоящих узлов." - вроде как отсюда следует, что если мы перемещаем узел с id=9 (left_key=25 и right_key=30), то, если опираться на картинку: вышестоящий узел - это любой узел, у которого left_key меньше значения left_key перемещаемого узла (т.е. меньше 25) Нижестоящий узел - это любой узел, у которого left_key больше значения left_key перемещаемого узла (т.е. больше 25) И далее написано: "1. Перемещение вверх по дереву (в область вышестоящих узлов), включает в себя: Перенос ветки (узла) в подчинение нижестоящему(????) по дереву узлу; Перенос ветки (узла) вверх без изменения родительского узла (изменение порядка узлов); " Окей. К примеру хотим перенести узел с id=9 в узел c id=5, т.е. переносим в область вышестоящих узлов, т.е. в подчинение не нижестоящему (как в цитате из статьи), в вышестоящему узлу... Либо идет речь что нижестоящий по дереву - это и есть более вышестоящий в иерархии? Короче вся проблема сводится не к тому, как перенести определенный узел, а к тому, как сделать проверку куда он переносится. Так как от этого зависит порядок перестроения всего дерева. Не совсем понятно как проводить проверку, как сравнивать ключи чтобы понимать какие узлы должны быть обновлены 0

@Airclaim 0 / 0 / 0 Регистрация: 19.02.2016 Сообщений: 3
	19.02.2016, 22:16	8
	Вопрос к гуру. Как найти красивое решение для построения в базе данных MySQL таблицы через NESTED SETS? Есть дерево,как пример root .Книги ..Книги художественные ...Исторические ...До 1917 ..Книги документальные ...Книги о войне ...Воспоминания .Письма ..Письма личные ..Письма исторические ...Письма писателей и так далее.... Как построить Дерева каталогов NESTED SETS? Читал, читал, а все же знаний не хватает. Понимаю, что такое надо применить. http://www.php.su/articles/?cat=phpdb&page=013 http://www.poiu.ru/lessons/index.php-18.htm Кто подскажет как создать таблицу запросов? Вывод должен быть таким. id pid numleft numright numlevel title 0