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

Пусть S – множество из N гиперкубов, параллельных осям, в пространстве <math>\mathbb{R}_d \;</math>. Одной из простейших операций к пространственной базе данных является ответ на оконные запросы на множестве S. Оконный запрос Q также представляет собой параллельный осям гиперкуб в пространстве <math>\mathbb{R}_d \;</math>, который предлагает вернуть все гиперкубы из S, имеющие пересечение с Q. Поскольку S, как правило, очень велико и пространственная база также имеет очень большой размер, задача состоит в разработке структуры данных с внешней памятью на дисках (в посвященной базам данных литературе такая структура часто называется индексом), позволяющей эффективно отвечать на подобные оконные запросы. Кроме того, при заданном множестве S структура данных должна быть эффективной в построении и поддерживать вставку и удаление объектов.

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

R-дерево, введенное Гуттманом [9], представляет собой многовариантное дерево 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-дерева в двух измерениях.

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

Любое R-дерево занимает линейное число O(N/B) блоков на диске, однако у разных R-деревьев может быть разная стоимость запроса, обновления и построения. При анализе сложности оконных запросов наряду со значениями N, M и B также учитывается размер выходных данных T.