HOME

TheInfoList



OR:

The UB-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 ...
. It is basically 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 ...
(information only in the leaves) with records stored according to Z-order, 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