UB træ

UB-tree er et balanceret træ til lagring og effektiv genfinding af multidimensionelle data . Foreslået af Rudolf Bayer og Folker Markle ; er et B⁺-træ med poster gemt i Z-orden , også kaldet Morton-orden. Z-ordenen beregnes ved at sammenflette tasterne bit for bit.

Indsættelse, sletning og punktforespørgsel udføres som med normale B⁺-træer. Men for at udføre en rækkeviddesøgning på multidimensionelle punktdata skal der tilvejebringes en algoritme til at beregne den næste Z-værdi, der er inden for rækkevidden af ​​den multivariate søgning, ud fra det punkt, der findes i databasen.

Den originale algoritme til at løse dette nøgleproblem var eksponentielt afhængig af dimensionalitet og derfor ikke gennemførlig [1] ("GetNextZ-Address"[ finish ] ). Løsning af denne vigtige del af UB-tree range forespørgslen[ klargør ] , lineær med bitlængde z-adresse, blev beskrevet senere [2] . Denne metode er allerede beskrevet i en ældre artikel [3] .

Noter

  1. ↑ Folker Markle (1999). "MISTRAL: Relationel forespørgselsbehandling ved hjælp af multidimensionelle adgangsteknikker". CiteSeerX  10.1.1.32.6487 .
  2. ↑ Frank Ramsack; Folker Markle; Robert Fenk; Martin Zirkel; Klaus Elhardt; Rudolf Bayer (10.-14. september 2000). Integrering af et UB-træ i en databasemotor (PDF) . 26. internationale konference om meget store databaser . pp. 263-272. Forældet parameter brugt |coauthors=( hjælp ) Arkiveret 29. april 2021 på Wayback Machine
  3. ↑ H. Tropf; H. Herzog. "Multidimensional Range Search in Dynamically Balanced Trees" (PDF) . Anvendt datalogi (2/1981): 71-77. ISSN  0013-5704 . Arkiveret (PDF) fra originalen 2021-03-10 . Hentet 2021-04-29 . Forældet parameter brugt |deadlink=( hjælp )