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

R-деревья

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