UB-tree
UB-tree | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
![]() Two dimensional Z-order | ||||||||||||
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
- ^ 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.
- v
- t
- e
(dynamic sets/associative arrays)
- 2–3
- 2–3–4
- AA
- (a,b)
- AVL
- B
- B+
- B*
- Bx
- (Optimal) Binary search
- Dancing
- HTree
- Interval
- Order statistic
- Palindrome
- (Left-leaning) Red–black
- Scapegoat
- Splay
- T
- Treap
- UB
- Weight-balanced
![]() | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |
- v
- t
- e