UB-strom - UB-tree

Image
Dvourozměrný Z-řád

UB-strom , jak je navrženo podle Rudolf Bayer a Volker Markl je vyvážený strom pro ukládání a načítání efektivně vícerozměrných dat . Je to v zásadě strom B + (informace pouze v listech) se záznamy uloženými podle pořadí Z , nazývaného 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ý („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. Tato metoda již byla popsána ve starším článku, 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 |journal= ( 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 (PDF) . 26. mezinárodní konference o velmi velkých databázích . 263–272.
  3. ^ Tropf, H .; Herzog, H. „Multidimenzionální vyhledávání rozsahu v dynamicky vyvážených stromech“ (PDF) . Angewandte Informatik (Aplikovaná informatika) (2/1981): 71–77. ISSN   0013-5704 .