View source for UB-tree

{{Short description|Tree structure in information science}}
{{Infobox data structure
| name               = UB-tree
| image              = Z-curve45.svg
| alt                = 
| caption            = Two dimensional Z-order
| type               = tree
| invented_by        = [[Rudolf Bayer]] and [[Volker Markl]]
| invented_year      = 
| space_avg          = 
| space_worst        = 
| search_avg         = 
| search_worst       = 
| insert_avg         = 
| insert_worst       = 
| delete_avg         = 
| delete_worst       = 
| peek_avg           = 
| peek_worst         = 
| find_min_avg       = 
| find_min_worst     = 
| delete_min_avg     = 
| delete_min_worst   = 
| decrease_key_avg   = 
| decrease_key_worst = 
| merge_avg          = 
| merge_worst        = 
}}
The '''UB-tree''', also known as the '''Universal B-Tree''',<ref>{{Cite book |last=Bayer |first=Rudolf |url=https://wwwbayer.in.tum.de/cgi-webcon/webcon/lehrstuhldb/download/39/application/pdf |title=The Universal B-Tree for multidimensional Indexing |date=September 1996 |language=en}}</ref> 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 (curve)|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<ref>{{cite CiteSeerX |first=V. |last=Markl |title=MISTRAL: Processing Relational Queries using a Multidimensional Access Technique |year=1999 |citeseerx=10.1.1.32.6487 }}</ref> ("GetNextZ-address"). A solution to this "crucial part of the UB-tree range query" has been described later.<ref>{{cite conference |first1=Frank |last1=Ramsak |first2=Volker |last2=Markl |first3=Robert |last3=Fenk |first4=Martin |last4=Zirkel |first5=Klaus |last5=Elhardt |first6=Rudolf |last6=Bayer |title=Integrating the UB-tree into a Database System Kernel |conference=26th International Conference on Very Large Data Bases |conference-url=http://www.vldb.org/archives/website/2000/ |date=September 10–14, 2000 |pages=263–272 |url=http://www.vldb.org/conf/2000/P263.pdf}}</ref> This method has already been described in an older paper<ref>{{cite journal |url=http://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf |first1=H. |last1=Tropf |first2=H. |last2=Herzog |title=Multidimensional Range Search in Dynamically Balanced Trees |journal=Angewandte Informatik (Applied Informatics) |issue=2/1981 |pages=71–77 |issn=0013-5704}}</ref> where using Z-order with search trees has first been proposed.

==References==
<references/>

{{CS-Trees}}

[[Category:Database index techniques]]
[[Category:Search trees]]


{{algorithm-stub}}