UB-tree

From Wikipedia, the free 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^[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

↑ Markl, V. (1999). MISTRAL: Processing Relational Queries using a Multidimensional Access Technique.
↑ 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". 26th International Conference on Very Large Data Bases. pp. 263–272. Check date values in: |date= (help)
↑ Tropf, H.; Herzog, H. "Multidimensional Range Search in Dynamically Balanced Trees" (PDF). Angewandte Informatik (Applied Informatics) (2/1981): 71–77. ISSN 0013-5704.

External links

Mistral

v t e Tree data structures

Binary trees	Binary search tree (BST) Cartesian tree MVP Tree Top tree T-tree Left-child right-sibling binary tree

Self-balancing binary search trees	AA tree AVL tree LLRB tree Red–black tree Scapegoat tree Splay tree Treap

B-trees	B+ tree B*-tree B^x-tree UB-tree 2–3 tree 2–3–4 tree (a,b)-tree Dancing tree HTree

Tries	Suffix tree Radix tree Hash tree Ternary search tree X-fast trie Y-fast trie

Binary space partitioning (BSP) trees	Quadtree Octree k-d tree Implicit k-d tree VP tree

Non-binary trees	Exponential tree Fusion tree Interval tree PQ tree Range tree SPQR tree Van Emde Boas tree

Spatial data partitioning trees	R-tree R+ tree R* tree X-tree M-tree Segment tree Hilbert R-tree Priority R-tree

Other trees	Heap Hash calendar Merkle tree Finger tree Order statistic tree Metric tree Cover tree BK-tree Doubly chained tree iDistance Link/cut tree Fenwick tree Log-structured merge-tree

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.