R*-дерево

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

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

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

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

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

R*-дерево описывает три метрики, с помощью которых можно количественно оценить качество разделения. Это перекрытие (общее между R*-деревьями и R-деревьями), определяемое как область пересечения ограничивающих рамок двух кластеров; Значение площади представляет собой сумму площадей двух ограничивающих рамок кластера, а значение поля представляет собой сумму периметров двух ограничивающих рамок кластера.

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

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

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

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

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

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

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

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

Ссылки

^ Перейти обратно: ^а ^б Бекманн, Н.; Кригель, HP ; Шнайдер, Р.; Сигер, Б. (1990). «R*-дерево: эффективный и надежный метод доступа к точкам и прямоугольникам». Материалы международной конференции ACM SIGMOD 1990 г. по управлению данными - SIGMOD '90 (PDF) . п. 322. дои : 10.1145/93597.98741 . ISBN 0897913655 .
^ Гуттман, А. (1984). «R-деревья: структура динамического индекса для пространственного поиска». Материалы международной конференции ACM SIGMOD 1984 года по управлению данными - SIGMOD '84 (PDF) . п. 47. дои : 10.1145/602259.602266 . ISBN 0897911288 .
^ Анг, CH; Тан, ТК (1997). «Новый алгоритм линейного разделения узлов для R-деревьев». Ин Шолль, Мишель; Вуазар, Аньес (ред.). Материалы 5-го Международного симпозиума по достижениям в области пространственных баз данных (SSD '97), Берлин, Германия, 15–18 июля 1997 г. Конспекты лекций по информатике. Том. 1262. Спрингер. стр. 337–349. дои : 10.1007/3-540-63238-7_38 .

Внешние ссылки

СМИ, связанные с R*-деревом, на Викискладе?

[rstar-1] Перейти обратно: ^а ^б Бекманн, Н.; Кригель, HP ; Шнайдер, Р.; Сигер, Б. (1990). «R*-дерево: эффективный и надежный метод доступа к точкам и прямоугольникам». Материалы международной конференции ACM SIGMOD 1990 г. по управлению данными - SIGMOD '90 (PDF) . п. 322. дои : 10.1145/93597.98741 . ISBN 0897913655 .

[guttman-2] Гуттман, А. (1984). «R-деревья: структура динамического индекса для пространственного поиска». Материалы международной конференции ACM SIGMOD 1984 года по управлению данными - SIGMOD '84 (PDF) . п. 47. дои : 10.1145/602259.602266 . ISBN 0897911288 .

[ang-tan-3] Анг, CH; Тан, ТК (1997). «Новый алгоритм линейного разделения узлов для R-деревьев». Ин Шолль, Мишель; Вуазар, Аньес (ред.). Материалы 5-го Международного симпозиума по достижениям в области пространственных баз данных (SSD '97), Берлин, Германия, 15–18 июля 1997 г. Конспекты лекций по информатике. Том. 1262. Спрингер. стр. 337–349. дои : 10.1007/3-540-63238-7_38 .

[ 1 ]

[ 2 ]

[ 3 ]

v т и Древовидные структуры данных
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic Palindrome (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal d-ary Fibonacci Leftist Pairing Skew binomial Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

v т и Структуры данных
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures