Объясните, кто может, что такое правый ключ(right key) и левый ключ(left key) во вложенных множествах(nested sets). С level и id всё понятно. PS Если я вообще правильно перевёл термин.
айди - уникальный идентификатор самой записи. он не зависит от нетсет сетс вообще. левел - уровень вложенности элемента левый-правый ключи - собственно то благодаря чему дерево из таблицы (а в реляционных базах именно таблицы) можно развернуть в граф (в сетевую базу). математика там достаточна проста для понимания. изучал http://www.getinfo.ru/article610.html ?
основа там очевидная, по right key можно выбрать всю ветку потомков, а по left key левую, очень удобно, level это количество в глубь веток
Вот я бы понял если left key это был бы минимальный айди а right key максимальный. И они вместе описывают все элементы которые дальше идут. Но там вроде всё по другому.
ничего они не описывают и к идентификаторам не относятся. они относятся к сохранности структуры дерева. вернее представления дерева в таблице. на самом деле ключи относительно просты для понимания. ты стоишь во входной двери своей квартиры. это корень дерева. как пить дать твою хату можно представить в виде графа. так вот. каждая дверь - это родитель, а каждое окно - сток. и вот ты идешь по правой стене. всегда по правой стене. входя в дверь (квартиры/комнаты/туалета) оставляешь ей некоторое число. подходя к окну - еще одно. пройдя окно - еще одно. выйдя из комнаты - еще одно. каждый раз выдавая число ты его просто инкрементишь. так вот, на входе/подходе (к двери/к окну) ты ставишь левый ключ, а на выходе/проходе (из комнаты/мимо окна) - правый. таким образом ты обойдешь всю хату (держа всегда стены справа) и окажешься опять во входной двери. не забудь выйдя из нее раздать ей правый ключ. такой вот нехитрой манипуляцией ты раздашь всем веткам и листам входящим в граф левые и правые ключи. и все они обладают определенной математикой. на входной двери левый ключ равен 1 а правый - удвоенному числу встреченных в квартире объектов. подходя к каждой следующей двери, которая ведет на уровень глубже - у тебя будет меняться четность ключей на противоположную. у окна или у комнаты в которой нет ни окон ни дверей в другую комнату (чулан например) правый ключ будет на единицу больше левого. если два окна или две двери попались тебе подряд - левый ключ следующего объекта будет на единицу больше правого ключа предыдущего. навскидку не припомню какой еще математике они должны отвечать... но пока надеюсь этого достаточно.
Ну впринципе получается ключи это тоже своеобразные идентификаторы ? PS Закидайте меня тухлыми помидорами если я туплю =) Добавлено спустя 1 минуту 17 секунд: Они ведь что то описывают
macheto, ключи нужны для того, чтобы за один проход выбрать потомков. Расставляются по принципу, описанному Ganzal. На картинке видно, что у всех потомков узла left будет больше, чем его собственный, а right - меньше. Для этого они и расставляются именно в таком порядке
И вот например ещё. Как определить по ключам есть там дальше ветвление или за этим элементом идут тока конечные элементы. Добавлено спустя 1 минуту 15 секунд: Всё кажется я начинаю понимать... Это просто цифры не более...
У элемента, у которого нет "потомков", right = left + 1. А вот что "потомки" являются только листьями, пожалуй, по ключам не определишь
Вообще в реляционной БД связи между таблицами должны быть вида 1:М или М:1. Поэтому понятия left-key и right-key лишь говорят с какой стороны этой связи находится таблица - со стороны М или 1.
Maputo, здесь Nested Sets обсуждаются, причём здесь ваши реляционные связи? Nested Sets (вложенные множества) - создание иерархии внутри одной таблицы, к реляционным связям не имеют никакого отношения
Да нет же, ну. Ганзал же описал логику их выставления. В мкрамер даже офигенную картинку привел. Если в выставлении чисел есть логика - значит они уже не просто числа, а числа, из которых можно извлечь полезные данные. Как пример - количество вложенных элементов вида ((r_key-1) - l_key))/2. Возьмем квадрат в центре второго ряда на картинке. левый ключ 10, правый 23. Ставим в формулу: ((23-1)-10) = (22-10)/2 = 12/2 = 6 Вуаля! Мы знаем, что под этим элементом хранится еще 6. И для этого нам не нужно было обходить всю структуру. Будь там 6, 600, или 6000000 элементов, мы затратим одинаковое количество времени на то, чтобы узнать их количество.
Проиллюстрирую на шкурном примере: реферальная система. Каждый может "привести друга". Если ваш "друг" что-то купит, то вам пирожок. И тому кто вас привел тоже пирожок. И выше по пирамиде. Определить кому причитается бонус очень просто: берем `left` даного пользователя за X и выбираем всех пользователей, чьи `left` и `right` содержат в себе этот X. Всех предков одним запросом, опа! Код (PHP): … WHERE :x BETWEEN `left` AND `right` Если в расчете надо ограничить вложенность, то поможет сравнение level.
Fell-x27, artoodetoo, спасибо. мне кажется сейчас я действительно понял что такое левый/правый ключ. и для чего они нужны.