R-дерево - удалить алгоритм с помощью повторной вставки

Question

Я пытаюсь реализовать R-дерево в Scala, следуя указаниям из оригинальной статьи о структуре R-дерева. В разделе алгоритма удаления указано:

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

Я не могу обернуть голову вокруг последнегочасть. Что подразумевается под higher level nodes must be placed higher in the tree? Как это реализовано? Моя идея заключалась в том, что я удаляю узлы с заниженными значениями, добавляю их в набор Q (их записи) и, в конце концов, заново вставляю их записи, используя Insert. Это неправильно или частично правильно, что требует чего-то дополнительного? Если вы можете объяснить с помощью примеров, это было бы здорово.

Answer 1

Вставка и удаление значений в R-Tree является довольно дорогой операцией, когда необходимо поддерживать оптимальную балансировку для быстрого окна или ближайших запросов, особенно в многопоточной среде.

Более эффективный подходиспользование одного писателя (актера или потока), который собирает обновления в пакетном режиме, упаковывает новый экземпляр R-Tree и публикует его в некоторой энергозависимой переменной для чтения.

Здесь - сравнение некоторого R-Tree реализации, которые могут быть использованы таким образом из Scala.

Answer 2

Узлы должны быть вставлены с правильной высотой, иначе дерево станет недействительным. Помните, что все листья должны быть на одном уровне.