Nested Sets VS Nested Intervals?

Question

[Сергей Протько]

Собственно, наткнулся на реализацию хранения древовидных структур с импользованием вложенных интервалов. Поиски особо ничего не дали, кроме как информации о том, что этот метод является попыткой улучшить метод со вложенными множествами. Более подробной информации о возможных подводных камнях я не нашел, так же как и явных доводов (помимо уменьшения колличества операций переиндексации) ЗА.


В данный момент выбираю метод хранения древовидных структур, где операции вставки/перемещения/удаления будут во много порядков более редки, неже ли выборка ветвей. Так что тут оптимизация этих операций не существенны. Но на будущее хотел бы знать, что лучше.

Answer 1

[Алексей Сундуков]

На вскидку для NI возникает такой минус — исчерпание размеров левого и правого ключей, когда придется перейти с, допустим, int на bigint. Зависит от соотношения размера дерева и шага для дырок в ключах. В принципе не проблема, потребуется просто чуть больше ресурсов. Но стоит о таких вещах подумать заранее, что бы не получилось так, что в самый неподходящий момент ресурсов то и не хватит.

Алгоритмический минус по сравнению с NS — зная левый и правый ключи узла невозможно вычислить количество потомков, а в NS это можно. К примеру, если каталог товаров храниться в NS, то для текущей категории (узел) можно указывать количество_товара/количество_подразделов/другое просто получив эту категорию и не получая её потомков.

В общем те или иные плюсы/минусы могут рассматриваться в контексте размера дерева, отношения количество_выборок/количество_вставок, аппаратных ресурсов.

Comments

[Сергей Протько]

как древо собираюсь хранить группы пользователей, типы или категории записей. Так что тут хоть и возможно большое колличество записей, но не более пары сотен (не представляю себе допустим интернет магазина, содержащего более сотни категорий и уж тем более групп пользователей. Так что пожалуй такие вещи стоит хранить в NI. Хотя опять же можно и в NS, операции вставки и переноса совершаться будут редко.

В любом случае, спасибо за ответ.

[Алексей Сундуков]

Ну я на такой задаче вообще не запариваюсь и использую AL. Получение всего дерева процесс безусловно рекурсивный, но в своей платформе просто сторю его полностью в сериализованном виде в кэше.

Answer 2

[max_mara]

В nested sets проблема с которой я столкнулся — обязательно должна быть корневая категория, иначе у меня все сыпалось лесом. Еще периодически у меня сбивались ключи и структура дерева тоже рассыпалась.

Поэтому у нас всегда кроме ключей, есть еще parent_id, по которому всегда можно восстановить дерево. Больше проблем не возникало.
Радует удобство выборки, если есть глубокая вложенность, не надо доставать все ветви рекурсией, все делается одним запросом.

Comments

[Сергей Протько]

минусы вложенных множеств я знаю, как и плюсы, просто сегодня сталкнулся с реализацией вложенных интервалов, которая вроде как оптимизирует вставку ноды и ее перемещение/удаление… Как минус пока могу предложить проблему с определением колличество дочерних эллементов между двумя нодами, когда даны только параметры этих нодов. Словом — буду эксперементировать…

И еще, если все что косается переиндексирования ключей, если заключить это дело в транзакцию, то это разве не спасет?