|
|
|
Деревья, давайте обсудим!
|
|||
|---|---|---|---|
|
#18+
Вот захотел обсудить раз и навсегда методы реализации деревьев! Не тех что растут в лесу, а тех что "растут" в базе! Можно просто хранить в виде: 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 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2003, 16:04 |
|
||
|
Деревья, давайте обсудим!
|
|||
|---|---|---|---|
|
#18+
Как правило нужно только полное имя(FullPath), ну и м.б. порядок дочек(OrderID) в дереве. И это не так сложно, написал тригер на изменение и встваку и забыл про FullPath и OrderID, вспоминаешь только когда нужно прочитать эти поля. Ну а использование стандартное - где есть отношение вложенности в таблицах с одинаковой структурой и не известно заранее сколько глубина вложенности и где записей не 100 милионов и глубина вложенности не очень большая(это для FullPath и OrderID). Если это так то лучше разбить на несколько таблиц ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2003, 16:35 |
|
||
|
Деревья, давайте обсудим!
|
|||
|---|---|---|---|
|
#18+
Красно Черные - это балансирующиеся деревья, для чего тебе они в Базе? Всё упирается в то для какой цели ты строиш дерево. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2003, 16:47 |
|
||
|
Деревья, давайте обсудим!
|
|||
|---|---|---|---|
|
#18+
Я его сейчас пока не строю. Уже понастроил за свою жизнь! Теперь хочу понять, когда какие лучше строить?! mahoune ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2003, 17:43 |
|
||
|
Деревья, давайте обсудим!
|
|||
|---|---|---|---|
|
#18+
по своему опыту общения с деревъями сделал такой вывод: чем больше избыточности, тем легче делать выборки, но труднее добавлять/изменять это дерево(поддерживать избыточность тяжело). В итоге каждый раз надобно искать компромисс... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2003, 18:12 |
|
||
|
Деревья, давайте обсудим!
|
|||
|---|---|---|---|
|
#18+
все зависит от того, какие операции с деревом или его узлами будут происходить. Меня пока устраивает Nested Sets ( Nested Sets ) - там в PDF статья была на английском. Структура таблицы: id, left, right + я еще храню level - иногда очень помогает ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2003, 19:59 |
|
||
|
Деревья, давайте обсудим!
|
|||
|---|---|---|---|
|
#18+
Почитал, но это же какой то наворот! Неужели так тоже удобно работать. По всем пробежаться Left/Right поменять? mahoune ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2003, 20:14 |
|
||
|
Деревья, давайте обсудим!
|
|||
|---|---|---|---|
|
#18+
Nested sets удобен если нужно часто выборки делать из БД делать. Например одним запросом можно получить структуру дерева, детей для указанного узла, родителей для указанного узла. Если разобраться с алгоритомом то можно будет и более сложные выборки за один-два запроса. Вообще я стал использовать этот алгоритм после того как с классом dbtree.php разобрался, поэтому вставку/удаление/перемещение узла вручную я не делал. Ты вроде ПХП/MySQL знаешь, можешь еще почитать: http://detail.phpclub.net/article/db_tree ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2003, 21:33 |
|
||
|
Деревья, давайте обсудим!
|
|||
|---|---|---|---|
|
#18+
перепробовал кучу вариантов, остановился на следующем: - данные узлов хранятся в своей таблице, сами узлы - в своей. - в таблице узлов хранятся не только непосредственные связи, но и вообще все транзиктивные связи, т.е. имеем явную избыточность, но зато обходимся без рекурсии для выборки, скажем, всех дочерних ID независимо от уровня. структура крайне проста: основная: ID, Name, /любые данные узла/ связи: ID, ParentID, Metric. если Metric=1, то ParentID - непосредственный "отец". Введение Metric позволяет указать в запросе некую максимальную вложенность выборки дочерних узлов. примечание: как и в любой системе с избыточностью такая схема требует "ручного" поддержания целостности таблиц, путей много и они все давно известны - триггера или открытие доступа только через процедуры. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2003, 22:42 |
|
||
|
Деревья, давайте обсудим!
|
|||
|---|---|---|---|
|
#18+
в догонку, получить полный путь к узлу легко - выбираем все паренты и сортируем по метрике ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2003, 22:43 |
|
||
|
Деревья, давайте обсудим!
|
|||
|---|---|---|---|
|
#18+
2mahoune Прислушайтесь к Макс М. Там не такой-уж и наворот. Зачем "По всем пробежаться Left/Right поменять"? Скажем, вставка или удаление записей - это просто один апдейт Left/Right, а не "по всем пробежаться". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.12.2003, 16:11 |
|
||
|
Деревья, давайте обсудим!
|
|||
|---|---|---|---|
|
#18+
При вставке точно нужно пробежаться по всем отрезкам (l-r), которые находятся правее места вставки, и проапдейтить. При удалении почти тоже самое. В этом один из основных недостатков алгоритма. Но реализовать никаких проблем не составляет (SQL Server 2000) Я использовал вложенные множества для выборки и, кроме того, связь Left-ParentLeft для отображения в гриде (удобнее, чем вложенные множества). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2003, 14:11 |
|
||
|
Деревья, давайте обсудим!
|
|||
|---|---|---|---|
|
#18+
Вот тут несколько статей про деревья - вдруг кому пригодится. Статья С. Виноградова Статья М. Голованова в RSDN Статья Д. Кузменко с продолжением Там же есть перевод статьи Joe Celko "Деревья в SQL" , сделанный Д.Салашником ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2003, 19:39 |
|
||
|
|
start [/forum/topic.php?fid=32&fpage=174&tid=1546691]: |
0ms |
get settings: |
9ms |
get forum list: |
14ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
71ms |
get topic data: |
11ms |
get forum data: |
2ms |
get page messages: |
44ms |
get tp. blocked users: |
1ms |
| others: | 238ms |
| total: | 396ms |
| 0 / 0 |
