UB fa

Az UB-tree egy kiegyensúlyozott fa többdimenziós adatok tárolására és hatékony visszakeresésére . Rudolf Bayer és Folker Markle javaslata ; egy B⁺-fa Z-rend szerint tárolt bejegyzésekkel , más néven Morton-rend. A z-sorrendet a kulcsok bitenkénti interleavelésével számítjuk ki.

A beszúrás, törlés és pontlekérdezés ugyanúgy történik, mint a normál B⁺-fák esetében. Ahhoz azonban, hogy többdimenziós pontadatokon tartománykeresést hajtsunk végre, biztosítani kell egy algoritmust, amely az adatbázisban talált pontból kiszámítja a következő Z-értéket, amely a többváltozós keresés tartományán belül van.

A kulcsprobléma megoldásának eredeti algoritmusa exponenciálisan függött a dimenzióktól, ezért nem volt megvalósítható [1] ("GetNextZ-Address"[ finomítás ] ). Az UB-fa tartomány lekérdezés ezen fontos részének megoldása[ tisztázni ] , lineáris bithosszúságú z-címmel, később került leírásra [2] . Ezt a módszert egy régebbi cikkben már leírták [3] .

Jegyzetek

  1. ↑ Folker Markle (1999). "MISTRAL: Relációs lekérdezések feldolgozása többdimenziós hozzáférési technikákkal". CiteSeerX  10.1.1.32.6487 .
  2. ↑ Frank Ramsack; Folker Markle; Robert Fenk; Martin Zirkel; Klaus Elhardt; Bayer Rudolf (2000. szeptember 10–14.). UB-fa integrálása adatbázismotorba (PDF) . 26. Nemzetközi Konferencia a Nagyon nagy adatbázisokról . pp. 263-272. Elavult használt paraméter |coauthors=( súgó ) Archiválva : 2021. április 29. a Wayback Machine -nél
  3. ↑ H. Tropf; H. Herzog. „Többdimenziós tartomány keresés dinamikusan kiegyensúlyozott fákban” (PDF) . Alkalmazott számítástechnika (2/1981): 71-77. ISSN  0013-5704 . Archivált (PDF) az eredetiből ekkor: 2021-03-10 . Letöltve: 2021-04-29 . Elavult használt paraméter |deadlink=( súgó )