R-дерево
-
Описание R-деревьев
- R-деревья используются для пространственного доступа и индексации многомерной информации.
- Предложены Антонином Гутманом в 1984 году.
- Применяются в реальном мире для хранения пространственных объектов и быстрого поиска.
-
Структура данных
- R-деревья группируют объекты по минимальному ограничивающему прямоугольнику.
- Каждый уровень дерева описывает все большее число объектов.
- R-деревья сбалансированы и упорядочивают данные по страницам.
-
Алгоритмы поиска
- Поиск выполняется с использованием ограничивающих рамок.
- Большинство узлов не считываются во время поиска.
- R-деревья подходят для больших наборов данных и баз данных.
-
Сложности и улучшения
- Основная сложность — построение эффективного дерева.
- Исследования направлены на улучшение построения и изменения дерева.
- R-деревья не гарантируют хорошей производительности в наихудшем случае.
-
Варианты и алгоритмы
- Приоритетное R-дерево, R*-дерево, R+ дерево, Гильбертово R-дерево, X-дерево.
- Алгоритмы включают поиск по диапазону, приоритетный поиск, вставку и разделение переполненных узлов.
-
Применение и преимущества
- R-деревья используются для хранения пространственных объектов и быстрого поиска.
- Обеспечивают преимущества в производительности по сравнению с наивной проверкой.
- Подходят для больших наборов данных и баз данных.
-
Разбиение и производительность
- Квадратичное разбиение Гуттмана: страницы часто перекрываются
- Линейное расщепление Гуттмана: более сложная структура, но быстрая в построении
- Раскол Грина: страницы пересекаются меньше, чем с Гуттманом
- Расширенное линейное разделение: создает разделенные страницы, что снижает производительность запросов
- Топологическое разделение R*-дерева: страницы перекрываются меньше, повторные вставки оптимизируют дерево
- Стратегия разделения отдает предпочтение квадратичным страницам для картографических приложений
-
Массовая загрузка и удаление
- Массовая загрузка R* дерева с использованием Sort-Tile-Recursive (STR): конечные страницы не перекрываются, страницы каталога незначительно перекрываются
- M-деревья: вложенные сферические страницы, разделение сложнее, страницы больше перекрываются
- Удаление записи: обновление ограничивающих прямоугольников, удаление страницы, повторная вставка дочерних элементов
-
Методы массовой загрузки
- Ближайший-X: сортировка по первой координате, разбиение на страницы нужного размера
- Упакованное Гильбертово R-дерево: сортировка по гильбертову значению центра прямоугольника
- Sort-Tile-Recursive (STR): оценка количества листьев, разбиение на разделы одинакового размера, повторная загрузка страниц
- Минимизация перекрытия сверху вниз (OMT): нисходящий подход, минимизация перекрытий, повышение производительности запросов
-
Другие структуры
- Дерево сегментов
- Интервальное дерево: вырожденное R-дерево для одного измерения
- Дерево K-d
- Иерархия ограничивающих объемов
- Пространственный индекс