Улучшение масштабируемости модифицированного алгоритма обхода дерева предзаказов

Question

Я думал о модифицированном алгоритме обхода дерева предзаказа для хранения деревьев в плоской таблице (такой как SQL).

В стандартном подходе мне не нравится одно свойство: вставлять должны касаться (в среднем) N / 2 узлов (все, что слева или справа выше точки вставки).

Реализации, которые я видел, основаны на последовательно пронумерованных значениях. Это не оставляет места для обновлений.

Это кажется плохим для параллелизма и масштабирования. Представьте, что у вас есть дерево с корнями в мире, содержащее группы пользователей для каждой учетной записи в большой системе, оно чрезвычайно велико, и вы должны хранить подмножества дерева на разных серверах. Дотрагиваться до половины всех узлов, чтобы добавить узел к нижней части дерева, плохо.

Вот идея, которую я рассматривал. В основном оставьте место для вставок, разделив пространство клавиш и разделившись на каждом уровне.

Вот пример с N _max = 64 (обычно это MAX_INT вашей БД)

                     0:64
              ________|________
             /                 \
         1:31                   32:63
        /    \                 /     \
    2:14    15-30         33:47       48:62

Здесь узел добавляется к левой половине дерева.

                     0:64  
              ________|________
             /                 \
         1:31                  32:63
      /   |   \               /     \
  2:11  11:20  21:30     33:47       48:62

Алгоритм должен быть расширен для процесса вставки и удаления, чтобы рекурсивно перенумеровать в левый / правый индексы для поддерева. Поскольку запрос непосредственных потомков узла является сложным, я думаю, что имеет смысл также хранить родительский идентификатор в таблице. Затем алгоритм может выбрать поддерево (используя left> p.left && right

Это сложнее, чем просто увеличивать все индексы, чтобы освободить место для вставки (или уменьшить для удаления), но он может повлиять на гораздо меньшее количество узлов (только на потомков родительского элемента вставленного / удаленного узла).

Мои вопросы в основном:

1. Эта идея была формализована или реализована?

2. Это то же самое, что и вложенные интервалы?

Answer 1

Я слышал, что люди делали это раньше, по тем же причинам, да.

Обратите внимание, что при этом вы теряете пару небольших преимуществ алгоритма

• обычно вы можете определить количество потомков узла по ((справа - слева + 1) div 2). Иногда это может быть полезно, например, если вы бы отобразили счетчик в древовидной структуре, который должен включать количество детей, которые будут найдены ниже в дереве
• Исходя из вышесказанного, легко выбрать все конечные узлы - ГДЕ (справа = слева + 1).

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

Тем не менее, это звучит так, как будто материализованные пути могут быть более полезными для вас, как предложено выше.

Answer 2

Я думаю, вам лучше взглянуть на другой способ хранения деревьев. Если ваше дерево широкое, но не очень глубокое (что кажется вероятным для предложенного вами случая), вы можете хранить полный список предков вплоть до корня для каждого узла. Таким образом, изменение узла не требует прикосновения ни к каким узлам, кроме изменяемого узла.

Answer 3

Вы можете разделить вашу таблицу на две части: первая (идентификатор узла, значение узла), вторая (идентификатор узла, дочерний идентификатор), в которой хранятся все ребра дерева. Вставка и удаление становятся O (глубина дерева) (вам нужно перейти к элементу и исправить то, что под ним).

Предлагаемое вами решение выглядит как B-дерево . Если вы можете оценить общее количество узлов в вашем дереве, то вы можете заранее выбрать глубину дерева.