Bx-puu

Tietojenkäsittelytieteessä B x -puu on B+‍‍-puihin perustuva  tehokas kysely- ja päivitysrakenne liikkuville objekteille .

Hakemiston rakenne

B x -puurakenteen perusta on B+‍‍-puu, jossa sisäisiä solmuja käsitellään hakemistoina, jotka sisältävät osoittimia oikeaan naapurisolmuun (samalla vanhemmalla). B x -puun [1] varhaisissa versioissa lehdet sisälsivät indeksoitujen liikkuvien kohteiden sijainnin ja vastaavan indeksointiajan. Optimoidussa versiossa [2] jokainen lehti sisältää id:n, nopeuden, sijaintifunktion yksiulotteisen (skalaari) arvon ja objektin viimeisen päivitysajan. Eroa lisää liikkuvien kohteiden sijainnin tallennuksen puute, koska se voidaan saada funktion arvosta .

B+‍‍-puiden käyttö objektien siirtämiseen

Kuten monet muutkin liikkuvien objektien indeksoinnit, kaksiulotteinen liikkuva kohde mallinnetaan lineaarifunktiolla O = ((x, y), (vx, vy), t), missä (x, y) ja (vx, vy) ) ovat kohteen sijainti ja nopeus hetkellä t eli viimeisen päivityksen ajankohtana. B+‍‍-puu on rakenne yksiulotteisten tietojen indeksointiin. B+‍‍-puun mukauttamiseksi liikkuvien kohteiden indeksointiin Bx -puu käyttää linearisointitekniikkaa , joka auttaa muuttamaan kohteen sijainnin hetkellä t yksiulotteiseksi arvoksi. Erityisesti objektit eritellään ensin päivitysajan mukaan. Aikaosion kohteille B x -puu muistaa objektin sijainnin tietyllä hetkellä, joka saadaan lineaarisella interpoloinnilla . Näin tekemällä Bx - puu säilyttää yhtenäisen kuvan kaikista jaetun elementin kohteista muuttamatta objektien päivitysaikaa.

Seuraavaksi tila ositetaan hilalla ja objektien sijainti linearisoidaan osioelementille ajassa tilantäyttökäyrän mukaan, esimerkiksi Peano -käyrät tai Hilbert-käyrät .

Sitten yhdistettynä jaetun elementin numeroon (aikatieto) ja lineaariseen järjestykseen (sijaintitieto) objekti indeksoidaan B x -puuhun yksiulotteisella avainarvolla (B x arvo):

Tässä indeksiosio on päivitysajan määrittämä osioelementin indeksi ja xrep on objektin sijainnin arvo tilantäyttökäyrällä indeksointihetkellä, tarkoittaa x:n binaariarvoa, "+" tarkoittaa merkkijonoa. ketjuttaminen.

Kun kohde O ((7, 2), (-0,1, 0,05), 10), tmu = 120, B x :n arvo O:lle voidaan laskea seuraavasti.

  1. O on indeksoitu aikaosion elementtiin 0, kuten edellä on kuvattu. Joten indeksiosio = (00) 2 .
  2. Objektin O sijainti osion 0 ajan asettamisen hetkellä on (1.5).
  3. Käyttämällä Z-käyrää, jonka luokka on 3, kohteen O, xrep, Z-arvo on (010011) 2 .
  4. Yhdistämme rivit indexpartition ja xrep, saamme arvon B x (00010011) 2 =19.

Lisäys, päivitys ja poistaminen

Jos uusi objekti annetaan, sen indeksiavain lasketaan ja objekti lisätään B x -puuhun kuten B+‍‍-puussa. Päivitys koostuu poistosta ja sen jälkeen lisäämisestä. Lisärakenteita käytetään kunkin indeksin viimeisen avaimen tallentamiseen, jotta objekti voidaan poistaa, kun avainta haetaan. Indeksiavain lasketaan ennen kuin se sisällytetään puuhun. Siten B x -puu perii suoraan B+‍‍-puun hyvät ominaisuudet ja saavuttaa hyvän päivityssuorituskyvyn.

Pyynnöt

Kysely alueen mukaan

Aluekysely hakee kaikki objektit, joiden sijainti osuu suorakaiteen muotoiseen alueeseen ajankohtana, joka ei ole aikaisempi kuin nykyinen aika.

Bx - puu käyttää kyselyikkunan laajennustekniikkaa vastatakseen tähän kyselyyn. Laajennuksella on kaksi tapausta - sijainti on joko laskettava jonakin aiemman ajankohtana tai myöhempänä ajankohtana. Tarkoituksena on laajentaa kyselyikkunaa siten, että se sisältää kaikki objektit, jotka eivät ole kyselyikkunassa objektiavaimessa määritettynä ajankohtana, mutta kuuluvat siihen pyynnön ajaksi.

Laajentamisen jälkeen sinun on selattava B x -puun osia löytääksesi objektit, jotka putoavat laajennettuun ikkunaan. Jokaisessa osiossa tilantäyttökäyrän käyttö tarkoittaa, että luonnollisen 2D-avaruuden kyselyalueesta tulee 1D-avaruuden aluekyselyiden joukko [1] .

Liian laajan alueen kyselyjen välttämiseksi epäsymmetristen tietojen kyselyikkunan laajentamisen jälkeen on olemassa optimointialgoritmi [3] , joka parantaa kyselyn suorituskykyä poistamalla tarpeettomat laajennukset.

Kysely K lähimmistä naapureista

K lähimmän naapurin kysely suoritetaan iteratiivisesti suorittamalla aluekyselyitä kasvattamalla hakualuetta, kunnes saamme k vastausta. Toinen mahdollisuus on käyttää samanlaisia ​​ideoita yhdessä iDistance -tekniikan kanssa .

Muut pyynnöt

Aluekyselyä ja K lähimmän naapurin kyselyalgoritmia voidaan helposti laajentaa tukemaan intervallikyselyjä, jatkuvia kyselyjä jne. [2] .

Relaatiotietokantojen mukauttaminen liikkuviin objekteihin

Koska B x -puu on B+‍‍-puun päälle rakennettu indeksi, kaikki B x - puun toiminnot, mukaan lukien lisäys, poisto ja haku, ovat samoja kuin B+‍‍-puussa. Näiden toimien toteuttamista ei tarvitse muuttaa. Ainoa ero toteutuksessa on indeksointiavaimen hankkimismenettelyn toteutuksessa tallennettuna toimintosarjana olemassa olevaan tietokantaan . Siten Bx - puu voidaan helposti integroida olemassa olevaan tietokantaan vaikuttamatta ytimeen .

SpADE [4]  on liikkuvien objektien hallintajärjestelmä, joka on rakennettu suositun MySQL-tietokannan päälle ja joka käyttää B x -puuta objektien indeksointiin. Toteutuksessa liikkuvat objektitiedot muunnetaan ja tallennetaan suoraan MySQL:ään, ja kyselyt muunnetaan vakiomuotoisiksi SQL-kyselyiksi, joita relaatiotietokannan ajonaika käsittelee tehokkaasti. Mikä tärkeintä, kaikki tämä tehdään siististi ja itsenäisesti häiritsemättä MySQL-ydintä.

Performance Tuning

Mahdollisia ongelmia tietojen vinossa

Bx -puu käyttää tilanvaraushilaa kaksiulotteisen sijainnin muuntamiseen yksiulotteiseksi avaimeksi. Tämä voi johtaa suorituskyvyn heikkenemiseen sekä kyselyissä että päivityksissä, kun työskentelet epäsymmetristen tietojen kanssa. Jos ruudukon solu on suuri, solu sisältää monia objekteja. Koska solun objektit eivät ole erotettavissa indeksin perusteella, alla olevassa B+‍‍-puussa on jonkin verran solmun ylivuotoa. Ylivuotosivujen olemassaolo ei ainoastaan ​​tuhoa puun tasapainoa, vaan myös lisää päivityskustannuksia. Kuten tavallisissa kyselyissä, aluekyselyssä suuremmat solut johtavat enemmän vääriin näytteisiin ja pidentävät suoritusaikaa. Toisaalta, jos tila jaetaan pienempään ruudukkoon, eli pienempiin soluihin, jokainen solu sisältää vähemmän objekteja. On epätodennäköistä, että sivun ylivuoto saavutetaan tässä tapauksessa, ja myös vääriä näytteitä tulee vähemmän, mutta enemmän soluja on skannattava. Tarkasteltavien solujen määrän lisääminen lisää myös kyselyn monimutkaisuutta.

Hakemiston määrittäminen

ST 2 B-puu [5] esittelee itseviritysjärjestelmän B x -puun suorituskyvyn virittämiseksi käsiteltäessä epäsymmetristä dataa tilassa ja ajassa. Työskentelyäkseen epäsymmetrisen datan kanssa ST 2 -tilassa B-puu jakaa koko tilan alueiksi, joilla on eri tiheys objekteja käyttämällä ohjauspisteiden joukkoa. Jokainen alue käyttää yksittäistä ruudukkoa, jonka solun koon määrää alueella olevien objektien tiheys.

B x -puussa on useita osioita eri aikaväleille. ST 2 B-puu käyttää intervallin lisäystä tai pienennystä indeksoinnin säätämiseksi tilan jakamisen ja ajan muutosten mukaiseksi. Erityisesti, kun osio tyhjenee ja alkaa kasvaa, valitaan uusi ohjauspisteiden joukko ja jokaiselle pisteelle valitaan uusi ruudukko viimeisen datatiheyden mukaan. Viritys perustuu tietyltä ajanjaksolta kerättyihin tilastoihin, jotta tilan osiointi vastaa paremmin uusinta datajakaumaa. Tässä mielessä ST 2 B-puun odotetaan minimoivan vaikutuksen, joka aiheutuu datan vinoutumisesta tilassa ja datan muutoksista ajan myötä.

Katso myös

Muistiinpanot

  1. 1 2 Jensen, Lin, Ooi, 2004 , s. 768-779.
  2. 12 Dan Lin, 2006 .
  3. Jensen, Tiesyte, Tradisauskas, 2006 .
  4. SpADE Arkistoitu alkuperäisestä 2. tammikuuta 2009. : Spatio-ajallinen autonominen tietokantamoottori sijaintitietoisille palveluille.
  5. Chen, Ooi, Tan, Nacismento, 2008 , s. 29-42.

Kirjallisuus