R * дерево - R* tree

R * дерево
R * дерево
Изобретенный	1990 г.
Изобретенный	Норберт Бекманн, Ханс-Петер Кригель , Ральф Шнайдер и Бернхард Зигер
Сложность времени в большой нотации O

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

Разница между R * -деревьями и R-деревьями

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

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

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

Представление

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

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

R-дерево с квадратичным разбиением Гутмана.
Есть много страниц, которые простираются с востока на запад по всей Германии, и страницы сильно перекрываются. Это невыгодно для большинства приложений, которым часто требуется только небольшая прямоугольная область, которая пересекается со многими срезами.
R-Tree с линейным разбиением по Ang-Tan.
Хотя фрагменты не расширяются так далеко, как в случае с Гуттманом, проблема нарезки затрагивает почти каждую конечную страницу. Листовые страницы немного перекрываются, но страницы каталогов имеют место.
Топологическое разбиение дерева R * .
Страницы очень мало перекрываются, поскольку R * -дерево пытается минимизировать перекрытие страниц, а повторные вставки дополнительно оптимизировали дерево. Стратегия разделения также не предпочитает срезы, поэтому получаемые страницы гораздо более полезны для обычных картографических приложений.

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

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

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