UB-boom - UB-tree

Image
Tweedimensionale Z-volgorde

De UB-boom zoals voorgesteld door Rudolf Bayer en Volker Markl is een gebalanceerde boom voor het opslaan en efficiënt ophalen van multidimensionale gegevens . Het is eigenlijk een B + -boom (informatie alleen in de bladeren) met records opgeslagen volgens Z-volgorde , ook wel Morton-volgorde genoemd. Z-volgorde wordt eenvoudig berekend door de toetsen bitsgewijs te interliniëren.

Invoegen, verwijderen en puntquery worden gedaan zoals bij gewone B + -bomen. Om bereikzoekopdrachten uit te voeren in multidimensionale puntgegevens, moet echter een algoritme worden verschaft voor het berekenen, vanaf een punt dat in de database wordt aangetroffen, de volgende Z-waarde die zich in het multidimensionale zoekbereik bevindt.

Het oorspronkelijke algoritme om dit sleutelprobleem op te lossen was exponentieel met de dimensionaliteit en dus niet haalbaar ("GetNextZ-adres"). Een oplossing voor dit "cruciale deel van de UB-boombereikvraag" lineair met de bitlengte van het z-adres is later beschreven. Deze methode is al beschreven in een ouder artikel, waarin eerst het gebruik van Z-volgorde met zoekbomen werd voorgesteld.

Referenties

  1. ^ Markl, V. (1999). "MISTRAL: Verwerking van relationele zoekopdrachten met behulp van een multidimensionale toegangstechniek". CiteSeerX   10.1.1.32.6487 . Cite journal vereist |journal= ( hulp )
  2. ^ Ramsak, Frank; Markl, Volker; Fenk, Robert; Zirkel, Martin; Elhardt, Klaus; Bayer, Rudolf (10-14 september 2000). Integratie van de UB-boom in een databasesysteemkernel (pdf) . 26e internationale conferentie over zeer grote databanken . blz. 263-272.
  3. ^ Tropf, H .; Herzog, H. "Multidimensionaal zoeken naar bereik in dynamisch gebalanceerde bomen" (PDF) . Angewandte Informatik (Toegepaste Informatica) (2/1981): 71-77. ISSN   0013-5704 .