Bx-træ

I datalogi er et B x -træ  en forespørgsels- og opdateringseffektiv indekseringsstruktur til at flytte objekter baseret på B+‍‍-træer .

Indeksstruktur

Grundlaget for B x -træstrukturen er et B+‍‍-træ, hvor interne knudepunkter behandles som mapper, der indeholder pointere til den højre naboknude (med samme overordnede). I tidlige versioner af B x -træet [1] indeholdt bladene positionen af ​​indekserede bevægelige objekter og den tilsvarende indekseringstid. I den optimerede version [2] indeholder hvert blad et id, hastighed, en endimensionel (skalar) værdi for positionsfunktionen og det sidste opdateringstidspunkt for objektet. Forskellen øges af manglen på opbevaring af positionen af ​​bevægelige objekter, da den kan opnås fra værdien af ​​funktionen .

Brug af B+‍‍-træer til at flytte objekter

Som med mange andre indekseringer af objekter i bevægelse, er et todimensionalt objekt i bevægelse modelleret af en lineær funktion O = ((x, y), (vx, vy), t), hvor (x, y) og (vx, vy ) er objektets position og hastighed på tidspunktet t , det vil sige på tidspunktet for den sidste opdatering. B+‍‍-træ er en struktur til indeksering af endimensionelle data. For at rumme B+‍‍-træet til indeksering af objekter i bevægelse, bruger Bx - træet en lineariseringsteknik , der hjælper med at konvertere objektets position på tidspunktet t til en endimensionel værdi. Især objekter opdeles først efter opdateringstid. For objekter inden for en tidspartition husker B x -træet objektets position på et givet tidspunkt, opnået ved lineær interpolation . Ved at gøre det bevarer Bx - træet et ensartet billede af alle objekter i det opdelte element uden at ændre opdateringstiden for objekterne.

Dernæst opdeles rummet af et gitter, og objekternes position lineariseres for skilleelementet i tid i henhold til den rumfyldende kurve, for eksempel Peano -kurver eller Hilbert-kurver .

Derefter, kombineret med det delte elementnummer (tidsinformation) og lineær rækkefølge (positionsinformation), indekseres objektet i B x -træet med en endimensionel nøgleværdi (B x - værdi):

Her er indekspartition indekset for partitionselementet bestemt af opdateringstiden, og xrep er værdien af ​​objektets position på rumudfyldningskurven på tidspunktet for indeksering, betyder den binære værdi af x, "+" betyder streng sammenkædning.

Givet et objekt O ((7, 2), (-0,1,0,05), 10), tmu = 120, kan værdien af ​​B x for O beregnes som følger.

  1. O indekseres ved element 0 af tidspartitionen som beskrevet ovenfor. Så indekspartition = (00) 2 .
  2. Placeringen af ​​objektet O på tidspunktet for indstilling af tidspunktet for partition 0 er (1,5).
  3. Ved at bruge en Z-kurve af orden 3 er Z-værdien af ​​objektet O, xrep, (010011) 2 .
  4. Vi forbinder linjerne indexpartition og xrep, vi får værdien B x (00010011) 2 =19.

Indsættelse, opdatering og sletning

Hvis et nyt objekt gives, beregnes dets indeksnøgle, og objektet indsættes i B x -træet som i et B+‍‍-træ. En opdatering består af en sletning efterfulgt af en indsættelse. Yderligere strukturer bruges til at gemme den sidste nøgle i hvert indeks, så objektet kan slettes, når nøglen slås op. Indeksnøglen beregnes, før den medtages i træet. Et B x -træ arver således direkte de gode egenskaber fra et B+‍‍-træ og opnår en god opdateringsydelse.

Forespørgsler

Forespørgsel efter område

Områdeforespørgslen henter alle objekter, hvis placering falder inden for det rektangulære område på et tidspunkt, der ikke er tidligere end det aktuelle tidspunkt.

Bx - træet bruger en forespørgselsvindueudvidelsesteknik til at besvare denne forespørgsel. Udvidelsen har to tilfælde - placeringen skal enten opgøres på et tidligere tidspunkt, eller på et senere tidspunkt. Hovedideen er at udvide forespørgselsvinduet på en sådan måde, at det vil inkludere alle objekter, der ikke er inkluderet i forespørgselsvinduet på det tidspunkt, der er angivet i objektnøglen, men falder ind i det for tidspunktet for anmodningen.

Efter udvidelsen skal du kigge gennem sektioner af B x -træet for at finde objekter, der falder ind i det udvidede vindue. I hver sektion betyder anvendelsen af ​​en rumudfyldende kurve, at forespørgselsområdet i naturligt 2D-rum bliver sættet af rækkeviddeforespørgsler i 1D-rummet [1] .

For at undgå for store forespørgsler efter udvidelse af forespørgselsvinduet i asymmetriske data, er der en optimeringsalgoritme [3] , der forbedrer forespørgselsydeevne ved at eliminere unødvendige udvidelser.

Forespørgsel efter K nærmeste naboer

Forespørgslen efter K nærmeste naboer udføres ved iterativt at udføre rækkeviddeforespørgsler med stigende søgeområde, indtil vi får k svar. En anden mulighed er at bruge lignende ideer sammen med iDistance -teknikken .

Andre anmodninger

Intervalforespørgslen og K nærmeste naboforespørgselsalgoritmer kan nemt udvides til at understøtte intervalforespørgsler, kontinuerlige forespørgsler osv. [2] .

Tilpasning af relationelle databaser til at rumme bevægelige objekter

Fordi B x -træet er et indeks bygget oven på et B+‍‍-træ, er alle operationer i et B x -træ, inklusive indsættelse, sletning og opslag, de samme som i et B+‍‍-træ. Der er ingen grund til at ændre implementeringen af ​​disse operationer. Den eneste forskel i implementeringen ligger i implementeringen af ​​proceduren for at få indekseringsnøglen som en lagret procedure i den eksisterende database . Således kan Bx -træet nemt integreres i en eksisterende database uden at påvirke kernen .

SpADE [4]  er et styringssystem for bevægelige objekter bygget oven på den populære MySQL-database , der bruger et B x -træ til at indeksere objekter. I implementeringen konverteres og lagres flytteobjektdata direkte i MySQL, og forespørgsler transformeres til standard SQL-forespørgsler, der behandles effektivt af relationsdatabasens runtime. Det vigtigste er, at alt dette gøres pænt og uafhængigt uden at forstyrre MySQL-kernen.

Performance Tuning

Potentielle problemer med dataskævhed

Bx - træet bruger et rumallokeringsgitter til at transformere en todimensionel position til en endimensionel nøgle. Dette kan føre til ydeevneforringelse i både forespørgsler og opdateringer, når der arbejdes med asymmetriske data. Hvis gittercellen er stor, indeholder cellen mange objekter. Fordi objekterne i en celle ikke kan skelnes med indeks, vil der være noget nodeoverløb i det underliggende B+‍‍-træ. Eksistensen af ​​overløbssider ødelægger ikke kun balancen i træet, men øger også omkostningerne ved opdatering. Som med normale forespørgsler, for en intervalforespørgsel, resulterer større celler i flere falske prøver og øger udførelsestiden. På den anden side, hvis rummet er opdelt i et mindre gitter, det vil sige i mindre celler, indeholder hver celle færre objekter. Det er usandsynligt, at sideoverløb vil blive opnået i dette tilfælde, og der vil også være færre falske prøver, men flere celler skal scannes. Forøgelse af antallet af celler at se på øger også kompleksiteten af ​​forespørgslen.

Opsætning af indekset

ST 2 B-træet [5] introducerer et selvindstillingsskema til tuning af ydeevnen af ​​et B x -træ, når der håndteres ikke-symmetriske data i rum og tid. For at arbejde med asymmetriske data i ST 2 -rum opdeler B-træet hele rummet i områder med forskellig tæthed af objekter ved hjælp af et sæt kontrolpunkter. Hver region bruger et individuelt gitter, hvis cellestørrelse bestemmes af tætheden af ​​objekter i området.

B x -træet har flere partitioner til forskellige tidsintervaller. ST 2 B-træet bruger intervalforøgelse eller -sænkning til at justere indeksering for at imødekomme rumopdeling og imødekomme tidsændringer. Især når partitionen tømmes og begynder at vokse, vælges et nyt sæt kontrolpunkter, og et nyt gitter for hvert punkt vælges i henhold til den sidste datatæthed. Tuningen er baseret på statistik indsamlet over en given tidsperiode, således at opdelingen af ​​rummet bedre matcher den seneste datafordeling. I denne forstand forventes ST 2 B-træet at minimere effekten forårsaget af dataskævhed i rummet og dataændringer over tid.

Se også

Noter

  1. ↑ 1 2 Jensen, Lin, Ooi, 2004 , s. 768-779.
  2. ↑ 12 Dan Lin, 2006 .
  3. ↑ Jensen, Tiesyte, Tradisauskas, 2006 .
  4. ↑ SpADE Arkiveret fra originalen den 2. januar 2009. : En spatio-temporal autonom databasemotor til lokationsbevidste tjenester.
  5. ↑ Chen, Ooi, Tan, Nacismento, 2008 , s. 29-42.

Litteratur