UB-tree

The UB- tree ( "Universal B- Tree" ) was proposed by Rudolf Bayer and Volker Markl and is a data structure for multidimensional database systems. It is a B -tree, in which the data are stored sorted by the Z- curve ( calculating the Z values ​​by bitwise interleaving of the key ). The core idea of this method was proposed much earlier ( for search trees in general of drip and Duke, as well as B- trees of Orenstein and Merrett ).

Insert, Delete and exact requests are handled as in normal B trees. For multi-dimensional range queries, you need a method to starting to find one encountered in the data structure Z value, the next, which is within the multi-dimensional search area.

The originally specified by Rudolf Bayer process for this was the cost exponentially practically not usable with the number of dimensions and thus for more than 4 dimensions. A solution to the problem ( "crucial part of the UB -tree range query" ), linearly with the bit length of the Z- values ​​, was described later ( " GetNextZ -address" ); this method had already been described in ( " BIGMIN " calculation).