UB tree

The UB tree ("Universal B-Tree") was proposed by Rudolf Bayer and Volker Markl and is a data structure for multi-dimensional database systems. It is a B ⁺ tree in which the data is stored sorted according to the Z curve (calculation of the Z values ​​by bit-wise entanglement of the keys). The core idea of ​​this procedure was proposed much earlier (for search trees in general by Tropf and Herzog and for B-trees by Orenstein and Merrett).

Insertion, deletion and exact queries are handled as with normal B + trees. For multi-dimensional area inquiries, a method is required to start from a Z-value found in the data structure to find the next one that lies within the multi-dimensional search area.

The procedure originally specified by Rudolf Bayer for this purpose was exponential in terms of effort with the number of dimensions and therefore not practicable for more than 4 dimensions. A solution to the problem (“crucial part of the UB tree range query”), linear with the bit length of the Z values, was described later (“GetNextZ-address”); this method was already described in ("BIGMIN" calculation).

See also

• Quadtree
• Kd tree
• R tree
• Area tree
• Gridfile as an alternative

Individual evidence

1. ↑ ^{a b} H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees, Applied Computer Science, 2/1981, pp 71-77. (PDF; 1.5 MB)
2. ↑ JA Orenstein and TH Merrett. A Class of Data Structures for Associative Searching. In PODS, 1984.
3. ^ V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999. ( Memento of the original from March 4, 2016 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. (PDF; 1.4 MB) 
4. ↑ F. Ramsak et al: Integrating the UB tree into a database system kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263-272. ( Memento of the original from March 4, 2016 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. (PDF; 136 kB)