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