UB-tree

From Wikipedia, the free encyclopedia

The UB-tree as proposed by Rudolf Bayer and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. It is basically a B+ tree (information only in the leaves) with records stored according to Z-order (curve), 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 ^[1] ("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 ^[2]; this method has already been described in ^[3] (called "BIGMIN" algorithm) where using Z-order with search trees has first been proposed.

[edit] References

1. ^ [1]V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999.
2. ^ [2]F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Lage Databases, (VLDB) 2000, pp 263-272.
3. ^ [3]H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees, Angewandte Informatik, 2/1981, pp 71-77.