Bx-fa

A számítástechnikában a B x fa egy hatékony indexelési struktúra, amely B+‍‍-fák  alapján lekérdezi és frissíti az objektumok mozgatását .

Index szerkezete

A B x fastruktúra alapja egy B+‍‍ fa, amelyben a belső csomópontokat a jobb szomszédos csomópontra mutató mutatókat tartalmazó könyvtárakként kezeli (ugyanazon szülővel). A B x -fa [1] korai változataiban a levelek tartalmazták az indexelt mozgó objektumok helyzetét és a megfelelő indexelési időt. Az optimalizált változatban [2] minden levél tartalmaz egy azonosítót, sebességet, a pozíciófüggvény egydimenziós (skaláris) értékét és az objektum utolsó frissítési idejét. A különbséget növeli a mozgó objektumok helyzetének tárolásának hiánya, mivel ez a függvény értékéből adódik .

B+‍‍-fák használata objektumok mozgatásához

A mozgó objektumok sok más indexeléséhez hasonlóan a kétdimenziós mozgó objektumokat egy O = ((x, y), (vx, vy), t) lineáris függvény modellezi , ahol (x, y) és (vx, vy) ) az objektum helyzete és sebessége a t időpontban , azaz az utolsó frissítés időpontjában. A B+‍‍-fa egy struktúra az egydimenziós adatok indexelésére. A B+‍‍-fa mozgó objektumok indexeléséhez való alkalmazkodása érdekében a Bx -fa egy linearizálási technikát használ, amely segít az objektum t időpontbeli helyzetének egydimenziós értékké alakításában. Az objektumok először frissítési idő szerint vannak lebontva. Az időpartíción belüli objektumok esetében a B x -fa megjegyzi az objektum pozícióját egy adott időpontban, amelyet lineáris interpolációval kapunk . Ezzel a Bx - fa konzisztens képet tart fenn a felosztott elemen belüli összes objektumról anélkül, hogy megváltoztatná az objektumok frissítési idejét.

Ezután a teret egy rács particionálja, és az objektumok helyzetét a térkitöltési görbe szerint linearizálja időben a partícióelemhez, például Peano -görbék vagy Hilbert-görbék .

Ezután a megosztott elemszámmal (időinformáció) és a lineáris sorrenddel (pozícióinformációval) kombinálva az objektumot egy egydimenziós kulcsértékkel (B x érték) indexeli a B x fába:

Itt az index-partíció a partíció elemének a frissítési idő által meghatározott indexe, az xrep pedig az objektum pozíciójának értéke a térkitöltő görbén az indexelés időpontjában, x bináris értékét jelenti, a "+" pedig karakterláncot összefűzés.

Adott egy O objektum ((7, 2), (-0,1,0,05), 10), tmu = 120, a B x értéke O-ra a következőképpen számítható ki.

  1. Az O az időpartíció 0 elemére indexelve van a fent leírtak szerint. Tehát indexpartíció = (00) 2 .
  2. Az O objektum pozíciója a 0 partíció idejének beállításakor (1.5).
  3. A 3. rendű Z-görbét használva az O objektum, xrep Z-értéke (010011) 2 .
  4. Összekapcsoljuk az indexpartition és az xrep sorokat, a B x (00010011) 2 =19 értéket kapjuk.

Beillesztés, frissítés és törlés

Ha egy új objektumot adunk meg, az indexkulcsot kiszámítja, és az objektumot beilleszti a B x -fába, mint egy B+‍‍-fában. A frissítés törlésből, majd beszúrásból áll. További struktúrák használatosak az egyes indexek utolsó kulcsának tárolására, így az objektum törölhető a kulcs kikeresésekor. Az indexkulcs kiszámítása a fába való felvétel előtt történik. Így a B x fa közvetlenül örökli a B+ fa jó tulajdonságait, és jó frissítési teljesítményt ér el.

Kérések

Lekérdezés tartomány szerint

A tartománylekérdezés lekéri az összes olyan objektumot, amelyek helye a téglalap alakú tartományba esik, az aktuális időpontnál nem korábbi időpontban.

A Bx - fa egy lekérdezési ablak kibővítési technikát használ a lekérdezés megválaszolásához. A bővítménynek két esete van – a helyet vagy valamely korábbi időpontban, vagy egy későbbi időpontban kell kiszámítani. A lényeg az, hogy a lekérdező ablakot úgy bővítjük ki, hogy benne legyen minden olyan objektum, amely az objektumkulcsban megadott időpontban nem szerepel a lekérdező ablakban, de a kérés idejére beleesik.

A kibontás után át kell néznie a B x -fa szakaszait, hogy megtalálja a kibontott ablakba eső objektumokat. Minden szakaszban a térkitöltő görbe alkalmazása azt jelenti, hogy a természetes 2D-s térben a lekérdezési tartomány az 1D-s térben lévő tartománylekérdezések halmazává válik [1] .

Az aszimmetrikus adatokban a lekérdezési ablak kiterjesztése utáni túlságosan nagy tartományú lekérdezések elkerülése érdekében létezik egy optimalizáló algoritmus [3] , amely a szükségtelen bővítések kiküszöbölésével javítja a lekérdezés teljesítményét.

K legközelebbi szomszédok lekérdezése

A K legközelebbi szomszéd lekérdezése a tartománylekérdezések iteratív végrehajtásával történik, növekvő keresési területtel, amíg k választ nem kapunk. Egy másik lehetőség, hogy hasonló ötleteket használunk az iDistance technikával együtt .

Egyéb kérések

A tartomány lekérdezés és a K legközelebbi szomszéd lekérdezési algoritmus könnyen kiterjeszthető az intervallum lekérdezések, a folyamatos lekérdezések stb. támogatására [2] .

Relációs adatbázisok adaptálása mozgó objektumok befogadására

Mivel a B x fa egy B+‍‍ fára épülő index, a B x fában lévő összes művelet , beleértve a beszúrást, a törlést és a keresést, ugyanaz, mint a B+ fában. Nincs szükség ezen műveletek végrehajtásának megváltoztatására. Az egyetlen különbség a megvalósításban abban rejlik, hogy az indexelési kulcsot a meglévő adatbázisban tárolt eljárásként kell megszerezni . Így a Bx -fa könnyen integrálható egy meglévő adatbázisba anélkül, hogy a kernelre hatással lenne .

Az SpADE [4]  egy mozgó objektumkezelő rendszer, amely a népszerű MySQL adatbázisra épül, és B x fát használ az objektumok indexelésére. A megvalósítás során a mozgó objektumadatokat közvetlenül a MySQL-ben konvertálják és tárolják, a lekérdezéseket pedig szabványos SQL-lekérdezésekké alakítják át, amelyeket a relációs adatbázis-futási környezet hatékonyan dolgoz fel. A legfontosabb, hogy mindez szépen és függetlenül történik, anélkül, hogy a MySQL kernelbe beleavatkoznánk.

Performance Tuning

Lehetséges problémák az adatok torzításával

A Bx - fa térkiosztási rácsot használ, hogy egy kétdimenziós pozíciót egydimenziós kulccsá alakítson át. Ez teljesítményromláshoz vezethet mind a lekérdezésekben, mind a frissítésekben, ha aszimmetrikus adatokkal dolgozik. Ha a rácscella nagy, a cella sok objektumot tartalmaz. Mivel a cellában lévő objektumok index alapján nem különböztethetők meg, az alapul szolgáló B+‍‍-fában lesz némi csomóponttúlcsordulás. A túlcsordulási oldalak megléte nemcsak a fa egyensúlyát rombolja le, hanem a frissítés költségeit is növeli. A normál lekérdezésekhez hasonlóan a tartománylekérdezéseknél a nagyobb cellák több hamis mintát eredményeznek, és megnövelik a végrehajtási időt. Másrészt, ha a teret egy kisebb rácsra, azaz kisebb cellákra osztjuk, minden cellában kevesebb objektum található. Ebben az esetben nem valószínű, hogy oldaltúlcsordulás érhető el, és kevesebb hamis minta is lesz, de több cellát kell átvizsgálni. A megtekintendő cellák számának növelése a lekérdezés összetettségét is növeli.

Az index beállítása

Az ST 2 B-fa [5] egy önhangoló sémát vezet be a B x fa teljesítményének hangolására, ha térben és időben nem szimmetrikus adatokkal foglalkozik. Az ST 2 térben lévő aszimmetrikus adatokkal való munkavégzéshez a B-fa a teljes teret különböző objektumsűrűségű régiókra osztja fel egy sor vezérlőpont segítségével. Minden régió egy egyedi rácsot használ, amelynek cellaméretét a régión belüli objektumok sűrűsége határozza meg.

A B x -fának több partíciója van különböző időintervallumokhoz. Az ST 2 B-fa az intervallum növelését vagy csökkentését használja az indexelés beállításához, hogy alkalmazkodjon a térfelosztáshoz és az időbeli változásokhoz. Különösen, amikor a partíció kiürül és növekedésnek indul, új vezérlőpont-készlet kerül kiválasztásra, és minden ponthoz új rács kerül kiválasztásra az utolsó adatsűrűségnek megfelelően. A hangolás egy adott időtartam alatt gyűjtött statisztikákon alapul, így a tér particionálása jobban illeszkedik a legfrissebb adateloszláshoz. Ebben az értelemben az ST 2 B-fa várhatóan minimálisra csökkenti az adatok térbeli torzulása és időbeli változása által okozott hatást.

Lásd még

Jegyzetek

  1. ↑ 1 2 Jensen, Lin, Ooi, 2004 , p. 768-779.
  2. ↑ 12 Dan Lin, 2006 .
  3. ↑ Jensen, Tiesyte, Tradisauskas, 2006 .
  4. ↑ SpADE Az eredetiből archiválva 2009. január 2-án. : Egy térbeli időbeli autonóm adatbázismotor helymeghatározó szolgáltatásokhoz.
  5. ↑ Chen, Ooi, Tan, Nacismento, 2008 , p. 29-42.

Irodalom