Хотя я видел примеры для вложенных множеств , я не видел много для вложенных интервалов, хотя в теории не должно быть затруднительно преобразовать один в другой. Вместо обхода предварительного заказа для маркировки узлов, выполните рекурсию в ширину. Хитрость заключается в том, чтобы выработать наиболее эффективный способ маркировки n дочерних узлов. Поскольку узел между a / b и c / d является (a + c) / (b + d), плохо обусловленная вставка (например, вставка дочерних элементов слева направо) рискует создать такой же экспоненциальный рост в значениях индекса, например, используя полный материализованный путь . Нетрудно противодействовать этому эффекту - создавайте новые индексы по одному, вставляя каждый в место, которое производит наименьший полученный знаменатель.
Что касается снижения производительности, многое зависит от операций, которые вы собираетесь выполнять. Есть все еще некоторые операции, которые потребуют полной перемаркировки всего дерева - методы вложенного набора или вложенного интервала работают лучше всего для структур, которые редко изменяются. Если вы делаете много структурных изменений в иерархии, с «стандартной» структурой родительско-дочерних таблиц может быть проще работать. помните также, что некоторые операции (например, количество потомков) намного проще с целочисленной маркировкой вложенных множеств, чем интервальные методы.