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[1] ("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.[2] This method has already been described in an older paper[3] where using Z-order with search trees has first been proposed.
Referencesedit
^Markl, V. (1999). "MISTRAL: Processing Relational Queries using a Multidimensional Access Technique". CiteSeerX10.1.1.32.6487.
^Ramsak, Frank; Markl, Volker; Fenk, Robert; Zirkel, Martin; Elhardt, Klaus; Bayer, Rudolf (September 10–14, 2000). Integrating the UB-tree into a Database System Kernel(PDF). 26th International Conference on Very Large Data Bases. pp. 263–272.
^Tropf, H.; Herzog, H. "Multidimensional Range Search in Dynamically Balanced Trees" (PDF). Angewandte Informatik (Applied Informatics) (2/1981): 71–77. ISSN 0013-5704.
tree, proposed, rudolf, bayer, volker, markl, balanced, tree, storing, efficiently, retrieving, multidimensional, data, basically, tree, information, only, leaves, with, records, stored, according, order, also, called, morton, order, order, simply, calculated,. 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 UB treeTwo dimensional Z orderTypetreeInvented byRudolf Bayer and Volker MarklTime complexity in big O notationAlgorithmAverageWorst caseInsertion 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 1 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 2 This method has already been described in an older paper 3 where using Z order with search trees has first been proposed References edit Markl V 1999 MISTRAL Processing Relational Queries using a Multidimensional Access Technique CiteSeerX 10 1 1 32 6487 Ramsak Frank Markl Volker Fenk Robert Zirkel Martin Elhardt Klaus Bayer Rudolf September 10 14 2000 Integrating the UB tree into a Database System Kernel PDF 26th International Conference on Very Large Data Bases pp 263 272 Tropf H Herzog H Multidimensional Range Search in Dynamically Balanced Trees PDF Angewandte Informatik Applied Informatics 2 1981 71 77 ISSN 0013 5704 nbsp This algorithms or data structures related article is a stub You can help Wikipedia by expanding it vte Retrieved from https en wikipedia org w index php title UB tree amp oldid 1179406150, wikipedia, wiki, book, books, library,
