R+ Дерево: Индексирование пространственных данных и оптимизация поиска
R+ tree
R+ дерево: эффективная структура данных для поиска пространственной информации (координаты X, Y). Индексация, компромисс между R-деревьями и kd-деревьями.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Дерево R+ – это метод поиска данных по местоположению, часто по координатам (x, y), и нередко для определения местоположений на поверхности Земли. Поиск по одному параметру – уже решенная задача, однако поиск по двум или более параметрам и запрос местоположений, близких по координатам x и y, требует более сложных алгоритмов. По сути, дерево R+ является древовидной структурой данных, вариантом R-дерева, используемым для индексирования пространственных данных.
An R+ tree is a method for looking up data using a location, often (x, y) coordinates, and often for locations on the surface of the Earth. Searching on one number is a solved problem; searching on two or more, and asking for locations that are nearby in both x and y directions, requires craftier algorithms. Fundamentally, an R+ tree is a tree data structure, a variant of the R tree, used for indexing spatial information.
Разница между деревьями R+ и R
R+ деревья — это компромисс между R-деревьями и kd-деревьями: они избегают перекрытия внутренних узлов, при необходимости вставляя объект в несколько листьев. Покрытие — это общая площадь, необходимая для охвата всех связанных прямоугольников. Перекрытие — это общая площадь, содержащаяся в двух или более узлах. Минимальное покрытие уменьшает количество "пустого пространства" (незанятой области), покрываемого узлами R-дерева. Минимальное перекрытие уменьшает количество поисковых путей к листьям (что еще более критично для времени доступа, чем минимальное покрытие). Эффективный поиск требует минимального покрытия и перекрытия. R+ деревья отличаются от R-деревьев тем, что: узлы не гарантированно заполнены хотя бы наполовину, записи любого внутреннего узла не перекрываются, и идентификатор объекта может храниться более чем в одном листе.
R+ trees are a compromise between R trees and kd trees: they avoid overlapping of internal nodes by inserting an object into multiple leaves if necessary. Coverage is the entire area to cover all related rectangles. Overlap is the entire area which is contained in two or more nodes. Minimal coverage reduces the amount of "dead space" (empty area) which is covered by the nodes of the R tree. Minimal overlap reduces the set of search paths to the leaves (even more critical for the access time than minimal coverage). Efficient search requires minimal coverage and overlap. R+ trees differ from R trees in that: nodes are not guaranteed to be at least half filled, the entries of any internal node do not overlap, and an object ID may be stored in more than one leaf node.
Преимущества
Поскольку узлы не перекрываются, производительность точечных запросов повышается, так как каждая пространственная область покрыта максимум одним узлом. Проходится по одному пути и посещается меньше узлов, чем в R-дереве.
Because nodes are not overlapped with each other, point query performance benefits since all spatial regions are covered by at most one node. A single path is followed and fewer nodes are visited than with the R tree.
Недостатки
Поскольку прямоугольники дублируются, R+ дерево может быть больше, чем R-дерево, построенное на том же наборе данных. Построение и поддержка R+ деревьев сложнее, чем построение и поддержка R-деревьев и других вариантов R-деревьев.
Since rectangles are duplicated, an R+ tree can be larger than an R tree built on same data set. Construction and maintenance of R+ trees is more complex than the construction and maintenance of R trees and other variants of the R tree.