| 词条 | UB-tree |
| 释义 |
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. References1. ^{{cite paper | first = V. | last = Markl | title = MISTRAL: Processing Relational Queries using a Multidimensional Access Technique | year = 1999 | url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.6487}} {{CS-Trees}}{{algorithm-stub}}2. ^{{cite conference | first1 = Frank | last1 = Ramsak | first2 = Volker | last2 = Markl | first3 = Robert | last3 = Fenk | first4 = Martin | last4 = Zirkel | first5 = Klaus | last5 = Elhardt | first6 = Rudolf | last6 = Bayer | title = Integrating the UB-tree into a Database System Kernel | conference = 26th International Conference on Very Large Data Bases | conferenceurl = http://www.vldb.org/dblp/db/conf/vldb/vldb2000.html | date = September 10–14, 2000 | pages = 263–272 | url = http://www.vldb.org/dblp/db/conf/vldb/RamsakMFZEB00.html}} 3. ^{{cite journal | url = http://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf | format = PDF | first1 = H. | last1 = Tropf | first2 = H. | last2 = Herzog | title = Multidimensional Range Search in Dynamically Balanced Trees | journal = Angewandte Informatik (Applied Informatics) | issue = 2/1981 | pages = 71–77 | issn = 0013-5704}} 2 : Database index techniques|Search trees |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。