Loading AI tools
Из Википедии, свободной энциклопедии
R*-деревья — вариант R-деревьев, используемый для индексирования пространственной информации. R*-деревья имеют слегка повышенные затраты на создание, чем стандартные R-деревья, так как данные могут требовать переустановки (удаление + вставка), но получающееся дерево обычно имеет лучшую производительность запросов. Подобно стандартному R-дереву, оно может запоминать как точки, так и пространственные данные. Дерево предложили Норберт Бекман, Ганс-Петер Кригель, Ральф Шнайдер и Бернхард Сигер в 1990[1].
R* дерево | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Тип | структура данных | ||||||||||||
Год изобретения | 1990 | ||||||||||||
Автор | Норберт Бекман, Ганс-Петер Кригель, Ральф Шнайдер и Бернхард Сигер | ||||||||||||
Сложность в О-символике | |||||||||||||
|
|||||||||||||
Медиафайлы на Викискладе |
Минимизация как покрытия, так и перекрытия важны для производительности R-деревьев. Перекрытие означает, что при запросах данных или вставке более чем одну ветвь дерева нужно расширять (по причине метода разбиения данных на области, которые могут накладываться). Минимизированное покрытие улучшает удаление, позволяя исключать полные страницы из поиска более часто, в частности, для запросов с отрицательными диапазонами. R*-дерево пытается уменьшить оба значения, используя комбинацию алгоритма разбиения просмотренного узла и концепции принудительной переустановки при переполнении узла. Подход основан на наблюдении, что структуры R-дерева высокочувствительны к порядку, в котором элементы дерева были вставлены, так что структуры на основе вставок (а не на основе массовой загрузки) скорее будут подоптимальными. Удаление и повторная вставка элементов дерева позволяет «найти» им место в дереве, которое будет более пригодно, чем первоначальное их расположение.
Когда узел переполняется, часть его элементов удаляется из узла и устанавливается заново в дерево. (Чтобы избежать бесконечной каскадной переустановки, вызванной переполнением другого узла при этой операции, процедура переустановки может быть вызвана только один раз на каждом уровне дерева при вставке любого нового элемента.) Это приводит к созданию более хорошо кластеризованных групп элементов в узлах, уменьшая покрытие узла. Более того, часто разбиение узла часто откладывается, что приводит к увеличению среднего заполнения узла. Повторную вставку можно рассматривать как метод оптимизации увеличивающегося дерева при переполнении узла.
Запросы в худшем случае и сложность удаления идентичны таким же действиям в R-дереве. Стратегия вставки в R*-дерево имеет сложность и более сложна по сравнению со стратегией линейного разбиения () R-дерева, но менее сложна по сравнению со стратегией квадратного разбиения () для размера страницы в объектов и имеет малый вклад в общую сложность. Полная сложность вставки остаётся сравнимой со сложностью R-дерева: повторная вставка влияет максимум на одну ветку дерева, а потому даёт повторных вставок, что сравнимо по производительности с обычным R-деревом. Так что общая сложность R*-дерева совпадает со сложностью обычного R-дерева.
Реализация полного алгоритма должна предусматривать обработку многих угловых случаев и зависимых ситуаций, которые здесь не обсуждаются.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.