The UB-tree as proposed by Rudolf Bayer and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data.

Records are stored according to Z-order, also called Morton order.

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").

[2] This method has already been described in an older paper[3] where using Z-order with search trees has first been proposed.