R-дерево (структура данных)

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

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

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

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

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

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

Структура 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-дерево, основанное на методе кластеризации, где в качестве центра использован итерационный алгоритм решения «задачи размещения». Алгоритм имеет квадратичную вычислительную сложность, но обеспечивает построение более компактных огибающих параллелепипедов в записях вершин структуры.

Поиск

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

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

Достоинства

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

Недостатки

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

Ссылки

• Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47–57. ISBN 0-89791-128-8
• [research.att.com/~marioh/spatialindex/ Spatial Index Library]
• [habrahabr.ru/post/224965/ R*-tree или индексация геопространственных данных]
• [citeseer.ist.psu.edu/brakatsoulas02revisiting.html Revisiting R-tree Construction Principles. Sotiris Brakatsoulas, Dieter Pfoser, and Yannis Theodoridis ]
• Гулаков В.К., Трубаков А.О. [iipo.tu-bryansk.ru/index.php?id=book_mdstruct Многомерные структуры данных.] 2010. 387 стр. ISBN 978-5-89838-515-6

Отрывок, характеризующий R-дерево (структура данных)

Объехав всю линию войск от правого до левого фланга, князь Андрей поднялся на ту батарею, с которой, по словам штаб офицера, всё поле было видно. Здесь он слез с лошади и остановился у крайнего из четырех снятых с передков орудий. Впереди орудий ходил часовой артиллерист, вытянувшийся было перед офицером, но по сделанному ему знаку возобновивший свое равномерное, скучливое хождение. Сзади орудий стояли передки, еще сзади коновязь и костры артиллеристов. Налево, недалеко от крайнего орудия, был новый плетеный шалашик, из которого слышались оживленные офицерские голоса.
Действительно, с батареи открывался вид почти всего расположения русских войск и большей части неприятеля. Прямо против батареи, на горизонте противоположного бугра, виднелась деревня Шенграбен; левее и правее можно было различить в трех местах, среди дыма их костров, массы французских войск, которых, очевидно, большая часть находилась в самой деревне и за горою. Левее деревни, в дыму, казалось что то похожее на батарею, но простым глазом нельзя было рассмотреть хорошенько. Правый фланг наш располагался на довольно крутом возвышении, которое господствовало над позицией французов. По нем расположена была наша пехота, и на самом краю видны были драгуны. В центре, где и находилась та батарея Тушина, с которой рассматривал позицию князь Андрей, был самый отлогий и прямой спуск и подъем к ручью, отделявшему нас от Шенграбена. Налево войска наши примыкали к лесу, где дымились костры нашей, рубившей дрова, пехоты. Линия французов была шире нашей, и ясно было, что французы легко могли обойти нас с обеих сторон. Сзади нашей позиции был крутой и глубокий овраг, по которому трудно было отступать артиллерии и коннице. Князь Андрей, облокотясь на пушку и достав бумажник, начертил для себя план расположения войск. В двух местах он карандашом поставил заметки, намереваясь сообщить их Багратиону. Он предполагал, во первых, сосредоточить всю артиллерию в центре и, во вторых, кавалерию перевести назад, на ту сторону оврага. Князь Андрей, постоянно находясь при главнокомандующем, следя за движениями масс и общими распоряжениями и постоянно занимаясь историческими описаниями сражений, и в этом предстоящем деле невольно соображал будущий ход военных действий только в общих чертах. Ему представлялись лишь следующего рода крупные случайности: «Ежели неприятель поведет атаку на правый фланг, – говорил он сам себе, – Киевский гренадерский и Подольский егерский должны будут удерживать свою позицию до тех пор, пока резервы центра не подойдут к ним. В этом случае драгуны могут ударить во фланг и опрокинуть их. В случае же атаки на центр, мы выставляем на этом возвышении центральную батарею и под ее прикрытием стягиваем левый фланг и отступаем до оврага эшелонами», рассуждал он сам с собою…
Всё время, что он был на батарее у орудия, он, как это часто бывает, не переставая, слышал звуки голосов офицеров, говоривших в балагане, но не понимал ни одного слова из того, что они говорили. Вдруг звук голосов из балагана поразил его таким задушевным тоном, что он невольно стал прислушиваться.
– Нет, голубчик, – говорил приятный и как будто знакомый князю Андрею голос, – я говорю, что коли бы возможно было знать, что будет после смерти, тогда бы и смерти из нас никто не боялся. Так то, голубчик.
Другой, более молодой голос перебил его:
– Да бойся, не бойся, всё равно, – не минуешь.
– А всё боишься! Эх вы, ученые люди, – сказал третий мужественный голос, перебивая обоих. – То то вы, артиллеристы, и учены очень оттого, что всё с собой свезти можно, и водочки и закусочки.
И владелец мужественного голоса, видимо, пехотный офицер, засмеялся.
– А всё боишься, – продолжал первый знакомый голос. – Боишься неизвестности, вот чего. Как там ни говори, что душа на небо пойдет… ведь это мы знаем, что неба нет, a сфера одна.
Опять мужественный голос перебил артиллериста.
– Ну, угостите же травником то вашим, Тушин, – сказал он.
«А, это тот самый капитан, который без сапог стоял у маркитанта», подумал князь Андрей, с удовольствием признавая приятный философствовавший голос.
– Травничку можно, – сказал Тушин, – а всё таки будущую жизнь постигнуть…
Он не договорил. В это время в воздухе послышался свист; ближе, ближе, быстрее и слышнее, слышнее и быстрее, и ядро, как будто не договорив всего, что нужно было, с нечеловеческою силой взрывая брызги, шлепнулось в землю недалеко от балагана. Земля как будто ахнула от страшного удара.
В то же мгновение из балагана выскочил прежде всех маленький Тушин с закушенною на бок трубочкой; доброе, умное лицо его было несколько бледно. За ним вышел владетель мужественного голоса, молодцоватый пехотный офицер, и побежал к своей роте, на бегу застегиваясь.


Князь Андрей верхом остановился на батарее, глядя на дым орудия, из которого вылетело ядро. Глаза его разбегались по обширному пространству. Он видел только, что прежде неподвижные массы французов заколыхались, и что налево действительно была батарея. На ней еще не разошелся дымок. Французские два конные, вероятно, адъютанта, проскакали по горе. Под гору, вероятно, для усиления цепи, двигалась явственно видневшаяся небольшая колонна неприятеля. Еще дым первого выстрела не рассеялся, как показался другой дымок и выстрел. Сраженье началось. Князь Андрей повернул лошадь и поскакал назад в Грунт отыскивать князя Багратиона. Сзади себя он слышал, как канонада становилась чаще и громче. Видно, наши начинали отвечать. Внизу, в том месте, где проезжали парламентеры, послышались ружейные выстрелы.
Лемарруа (Le Marierois) с грозным письмом Бонапарта только что прискакал к Мюрату, и пристыженный Мюрат, желая загладить свою ошибку, тотчас же двинул свои войска на центр и в обход обоих флангов, надеясь еще до вечера и до прибытия императора раздавить ничтожный, стоявший перед ним, отряд.
«Началось! Вот оно!» думал князь Андрей, чувствуя, как кровь чаще начинала приливать к его сердцу. «Но где же? Как же выразится мой Тулон?» думал он.
Проезжая между тех же рот, которые ели кашу и пили водку четверть часа тому назад, он везде видел одни и те же быстрые движения строившихся и разбиравших ружья солдат, и на всех лицах узнавал он то чувство оживления, которое было в его сердце. «Началось! Вот оно! Страшно и весело!» говорило лицо каждого солдата и офицера.
Не доехав еще до строившегося укрепления, он увидел в вечернем свете пасмурного осеннего дня подвигавшихся ему навстречу верховых. Передовой, в бурке и картузе со смушками, ехал на белой лошади. Это был князь Багратион. Князь Андрей остановился, ожидая его. Князь Багратион приостановил свою лошадь и, узнав князя Андрея, кивнул ему головой. Он продолжал смотреть вперед в то время, как князь Андрей говорил ему то, что он видел.
Выражение: «началось! вот оно!» было даже и на крепком карем лице князя Багратиона с полузакрытыми, мутными, как будто невыспавшимися глазами. Князь Андрей с беспокойным любопытством вглядывался в это неподвижное лицо, и ему хотелось знать, думает ли и чувствует, и что думает, что чувствует этот человек в эту минуту? «Есть ли вообще что нибудь там, за этим неподвижным лицом?» спрашивал себя князь Андрей, глядя на него. Князь Багратион наклонил голову, в знак согласия на слова князя Андрея, и сказал: «Хорошо», с таким выражением, как будто всё то, что происходило и что ему сообщали, было именно то, что он уже предвидел. Князь Андрей, запихавшись от быстроты езды, говорил быстро. Князь Багратион произносил слова с своим восточным акцентом особенно медленно, как бы внушая, что торопиться некуда. Он тронул, однако, рысью свою лошадь по направлению к батарее Тушина. Князь Андрей вместе с свитой поехал за ним. За князем Багратионом ехали: свитский офицер, личный адъютант князя, Жерков, ординарец, дежурный штаб офицер на энглизированной красивой лошади и статский чиновник, аудитор, который из любопытства попросился ехать в сражение. Аудитор, полный мужчина с полным лицом, с наивною улыбкой радости оглядывался вокруг, трясясь на своей лошади, представляя странный вид в своей камлотовой шинели на фурштатском седле среди гусар, казаков и адъютантов.
– Вот хочет сраженье посмотреть, – сказал Жерков Болконскому, указывая на аудитора, – да под ложечкой уж заболело.
– Ну, полно вам, – проговорил аудитор с сияющею, наивною и вместе хитрою улыбкой, как будто ему лестно было, что он составлял предмет шуток Жеркова, и как будто он нарочно старался казаться глупее, чем он был в самом деле.
– Tres drole, mon monsieur prince, [Очень забавно, мой господин князь,] – сказал дежурный штаб офицер. (Он помнил, что по французски как то особенно говорится титул князь, и никак не мог наладить.)
В это время они все уже подъезжали к батарее Тушина, и впереди их ударилось ядро.
– Что ж это упало? – наивно улыбаясь, спросил аудитор.
– Лепешки французские, – сказал Жерков.
– Этим то бьют, значит? – спросил аудитор. – Страсть то какая!
И он, казалось, распускался весь от удовольствия. Едва он договорил, как опять раздался неожиданно страшный свист, вдруг прекратившийся ударом во что то жидкое, и ш ш ш шлеп – казак, ехавший несколько правее и сзади аудитора, с лошадью рухнулся на землю. Жерков и дежурный штаб офицер пригнулись к седлам и прочь поворотили лошадей. Аудитор остановился против казака, со внимательным любопытством рассматривая его. Казак был мертв, лошадь еще билась.