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

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

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

Примечания