Меню
Главная
Случайная статья
Настройки
|
UB-дерево— сбалансированное дерево для хранения и эффективного извлечения многомерных данных[англ.]. Предложено Рудольфом Байером и Фолкером Марклем; является B-деревом с записями, хранящимися в соответствии с Z-порядком, также называемым порядком Мортона. Z-порядок вычисляется путём побитового чередования ключей.
Вставка, удаление и точечный запрос выполняются как с обычными B-деревьями. Однако для выполнения поиска по диапазону в многомерных точечных данных должен быть предусмотрен алгоритм для вычисления из точки, обнаруженной в базе данных, следующего Z-значения, которое находится в диапазоне многомерного поиска.
Первоначальный алгоритм решения этой ключевой проблемы был экспоненциально зависим от размерности и, следовательно, неосуществим[1] («ПолучитьДальшеZ-адрес»[уточнить]). Решение этой важной части запроса диапазона UB-дерева
Примечания
- Фолкер Маркль (1999). MISTRAL: обработка реляционных запросов с использованием техники многомерного доступа. CiteSeerX 10.1.1.32.6487.
-
-
|
|