WikiDer > УБ-дерево

UB-tree
Двумерный Z-порядок

В УБ-дерево как предложено Рудольф Байер и Фолькер Маркл это сбалансированное дерево для хранения и эффективного извлечения многомерные данные. Это в основном B + дерево (информация только в листах) с записями, хранящимися согласно Z-порядок, также называемый орденом Мортона. Z-порядок просто вычисляется путем побитового чередования ключей.

Вставка, удаление и точечный запрос выполняются как с обычными деревьями B +. Однако для выполнения поиска по диапазону в многомерных точечных данных должен быть предусмотрен алгоритм для вычисления из точки, обнаруженной в базе данных, следующего Z-значения, которое находится в диапазоне многомерного поиска.

Первоначальный алгоритм решения этой ключевой проблемы был экспоненциальным с размерностью и, следовательно, неосуществим.[1] ("GetNextZ-адрес"). Решение этой «важной части запроса диапазона UB-дерева», линейного с длиной в битах z-адреса, было описано позже.[2] Этот метод уже был описан в более старой статье.[3] где впервые было предложено использование Z-порядка с деревьями поиска.

Рекомендации

  1. ^ Маркл В. (1999). "MISTRAL: Обработка реляционных запросов с использованием техники многомерного доступа". CiteSeerX 10.1.1.32.6487. Цитировать журнал требует | журнал = (помощь)
  2. ^ Рамсак, Франк; Маркл, Фолькер; Фенк, Роберт; Циркель, Мартин; Эльхардт, Клаус; Байер, Рудольф (10–14 сентября 2000 г.). Интеграция UB-дерева в ядро ​​системы баз данных. 26-я Международная конференция по очень большим базам данных. С. 263–272.
  3. ^ Tropf, H .; Герцог, Х. «Поиск многомерного диапазона в динамически сбалансированных деревьях» (PDF). Angewandte Informatik (Прикладная информатика) (2/1981): 71–77. ISSN 0013-5704.