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

R-дерево, введенное Гуттманом [9], представляет собой многовариантное дерево <math>\mathcal{T} \;</math>, очень похожее на [[B-дерево (дерево многоканального поиска)|B-дерево]], использующееся для хранения множества S, благодаря чему на оконные запросы можно эффективно получать ответы. Каждая вершина <math>\mathcal{T} \;</math> помещается в один блок диска. Гиперкубы из S хранятся только в листьях <math>\mathcal{T} \;</math>. Все листья <math>\mathcal{T} \;</math> находятся на одном и том же уровне, в каждом из них хранится <math>\Theta(B) \;</math> гиперкубов из S; каждая внутренняя вершина, кроме корня, имеет [[\Theta(B) \;]] инцидентных ей исходящих дуг. Корень <math>\mathcal{T} \;</math> имеет только две исходящих дуги. Для любой вершины <math>u \in \mathcal{T} \;</math> обозначим за R(u) наименьший параллельный осям гиперкуб с, называемый минимальным ограничивающим прямоугольником, который включает все гиперкубы, хранящиеся ниже u. В каждой внутренней вершине <math>v \in \mathcal{T} \;</math> с детьми <math>v_1, ..., v_b \;</math> ограничивающий прямоугольник <math>R(v_i) \;</math> хранится вместе с указателем на <math>v_i \;</math> для i = 1, ..., k. Заметим, что эти ограничивающие прямоугольники могут перекрываться. На рис. 1 представлен пример R-дерева в двух измерениях.

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