R-дерево: различия между версиями

При рассмотрении структур данных с внешней памятью в качестве модели вычислений нередко используется стандартная модель внешней памяти [ ], также называемая моделью ввода-вывода. В данной модели машина состоит из внешней памяти неограниченного объема (диска) и основной памяти размера M. Блок из В последовательных элементов может быть передан между основной и дисковой памятью за одну операцию ввода-вывода. Структура данных внешней памяти хранится на диске по блокам, но вычисление может производиться только над элементами в основной памяти, так что любая операция (такая как запрос, обновление и построение) на структуре данных должна включать некоторое число операций ввода-вывода; количеством операций ввода-вывода измеряется сложность основной операции.

R-дерево, введенное Гуттманом [ ], представляет собой многовариантное дерево T, очень похожее на B-дерево, использующееся для хранения множества S, благодаря чему на оконные запросы можно эффективно получать ответы. Каждая вершина T помещается в один блок диска. Гиперкубы из S хранятся только в листьях T. Все листья T находятся на одном и том же уровне, в каждом из них хранится 0{B) гиперкубов из S; каждая внутренняя вершина, кроме корня, имеет 0{B) инцидентных ей исходящих дуг. Корень T имеет только две исходящих дуги. Для любой вершины u 2 T обозначим за R(u) наименьший параллельный осям гиперкуб с, называемый минимальным ограничивающим прямоугольником, который включает все гиперкубы, хранящиеся ниже u. В каждой внутренней вершине v 2 T с детьми v1, ... ,Vb ограничивающий прямоугольник R(vi) хранится вместе с указателем на vi для i = 1, ...,  : : k. Заметим, что эти ограничивающие прямоугольники могут перекрываться. На рис. 1 представлен пример R-дерева в двух измерениях.

Хотя структура R-дерева ограничена, группировка гиперкубов в листья и группировка поддеревьев в поддеревья большей величины допускает немалую долю свободы. Различные стратегии группировки приводят к созданию различных вариантов R-деревьев. Большинство существующих R-деревьев используют различные эвристики для группировки гиперкубов, «близких» друг к другу в пространственном отношении, так что оконному запросу не придется посещать слишком много «лишних» вершин. В общем случае имеются два способа построения R-дерева: повторная вставка и массовая загрузка. К первому типу алгоритмов относятся исходное R-дерево [ ], R+-дерево [15], R*-дерево [6] и т.п. Эти алгоритмы используют O(logB N) операций ввода-вывода для вставки объекта и, следовательно, O(NlogB N) операций ввода-вывода для построения R-дерева на множестве S, что плохо масштабируется для больших значений N. Если множество S известно заранее, намного эффективнее оказывается организовать массовую загрузку всего R-дерева за один проход. Существует множество алгоритмов массовой загрузки – с ними можно ознакомиться, например, в [7, 8, 10, 11, 13]. Большинство этих алгоритмов строит R-дерево за O(N/B log M/B N/B) операций ввода-вывода (именно столько их требуется для сортировки N элементов); полученные в результате R-деревья обычно оказываются лучше созданных при помощи повторной вставки. За прошедшие десятилетия специалистами по работе с базами данных было опубликовано много работ, посвященных R-деревьям, полный список которых был бы слишком обширным. Манопулос и др. [14] приводят великолепный обзор литературы по данному вопросу. Однако ни один из вышеупомянутых вариантов R-деревьев не гарантирует нужной сложности выполнения запроса; Ардж и др. [3] построили пример, демонстрирующий, что в случае некоторых из наиболее популярных R-деревьев приходится посещать все вершины, не дав ни одного ответа.

Теорема 1 ([1, 12]). Имеется множество из N точек в пространстве Rd, такое, что для любого R-дерева T, построенного на этих точках, существует пустой оконный запрос, для выполнения которого алгоритм запроса должен посетить Z2((N/B)1-lld) вершин T.

R-дерево с приоритетами, предложенное Арджем и др. [ ], соответствует вышеприведенной нижней границе.

Теорема 2 ([3]). Для любого множества S, содержащего N параллельных осям гиперкубов в пространстве Rd, R-дерево с приоритетами отвечает на оконный запрос при помощи O{{NIB)l~lld + T/B) операций ввода-вывода и может быть построено при помощи O(N/BlogM/BN/B) операций ввода-вывода.

Было также отмечено, что R-деревья с приоритетами на практике работают весьма успешно [ 3]. Однако неизвестно, как эффективно обновлять их с сохранением границы для наихудшего случая. Для поддержки операций вставки и удаления был предложен логарифмический метод [3], однако получающаяся структура уже не будет R-деревом. Заметим, однако, что нижняя граница из теоремы 1 относится только к R-деревьям. Если структура данных не ограничена определением R-дерева, в процессе выполнения оконных запросов можно получить более подходящие границы; см., например, [4].