PROFILBARU.COM

R-дерево
R-дерево
Тип	Многомерное дерево Двоичное дерево поиска
Год изобретения	1984
Автор	Антонин Гуттман
Сложность в О-символике
	Медиафайлы на Викискладе

R-дерево (англ. R-trees) — древовидная структура данных (дерево), предложенная в 1984 году Антонином Гуттманом. Она подобна B-дереву, но используется для организации доступа к пространственным данным, то есть для индексации многомерной информации, такой, например, как географические данные с двумерными координатами (широтой и долготой). Типичным запросом с использованием R-деревьев мог бы быть такой: «Найти все музеи в пределах 2 километров от моего текущего местоположения».

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

Алгоритмы вставки и удаления используют эти ограничивающие прямоугольники для обеспечения того, чтобы «близкорасположенные» объекты были помещены в одну листовую вершину. В частности, новый объект попадёт в ту листовую вершину, для которой потребуется наименьшее расширение её ограничивающего прямоугольника. Каждый элемент листовой вершины хранит два поля данных: способ идентификации данных, описывающих объект, (либо сами эти данные) и ограничивающий прямоугольник этого объекта.

Аналогично, алгоритмы поиска (например, пересечение, включение, окрестности) используют ограничивающие прямоугольники для принятия решения о необходимости поиска в дочерней вершине. Таким образом, большинство вершин никогда не затрагиваются в ходе поиска. Как и в случае с B-деревьями, это свойство R-деревьев обусловливает их применимость для баз данных, где вершины могут выгружаться на диск по мере необходимости.

Для расщепления переполненных вершин могут применяться различные алгоритмы, что порождает деление R-деревьев на подтипы: квадратичные и линейные.

Изначально R-деревья не гарантировали хороших характеристик для наихудшего случая, хотя хорошо работали на реальных данных. Однако в 2004-м году был опубликован новый алгоритм, определяющий приоритетные R-деревья. Утверждается, что этот алгоритм эффективен, как и наиболее эффективные современные методы, и в то же время является оптимальным для наихудшего случая^[1].

Структура R-дерева

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

MaxEntries — максимальное число детей у вершины
MinEntries — минимальное число детей у вершины, за исключением корня.

Для корректной работы алгоритмов необходимо выполнение условия MinEntries <= MaxEntries / 2. В корневой вершине может быть от 2 до MaxEntries потомков. Часто выбирают MinEntries = 2, тогда для корня выполняются те же условия, что и для остальных вершин. Также иногда разумно выделять отдельные константы для количества точек в листовых вершинах, так как их часто можно делать больше.

Алгоритмы

Вставка

Построение R-дерева происходит, как правило, с помощью многократного вызова операции вставки элемента в дерево. Идея вставки похожа на вставку в B-дерево: если добавление элемента в очередную вершину приводит к переполнению, то вершина разделяется. Приведём ниже классический алгоритм вставки, описанный Антонином Гуттманом.

Функция Insert

Вызывает ChooseLeaf, чтобы выбрать лист, куда необходимо добавить элемент. Если вставка выполнена, то дерево могло быть разделено, и разделение могло дойти до вершины. В этом случае ChooseLeaf возвращает две разделенные вершины SplitNodes для вставки в корень
Вызывает функцию AdjustBounds, которая расширяет ограничивающий прямоугольник корня на вставляемую точку
Проверяет, если ChooseLeaf вернула ненулевые SplitNodes, то дерево растёт на уровень вверх: с этого момента корнем объявляется вершина, дети которой те самые SplitNodes

Функция ChooseLeaf

если на входе лист (база рекурсии), то:
- вызывает функцию DoInsert, которая осуществляет непосредственную вставку элемента в дерево и возвращает два листа, если произошло разделение
- изменяет ограничивающий прямоугольник вершины с учётом вставленного элемента
- возвращает SplitNodes, которые нам вернул DoInsert
если на входе нелистовая вершина:
- из всех потомков выбирается тот, чьи границы требуют минимального увеличения для вставки данного элемента
- рекурсивно вызывается ChooseLeaf для выбранного потомка
- поправляются ограничивающие прямоугольники
- если splittedNodes от рекурсивного вызова нулевые, то покидаем функцию, иначе:
  - если NumEntries < MaxEntries, то добавляем новую вершину к детям, чистим SplitNodes
  - иначе (когда нет мест для вставки), мы конкатенируем массив детей с новой вершиной и передаём полученное функции LinearSplitNodes или другой функции разделения вершин, и вернём из ChooseLeaf те SplitNodes, которые нам вернула используемая функция разделения.

Функция LinearSplit

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

по каждой координате для всего набора разделяемых вершин вычисляется разница между максимальной нижней границей прямоугольника по этой координате и минимальной верхней, затем эта величина нормализуется на разницу между максимальной и минимальной координатой точек исходного набора для построения всего дерева
находится максимум этого нормализованного разброса по всем координатам
устанавливаем в качестве первых детей для возвращаемых вершин node1 и node2 те вершины из входного списка, на которых достигался максимум, удаляем их из входного списка, корректируем bounds для node1 и node2
далее, выполняется вставка для оставшихся вершин:
- если в списке осталось настолько мало вершин, что если их все добавить в одну из выходных вершин, то в ней окажется MinEntries вершин, то в неё добавляется остаток, возврат из функции
- если в какой-то из вершин уже набран максимум потомков, то остаток добавляется в противоположную, возврат
- для очередной вершины из списка сравнивается, на сколько надо увеличить ограничивающий прямоугольник при вставке в каждую из двух будущих вершин, где меньше — туда её и вставляется

Функция физической вставки DoInsert

если в вершине есть свободные места, то точка вставляется туда
если же мест нет, то дети вершины конкатенируются со вставляемой точкой и вызывается функция LinearSplit или другую функцию разделения, возвращающую две разделённые вершины, которые мы возвращаем из doInsert

Разбиение с помощью алгоритмов кластеризации

Иногда вместо R-дерева используют так называемое cR-дерево (c означает clustered). Основная идея в том, что для разделения вершин или точек используются алгоритмы кластеризации, такие как k-means. Сложность k-means тоже линейная, но он в большинстве случаев даёт лучший результат, чем линейный алгоритм разделения Гуттмана, в отличие от которого он не только минимизирует суммарную площадь огибающих параллелепипедов, но и расстояние между ними и площадь перекрытия. Для кластеризации точек используется выбранная метрика исходного пространства, для кластеризации вершин можно использовать расстояние между центрами их огибающих параллелепипедов или максимальное расстояние между ними.

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

Интересна идея использовать кластеризацию на несколько кластеров, где несколько может быть больше двух. Однако надо учитывать, что это накладывает определённые ограничения на параметры структуры р-дерева.

Отметим, что помимо cR-дерева существует его вариация clR-дерево, основанное на методе кластеризации, где в качестве центра использован итерационный алгоритм решения «задачи размещения». Алгоритм имеет квадратичную вычислительную сложность, но обеспечивает построение более компактных огибающих параллелепипедов в записях вершин структуры.

Поиск

Поиск в дереве довольно тривиален, надо лишь учитывать тот факт, что каждая точка пространства может быть покрыта несколькими вершинами.

Удаление

Данный алгоритм^[2] удаляет некоторую запись E из R-дерева. Алгоритм состоит из следующих шагов:

Поиск узла, содержащего запись. Вызвать функцию поиска FindLeaf для того чтобы найти лист L, содержащий запись E. Остановить выполнение алгоритма, если запись не найдена.
Удаление записи. Удалить запись E из листа L.
Обновление изменений. Вызвать функцию CondenseTree для записи L.
Проверка корня дерева. Если корень дерева - не листовой узел, в котором осталась только одна запись, то сделать эту запись корнем дерева.

Функция FindLeaf

Пусть T - корень дерева, в E - искомая запись.

Поиск в поддереве. Если T - не листовой узел, то проверить каждое вхождение записи E в каждой записи узла T по следующему условию: если запись E входит в прямоугольник записи в T, то вызвать функцию FindLeaf.
Поиск записи в листовом узле. Если T - лист, то найти запись E в этом листе, и если нашлась - вернуть ее.

Функция CondenseTree

Пусть из листа L удалили запись E. Тогда, необходимо устранить тот узел, у которого осталось мало записей (меньше чем MinEntries) и переместить его записи. При продвижении вверх по дереву, если необходимо - совершать удаление записей (по тому же самому критерию). По пути к корню перерасчитывать прямоугольники, делая их как можно меньше. Ниже описан алгоритм. Данную функцию можно реализовать и с помощью рекурсии.

Инициализация. Пусть N = L, а Q - множество удаленных узлов, изначально пустое.
Найти вышестоящий узел. Если N - корень, то перейти к последнему шагу алгоритма (вставка записей заново). Иначе пусть P - родитель узла N.
Исключение маленьких узлов. Если узел N имеет меньше MinEntries записей, то удалить N из P и добавить его в Q.
Перерасчет прямоугольников. Если N не была удалена, то перерасчитать его прямоугольник так, чтобы он содержал в себе все записи в N.
Движение вверх по дереву. Пусть N = P. Повторить второй шаг поиска вышестоящего узла.
Вставка "осиротевших" записей. Нужно вставить заново записи из множества Q. Если запись в Q - листовой узел, то все его записи вставить по алгоритму Insert. Если Q - не листовой узел, то его нужно вставить так, чтобы все его листовые узлы были на том же уровне дерева, что и листовые узлы самого дерева (по свойству R-дерева, согласно которому все листовые узлы хранятся на одном уровне глубины дерева).

Обсуждение R-деревьев

Достоинства

эффективно хранят локализованные в пространстве группы объектов
сбалансированный, значит, быстрый поиск в худшем случае
вставка/удаление одной точки не требует существенной перестройки дерева (динамический индекс)

Недостатки

чувствительно к порядку добавляемых данных
ограничивающие прямоугольники вершин могут перекрываться

См. также

Список структур данных (деревья)

Примечания

↑ L. Arge; M. de Berg; H. J. Haverkort; K. Yi (2004). "The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree" (PDF). SIGMOD. Архивировано (PDF) 6 марта 2021. Дата обращения: 12 октября 2011.
↑ Antonin Guttman. [https://klevas.mif.vu.lt/~algis/DSA/guttman.pdf R-TREES. A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING] (англ.) // ACM. — 1984. Архивировано 24 марта 2018 года.