UB-дерево
| UB-дерево | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
 Двумерный Z-порядок | ||||||||||||
| Тип | дерево | |||||||||||
| Изобретён | Рудольф Байер и Фолькер Маркл | |||||||||||
| ||||||||||||
UB -дерево , предложенное Рудольфом Байером и Фолькером Марклом, представляет собой сбалансированное дерево для хранения и эффективного извлечения многомерных данных . По сути, это B+-дерево (информация только в листьях) с записями, хранящимися в соответствии с Z-порядком , также называемым порядком Мортона. Z-порядок просто вычисляется путем побитового чередования ключей.
Вставка, удаление и точечный запрос выполняются так же, как и в обычных деревьях B+. Однако для выполнения поиска диапазона в многомерных точечных данных должен быть предусмотрен алгоритм для вычисления из точки, обнаруженной в базе данных, следующего Z-значения, которое находится в многомерном диапазоне поиска.
Первоначальный алгоритм решения этой ключевой проблемы был экспоненциальным с размерностью и поэтому был неосуществим. [1] («GetNextZ-адрес»). Решение этой «важнейшей части запроса диапазона UB-дерева» будет описано позже. [2] Этот метод уже был описан в более старой статье. [3] где впервые было предложено использование Z-порядка с деревьями поиска.
Ссылки [ править ]
- ^ Маркл, В. (1999). «МИСТРАЛЬ: обработка реляционных запросов с использованием метода многомерного доступа». CiteSeerX 10.1.1.32.6487 .
- ^ Рамсак, Фрэнк; Маркл, Волкер; Фенк, Роберт; Циркель, Мартин; Эльхардт, Клаус; Байер, Рудольф (10–14 сентября 2000 г.). Интеграция UB-дерева в ядро системы базы данных (PDF) . 26-я Международная конференция по очень большим базам данных . стр. 263–272.
- ^ Тропф, Х.; Херцог, Х. «Поиск многомерного диапазона в динамически сбалансированных деревьях» (PDF) . Angewandte Informatik (Прикладная информатика) (2/1981): 71–77. ISSN 0013-5704 .
 | Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее . |