R-деревья и их использование для организации индексов в пространственных базах данных
Коротко рассмотрим еще одно расширение механизма B-деревьев, используемое главным образом для организации индексов в пространственных базах данных, - R-деревья. Подобно B+-деревьям, R-дерево представляет собой ветвистую сбалансированную древовидную структуру с разной организацией внутренних и листовых страниц.
Но информация, хранящаяся в R-дереве несколько отличается от той, которая содержится в B-деревьях. В дополнение к находящимся в листовых страницах идентификаторам пространственных объектов, в R-деревьях хранится информация о границах индексируемого объекта. В случае двумерного пространства сохраняются горизонтальные и вертикальные координаты нижнего левого и верхнего правого углов наименьшего прямоугольника, содержащего индексируемый объект. Пример простого R-дерева, содержащего информацию о шести пространственных объектах, приведен на рисунке 5.7.
Рис. 5.7. Простое R-дерево для представления шести пространственных объектов
