Деревья -> Форум на Исходниках.RU [Powered by Invision Power Board]

Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум на Исходниках.RU > Базы данных: SQL > Деревья

Автор: n0rd 21.10.06, 20:35

Есть необходимость организовать хранение деревьев каталогов в БД. Структура должна быть оптимальной для быстрого нахождения пути от корня дерева до некоторого листа.
Пока думаю сделать хранение дерева с помощью Nested sets, там указанный поиск реализуется просто и работает вроде быстро, однако встает еще задача выбора всех потомков заданного узла, лежащих ровно на 1 уровень ниже этого узла (выборка всех файлов и подкаталогов заданного каталога) и как ее делать просто (а не сотней последовательных запросов, если таких потомков будет 100 штук) я что-то пока не догоняю. Есть у кого какой-нить опыт в этом деле?

Автор: jack128 21.10.06, 22:19

чесно говоря не в курсе, что такое Nested sets,но могу предложить структуру, типа такой:

id Integer;
parent_id integer;
parent_path varchar(<>)
поле parent_path содержит полный путь к от корня к родителю текущего узла в строковом виде.
заполняется, естественно в триггере

Автор: n0rd 23.10.06, 13:23

Про nested sets написано, например, тут:
http://ibase.ru/devinfo/DBMSTrees/9603d06.html
http://ibase.ru/devinfo/DBMSTrees/9604d06.html
http://ibase.ru/devinfo/DBMSTrees/9605d06.html

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

Т.к. в программировании БД я практически ничего не понимаю, у меня еще вопросец назрел:
Вставка поддерева в дерево, организованное с помощью вложенных множеств (тех самых nested sets) включает в себя две фазы: перенумерация части вершин дерева и, собственно, вставка новых вершин. Собственно меня волнует что произойдет, при попытке двух клиентов добавить разные поддеревья в одно дерево одновременно. Перенумерации должны выполняться строго последовательно (неважно какая выполнится раньше, главное, чтобы для перенумерации, выполняющейся позже были видны изменения, которые внесла первая), иначе нарушится целостность структуры данных. Как этого добиться на Firebird 1.5?

Автор: jack128 23.10.06, 15:56

Цитата n0rd @ 23.10.06, 13:23

Про nested sets написано, например, тут:

Цитата n0rd @ 23.10.06, 13:23

Т.к. в программировании БД я практически ничего не понимаю

нет в жизни счастья.. одни в программировании ничего не понимают, другие в английском...

Цитата n0rd @ 23.10.06, 13:23

перенумерация части вершин дерева

нафиг? я те продложил простой способ безовсяких перенумераций..

Цитата n0rd @ 23.10.06, 13:23

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

ну выполняй перенумерацию эту в контексте одной транзакции...

Автор: Romkin 27.10.06, 07:45

Цитата n0rd @ 23.10.06, 13:23

Собственно меня волнует что произойдет, при попытке двух клиентов добавить разные поддеревья в одно дерево одновременно. Перенумерации должны выполняться строго последовательно (неважно какая выполнится раньше, главное, чтобы для перенумерации, выполняющейся позже были видны изменения, которые внесла первая), иначе нарушится целостность структуры данных. Как этого добиться на Firebird 1.5?

Тебя это не должно волновать

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