UB-tree
Encyclopedia
The UB-tree as proposed by Rudolf Bayer
and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. It is basically a B+ tree
(information only in the leaves) with records stored according to Z-order
, also called Morton order. Z-order is simply calculated by bitwise interlacing 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 ("GetNextZ-address"). A solution to this "crucial part of the UB-tree range query" linear with the z-address bit length has been described later. This method has already been described in an older paper where using Z-order with search trees has first been proposed.
Rudolf Bayer
Rudolf Bayer has been Professor of Informatics at the Technical University of Munich since 1972. He is noted for inventing three data sorting structures: the B-tree , the UB-tree and the red-black tree.Bayer is a recipient of 2001 ACM SIGMOD Edgar F. Codd Innovations Award.-External links:*...
and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. It is basically a B+ tree
B+ tree
In computer science, a B+ tree or B plus tree is a type of tree which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. It is a dynamic, multilevel index, with maximum and minimum bounds on the number of...
(information only in the leaves) with records stored according to Z-order
Z-order (curve)
In mathematical analysis and computer science, Z-order, Morton order, or Morton code is a space-filling curve which maps multidimensional data to one dimension while preserving locality of the data points. It was introduced in 1966 by G. M. Morton...
, also called Morton order. Z-order is simply calculated by bitwise interlacing 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 ("GetNextZ-address"). A solution to this "crucial part of the UB-tree range query" linear with the z-address bit length has been described later. This method has already been described in an older paper where using Z-order with search trees has first been proposed.