UB-tree

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 [ [http://citeseer.comp.nus.edu.sg/rd/0%2C383353%2C1%2C0.25%2CDownload/http://citeseer.comp.nus.edu.sg/cache/papers/cs/18083/http:zSzzSzmistral.informatik.tu-muenchen.dezSzresultszSzpublicationszSzMar99.pdf/mistral-processing-relational-queries.pdf] V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999.] ("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 [ [http://www.vldb.org/conf/2000/P263.pdf] F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Lage Databases, (VLDB) 2000, pp 263-272.] ; this method has already been described in [ [http://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf] H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees, Angewandte Informatik, 2/1981, pp 71-77.] (called "BIGMIN" algorithm) where using Z-order with search trees has first been proposed.

References