Bx-tree

I datalogi, B træet er en forespørgsel og opdatering effektiv B + træ-baserede indeks struktur for bevægelige objekter.

Indeksstruktur

Basisstrukturen af ​​B-træet er en B + træ, hvor de indre knudepunkter tjene som en mappe, der hver indeholder en pointer til sin ret søskende. I den tidligere version af B-træet, bladet noder indeholdt steder de bevægende-objekt bliver indekseret og tilsvarende indeks tid. I den optimerede udgave, hvert blad node bidrag indeholder id, hastighed, single-dimensionelle kortlægning værdi og den seneste opdatering tid af objektet. Fanout forøges ved ikke at lagre beliggenheden af ​​bevægelige objekter, da disse kan udledes af kortlægning værdier.

Udnyt B + træ for bevægelige objekter

Som for mange andre bevægelige objekter indekser, er en 2-dimensional bevægelse objekt modelleres som en lineær funktion som O = ,, t), hvor og er placering og hastighed af objektet på et givet tidspunkt instans t, dvs tidspunktet for sidste opdatere. B + træ er en struktur for indeksering enkelt dimensionelle data. For at vedtage B + træet som en bevægende objekt indeks, B-træet bruger en linearisering teknik, der er med til at integrere objekter 'placering på tidspunkt t til enkelt dimensionelle værdi. Konkret er objekter først partitioneret efter deres opdatering tid. For objekter inden for samme partition, B-træet gemmer deres placeringer på et givet tidspunkt, som skønnes ved lineær interpolation. Ved at gøre dette, B-træet holder et konsistent billede af alle objekter i samme partition uden at gemme opdateringen tid en objekter.

For det andet, er rummet delt af et gitter og placeringen af ​​et objekt lineariseres inden skillevæggene ifølge et rum-påfyldning kurve, fx de Peano eller Hilbert kurver.

Endelig med kombinationen af ​​den partition nummer og den lineære orden, er et objekt indekseret i B-træ med en endimensional indeks nøgle Bvalue:

Her indeks-partition er et indeks partition bestemt af opdateringen tid og xRep er rum-påfyldning kurve værdien af ​​genstanden holdning på den indekserede tidspunkt, betegner den binære værdi af x, og "+" betyder sammenkædning.

Givet et objekt O ,, 10), TMU = 120, kan Bvalue for O beregnes som følger.

  • O er indekseret i partition 0 som nævnt. Derfor indexpartition = 2.
  • O position på etiketten tidsstempel partition 0 er.
  • Brug af Z-kurve med henblik = 3, Z-værdien af ​​O, dvs xRep er 2.
  • Sammenkæde indexpartition og xRep, Bvalue 2 = 19.

Indlæsning, opdatering og sletning

Med et nyt objekt, sit indeks nøglen er beregnet og derefter objektet indsættes i B-træet som i B + træ. En opdatering består af en deletion efterfulgt af en insertion. En ekstra struktur anvendes til at holde den nyeste nøgle hvert indeks, således at et objekt kan slettes ved at søge efter nøglen. Indeksering nøglen er beregnet før påvirker træet. På denne måde B-træet direkte arver de gode egenskaber af B + træet, og opnår effektiv opdatering ydeevne.

Forespørgsler

Range forespørgsel

En række forespørgsel henter alle objekter, hvis placering falder inden for rektangulære interval på tid er ikke før det aktuelle tidspunkt.

B-tree bruger query-vindue udvidelsen teknik til at besvare forespørgsler. Da B-tree lagrer et objekts placering som for engang efter opdatering tid, udvidelsen indebærer to tilfælde: en placering enten skal bringes tilbage til et tidligere tidspunkt eller frem til et senere tidspunkt. Hovedidéen er at udvide forespørgslen vinduet, så det omslutter alle objekter, hvis positioner er ikke inden for forespørgslen vinduet på sit label tidsstempel men vil træde forespørgslen vinduet på forespørgslen tidsstempel.

Efter udvidelsen, skillevæggene af B-tree skal gennemløbes for at finde genstande, der falder i det udvidede forespørgslen vinduet. I hver partition, anvendelse af et rum-filling curve betyder, at en række forespørgsel i native, to-dimensionelle rum bliver et sæt range forespørgsler i den transformerede, endimensionale rum.

For at undgå alt for store forespørgsel regionen efter ekspansion i skæve datasæt, en optimering af forespørgslen algoritmen eksisterer, hvilket forbedrer forespørgslen effektiviteten ved at undgå unødvendig forespørgsel udvidelsen.

K nærmeste nabo forespørgsel

K nærmeste nabo forespørgsel beregnes ved iterativt at udføre range forespørgsler med en trinvist udvidet søgning regionen indtil k svar er opnået. En anden mulighed er at ansætte lignende-forespørgsler ideer i iDistance Teknik.

Andre forespørgsler

Rækken forespørgsel og K nærmeste nabo query algoritmer kan let udvides til at understøtte interval forespørgsler, kontinuerlige forespørgsler, etc.

Tilpasning relationelle database motorer til at rumme bevægelige objekter

Da B-træet er et indeks bygget oven på en B + træ indeks, alle operationer i B-træet, herunder insertion, deletion og søgning, er de samme som dem i B + træ. Der er ingen grund til at ændre implementeringer af disse operationer. Den eneste forskel er at gennemføre proceduren for at udlede indeksering nøgle som en lagret procedure i en eksisterende DBMS. Derfor B-træet kan nemt integreres i eksisterende DBMS uden at røre kernen.

Spade bevægelige objekt management system bygget oven på en populær relationsdatabase MySQL, der anvender B-træet for at indeksere objekterne. I forbindelse med gennemførelsen, bevæger objekt data transformeres og gemmes direkte på MySQL, og forespørgsler forvandles til standard SQL-sætninger, som er effektivt behandlet i den relationelle motor. Vigtigst er det, er alle disse opnås pænt og selvstændigt uden at infiltrere ind i MySQL kerne.

Ydeevne tuning

Potentielt problem med data skew

B træet anvender et gitter for rummet opdeling mens kortlægning todimensional beliggenhed i endimensional nøgle. Dette kan indføre forringelse af ydeevnen for både forespørgslen og opdatere operationer, mens der beskæftiger sig med skæve data. Hvis netfelt oversize, er mange objekter indeholdt i en celle. Da objekter i en celle er umulig at skelne til indekset, vil der være nogle overflow knudepunkter i det underliggende B + træ. Den eksisterende af overløb sider ikke kun ødelægger afbalancering af træet, men også øger opdateringen omkostninger. Med hensyn til de forespørgsler, for given forespørgsel regionen, storcellet pådrager mere falske positiver og øger behandlingstiden. På den anden side, hvis pladsen er delt med finere gitter, dvs. mindre celler, hvor hver celle indeholder få objekter. Der er næppe overløb siderne, så opdateringen omkostningerne minimeres. Færre falske positiver hentes i en forespørgsel. Der er imidlertid behov flere celler, der skal søges. Stigningen i antallet af celler søgte også øger arbejdsbyrden for en forespørgsel.

Indeks tuning

Den STB-tree introducerer en selvstændig tuning ramme for tuning udførelsen af ​​B-tree mens der beskæftiger sig med data skævt i rummet og data forandring med tiden. For at håndtere data skævt i rummet, STB-træet opdeler hele rummet i regioner med forskellig objekt tæthed ved hjælp af et sæt af referencepunkter. Hver region anvender en individuel gitter, hvis cellestørrelse bestemmes af objektet densitet inde i den.

B-træet har flere partitioner vedrørende forskellige tidsintervaller. Som tiden er gået, hver partition vokser og krymper skiftevis. STB-tree udnytter denne funktion til at tune indekset online for at tilpasse rummet partitionering at gøre sig rumme de data ændrer sig med tiden. Især da en partition krymper at tømme og begynder at gro, det vælger et nyt sæt referencepunkter og nye gitter for hvert referencepunkt i henhold til de seneste data tæthed. Tuningen er baseret på de seneste statistikker, der indsamles i en given periode af tid, så vejen for rummet partitionering er meningen at passe de seneste data fordeling bedst. På denne måde, forventes STB-træet for at minimere virkningen forårsaget af data skævt i rummet og dataændringer med tiden.

  0   0

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha