Среди известных ограничений вложенных наборов Джо Селко (модифицированный обход предварительного заказа) стоит отметить снижение производительности по мере роста дерева до большого размера.
Вадим Тропашко предложил вложенные интервалы и приводит примеры и теоретическое объяснение в этой статье: http://arxiv.org/html/cs.DB/0401014
Это жизнеспособное решение, есть ли какие-нибудь жизнеспособные примеры (на любом языке), абстрагированные от собственного уровня БД?
Хотя я видел примеры для вложенных наборов, я видел мало для вложенных интервалов, хотя теоретически преобразование из одного в другое не должно быть трудным. Вместо того, чтобы выполнять предварительный обход для маркировки узлов, выполните рекурсию в ширину. Уловка состоит в том, чтобы найти наиболее эффективный способ пометить n дочерних узлов узла. Поскольку узел между a / b и c / d является (a + c) / (b + d), плохо подготовленная вставка (например, вставка дочерних элементов слева направо), рискует создать такой же экспоненциальный рост в значениях индекса, например, используя полный материализованный путь. Противодействовать этому эффекту несложно - создавайте новые индексы по одному, вставляя каждый в то место, которое дает наименьший результирующий знаменатель.
Что касается снижения производительности, многое зависит от операций, которые вы собираетесь выполнять. Есть еще некоторые операции, которые потребуют полной перемаркировки всего дерева - методы вложенного набора или вложенного интервала лучше всего подходят для структур, которые редко меняются. Если вы вносите много изменений в структуру иерархии, возможно, будет проще работать со «стандартной» структурой родительско-дочерней таблицы. помните также, что некоторые операции (например, количество потомков) намного проще с целочисленной маркировкой вложенных наборов, чем методы интервалов.
Я написал жемчужину, которая абстрагирует все вычисления вложенных интервалов, которые будут использоваться с Rails ActiveRecord https://github.com/clyfe/acts_as_nested_interval/, который используется в продакшене в нескольких системах.
