UB-tree

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

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

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

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

.