Гильбертово R-дерево
-
R-дерево Гильберта
- Индекс для многомерных объектов, таких как линии, области и трехмерные объекты
- Использует кривую Гильберта для установления линейного порядка в прямоугольниках данных
- Существует два типа: для статических и динамических баз данных
-
Упакованные Гильбертовы R-деревья
- Подходят для статических баз данных с редкими обновлениями
- Используют кривую Гильберта для группировки прямоугольников данных
- Узлы полностью заполнены, за исключением последнего узла на каждом уровне
-
Динамические Гильбертовы R-деревья
- Поддерживают вставки и удаления
- Используют гибкий механизм отложенного разделения
- Каждый узел имеет четко определенный набор родственных узлов
-
Кривая Гильберта
- Базовая кривая на сетке 2х2
- Кривая порядка i заменяется кривой порядка i-1
- Кривая Гильберта накладывает линейный порядок на точки сетки
-
Алгоритм Гильберта-Pack
- Вычислить значение Гильберта для каждого прямоугольника данных
- Сортировка прямоугольников по возрастанию значений Гильберта
- Создание конечных узлов и узлов на более высоком уровне
-
Структура R-дерева Гильберта
- Конечные узлы содержат не более Cl записей
- Неконечные узлы содержат не более Cn записей
- LHV используется для определения порядка в узлах
-
Политика разделения
- Простое R-дерево разбивает узел при переполнении
- Политика разделения от 1 до 2
- Политика разделения от 2 до 3
- Политика разделения от s до(s+1)
-
Алгоритмы поиска, вставки и обработки переполнения
- Поисковый алгоритм
- Алгоритм вставки
- Обработка переполнения
-
Алгоритм поиска
- Начинается с корня и спускается по дереву
- Проверяет узлы, пересекающие прямоугольник запроса
- Сообщает о записях, пересекающихся с окном запроса
-
Вставка
- Используется гильбертово значение центра нового прямоугольника
- На каждом уровне выбирается узел с минимальным LHV
- Вставляется новый прямоугольник в конечный узел
- Вызывается AdjustTree для фиксации MBR и LHV
-
Алгоритм выбора листа
- Возвращает конечный узел для нового прямоугольника
- Инициализация, проверка листа, выбор поддерева, спуск до листа
-
Дерево настроек
- Регулирует MBR и LHV узлов, охватывающих узлы в наборе S
- Распространяет расколы, если таковые имеются
-
Удаление
- Не требует повторной вставки потерянных узлов
- Ключи могут быть заимствованы у дочерних узлов или узел объединен с дочерними
- Для удаления требуется s взаимодействующих братьев и сестер
-
Обработка переполнения
- Переполненные узлы перемещаются в s — 1 взаимодействующих братьев и сестер или разделяются на s + 1 узел
- Алгоритм HandleOverflow возвращает новый узел при разделении