Какие алгоритмы построения nested set вы знаете?

Question

[Антон Корзунов]

С ходу на хабре обнаружил только одну статью на эту тему - habrahabr.ru/post/153861
Предложенный алгоритм отличается прямо таки феноминальной вычислительной сложностью. Чуть более оригинальный(www.ibase.ru/devinfo/DBMSTrees/sqltrees.html) опять же далеко не хорошо работает, эмулируя по сути обход дерева.
Пытался разобраться зачем такие сложности, и почему проблему нельзя решить более "приятными" для табличного SQL средствами - но других решений в онлайне не обнаружил (варианты через выгрузку данных, и обработку "на нормальных языках" вообще не рассматриваю).
Сам решил задачу построения через 5 запросов*глубина дерева, и все не могу понять почему так никто не делает...

Answer 1

[Дмитрий Энтелис]

imho
Потому что это все по большому счету занимательные задачки для ума.
На живом проекте за попытку сделать запросы в базу в цикле к вам придет злой CTO/CIO/DBA и оторвет лишние части тела.
Если надо из обычной реляционной базы построить дерево - правильный подход сделать 1 запрос в базу и построить дерево средствами языка.
Если это надо делать регулярно - возможно имеет смысл подумать о хранении этого дерева каким то другим способом.

Comments

[Антон Корзунов]

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

[Дмитрий Энтелис]

kashey: приведите пример реально задачи когда без такой структуры в памяти не обойтись?

[Антон Корзунов]

Дмитрий Энтелис: в систему "адресации" NS входят также хэши по Morton или Hilbert кодам, те geospatial задачки. При желании и мапинг IP можно представить в виде вложенных отрезков. В общем можно придумать мильен задач, где выборка по интервалу будет удобна, и будет работать сильно быстрее других вариантов.
Обычные AS тут вообще не подойдут, а CS резко деградирует при увеличении глубины дерева.

[Дмитрий Энтелис]

kashey: Спасибо, не знал)