R*-дерево
-
R*-деревья: определение и особенности
- R*-деревья — разновидность R-деревьев для индексации пространственной информации
- Стоимость построения выше, чем у стандартных R-деревьев, но производительность лучше
- Хранят как точечные, так и пространственные данные
-
Различия между R*-деревьями и R-деревьями
- Минимизация охвата и перекрытия важна для производительности
- R*-дерево сокращает охват и перекрытие с помощью пересмотренного алгоритма разделения и принудительного повторного включения
- Удаление и повторная вставка записей оптимизируют дерево
-
Показатели качества разделения
- Перекрытие, Area и Margin используются для оценки качества разделения
- Улучшенная эвристика разделения делает страницы более прямоугольными
-
Стратегии разделения
- R*-дерево использует топологическое разбиение для минимизации перекрытия
- Повторные вставки оптимизируют дерево, но увеличивают сложность
-
Алгоритм и сложность
- R*-дерево использует тот же алгоритм для запросов и удалений, что и R-дерево
- Сложность вставки O(M log M) для страницы размером M объектов
- Общая сложность вставки сопоставима с R-деревом
-
Рекомендации и внешние ссылки
- Реализация полного алгоритма требует учета угловых случаев и связанных ситуаций
- Материалы по R*-tree доступны на Викискладе