UB-strom - UB-tree

Dvourozměrný Z-řád

The UB-strom jak navrhuje Rudolf Bayer a Volker Markl je vyvážený strom pro ukládání a efektivní načítání vícerozměrná data. Je to v zásadě B + strom (informace pouze v listech) se záznamy uloženými podle Z-pořadí, nazývaný také Mortonův řád. Pořadí Z se jednoduše vypočítá bitovým prokládáním kláves.

Vkládání, mazání a bodový dotaz se provádí jako u běžných stromů B +. Chcete-li provádět vyhledávání rozsahů ve vícerozměrných bodových datech, je třeba poskytnout algoritmus pro výpočet další hodnoty Z, která je ve vícerozměrném rozsahu hledání, z bodu nalezeného v databázi.

Původní algoritmus k řešení tohoto klíčového problému byl exponenciální s rozměrností, a proto nebyl proveditelný[1] („GetNextZ-address“). Řešení této „rozhodující části dotazu na rozsah UB-stromu“ lineárního s bitovou délkou adresy z bylo popsáno později.[2] Tato metoda již byla popsána ve starší práci[3] kde bylo nejprve navrženo použití pořadí Z s vyhledávacími stromy.

Reference

  1. ^ Markl, V. (1999). "MISTRAL: Zpracování relačních dotazů pomocí vícerozměrné přístupové techniky". CiteSeerX  10.1.1.32.6487. Citovat deník vyžaduje | deník = (Pomoc)
  2. ^ Ramsak, Frank; Markl, Volker; Fenk, Robert; Zirkel, Martin; Elhardt, Klaus; Bayer, Rudolf (10. – 14. Září 2000). Integrace stromu UB do jádra databázového systému. 26. mezinárodní konference o velmi velkých databázích. 263–272.
  3. ^ Tropf, H .; Herzog, H. „Vyhledávání vícerozměrného rozsahu v dynamicky vyvážených stromech“ (PDF). Angewandte Informatik (Aplikovaná informatika) (2/1981): 71–77. ISSN  0013-5704.