Извиняюсь за небольшой оффтоп, но всетаки спрошу здесь: кто какие способы хранения древовидных структур в реляционных бд знает/использует?

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

кто-нибудь ковырял эту тему?

про это видел,
http://gsbelarus.com/gs/modules.php?name=N...cle&sid=314

а связи из вложениями не могут подойти по id с LEFT JOIN и etc? 

связи ID<->ParentID самое очевидное. Вас интересует способ хранения или загрузки?

Вопрос скорее в раздел про базы данных

не совсем понятно как это сделать

вот есть еще модуль DBIx::Tree

если дерево будет так, то как мне вытащить, рекурсию надо как-то написать на perl?



    


Добавлено @ 01:29
Aslan74, и хранения, и загрузки   mysql

UPD:

довольно не плохо описано в модуле DBIx::Tree

Это сообщение отредактировал(а) gcc - 5.2.2009, 02:03

Вот в том-то и дело, что самое очевидное обычно не самое удобное =(
Вот сколько запросов придется делать чтобы в такой схеме выполнить следующие стандартные операции (рекурсию не рассматриваем):

1. Выбрать дерево целиком (с уровнем каждого элемента)
2. Выбор подчиненных узлов определенного узла
3. Выбор родительской ветки (с уровнями элементов)
4. Выбор ветки в которой участвует заданный узел (с уровнями элементов)

Врядли каждую операцию удасться вписать в один запрос. Несомненный плюс данной схемы - простота добавления/перемещения узлов.


Это сообщение отредактировал(а) Ramirez - 5.2.2009, 12:01

в innodb программно как делается, наверное на внешних ключах...

я хотел как раз это сделать на MyISA, мне этот модуль подходит, там еще есть http://search.cpan.org/search?query=DBIx%3...e+&mode=all

хотите дам реализацию на Rose?

делаем так: база такая

CREATE TABLE nodes (
    id          INTEGER PRIMARY KEY,
    parent_id   INTEGER,
    name        TEXT
);

это для sqlite

создаем объект My::Node


заполняем:


получаем выбоку из "леса"


ну и наблюдаем результ:

вот такие дела. 

Это сообщение отредактировал(а) NuINu - 5.2.2009, 17:17

NuINu, кстате, а ORM делает один запрос или несколько маленьких? ну если вытаскивать много данных на одну страницы с разных таблиц?

по разному
хочешь посмотреть добавь:

package main;
$Rose:B::Object::QueryBuilder::Debug = 1;

gcc, да несколько она делает.. это только Oracle (ну может еще что то стольже дорогое) умеет делать рекурсивные запросы,
а mysql и postgresql - только за несколько раз

NuINu, вы предложили все ту-же архитектуру "в лоб" (child <-> parent), просто красиво скрыв реализацию за фреймворком. Но волшебства-то не бывает, например если выбирать ветку дерева БД все равно придется выполнить несколько запросов (на каждый уровень по запросу). Это физическое ограничение выбранной архитектуры данных. Этим конечно можно пренебрегать пока данных не много. А если уровень вложенности 100 или 1000 уровней а количество записей миллионы? И таких проблем у архитектур "в лоб" множество. Решить их можно только использовав другую архитектуру, представив данные в БД другим, более оптимальным способом.

Вопрос, был скорее: как оптимальнее переложить древовидную структуру в БД, чтобы с ней было удобно работать. кто нибудь встречал что-то лучше чем Nested Sets?

Ramirez, насколько я помню вся история баз данных начиналась именно с иерархических структур.
т.е ранее все бд специально предназначались для хранения деревьев.




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

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

вот еще не мого про DBIx::Tree

http://www.dbpd.com/vault/9810/edb.html

я вот сделал это дерево для одно сайтика

а как управлять с помошью HTML форм этим деревом? если я захожу переметсить какой-то раздел, то как это сделать красиво (показаст ьродителя и подродителлей),  может с JS как-то? кто делал?

Лучше всего одна таблица с

ParentId 
ID 

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

Я делал это несколькими способами.
1. Самый простой: в форме деталей раздела поле select, а в нем все разделы.
выбираешь нужный, и сабмитишь

2. аяксовый
есть для jquery плагин. simpletree кажется.
у него есть возможность перемещать узлы дерева мышкой.
выводишь на страницу дерево, перемещаешь узлы куда надо.
И нажимаешь кнопку сохранить структуру дерева.
жаваскрипт пробегает по всему дереву строит список узлов и информацией об id, parentid
и отправляет на сервер. Там это все сохраняется в таблицу.
Вариант очень удобен для сортировки узлов дерева.

3. Тоже что и второй, только данные отправляются по каждому узлу,
который перетащил куда-либо.
Вариант удобен для работы с большими деревьями.

подскажите как вывести всех родителей дерева из id и name

есть


используется MySQL, рекурсии в ней нету,  такой запрос не реально написать

может ORM поможет? или как запрос написать, в гугле не нашел....!

gcc, ну вы почитайте топик с самого начала. Все как раз таким вопросом и задаются.
Там даже статья есть.
В MySQL - пока никак.  Т.е. нужно придумывать доп. конструкции в базе
В PostgreSQL - вроде добавили рекурсию в последней версии

1. По каждому найденному родительскому узлу делать sql запрос.
Минусы - много запросов к бд.
Если кол. данных возвращаемых запросом небольшое, то есть большая вероятность, что запросы
будут положены в кеш бд. Соответственно скорость работы будет высокой.

2. Кешировать у себя в программе целиком дерево.
Можно кешировать простым списком, а можно строить полноценное дерево.
На CPAN есть модули работы с деревьями.
Т.к. данные все есть, то выбрать из них нужное не составит проблем.
Способ не очешь хорош на больших деревьях, т.к. приходится все дерево хранить в памяти.
Но зато очень быстрый.

Если Ваше приложение - cgi, то стоит подумать, что выбрать. Если fastcgi и т.п., то однозначно второй способ.
Только надо не забывать при изменении дерева обновлять кеш.

Я всегда использовал второй способ для древовидной структуры сайтов. Мне так удобней.
Выбирается 1 раз все дерево. И эти данные пихаются в разные функции, которые на выходе дают, что я хочу.
Получается выгода, если в течение одного запроса пользователя нужно несколько раз использовать данные дерева.
Например, построить меню и путь к текущей странице ( цепочка ссылок предков )

И еще. Можно хранить не целиком все данные о дереве, а только id, parent_id, sort. Тогда будет меньше памяти занимать. А недостающие данные можно уже доставать sql запросом.

нашел что NestedSet как раз для того чтобы, вытащить часть родителей и не делать рекурсию...

еще нашел вариант, серилизации в отдельном столбце всех id родителей, например: 001.005.009.020.030

Это сообщение отредактировал(а) gcc - 5.5.2009, 11:57

NestedSet  вообще позволяет делать практические любые операции с деревом без рекурсии и достаточно простыми запросами.
единственный минус - очень ресурсоемкие операции вставки/перемещения узлов.

Это сообщение отредактировал(а) Ramirez - 8.5.2009, 11:20