UB-tree
The UB-tree, also known as the Universal B-Tree,[1] as proposed by Rudolf Bayer and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. Like a B+ tree, information is stored only in the leaves. Records are stored according to Z-order, also called Morton order. Z-order is calculated by bitwise interlacing of 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[2] ("GetNextZ-address"). A solution to this "crucial part of the UB-tree range query" has been described later.[3] This method has already been described in an older paper[4] where using Z-order with search trees has first been proposed.
References
- ↑ Bayer, Rudolf (September 1996) (in en). The Universal B-Tree for multidimensional Indexing. https://wwwbayer.in.tum.de/cgi-webcon/webcon/lehrstuhldb/download/39/application/pdf.
- ↑ Markl, V. (1999). "MISTRAL: Processing Relational Queries using a Multidimensional Access Technique". CiteSeerX 10.1.1.32.6487.
- ↑ Ramsak, Frank; Markl, Volker; Fenk, Robert; Zirkel, Martin; Elhardt, Klaus; Bayer, Rudolf (September 10–14, 2000). "Integrating the UB-tree into a Database System Kernel". 26th International Conference on Very Large Data Bases. pp. 263–272. http://www.vldb.org/conf/2000/P263.pdf.
- ↑ Tropf, H.; Herzog, H.. "Multidimensional Range Search in Dynamically Balanced Trees". Angewandte Informatik (Applied Informatics) (2/1981): 71–77. ISSN 0013-5704. http://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf.
 |  |
