Как лучше хранить дерево в реляционной БД
префикс хранить для каждого узла
В виде
create table mytree (
node text/blob/varchar primary key,
node_content char(33) default "хуй",
node_fk text/blob/varchar - вероятно, не понадобится);
Правда в таком варианте мы ограничиваем кол-во прямых потомков узла, но зато, чтоб найти всех потомков узла
"abdrgefystem" просто берем node like "abdrgefystem%";
create table mytree (
node text/blob/varchar primary key,
node_content char(33) default "хуй",
node_fk text/blob/varchar - вероятно, не понадобится);
Правда в таком варианте мы ограничиваем кол-во прямых потомков узла, но зато, чтоб найти всех потомков узла
"abdrgefystem" просто берем node like "abdrgefystem%";
что такое префикс?
в смысле путь от корня до узла, в виде строки
такой вот отстой
такой вот отстой
в Oracle чтоб такие запросы делать есть START WITH и CONNECT BY
да, в Оракле что-то было такое, но, к сожалению, у нас что-то дешевое типа MySQL
а пронумеровывать узлы как-нибудь хитро нельзя?
"видел" два подхода (не считая префиксов, конечно - ибо ацтой 
)
первый - таблица ссылается сама на себя. Получать всех потомков или предков, учитывая вложенность, - довольно геморно
второй - особо не вникал, но там заводятся для каждого элемента два числа - условно, left и right - и по ним определяется местоположение в дереве
В этом случае изменение места в дереве происходит геморно (надо все переиндексивровать а всевозможные рекурсивные выбори - просто (выборка типа "выбрать всех у кого нет потомков" имеет вид "where (right - left) = 1" (вроде бы так
За подробностями - в гугл
)первый - таблица ссылается сама на себя. Получать всех потомков или предков, учитывая вложенность, - довольно геморно
второй - особо не вникал, но там заводятся для каждого элемента два числа - условно, left и right - и по ним определяется местоположение в дереве
В этом случае изменение места в дереве происходит геморно (надо все переиндексивровать а всевозможные рекурсивные выбори - просто (выборка типа "выбрать всех у кого нет потомков" имеет вид "where (right - left) = 1" (вроде бы так
За подробностями - в гугл
вот, нашел какую-то статейку
статейка
статейка
Вот чувак заморачивался этим вопросом.
http://dull.ru/keyword/trees/
http://dull.ru/keyword/trees/
всем спасибо
Юзай LDAP , или же можешь посмотреть как они реализуют хранение дерева.
, или же можешь посмотреть как они реализуют хранение дерева.а в чём отстойность метода, если в качестве префикса юзать например путь в виде x.y.z, где x,y,z - соответственно номера узлов на каждом уровне?
Для глубоких деревьев хранить (и обновлять при модификациях) нужно много.
Поле будет типа VARCHAR, надо полагать?
И какой индекс ты для такого префикса будешь использовать?
И какой индекс ты для такого префикса будешь использовать?
Не нужно, если ограничить заранее количество прямых потомков у узла. Исключение - перемещение поддерева в другую точку.
> Не нужно, если ограничить заранее количество прямых потомков у узла.
Как это поможет?
Как это поможет?
ну да, varchar, а с каких пор они не индексируются?
ЗЫ зато очень просто найти нужные данные, просто найти всех предков и потомков, это наглядно, легко добавляются новые узлы, особенно когда неважен порядок непосредственных дочерних элементов каждого узла.
ЗЫ зато очень просто найти нужные данные, просто найти всех предков и потомков, это наглядно, легко добавляются новые узлы, особенно когда неважен порядок непосредственных дочерних элементов каждого узла.
А так, что если у нас максимум, например, 2 потомка, то мы юзаем 1010.....; если больше, то выделяем на адресацию каждого узла соответствующее количество разрядов.
Чтоб выбрать подузлы понятно, что делать.
Чтоб выбрать подузлы понятно, что делать.
тогда и вложенность ограничивается, хотя моим способом - тоже
Вложенность ограничивается длинной поля.
Всё равно при глубине дерева N будут храниться пути длиной O(N). Без этого ограничения - O(N*ln(N - небольшая разница.
Тут надо думать над конкретной задачей, видимо ) Все и сразу - это только в сказке...
это можно обойти, сделав поле с путём как text =) только резко упадёт скорость выборки
> это можно обойти, сделав поле с путём как text
длина путей от этого уменьшится?
длина путей от этого уменьшится?
длина - нет, просто ограничение на длину исчезнет, но пропадёт возможность индексировать по этому полю
> ну да, varchar, а с каких пор они не индексируются?
они конечно индексируются, только ты почитай, как именно.
они конечно индексируются, только ты почитай, как именно.
Оставить комментарий
6yrop
чтобы запрос: выбрать всех потомков заданного узла, формулировался на SQL просто?