Bx-дерево
-
Структура индекса Bx-дерева
- Bx-дерево использует дерево B+ для индексации движущихся объектов.
- Внутренние узлы содержат указатели на правых родственников.
- Конечные узлы содержат идентификатор, скорость, значение отображения и время последнего обновления.
-
Использование дерева B+ для перемещения объектов
- Двумерные объекты моделируются как линейные функции.
- Дерево B+ используется для линеаризации местоположения объектов.
- Объекты разбиваются на разделы по времени обновления.
- Местоположение объектов линеаризуется внутри разделов.
-
Установка, обновление и удаление
- Для вставки нового объекта вычисляется индексный ключ.
- Обновление состоит из удаления и вставки.
- Вспомогательная структура используется для хранения последнего ключа.
-
Запросы
- Запрос диапазона извлекает объекты в пределах заданного диапазона.
- Используется метод увеличения окна запроса.
- Запрос K ближайших соседей вычисляется итеративно.
-
Адаптация движков реляционных баз данных
- Bx-дерево легко интегрируется в существующие СУБД.
- SpADE использует Bx-дерево для индексации объектов в MySQL.
-
Настройка производительности
- Искажение данных может снизить производительность.
- ST2B-дерево использует самонастраивающуюся структуру для оптимизации.
- ST2B-дерево разбивает пространство на области с разной плотностью объектов.