B x -träd

Inom datavetenskap är B x - trädet en fråga som används för att uppdatera effektiva B+-trädbaserade indexstrukturer för rörliga objekt.

Indexstruktur

Basstrukturen för B x -trädet är ett B+-träd där de interna noderna fungerar som en katalog, var och en innehåller en pekare till sitt högra syskon. I den tidigare versionen av B x -trädet innehöll lövnoderna de rörliga objektsplatserna som indexerades och motsvarande indextid. I den optimerade versionen innehåller varje lövnodpost id, hastighet, endimensionell mappningsvärde och den senaste uppdateringstiden för objektet. Fanouten ökas genom att inte lagra positionerna för rörliga objekt, eftersom dessa kan härledas från kartläggningsvärdena .

Använda B+-trädet för att flytta objekt

Ett exempel på B x -trädet med antalet indexpartitioner lika med 2 inom ett maximalt uppdateringsintervall tmu. I det här exemplet finns det maximalt tre partitioner som finns samtidigt. Efter linjärisering indexeras objektplatser som infogats vid tidpunkt 0 i partition 0 med etiketttidsstämpel 0,5 tmu, objektplatser uppdaterade under tid 0 till 0,5 tmu indexeras i partition 1 med etiketttidsstämpel tmu, och så vidare (som indikeras med pilar). Allt eftersom tiden går, upphör det första intervallet upprepade gånger (skuggat område), och ett nytt intervall läggs till (streckad linje).

modelleras ett tvådimensionellt rörligt objekt som en linjär funktion som O = ((x, y), (vx, vy), t ), där (x, y) och (vx, vy ) är objektets plats och hastighet vid en given tidpunkt t , dvs tiden för senaste uppdatering. B+-trädet är en struktur för att indexera endimensionell data. För att anta B+-trädet som ett rörligt objektindex, använder Bx-trädet en linjäriseringsteknik som hjälper till att integrera objekts placering vid tidpunkten t till ett endimensionellt värde. Specifikt partitioneras objekt först enligt deras uppdateringstid. För objekt inom samma partition lagrar B x -trädet sina platser vid en given tidpunkt som uppskattas genom linjär interpolation . Genom att göra det behåller B x -trädet en konsekvent vy av alla objekt inom samma partition utan att lagra uppdateringstiden för ett objekt.

För det andra är utrymmet uppdelat av ett rutnät och platsen för ett objekt linjäriseras inom skiljeväggarna enligt en utrymmesfyllande kurva, t.ex. Peano- eller Hilbert -kurvorna .

Slutligen, med kombinationen av partitionsnumret (tidsinformation) och den linjära ordningen (platsinformation), indexeras ett objekt i B x -träd med en endimensionell indexnyckel B x värde:

Här är index-partition en index-partition som bestäms av uppdateringstiden och xrep är det rymdfyllande kurvvärdet för objektets position vid den indexerade tiden, [ X ] 2 {\ anger det binära värdet av x, och "+" betyder sammanlänkning.

Givet ett objekt O ((7, 2), (-0,1,0,05), 10), tmu = 120, kan B x -värdet för O beräknas enligt följande.

  1. O indexeras i partition 0 som nämnts. Därför är indexpartition = (00) 2 .
  2. O:s position vid etikettens tidsstämpel för partition 0 är (1,5).
  3. Med Z-kurva med ordning = 3 är Z-värdet för O, dvs. xrep (010011) 2 .
  4. Sammanfoga indexpartition och xrep, B x- värde (00010011) 2 =19.
  5. Exempel O ((0,6), (0,2, -0,3 ),10) och tmu=120 sedan O:s position vid partitionens etiketttidsstämpel: ???

Insättning, uppdatering och radering

Givet ett nytt objekt, beräknas dess indexnyckel och sedan infogas objektet i B x -trädet som i B+-trädet. En uppdatering består av en radering följt av en infogning. En hjälpstruktur används för att behålla den senaste nyckeln för varje index så att ett objekt kan tas bort genom att söka efter nyckeln. Indexeringsnyckeln beräknas innan trädet påverkas. På så sätt ärver B x -trädet direkt B+-trädets goda egenskaper och uppnår effektiv uppdateringsprestanda.

Frågor

Områdesfråga

En intervallfråga hämtar alla objekt vars plats faller inom det rektangulära intervallet vid tidpunkten inte före den aktuella tiden.

B x -trädet använder frågefönsterförstoringsteknik för att svara på frågor. Eftersom B x -trädet lagrar ett objekts position någon gång efter dess uppdateringstid, involverar utvidgningen två fall: en plats måste antingen föras tillbaka till en tidigare tidpunkt eller framåt till en senare tidpunkt. Huvudidén är att förstora frågefönstret så att det omsluter alla objekt vars positioner inte är inom frågefönstret vid dess etiketttidsstämpel men kommer in i frågefönstret vid frågetidsstämpeln.

måste partitionerna i B x -trädet korsas för att hitta objekt som faller i det förstorade frågefönstret. I varje partition innebär användningen av en utrymmesfyllande kurva att en intervallfråga i det ursprungliga, tvådimensionella utrymmet blir en uppsättning intervallfrågor i det transformerade, endimensionella utrymmet.

För att undvika alltför stor frågeregion efter expansion i skeva datamängder finns en optimering av frågealgoritmen, vilket förbättrar frågeeffektiviteten genom att undvika onödig frågeförstoring.

K närmaste granne fråga

K närmaste grannfråga beräknas genom att iterativt utföra intervallfrågor med en stegvis förstorad sökregion tills k svar erhålls. En annan möjlighet är att använda liknande frågeidéer i The iDistance Technique .

Andra frågor

Områdesfrågan och K Nearest Neighbor-frågealgoritmerna kan enkelt utökas för att stödja intervallfrågor, kontinuerliga frågor, etc.

Anpassa relationsdatabasmotorer för att rymma rörliga objekt

Eftersom B x -trädet är ett index byggt ovanpå ett B+-trädindex, är alla operationer i B x -trädet, inklusive infogning, borttagning och sökning, desamma som i B+-trädet. Det finns inget behov av att ändra implementeringen av dessa operationer. Den enda skillnaden är att implementera proceduren att härleda indexeringsnyckeln som en lagrad procedur i ett befintligt DBMS . Därför kan B x -trädet enkelt integreras i befintliga DBMS utan att röra kärnan .

SpADE är ett flyttande objekthanteringssystem byggt ovanpå ett populärt relationsdatabassystem MySQL , som använder B x -trädet för att indexera objekten. I implementeringen transformeras och lagras rörliga objektdata direkt på MySQL, och frågor omvandlas till vanliga SQL-satser som effektivt bearbetas i relationsmotorn. Viktigast av allt, alla dessa uppnås prydligt och oberoende utan att infiltrera i MySQL-kärnan.

Prestandajustering

Potentiellt problem med dataskev

B x -trädet använder ett rutnät för rymduppdelning samtidigt som tvådimensionell plats kartläggs till endimensionell nyckel. Detta kan introducera prestandaförsämring av både fråge- och uppdateringsoperationer när man hanterar skev data. Om rutnätscellen är överdimensionerad finns många objekt i en cell. Eftersom objekt i en cell inte går att särskilja för indexet, kommer det att finnas några överflödesnoder i det underliggande B+-trädet. Att det finns överflödessidor förstör inte bara balanseringen av trädet utan ökar också uppdateringskostnaden. När det gäller frågorna, för den givna frågeregionen, får stora celler fler falska positiva resultat och ökar bearbetningstiden. Å andra sidan, om utrymmet är uppdelat med finare rutnät, dvs mindre celler, innehåller varje cell få objekt. Det finns knappast överflöd av sidor så att uppdateringskostnaden minimeras. Färre falska positiva resultat hämtas i en fråga. Det behövs dock fler celler för att söka. Ökningen av antalet genomsökta celler ökar också arbetsbelastningen för en fråga.

Indexjustering

ST 2 B-trädet introducerar ett självinställande ramverk för att justera prestanda för B x -trädet samtidigt som det hanterar dataskevhet i rymden och dataförändringar med tiden. För att hantera dataskevhet i rymden delar ST 2 B-trädet upp hela rymden i regioner med olika objektdensitet med hjälp av en uppsättning referenspunkter. Varje region använder ett individuellt rutnät vars cellstorlek bestäms av objektdensiteten inuti den.

B x -trädet har flera partitioner avseende olika tidsintervall. Allt eftersom tiden går, växer och krymper varje partition växelvis. ST 2 B-trädet använder denna funktion för att justera indexet online för att justera utrymmespartitioneringen för att anpassa sig till dataförändringarna med tiden. När en partition krymper till tom och börjar växa, väljer den en ny uppsättning referenspunkter och ett nytt rutnät för varje referenspunkt enligt den senaste datatätheten. Inställningen baseras på den senaste statistiken som samlats in under en given tidsperiod, så att sättet för rymdpartitionering antas passa den senaste datadistributionen bäst. förväntas ST 2 B-trädet att minimera effekten som orsakas av dataskevning i rymden och dataförändringar med tiden.

Se även

  1. ^ a b Christian S. Jensen, Dan Lin och Beng Chin Ooi. Fråga och uppdatera Effektiv B+trädbaserad indexering av rörliga objekt . I Proceedings of 30th International Conference on Very Large Data Bases (VLDB), sidorna 768-779, 2004.
  2. ^ a b Dan Lin. Indexering och sökning av rörliga objektdatabaser , doktorsavhandling, National University of Singapore, 2006.
  3. ^ Jensen, CS, D. Tiesyte, N. Tradisauskas, Robust B+-Tree-Based Indexing of Moving Objects, i Proceedings of the Seventh International Conference on Mobile Data Management, Nara, Japan, 9 sidor, 9–12 maj 2006.
  4. ^ SpADE Arkiverad 2009-01-02 på Wayback Machine : En SPatio-temporal autonom databasmotor för platsmedvetna tjänster.
  5. ^ Su Chen, Beng Chin Ooi, Kan-Lee. Tan och Mario A. Nacismento, ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree for Moving Objects Archived 2011-06-11 at the Wayback Machine . I Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD), sidan 29-42, 2008.
Hämtad från " https://en.wikipedia.org/w/index.php?title=Bx-tree&oldid=1091252550 "