Гость
Войти | Профиль | Очистить
Действия ...
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Деревья, давайте обсудим! / 13 сообщений из 13, страница 1 из 1
26.12.2003, 16:04
    #32364704
mahoune
mahoune
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревья, давайте обсудим!
Вот захотел обсудить раз и навсегда методы реализации деревьев!
Не тех что растут в лесу, а тех что "растут" в базе!

Можно просто хранить в виде:
ID | Parent | Name

Но в такую схему не плохобы добавить порядок "дочек" в Parent , получаем:
ID | Parent | OrderID | Name

Для ускорения видел такую схему:
ID | Parent | OrderID | FullPath | Name
или еще более детально
ID | Parent | OrderID | DeepLevel | FullPath | Name
Где соответственно FullPath показывает полный путь до Узла . А DeepLevel - уровень вложенности по отношению к корню. Но тогда при перемещении Parent в другую ветвь надо просматривать все Child и менять в них FullPath и Level . Это удобно если изменения в структуру не вносятся, а только происходит добавление.

Еще есть "Красно Черные" деревья и прочая муть!

В каких ситуациях что использовать?

mahoune
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.12.2003, 16:35
    #32364753
bas
bas
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревья, давайте обсудим!
Как правило нужно только полное имя(FullPath), ну и м.б. порядок дочек(OrderID) в дереве.

И это не так сложно, написал тригер на изменение и встваку и забыл про FullPath и OrderID, вспоминаешь только когда нужно прочитать эти поля.

Ну а использование стандартное - где есть отношение вложенности в таблицах с одинаковой структурой и не известно заранее сколько глубина вложенности и где записей не 100 милионов и глубина вложенности не очень большая(это для FullPath и OrderID). Если это так то лучше разбить на несколько таблиц
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.12.2003, 16:47
    #32364769
GroZ
GroZ
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревья, давайте обсудим!
Красно Черные - это балансирующиеся деревья, для чего тебе они в Базе? Всё упирается в то для какой цели ты строиш дерево.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.12.2003, 17:43
    #32364835
mahoune
mahoune
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревья, давайте обсудим!
Я его сейчас пока не строю. Уже понастроил за свою жизнь!
Теперь хочу понять, когда какие лучше строить?!

mahoune
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.12.2003, 18:12
    #32364869
Hibernate
Hibernate
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревья, давайте обсудим!
по своему опыту общения с деревъями сделал такой вывод:
чем больше избыточности, тем легче делать выборки, но труднее добавлять/изменять это дерево(поддерживать избыточность тяжело).
В итоге каждый раз надобно искать компромисс...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.12.2003, 19:59
    #32364944
Макс М.
Макс М.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревья, давайте обсудим!
все зависит от того, какие операции с деревом или его узлами будут происходить.
Меня пока устраивает Nested Sets ( Nested Sets ) - там в PDF статья была на английском.
Структура таблицы:
id, left, right + я еще храню level - иногда очень помогает
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.12.2003, 20:14
    #32364954
mahoune
mahoune
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревья, давайте обсудим!
Почитал, но это же какой то наворот! Неужели так тоже удобно работать. По всем пробежаться Left/Right поменять?

mahoune
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.12.2003, 21:33
    #32364992
Макс М.
Макс М.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревья, давайте обсудим!
Nested sets удобен если нужно часто выборки делать из БД делать. Например одним запросом можно получить структуру дерева, детей для указанного узла, родителей для указанного узла. Если разобраться с алгоритомом то можно будет и более сложные выборки за один-два запроса.
Вообще я стал использовать этот алгоритм после того как с классом dbtree.php разобрался, поэтому вставку/удаление/перемещение узла вручную я не делал. Ты вроде ПХП/MySQL знаешь, можешь еще почитать:
http://detail.phpclub.net/article/db_tree
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.12.2003, 22:42
    #32365013
vdimas
vdimas
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревья, давайте обсудим!
перепробовал кучу вариантов, остановился на следующем:
- данные узлов хранятся в своей таблице, сами узлы - в своей.
- в таблице узлов хранятся не только непосредственные связи, но и вообще все транзиктивные связи, т.е. имеем явную избыточность, но зато обходимся без рекурсии для выборки, скажем, всех дочерних ID независимо от уровня.

структура крайне проста:

основная:
ID, Name, /любые данные узла/

связи:
ID, ParentID, Metric.

если Metric=1, то ParentID - непосредственный "отец".

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

примечание:
как и в любой системе с избыточностью такая схема требует "ручного" поддержания целостности таблиц, путей много и они все давно известны - триггера или открытие доступа только через процедуры.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.12.2003, 22:43
    #32365014
vdimas
vdimas
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревья, давайте обсудим!
в догонку, получить полный путь к узлу легко - выбираем все паренты и сортируем по метрике
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.12.2003, 16:11
    #32365334
alexeyvg
alexeyvg
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревья, давайте обсудим!
2mahoune
Прислушайтесь к Макс М. Там не такой-уж и наворот.
Зачем "По всем пробежаться Left/Right поменять"?
Скажем, вставка или удаление записей - это просто один апдейт Left/Right, а не "по всем пробежаться".
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.12.2003, 14:11
    #32365939
HCMan
HCMan
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревья, давайте обсудим!
При вставке точно нужно пробежаться по всем отрезкам (l-r), которые находятся правее места вставки, и проапдейтить. При удалении почти тоже самое. В этом один из основных недостатков алгоритма. Но реализовать никаких проблем не составляет (SQL Server 2000)

Я использовал вложенные множества для выборки и, кроме того, связь Left-ParentLeft для отображения в гриде (удобнее, чем вложенные множества).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.12.2003, 19:39
    #32366411
Varan
Varan
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревья, давайте обсудим!
Вот тут несколько статей про деревья - вдруг кому пригодится.
Статья С. Виноградова
Статья М. Голованова в RSDN
Статья Д. Кузменко с продолжением
Там же есть перевод статьи Joe Celko "Деревья в SQL" , сделанный Д.Салашником
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Деревья, давайте обсудим! / 13 сообщений из 13, страница 1 из 1
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
созд. / загр.: 480ms
Закрыть
start [/forum/topic.php?fid=32&mobile=1&tid=1546691]:
 0ms
get settings:
 8ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 145ms
get topic data:
 13ms
get forum data:
 3ms
get page messages:
 51ms
get tp. blocked users:
 2ms
others: 236ms
total:  480ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]