Дерево R *

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

In данные обработка R * -деревья - это вариант R-деревьев, используемых для индексации пространственной информации. R * -деревья имеют немного более высокую стоимость строительства, чем стандартные R-деревья, так как данные могут нуждаться в повторной вставке; но получившееся дерево обычно будет иметь лучшую производительность запроса. Как и стандартное R-дерево, оно может хранить как точечные, так и пространственные данные. Он был предложен Норбертом Бекманном, Хансом-Петером Кригелем, Ральфом Шнайдером и Бернхардом Зигером в 1990 году.

• 1 Разница между R * -деревьями и R-деревьями
• 2 Производительность
• 3 Алгоритм и сложность
• 4 Ссылки
• 5 Внешние ссылки

R * -дерево, построенное путем повторной вставки (в ELKI ). В этом дереве мало перекрытий, что обеспечивает хорошую производительность запросов. Красные и синие MBR - это страницы индекса, зеленые - это листовые узлы.

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

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

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

Влияние различных эвристик разбиения на базу данных с почтовыми округами Германии

• 

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

• 

  R-Tree с линейным разбиением по Ang-Tan.. Хотя срезы не расширяются так далеко, как с Guttman, проблема срезов затрагивает почти каждую конечную страницу. Листовые страницы немного перекрываются, но страницы каталогов имеют место.

• 

  R * tree топологическое разделение.. Страницы перекрываются очень мало, так как R * -дерево пытается минимизировать перекрытие страниц, а повторные вставки дополнительно оптимизировали дерево. Стратегия разделения также не предпочитает срезы, поэтому получаемые страницы гораздо более полезны для обычных картографических приложений.

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

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

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

• СМИ, относящиеся к дереву R * на Wikimedia Commons