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.

UB-tree
Two dimensional Z-order
Type	tree
Invented by	Rudolf Bayer and Volker Markl
Time complexity in big O notation Operation Average Worst case Space complexity

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.