UB-дерево

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

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

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

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

Примечания
  1. Фолкер Маркль (1999). “MISTRAL: обработка реляционных запросов с использованием техники многомерного доступа”. CiteSeerX 10.1.1.32.6487.
  2. Франк Рамсак; Фолкер Маркл; Роберт Фенк; Мартин Циркель; Клаус Эльхардт; Рудольф Байер (September 10–14, 2000). «Интеграция UB-дерева в ядро системы баз данных» in 26-я Международная конференция по очень большим базам данных.: 263–272.
  3. Х. Тропф; Х. Херцог. “Поиск многомерного диапазона в динамически сбалансированных деревьях” (PDF). Прикладная информатика (2/1981): 71—77. ISSN 0013-5704. Используется устаревший параметр |coauthors= (справка)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.