| UB-tree | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
 Two dimensional Z-order | ||||||||||||
| Type | tree | |||||||||||
| Invented by | Rudolf Bayer andVolker Markl | |||||||||||
| ||||||||||||
TheUB-tree, also known as theUniversal B-Tree,[1] as proposed byRudolf Bayer andVolker Markl is abalanced tree for storing and efficiently retrievingmultidimensional data. Like aB+ tree, information is stored only in the leaves. Records are stored according toZ-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[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.
 | Thisalgorithms ordata structures-related article is astub. You can help Wikipedia byadding missing information. |