R*-дерево

R* дерево
Тип	структура данных
Год изобретения	1990
Автор	Норберт Бекман, Ганс-Петер Кригель, Ральф Шнайдер и Бернхард Сигер
Сложность в О-символике
В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(log n) Вставка O(log n)
Медиафайлы на Викискладе

R*-деревья — вариант R-деревьев, используемый для индексирования пространственной информации. R*-деревья имеют слегка повышенные затраты на создание, чем стандартные R-деревья, так как данные могут требовать переустановки (удаление + вставка), но получающееся дерево обычно имеет лучшую производительность запросов. Подобно стандартному R-дереву, оно может запоминать как точки, так и пространственные данные. Дерево предложили Норберт Бекман, Ганс-Петер Кригель, Ральф Шнайдер и Бернхард Сигер в 1990^[1].

Отличие R*-деревьев и R-деревьев

R*-дерево, построенное путём кратной вставки (в ELKI^[англ.]). Есть небольшое перекрытие в этом дереве, что приводит к хорошей производительности запросов. Красные и синие прямоугольники являются страницами индексов, зелёные прямоугольники являются листьями.

Минимизация как покрытия, так и перекрытия важны для производительности R-деревьев. Перекрытие означает, что при запросах данных или вставке более чем одну ветвь дерева нужно расширять (по причине метода разбиения данных на области, которые могут накладываться). Минимизированное покрытие улучшает удаление, позволяя исключать полные страницы из поиска более часто, в частности, для запросов с отрицательными диапазонами. R*-дерево пытается уменьшить оба значения, используя комбинацию алгоритма разбиения просмотренного узла и концепции принудительной переустановки при переполнении узла. Подход основан на наблюдении, что структуры R-дерева высокочувствительны к порядку, в котором элементы дерева были вставлены, так что структуры на основе вставок (а не на основе массовой загрузки) скорее будут подоптимальными. Удаление и повторная вставка элементов дерева позволяет «найти» им место в дереве, которое будет более пригодно, чем первоначальное их расположение.

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

Производительность

• Улучшенная эвристика разбиения даёт страницы, которые более прямоугольны, а потому лучше приспособлены для многих алгоритмов.
• Метод повторной вставки оптимизирует существующее дерево, но увеличивает сложность.
• Эффективно поддерживает точки и пространственные данные.

• Результаты различных подходов к разбиению на базе данных немецких почтовых отделений
• 
  R-дерево с квадратным разбиением Гутмана ^[2].
  Есть много страниц, которые распространяются слева направо через всю Германию и страницы сильно перекрываются. Это не вполне благоприятное свойство для большинства приложений, для которых часто нужны только малые прямоугольные области, пересекающиеся со многими полосами.
• 
  R-дерево с линейным разбиением Анга-Тана^[3].
  Хотя прямоугольники не столь протяжёны, как в разбиении Гутмана, проблема разбиения на полосы действует почти на каждый лист на странице. Страницы листов пересекаются мало, но справочные страницы пересекаются сильно.
• 
  Топологическое разбиение R* дерева^[1].
  Страницы перекрываются очень мало, поскольку R*-дерево пытается минимизировать перекрытые страниц, а повторная вставка далее оптимизирует дерево. Стратегия разбиения также не даёт предпочтения полосам, так что получающиеся страницы более пригодны для картографических приложений.

Алгоритм и сложность

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

Запросы в худшем случае и сложность удаления идентичны таким же действиям в R-дереве. Стратегия вставки в R*-дерево имеет сложность ${\displaystyle {\mathcal {O}}(M\log M)}$ и более сложна по сравнению со стратегией линейного разбиения (${\displaystyle {\mathcal {O}}(M)}$) R-дерева, но менее сложна по сравнению со стратегией квадратного разбиения (${\displaystyle {\mathcal {O}}(M^{2})}$) для размера страницы в ${\displaystyle M}$ объектов и имеет малый вклад в общую сложность. Полная сложность вставки остаётся сравнимой со сложностью R-дерева: повторная вставка влияет максимум на одну ветку дерева, а потому даёт ${\displaystyle {\mathcal {O}}(\log n)}$ повторных вставок, что сравнимо по производительности с обычным R-деревом. Так что общая сложность R*-дерева совпадает со сложностью обычного R-дерева.

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

Примечания

1. Beckmann, Kriegel, Schneider, Seeger, 1990, с. 322.
2. Guttman, 1984, с. 47.
3. Ang, Tan, 1997, с. 337–349.

Литература

• Beckmann N., Kriegel H. P., Schneider R., Seeger B. The R*-tree: an efficient and robust access method for points and rectangles // Proceedings of the 1990 ACM SIGMOD international conference on Management of data — SIGMOD '90. — 1990. — ISBN 0897913655. — doi:10.1145/93597.98741.
• Guttman A. R-Trees: A Dynamic Index Structure for Spatial Searching // Proceedings of the 1984 ACM SIGMOD international conference on Management of data — SIGMOD '84. — 1984. — ISBN 0897911288. — doi:10.1145/602259.602266.
• Ang C. H., Tan T. C. New linear node splitting algorithm for R-trees // Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997 / Michel Scholl, Agnès Voisard. — Springer, 1997. — Т. 1262. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-63238-7_38.