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