УБ - стабло

Из Википедије, слободне енциклопедије

УБ - стабло као што је предложио Рудолф Бајер и Волкер Маркл је уравнотежено дрво за чување и ефикасно преузимање мултидимензионалних података. То је у основи Б + стабло ( информације су само у листовима ) са записима ускладиштеним према З - криви , такође назива Мортон поредак .

Убацивање , брисање , и тачка упит се могу урадили као и са обичним Б + стаблом. Да бисте извршили претрегу домета у вишедимензионалним тачкама података мора да се обезбеди алгоритам за рачунање , од тачке на коју смо наишли у бази података , следећег З- вредности која је у мултидимензионалн опсегз претраге.

Оригинални алгоритам за решавање овог кључног проблема је експоненцијални са димензионалносћу и ради тога овај начин није могућ [1] ( " ГетНектЗ - адреса“ ). Решење за овај " кључни део УБ - стабла " линеарног са з - адресом бита је касније описано. .[2] Овај метод је већ описан у старијем раду [3] , где користећи З- редослед је прво био предложен са стаблима претраге .

References[уреди]

  1. ^ . "MISTRAL: Processing Relational Queries using a Multidimensional Access Technique".
  2. ^ 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. 
  3. ^ 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[уреди]