Interested Article - UB-дерево

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

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

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

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

Примечания

  1. Фолкер Маркль (1999). "MISTRAL: обработка реляционных запросов с использованием техники многомерного доступа". CiteSeerX . {{ cite journal }} : Cite journal требует |journal= ( справка )
  2. Франк Рамсак (September 10–14, 2000). (PDF) . . pp. 263—272. (PDF) из оригинала 29 апреля 2021 . Дата обращения: 29 апреля 2021 . {{ cite conference }} : Неизвестный параметр |coauthors= игнорируется ( |author= предлагается) ( справка ) . Дата обращения: 29 апреля 2021. Архивировано 29 апреля 2021 года.
  3. Х. Тропф; Х. Херцог. (PDF) . Прикладная информатика (2/1981): 71—77. ISSN . (PDF) из оригинала 10 марта 2021 . Дата обращения: 29 апреля 2021 .
Источник —

Same as UB-дерево