Есть ли способ сделать ТруЪ дерево aka NestedSet и отобразить его на реляционную БД? В гугле примеров нет, наткнулся на блог где написано что это реализовано в CaveatEmptor но ничего подобного там нет кроме простейшей Parent-child структуры. Собсно мне необходимо доставать все дерево сразу. Это возможно? Может есть у кого-нибудь пример?
Здравствуйте, Аноним, Вы писали:
А>Собсно мне необходимо доставать все дерево сразу.
Не проще ли воспользоватся бинарной или xml сериализацией? В базе хранить ее как БЛОБ?
Аноним wrote: > Есть ли способ сделать ТруЪ дерево aka NestedSet и отобразить его на > реляционную БД? В гугле примеров нет, наткнулся на блог где написано что > это реализовано в CaveatEmptor но ничего подобного там нет кроме > простейшей Parent-child структуры. Собсно мне необходимо доставать все > дерево сразу. Это возможно? Может есть у кого-нибудь пример?
Можно. Есть старый добрый трюк для этого, он применим к любой
реляционной структуре.
Корень дерева обозначаем интервалом от 0 до 1, его левый узел будет от 0
до 1/2, правый узел от 1/2 до 1. Левый узел левого узла — от 0 до 1/4 и т.п.
Тогда запрос на всех детей узла будет простым запросом на выбор всех
узлов, попадающих в данный интервал.
Да, эту схему полезно совмещать с parent/child для улучшения навигации
по дереву.
Здравствуйте, Cyberax, Вы писали:
C>Аноним wrote: >> Есть ли способ сделать ТруЪ дерево aka NestedSet и отобразить его на >> реляционную БД? В гугле примеров нет, наткнулся на блог где написано что >> это реализовано в CaveatEmptor но ничего подобного там нет кроме >> простейшей Parent-child структуры. Собсно мне необходимо доставать все >> дерево сразу. Это возможно? Может есть у кого-нибудь пример? C>Можно. Есть старый добрый трюк для этого, он применим к любой C>реляционной структуре.
aka50 wrote: > Это даже имеет название Nested Intervals. > Вот тут подробнее: http://www.dbazine.com/oracle/or-articles/tropashko4 > Ну и собственно в hibernate использовать NamedQuery. > Проблема в том, что эти методы, кроме Adjacency List на rdbms > нормально не ложаться, и следовательно hibernate имеет нулевую > поддержку этого добра.
Nested Intervals как раз на RDBMS замечательно ложится: "SELECT ... FROM
Blah f WHERE f.left>=0 and right<0.5". Другое дело, что в результате
запроса у нас не будет топологической сортировки — но часто это и не нужно.
> 1. Грузи дерево как плоский collection. > 2. Например в DAO превращай это в Tree<MyObject>. > правда это будет readonly решение.
По своему опыту — часто проблема уже с загрузкой дерева, мне обычно
нужно загрузить все подузлы, которые удовлетворяют какому-нибудь
условию. С NI это делается достаточно просто.
Здравствуйте, Cyberax, Вы писали:
C>aka50 wrote: >> Проблема в том, что эти методы, кроме Adjacency List на rdbms >> нормально не ложаться, и следовательно hibernate имеет нулевую >> поддержку этого добра. C>Nested Intervals как раз на RDBMS замечательно ложится: "SELECT ... FROM C>Blah f WHERE f.left>=0 and right<0.5". Другое дело, что в результате C>запроса у нас не будет топологической сортировки — но часто это и не нужно.
По хорошему ни один из методов на rdbms толково не ложится:
1. adjacency — легкая вставка, integrity с поддержкой cascade на уровне бд,
и не зависит от производителя (т.е. обычные fk/pk). Но выборка — не обойтись без
подпорок в виде БЛ/хранимок или рекурсивных запросов как в oracle.
2. materialized path — хитрая вставка (либо неявные узлы). Реализация большинства
операций внешними процедурами в том числе и integrity.
3. nested sets/intervals — схожие техники, но расходятся по эффективности решения
задач хранения/вставки/удаления/выборки. В целом неплохо ложатся на rdbms,
но опять же сложная вставка/удаление и непереносимость реализации например cascade
delete.
Nested Intervals.