Обсуждение статьи ДЕРЕВО КАТАЛОГОВ NESTED SETS (ВЛОЖЕННЫЕ МНОЖЕСТВА) И УПРАВЛЕНИЕ ИМ

[Phoinix]

Сама статья находится по адресу:

http://www.webscript.ru/stories/04/09/01/8197045

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

Последний комментарий

Dmitry Zlygin пишет 09.09.2004 @ 19:13
Не пинайте сильно, но из статьи не понял сути организации такого дерева. Что за поля такие, на что ссылаются? Что такое правый ключ, левый ключ, что они обозначают? Зачем применяется уровень? Статья явно рассчитана на тех, кто уже знает Nested Sets. Я не знаю, и, думаю, что не один в своем незнании. Man что?

Нормальные FOREIGN KEYS определить нельзя, хотя бы в терминах распространенного PostgreSQL?

Как сейчас есть - одна из самый бестолковых статей на сайте (не в обиду будет сказано).

1. "Что за поля такие, на что ссылаются?" - Обычные поля тип - INT(), никуда не ссылаются .
2. В них (правый и левый ключ) хранится информация о дереве. Так же по ним выбираются диапазоны дерева, и сортировка (по левому ключу);
3. Уровень применяется для удобства, что бы видеть на каком уровне находится узел, а так же для упрошения выбора родительского и подчиненных узлов;
4. Статья явно расчитана на тех, кто хоть когда имел опыт работы с деревьями, первый раздел посвящен именно организации, если информации там не хватает, то: man Google, man yandex;
5. Что значит нормальные FOREIGN KEYS? Есть еще и не нормальные ? И собсвенно не понял этой фразы. На протяжении всей статьи мы работаем с одной таблицей, и куда прилепить FOREING KEYS в статье, ума не приложу... Если же ты хочешь прицепить еще одну таблицу, то вперед, поле ID в дереве которое PRIMARY KEY никто не отменял...

[OFF]А вот насчет бестолковости, я бы не был столь критичен... Вы собственно кто? что бы делать такие утверждения? Очередной Победитель региональной олимпиады по программированию???[/OFF]

P.S. Собственно, все комментарии и вопросы по статье наверно лучше выкладывать сюда...

[NeoNox]

Phoinix не заморачивайся. Парень просто не в теме и ему обидно стало за свою недалекость. Когда возникнет задача - откопает и еще спасибо скажет.

[Phoinix]

NeoNox
Да нет... просто сама по себе тема интересная, я сам некоторое время использовал принцип построения дерева:

| id | paretn_id | name | ... |

И имел довольно большой гемморой, пока случайно не натолкнулся на Nested Sets... Хотя решение было написано для PHP, перевести на Perl было не долго...
Но мне не понравился класс PHP cdbtree, в части переноса узлов. Поэтому я сделал свое решение, которое позволяет 1 запросом перемещать узел в любую точку дерева...

Интересен факт, что мои знакомые программисты, которые не используют подобный принцип построения деревьев, видят в нем удобство, но не могут перейти в силу того, что прийдется изменять очень много своих наработок. Поэтому хочется что бы начинающие пользователи все-таки поняли идею, и применяли её в дальнейшем, и меньше наступали на грабли. А то что это им прийдется "вдалбливать", я думаю, ты знаешь лучше меня...

[APL]

Вот подробная и понятная статья:

http://www.pyaticom.ru/article/004/

[Croaker]

APL
[OFF]Вообще-то эта статья та же самая.[/OFF]

[Phoinix]

APL Croaker
[OFF]:D:D
Это точно... на неё я даже ссылку с основного сайта не сделал... т.к. нет соответсвующего раздела, эта ссылка предназначалась для rusdoc...[/OFF]

[APL]

Сорри, не смотрел...

[Dmitry Zlygin]

Насчет недалекости 2 NeoNox - извините, всех делов не знаем, неужели благородный дон настолько крут, что знает все и вся в программировании?

Спасибо за плохо написанную/скомпонованную статью не вижу смысла говорить. Вы так и не объяснили смысла полей left и right.

Речь шла о том, что неплохо бы написать в статье небольшое теоретическое введение, или сделать по крайней мере ссылку на статью с теорией.

Насчет деревьев - работали, старым дедовским методом смежных вершин. Увидел новое слово - заинтересовался - а тут такая фигня, типа, вы это все давно знаете. Этакий снобизм. Я думаю, не все читатели сайта в курсе ВСЕХ потенциально применимых в программировании технологий.

Насчет foreign key - разобрался, в nested sets они действительно не нужны. Насчет того, что в случае одной таблицы не может быть foreign key - это вы лихо... реализация дерева методом смежных вершин:

create table test(
name varchar(10) not null primary key,
parent varchar(10) null references test(name)
);

чем же, по-вашему, является поле parent в примере выше?

По поводу статьи: " Квадратами обозначены узлы дерева, синие цифры в верхнем правом и верхнем левом углах узла - уровень и уникальный идентификатор соответственно, а красные цифры в нижних углах - это левый и правый ключ. Именно в этих двух цифрах - левом и правом ключе заложена вся информация о дереве."   Именно в этой фразе отражена суть того, что мне не понравилось \ Во втором предложении смысла - ноль целых ноль десятых.

Как это описывается хорошо/понятно - можно посмотреть на:
http://www.sql.ru/articles/mssql/01091502TreesInSQL.shtml

[Гость]

Поэтому хочется что бы начинающие пользователи все-таки поняли идею, и применяли её в дальнейшем, и меньше наступали на грабли. А то что это им прийдется "вдалбливать", я думаю, ты знаешь лучше меня...

И опять ни слова дополнительного пояснения сверх статьи. Ну все ж понятно, особо непонятливых уже послали на google/yandex. Вы не беспокойтесь, уважаемый, дорогу к поисковикам как-то и сами...

А вам остается только, как маститым гуру, поругивать бестолковых глупых новичков.

[Dmitry Zlygin]

Поэтому хочется что бы начинающие пользователи все-таки поняли идею, и применяли её в дальнейшем, и меньше наступали на грабли. А то что это им прийдется "вдалбливать", я думаю, ты знаешь лучше меня...

И опять ни слова дополнительного пояснения сверх статьи. Ну все ж понятно, особо непонятливых уже послали на google/yandex. Вы не беспокойтесь, уважаемый, дорогу к поисковикам как-то и сами...

А вам остается только, как маститым гуру, поругивать бестолковых глупых новичков.

[Макс]

Dmitry Zlygin
цитата из статьи :

На схеме представлено дерево, описанное по всем правилам метода "Вложенных множеств". Квадратами обозначены узлы дерева, синие цифры в верхнем правом и верхнем левом углах узла - уровень и уникальный идентификатор соответственно, а красные цифры в нижних углах - это левый и правый ключ. Именно в этих двух цифрах - левом и правом ключе заложена вся информация о дереве. И если информацию о ключах занести в базу данных, то работа с деревом намного упрощается.
     Обратите внимание на то, в каком порядке проставлены эти ключи. Если мысленно пройтись по порядку от 1 до 32, то вы обойдете все узлы дерева слева направо. Фактически это путь обхода всех узлов дерева слева направо.

последний абзац + картинка объясняют всю суть метода. Посмотри на картинку, пройдись мысленно по цифрам, подумай, еще раз подумай.
Можешь еще почитать начало статьи на http://detail.phpclub.ru/article/db_tree . Если и оттуда ничего не поймешь, то я объяснить ничего тебе не смогу.

[Dmitry Zlygin]

2 Макс - спасибо за попытку объяснить, но лучше написано в документе, на который я привожу ссылку ("Древовидные структуры в SQL", по материалам статьи Joe Celko "Trees in SQL").

Понимаете, Макс, когда Phoinix пытается рассказать о nested sets, он не достигает понятности (плохой учитель ). Хотя в статье, на которую вы ссылаетесь, все же понятнее, чем у него. Ниже - объяснение еще проще, становится сразу понятным название метода хранения деревьев - "вложенные множества".

Чтобы изобразить древовидную структуру в виде вложенных множеств, заменим вершины графа овалами, где подчиненные овалы вложены один в другой. Основание дерева будет представлено самым большим овалом, который содержит все остальные овалы. Концевые вершины будут представлены самыми внутренними овалами, не содержащими внутри никаких других овалов, а вложенность будет показана иерархическими взаимоотношениями. Поля rgt и lft (я не использую зарезервированные слова RIGHT и LEFT) - это именно то, что показывает вложенность.

Если эта образная модель не работает, то представьте себе маленького червя, ползущего вдоль дерева против часовой стрелки. Каждый раз, когда он достигает правую или левую сторону вершины, он нумерует ее. Червь останавливается после того, когда он обойдет вокруг всего дерева и вернется назад к основанию.

... немного далее ...

Для преобразования графа в модель вложенных множеств вспомните о маленьком червячке, ползущем вдоль дерева. Червь начинает двигаться сверху - от основания - и обползает вокруг всего дерева. Когда он приходит к вершине, он присваивает значение стороне, которую он посещает и увеличивает значение счетчика на единицу. Каждая вершина получает два значения - одно для правой стороны и одно для левой.

[Макс]

всем не угодишь. Мне например пример с овалами совсем не нравится (хотя он объясняет суть названия метода).
А про червяка согласен, сам по нему разбирался.

[Phoinix]

Dmitry Zlygin

Понимаете, Макс, когда Phoinix пытается рассказать о nested sets, он не достигает понятности (плохой учитель  ). Хотя в статье, на которую вы ссылаетесь, все же понятнее, чем у него. Ниже - объяснение еще проще, становится сразу понятным название метода хранения деревьев - "вложенные множества".

Возможно Вы и правы, но основное направление статьи - не что такое Nested Sets, а как ими управлять...
Можно конечно глупо скопировать статью, ссылку на которую дал Макс (собственно первые абзацы так и сделаны), потом дописать свое... Тогда вопрос: А почему в статье не описан сам принцив SQL запросов и что это такое, и вообще что за базы данных...

Вы не беспокойтесь, уважаемый, дорогу к поисковикам как-то и сами

Вот, Вот... Если что-то не понятно, то вперед в поисковики, если не помогло, тогда уже к автору за пояснениями...

P.S. Вообще непонятено рассуждение Dmitry Zlygin.
Если человеку, что-то не понятно, он может это спросить, у меня, лично, нет желания от кого-то что-то прятать, скрывать и доказывать, что он дурак, а я умный, раз ничего не понял из того что я написал.
Только как человек спрашивает, такой ответ он и получает.
Я знаю как работать с деревьями Nested Sets, Вы нет.
Я написал статью, которая по моему мнению, достаточно понятно раскрывает тему. Вы что-то не поняли из этой статьи. Я оскорбил Ваше самолюбие? Извините, не хотел...
У Вас возникли вопросы по ходу статьи, задавайте их, коментарии для того и существуют, для того, что бы делать уточнения, но никак не ставить оценку статье...

[Гость]

Привет всем!

Статья очень хорошая, написана очень хорошо, но к сожалению в ней неописано решение одной пролемы которая возникает у меня (да наверное не только у меня) при использовании этого алгоритма

Проблема в следующем

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

ID | ID parent | left_key | right_key | level

где ID parent - ID родительского узла.

Поясню для чего это мне надо

Вместе с сами алгоритмом для визульного представления я  использую JS класс dTree который позволяе создавать меню типа проводника Windows.

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

Пока что делаю так

1)Запрашиваю список всех разделов
2)Для каждого раздела отдельным запросом определяю ID родителя.

Пока что всё нормально, но если в дереве будет штук 500 разделов то это 500 запросов в одном сценарии.Ужас!

Может кто то решил эту проблему?
Подскажите решение.

Спасибо!