UB-tree
In the area of UB-tree, numerous investigations, discussions and debates have arisen over the years. Since its inception, UB-tree has been the subject of interest not only at an academic level, but also in society in general. Its impact has been such that it has permeated different aspects of daily life, from culture, politics, economy, to technology. In this article, we will thoroughly explore the importance of UB-tree, its implications and its influence in today's world. From its origins to the present, we will analyze its evolution and its role in contemporary society.
| UB-tree | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
 Two dimensional Z-order | ||||||||||||
| Type | tree | |||||||||||
| Invented by | Rudolf Bayer and Volker Markl | |||||||||||
| ||||||||||||
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). The Universal B-Tree for multidimensional Indexing.
- ^ 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 (PDF). 26th International Conference on Very Large Data Bases. pp. 263–272.
- ^ Tropf, H.; Herzog, H. "Multidimensional Range Search in Dynamically Balanced Trees" (PDF). Angewandte Informatik (Applied Informatics) (2/1981): 71–77. ISSN 0013-5704.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |