UB-träd
| UB-träd | ||||
|---|---|---|---|---|
 Tvådimensionell Z-ordning
| ||||
| Typ | träd | |||
| Uppfanns av | Rudolf Bayer och Volker Markl | |||
| Tidskomplexitet i stor O-notation | ||||
| ||||
UB -trädet som föreslagits av Rudolf Bayer och Volker Markl är ett balanserat träd för att lagra och effektivt hämta flerdimensionell data . Det är i grunden ett B+-träd (information endast i löven) med poster lagrade enligt Z-ordning , även kallad Morton-ordning. Z-ordningen beräknas helt enkelt genom att bitvis sammanfläta nycklarna.
Infogning, radering och punktförfrågan görs som med vanliga B+-träd. För att utföra avståndssökningar i flerdimensionell punktdata måste emellertid en algoritm tillhandahållas för att beräkna, från en punkt som påträffas i databasen, nästa Z-värde som ligger i det flerdimensionella sökområdet.
Den ursprungliga algoritmen för att lösa detta nyckelproblem var exponentiell med dimensionaliteten och därför inte genomförbar ("GetNextZ-adress"). En lösning på denna "avgörande del av UB-trädintervallsfrågan" linjär med z-adressbitlängden har beskrivits senare. Denna metod har redan beskrivits i en äldre artikel där användning av Z-ordning med sökträd först har föreslagits.
-
^
Markl, V. (1999). "MISTRAL: Bearbetning av relationsfrågor med hjälp av en multidimensionell åtkomstteknik". CiteSeerX 10.1.1.32.6487 .
{{ citera journal }}: Citera journal kräver|journal=( hjälp ) - ^ Ramsak, Frank; Markl, Volker; Fenk, Robert; Zirkel, Martin; Elhardt, Klaus; Bayer, Rudolf (10–14 september 2000). Integrering av UB-trädet i en databassystemkärna (PDF) . 26:e internationella konferensen om mycket stora databaser . s. 263–272.
- ^ Tropf, H.; Herzog, H. "Multidimensional Range Search in Dynamically Balanced Trees" (PDF) . Angewandte Informatik (Tillämpad informatik) (2/1981): 71–77. ISSN 0013-5704 .