Войти
R-дерево Гильберта, вариант R-дерева, является индексом для многомерных такие объекты, как линии, области, трехмерные объекты или параметрические объекты на основе пространственных объектов большой размерности. Его можно рассматривать как расширение B + -дерева для многомерных объектов.
Производительность R-деревьев зависит от качества алгоритма, который кластеризует прямоугольники данных на узле. R-деревья Гильберта используют кривые заполнения пространства и, в частности, кривую Гильберта, чтобы наложить линейный порядок на прямоугольники данных.
Существует два типа R-деревьев Гильберта: один для статических баз данных и один для динамических баз данных. В обоих случаях кривые заполнения гильбертова пространства используются для лучшего упорядочивания многомерных объектов в узле. Такой порядок должен быть «хорошим» в том смысле, что он должен группировать «похожие» прямоугольники данных вместе, чтобы минимизировать площадь и периметр результирующих минимальных ограничивающих прямоугольников (MBR). Упакованные R-деревья Гильберта подходят для статических баз данных, в которых обновления очень редки или в которых обновлений нет вообще.
Динамическое R-дерево Гильберта подходит для динамических баз данных, в которых в реальном времени могут происходить вставки, удаления или обновления. Кроме того, динамические R-деревья Гильберта используют гибкий механизм отложенного разделения для увеличения использования пространства. Каждый узел имеет четко определенный набор узлов-братьев. Это делается путем упорядочивания узлов R-дерева. R-дерево Гильберта сортирует прямоугольники в соответствии с центром прямоугольников (то есть MBR). (Значение Гильберта точки - это длина кривой Гильберта от начала до точки.) При заданном порядке каждый узел имеет четко определенный набор узлов-братьев; таким образом, можно использовать отложенное разделение. Регулируя политику разделения, R-дерево Гильберта может достичь желаемой степени использования пространства. Напротив, другие варианты R-дерева не контролируют использование пространства.
Хотя следующий пример предназначен для статической среды, он объясняет интуитивно понятный принципы хорошего дизайна R-дерева. Эти принципы действительны как для статических, так и для динамических баз данных.
Руссопулос и Лейфкер предложили метод построения упакованного R-дерева, который обеспечивает почти 100% -ное использование пространства. Идея состоит в том, чтобы отсортировать данные по координате x или y одного из углов прямоугольников. Сортировка по любой из четырех координат дает аналогичные результаты. В этом обсуждении точки или прямоугольники сортируются по координате x левого нижнего угла прямоугольника, что называется «R-деревом с низкой степенью сжатия». Просматривается отсортированный список прямоугольников; последовательные прямоугольники назначаются одному и тому же листу R-дерева, пока этот узел не заполнится; затем создается новый листовой узел, и сканирование отсортированного списка продолжается. Таким образом, узлы результирующего R-дерева будут полностью упакованы, за возможным исключением последнего узла на каждом уровне. Это приводит к использованию пространства ≈100%. Аналогичным образом создаются более высокие уровни дерева.
На рисунке 1 показана проблема R-дерева с низкой упаковкой. На рисунке 1 [справа] показаны конечные узлы R-дерева, которые метод упаковки lowx создаст для точек на рисунке 1 [слева]. Тот факт, что результирующие родительские узлы занимают небольшую площадь, объясняет, почему R-дерево с низкой степенью сжатия обеспечивает отличную производительность для точечных запросов. Однако тот факт, что у отцов большие периметры, объясняет снижение производительности запросов по регионам. Это согласуется с аналитическими формулами производительности R-дерева. Интуитивно понятно, что алгоритм упаковки в идеале должен назначать соседние точки одному листу. Незнание координаты y R-деревом с низкой степенью сжатия имеет тенденцию нарушать это эмпирическое правило.
Рис. 1: [Слева] 200 точек равномерно распределены; [Справа] MBR узлов, сгенерированных алгоритмом «lowx-упакованного R-дерева»
В разделе ниже описаны два варианта R-деревьев Гильберта. Первый индекс подходит для статической базы данных, в которой обновления очень редки или в которых обновлений нет вообще. Узлы результирующего R-дерева будут полностью упакованы, за возможным исключением последнего узла на каждом уровне. Таким образом, загрузка площадей составляет ≈100%; эта структура называется упакованным R-деревом Гильберта. Второй индекс, называемый динамическим гильбертовым R-деревом, поддерживает вставки и удаления и подходит для динамической среды.
Ниже приводится краткое введение в кривую Гильберта. Базовая кривая Гильберта на сетке 2x2, обозначенная H 1, показана на рисунке 2. Чтобы получить кривую порядка i, каждая вершина базовой кривой заменяется кривой порядка i - 1, которые можно соответствующим образом повернуть и / или отразить. На рисунке 2 также показаны кривые Гильберта второго и третьего порядка. Когда порядок кривой стремится к бесконечности, как и другие кривые заполнения пространства, результирующая кривая представляет собой фрактал с фрактальной размерностью, равной двум. Кривая Гильберта может быть обобщена для более высоких размерностей. Алгоритмы построения двумерной кривой заданного порядка можно найти в и. Алгоритм для более высоких размерностей приведен в.
Траектория кривой заполнения пространства накладывает линейный порядок на точки сетки; этот путь можно рассчитать, начав с одного конца кривой и проследив путь до другого конца. Фактические значения координат каждой точки можно вычислить. Однако для кривой Гильберта это намного сложнее, чем, например, для кривой Z-порядка. На рисунке 2 показан один такой порядок для сетки 4x4 (см. Кривую H 2). Например, точка (0,0) на кривой H 2 имеет значение Гильберта, равное 0, в то время как точка (1,1) имеет значение Гильберта, равное 2. Значение Гильберта прямоугольника равно определяется как значение Гильберта его центра.
Рисунок 2: Кривые Гильберта порядка 1, 2 и 3
Кривая Гильберта налагает линейное упорядочение на прямоугольники данных, а затем проходит по отсортированному списку, назначая каждый набор прямоугольников C узлу в R-дерево. Конечный результат состоит в том, что набор прямоугольников данных на одном и том же узле будет близок друг к другу в линейном порядке и, скорее всего, в собственном пространстве; таким образом, результирующие узлы R-дерева будут иметь меньшие площади. Рисунок 2 иллюстрирует интуитивно понятные причины, по которым наши методы, основанные на Гильберте, дают хорошие результаты. Данные состоят из точек (те же точки, что и на рисунке 1). Группируя точки в соответствии с их значениями Гильберта, MBR результирующих узлов R-дерева имеют тенденцию быть маленькими квадратными прямоугольниками. Это указывает на то, что узлы, скорее всего, будут иметь небольшую площадь и небольшой периметр. Значения небольшой площади обеспечивают хорошую производительность для точечных запросов; малая площадь и малые значения периметра обеспечивают хорошую производительность для больших запросов.
(упаковывает прямоугольники в R-дерево). Шаг 1. Вычислите значение Гильберта для каждого прямоугольника данных. Шаг 2. Сортировка прямоугольников данных по возрастанию Значения Гильберта. Шаг 3. / * Создаем листовые узлы (уровень l = 0) * /
Шаг 4. / * Создайте узлы на более высоком уровне (l + 1) * /
Здесь предполагается, что данные статичны или частота модификации мала. Это простая эвристика для построения R-дерева с ~ 100% использованием пространства, которое в то же время будет иметь хорошее время отклика.
Производительность R-деревьев зависит от качества алгоритма, который кластеризует прямоугольники данных на узле. R-деревья Гильберта используют кривые заполнения пространства, в частности кривую Гильберта, чтобы наложить линейный порядок на прямоугольники данных. Значение Гильберта прямоугольника определяется как значение Гильберта его центра.
R-дерево Гильберта имеет следующую структуру. Листовой узел содержит не более C l записей, каждая из которых имеет форму (R, obj _id), где C l - емкость листа, R - MBR реального объекта ( x low, x high, y low, y high), а obj-id - указатель на запись описания объекта. Основное различие между R-деревом Гильберта и R * -деревом состоит в том, что нелистовые узлы также содержат информацию о LHV (наибольшее значение Гильберта). Таким образом, нелистовой узел в R-дереве Гильберта содержит не более C n элементов формы (R, ptr, LHV), где C n - емкость не -leaf node, R - это MBR, которая охватывает всех дочерних узлов этого узла, ptr - указатель на дочерний узел, а LHV - наибольшее значение Гильберта среди прямоугольников данных, заключенных R. Обратите внимание, что, поскольку нелистовый узел выбирает одно из значений Гильберта дочерних узлов должно быть значением его собственного LHV, нет дополнительных затрат на вычисление значений Гильберта для MBR нелистовых узлов. На рисунке 3 показаны прямоугольники, организованные в R-дерево Гильберта. Значения Гильберта центров - это числа рядом с символами «x» (показаны только для родительского узла «II»). LHV указаны в [скобках]. На рисунке 4 показано, как дерево с рисунка 3 хранится на диске; содержимое родительского узла «II» показано более подробно. Каждый прямоугольник данных в узле «I» имеет гильбертовское значение v ≤33; аналогично каждый прямоугольник в узле 'II' имеет значение Гильберта больше 33 и ≤ 107 и т. д.
Рисунок 3: Прямоугольники данных, организованные в R-дерево Гильберта (значения Гильберта и наибольшие значения Гильберта (LHV) указаны в скобках)
Простое R-дерево разбивает узел при переполнении, создавая два узла из исходного. Эта политика называется политикой разделения «1 на 2». Также можно отложить разделение, дождавшись, пока два узла не разделятся на три. Обратите внимание, что это похоже на политику разделения B * -дерева. Этот метод называется политикой разделения «2 на 3».
В общем, это может быть расширено до политики разделения s-to- (s + 1); где s - порядок политики разделения. Чтобы реализовать политику разделения заказов, переполняющийся узел пытается протолкнуть некоторые из своих записей одному из своих s - 1 братьев и сестер; если все они заполнены, необходимо выполнить разделение s-to- (s + 1). S -1 братьев и сестер называются сотрудничающими братьями и сестрами.
Далее подробно описываются алгоритмы поиска, вставки и обработки переполнения.
Алгоритм поиска аналогичен тому, который используется в других вариантах R-дерева. Начиная с корня, он спускается по дереву и проверяет все узлы, которые пересекают прямоугольник запроса. На конечном уровне он сообщает обо всех записях, которые пересекают окно запроса как квалифицированные элементы данных.
Поиск алгоритма (корневой узел, прямоугольник w): . S1. Поиск нелистовых узлов:.
S2. Листовые узлы поиска:.
Рисунок 4: Файловая структура для R-дерева Гильберта
Чтобы вставить новый прямоугольник r в R-дереве Гильберта, значение Гильберта h центра нового прямоугольника используется в качестве ключа. На каждом уровне выбирается узел с минимальным значением LHV, превышающим h всех его братьев и сестер. Когда достигается листовой узел, прямоугольник r вставляется в правильном порядке согласно h. После того, как новый прямоугольник вставлен в листовой узел N, вызывается AdjustTree, чтобы зафиксировать MBR и наибольшие значения Гильберта в узлах верхнего уровня.
Вставка алгоритма (узел Корень, прямоугольник r): / * Вставляет новый прямоугольник r в R-дерево Гильберта. h - значение Гильберта прямоугольника * /. I1. Найдите соответствующий листовой узел:.
I2. Вставить r в листовой узел L:.
I3. Распространение изменений вверх:
I4. Увеличить дерево выше:
Алгоритм ChooseLeaf (rect r, int h): . / * Возвращает листовой узел, в который нужно поместить новый прямоугольник r. * /. C1. Инициализация:
C2. Проверка листа:
C3. Выберите поддерево:
C4. Спускайтесь до тех пор, пока не будет достигнут лист:
Algorithm AdjustTree (set S): . / * S - это набор узлов, который содержит обновляемый узел, его сотрудничающие братья и сестры (если произошло переполнение) и вновь созданный. узел NN (если произошло разделение). Подпрограмма поднимается от конечного уровня к корню, регулируя MBR и LHV узлов, которые покрывают узлы в S. Она распространяет разбиения (если есть) * /. A1. Если корневой уровень достигнут, остановитесь.. A2. Распространение узла, разделенного вверх:.
A3. Настройте MBR и LHV на родительском уровне:
A4. Переход на следующий уровень:
В R-дереве Гильберта нет необходимости повторно вставлять осиротевшие узлы всякий раз, когда родительский узел становится недостаточным. Вместо этого ключи могут быть заимствованы у братьев и сестер, или незаполненный узел объединяется со своими братьями и сестрами. Это возможно, потому что узлы имеют четкий порядок (в соответствии с наибольшим значением Гильберта, LHV); Напротив, в R-деревьях нет такой концепции относительно узлов-братьев. Обратите внимание, что операции удаления требуют s взаимодействующих братьев и сестер, тогда как операции вставки требуют s - 1 братьев и сестер.
Удаление алгоритма (r): . D1. Найдите лист хоста:.
D2. Удалить r:.
D3. Если L недополнение.
D4. Отрегулируйте MBR и LHV на родительских уровнях..
Алгоритм обработки переполнения в R-дереве Гильберта обрабатывает переполненные узлы либо путем перемещения некоторых записей в один из s - 1 взаимодействующих братьев и сестер, либо путем разделения s узлов на s +1 узлы.
Алгоритм HandleOverflow (узел N, прямоугольник r): . / * возвращает новый узел, если произошло разбиение. * /. H1. Пусть ε - набор, содержащий все элементы из N
H2. Добавьте r к ε.. H3. Если хотя бы один из s - 1 взаимодействующих братьев и сестер не заполнен,
H4. Если все s сотрудничающих братьев и сестер заполнены,
 | На Викискладе есть материалы, связанные с R-деревом Гильберта. |
