The UB-tree as proposed by
Rudolf Bayer
Rudolf Bayer (born 3 March 1939) is a German computer scientist.
He is professor emeritus of Informatics at the Technical University of Munich where he had been employed since 1972. He is noted for inventing three data sorting structures: the B- ...
and
Volker Markl
Volker Markl (born 1971) is a German computer scientist and database systems researcher.
Career
In 1999, Markl received his PhD in computer science under the direction of Rudolf Bayer at the Technical University of Munich. His doctoral researc ...
is a
balanced tree
In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donald ...
for storing and efficiently retrieving
multidimensional data
In statistics, econometrics and related fields, multidimensional analysis (MDA) is a data analysis process that groups data into two categories: data dimensions and measurements. For example, a data set consisting of the number of wins for a sin ...
. It is basically a
B+ tree (information only in the leaves) with records stored according to
Z-order
Z-order is an ordering of overlapping two-dimensional objects, such as Window (computing), windows in a stacking window manager, shapes in a vector graphics editor, or objects in a 3D application.Foley, James, Andries van Dam, Steven Feiner, and ...
, also called Morton order. Z-order is simply calculated by bitwise interlacing the keys.
Insertion, deletion, and point query are done as with ordinary B+ trees. To perform range searches in multidimensional point data, however, an algorithm must be provided for calculating, from a point encountered in the data base, the next Z-value which is in the multidimensional search range.
The original algorithm to solve this key problem was exponential with the dimensionality and thus not feasible ("GetNextZ-address"). A solution to this "crucial part of the UB-tree range query" linear with the z-address bit length has been described later. This method has already been described in an older paper
where using Z-order with search trees has first been proposed.
References
Database index techniques
Search trees
{{algorithm-stub