Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Как лучше реализовать в БД иерархическую структуру? / 12 сообщений из 12, страница 1 из 1
06.12.2015, 23:06
    #39121824
kormot
kormot
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как лучше реализовать в БД иерархическую структуру?
Добрый день!
Я помнится на этом форуме видел топик с обсуждением способов хранения иерархических структур в базе данных. Но сейчас что-то поиском найти не смог, напишу новый топик.

Я оттуда для себя подчерпнул и использовал в своих проектах такой способ:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
TABLE object (
  id   SERIAL PRIMARY KEY,
  objData CHAR(255)
)

TABLE objectRel (
  id SERIAL PRIMARY KEY,
  masterID SERIAL,
  childID  SERIAL,
  relLevel INT UNSIGNED,
  UNIQUE KEY (masterID, childID),
  FOREIGN KEY (masterID) REFERENCES object(id) ON DELETE CASCADE ON UPDATE CASCADE,
  FOREIGN KEY (childID) REFERENCES object(id) ON DELETE CASCADE ON UPDATE CASCADE
)



где relLevel это уровень вложенности элемента childID в элементе masterID. Соответственно для дерева хранятся записи с вложенностью всех элементов.
С ростом числа элементов и их вложенностью таблица objectRel очень быстро растёт.

Скажите пожалуйста насколько это эффективный способ хранения древовидной структуры в БД.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.12.2015, 23:32
    #39121827
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как лучше реализовать в БД иерархическую структуру?
kormotС ростом числа элементов и их вложенностью таблица objectRel очень быстро
растёт.
Не очень быстро. Всего лишь M*N.

kormotнасколько это эффективный способ хранения древовидной структуры в БД.
Для хранения - совсем не эффективный. Для работы с этим деревом - очень эффективный. Выбирай.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.12.2015, 01:07
    #39121838
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как лучше реализовать в БД иерархическую структуру?
Dimitry SibiryakovДля работы с этим деревом - очень эффективный.Точнее, эффективный для чтения.
Для модификации чудовищно неэффективный.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.12.2015, 01:31
    #39121840
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как лучше реализовать в БД иерархическую структуру?
miksoftДля модификации чудовищно неэффективный.
Ну так модификация деревьев это обычно весьма редкая операция.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.12.2015, 01:53
    #39121846
Зимаргл
Зимаргл
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как лучше реализовать в БД иерархическую структуру?
Dimitry SibiryakovkormotС ростом числа элементов и их вложенностью таблица objectRel очень быстро
растёт.
Не очень быстро. Всего лишь M*N.

Почему это м*н?

Похоже на просто м (число объектов, включая дочки) плюс число связей родители с дочками.

Так что вполне эффективно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.12.2015, 15:53
    #39128717
Gorm
Gorm
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как лучше реализовать в БД иерархическую структуру?
ChaildID - совершенно абсолютно лишнее
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.12.2015, 18:31
    #39128997
Кот Матроскин
Кот Матроскин
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как лучше реализовать в БД иерархическую структуру?
GormChaildID - совершенно абсолютно лишнее
Таблица objectRel без поля childID - это будет оригинально, да.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2015, 13:50
    #39131826
olzhas
olzhas
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как лучше реализовать в БД иерархическую структуру?
kormot,

Дерево делается одной таблицей.

Код: sql
1.
2.
3.
4.
5.
create table tree (
object_id int not null primary key,
parent_id int reference tree(object_id),
object_data varchar(255)
)



Уровень можно вычислить запросом.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.12.2015, 08:54
    #39137784
kormot
kormot
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как лучше реализовать в БД иерархическую структуру?
olzhasУровень можно вычислить запросом.
А не будет ли это в плане вычислительных затрат накладней, чем реализация дерева через таблицу с уже разложенными по полочкам связям всех узлов?

Я может не особо sql знаю, но если использовать одну таблицу, то для вычисления потомков n-го уровня вложенности надо использовать рекурсию. Или это не так?

Можете мне пожалуйста для общего развития дать пример запроса выдающего из вашего примера всех потомков данного узла с указанием их уровня вложенности?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.12.2015, 11:23
    #39137920
mad_nazgul
mad_nazgul
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как лучше реализовать в БД иерархическую структуру?
olzhaskormot,

Дерево делается одной таблицей.

Код: sql
1.
2.
3.
4.
5.
create table tree (
object_id int not null primary key,
parent_id int reference tree(object_id),
object_data varchar(255)
)



Уровень можно вычислить запросом.

Тут проблема в том, что вставка/удаление будет быстрой, а вот поиск при большой глубине вложенности медленный.

Можно и по другому...
Через Nested set
Здесь с точностью до наоборот.
Поиск "быстрый", а вот вставка/удаление медленными.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.12.2015, 13:43
    #39138132
Quotes Only
Quotes Only
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как лучше реализовать в БД иерархическую структуру?
http://habrahabr.ru/post/193166/ Хранение деревьев в базе данных. Часть первая, теоретическая

Итак. Существует несколько шаблонов проектирования баз данных для хранения и обработки иерархических структур:
Adjacency List («список смежности»)

Materialized Path («материализованный путь»)

Nested Sets («вложенные множества»)

Closure Table («таблица связей»)

. . .
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.12.2015, 13:59
    #39138165
olzhas
olzhas
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как лучше реализовать в БД иерархическую структуру?
kormot,

Как выше написали есть несколько моделей все зависит от задачи.
Вычисление уровней пойдет через рекурсию (sql запросы разные в зависимости от базы данных), да это ударит по производительности. но только если эти уровни вам нужны. Если это критично можете добавить дополнительное поле, но вам самому надо будет его обслуживать.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Как лучше реализовать в БД иерархическую структуру? / 12 сообщений из 12, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
созд. / загр.: 508ms
Закрыть
start [/forum/topic.php?fid=32&mobile=1&tid=1540419]:
 0ms
get settings:
 9ms
get forum list:
 16ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 157ms
get topic data:
 13ms
get forum data:
 3ms
get page messages:
 53ms
get tp. blocked users:
 1ms
others: 248ms
total:  508ms
x
x
Закрыть


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