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,{{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 |year=1996 |language=en}} 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{{cite CiteSeerX |first=V. |last=Markl |title=MISTRAL: Processing Relational Queries using a Multidimensional Access Technique |year=1999 |citeseerx=10.1.1.32.6487 }} ("GetNextZ-address"). A solution to this "crucial part of the UB-tree range query" has been described later.{{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}} This method has already been described in an older paper{{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}} where using Z-order with search trees has first been proposed.