The UB-tree, also known as the Universal B-Tree, as proposed by
Rudolf Bayer 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 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 singl ...
. Like a
B+ tree
A B+ tree is an m-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children.
A B+ tree can be viewed as a B ...
, information is stored only in the leaves. Records are stored according to
Z-order, also called Morton order. Z-order is calculated by bitwise interlacing of 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" 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