Просмотр кода страницы UB-дерево

[[Файл:Z-curve45.svg|thumb|Двумерный Z-порядок.]]
'''UB-дерево'''— [[сбалансированное дерево]] для хранения и эффективного извлечения {{нп5|Многомерный анализ|многомерных данных||Multidimensional analysis}}. Предложено [[Байер, Рудольф|Рудольфом Байером]] и [[Маркль, Фолкер|Фолкером Марклем]]; является [[B⁺-дерево]]м с записями, хранящимися в соответствии с [[Кривая Мортона|Z-порядком]], также называемым порядком Мортона. Z-порядок вычисляется путём побитового чередования ключей.

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

Первоначальный алгоритм решения этой ключевой проблемы был экспоненциально зависим от размерности и, следовательно, неосуществим<ref>{{cite journal|author=Фолкер Маркль|title=MISTRAL: обработка реляционных запросов с использованием техники многомерного доступа|year=1999|citeseerx=10.1.1.32.6487}}</ref> («ПолучитьДальшеZ-адрес»{{уточнить}}). Решение этой важной части запроса диапазона UB-дерева{{уточнить}}, линейного с длиной в битах z-адреса, было описано позже<ref>{{cite conference|author=Франк Рамсак|coauthors=Фолкер Маркл; Роберт Фенк; Мартин Циркель; Клаус Эльхардт; Рудольф Байер|title=Интеграция UB-дерева в ядро системы баз данных|conference=26-я Международная конференция по очень большим базам данных|conference-url=http://www.vldb.org/archives/website/2000/|date=September 10–14, 2000|pages=263–272|url=http://www.vldb.org/conf/2000/P263.pdf|access-date=2021-04-29|archive-date=2021-04-29|archive-url=https://web.archive.org/web/20210429221041/http://www.vldb.org/conf/2000/P263.pdf|url-status=live}} {{Cite web |url=http://www.vldb.org/conf/2000/P263.pdf |title=Источник |access-date=2021-04-29 |archive-date=2021-04-29 |archive-url=https://web.archive.org/web/20210429221041/http://www.vldb.org/conf/2000/P263.pdf |url-status=unfit }}</ref>. Этот метод уже был описан в более старой статье<ref>{{cite journal|url=http://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf|author=Х. Тропф|author2=Х. Херцог|title=Поиск многомерного диапазона в динамически сбалансированных деревьях|journal=Прикладная информатика|issue=2/1981|pages=71–77|issn=0013-5704|access-date=2021-04-29|archive-date=2021-03-10|archive-url=https://web.archive.org/web/20210310001853/https://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf|url-status=live}}</ref>.

== Примечания ==
{{Примечания}}

{{rq|check|checktranslate}}
{{Деревья (структуры данных)}}

[[Категория:Техники индексации данных]]
[[Категория:Деревья поиска]]