UB-tree explained

UB-tree
Type:tree
Invented By:Rudolf Bayer and Volker Markl

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, 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" has been described later.[2] This method has already been described in an older paper[3] where using Z-order with search trees has first been proposed.

References

  1. V. . Markl . MISTRAL: Processing Relational Queries using a Multidimensional Access Technique . 1999 . 10.1.1.32.6487 .
  2. Frank . Ramsak . Volker . Markl . Robert . Fenk . Martin . Zirkel . Klaus . Elhardt . Rudolf . Bayer . Integrating the UB-tree into a Database System Kernel . 26th International Conference on Very Large Data Bases . http://www.vldb.org/archives/website/2000/ . September 10–14, 2000 . 263–272 .
  3. Multidimensional Range Search in Dynamically Balanced Trees . H. . Tropf . H. . Herzog . Angewandte Informatik (Applied Informatics) . 2/1981 . 71–77 . 0013-5704.