haku: @author Lilja, Timo / yhteensä: 2
viite: 2 / 2
« edellinen | seuraava »
| Tekijä: | Lilja, Timo |
| Työn nimi: | Interval Deletion in B-trees |
| B-puiden intervallipoistot | |
| Julkaisutyyppi: | Diplomityö |
| Julkaisuvuosi: | 2005 |
| Sivut: | (6) + 57 Kieli: eng |
| Koulu/Laitos/Osasto: | Tietotekniikan osasto |
| Oppiaine: | Ohjelmistotekniikka (T-106) |
| Valvoja: | Soisalon-Soininen, Eljas |
| Ohjaaja: | |
| Digitoitu julkaisu: | https://aaltodoc.aalto.fi/handle/123456789/92751 |
| OEVS: | Digitoitu arkistokappale on julkaistu Aaltodocissa
|
| Sijainti: | P1 Ark Aalto | Arkisto |
| Avainsanat: | data structures algorithms search trees tree group update bulk update group deletion bulk deletion group insertion bulk insertion interval deletion range deletion tietorakenne algoritmi hakupuu puu ryhmäpäivitys ryhmäpoisto ryhmälisäys intervallipoisto avainvälipoisto |
| Tiivistelmä (fin): | Intervallipoistossa B-puuhakurakenteesta poistetaan kaikki annetulle avainvälille kuuluvat avaimet. Intervallipoisto on erikoistapaus yleisestä ryhmäpoisto-operaatiosta, jossa joukko avaimia poistetaan puusta. Kun poistettavan ryhmän aliryhmä muodostaa jatkuvan avainvälialueen puussa, voidaan soveltaa intervallipoistoa. Relaatiotietokannoissa transaktion toteuttava prosessi tuottaa indeksiin kohdistuvia intervallipoisto-operaatioita tietyissä tilanteissa silloin, kun viite-eheys on säilytettävä. Ylhäältä alaspäin etenevä tasapainotus on menetelmä, jossa puu tasapainotetaan päivitysoperaation etsintävaiheessa. Alun perin tasapainotukset suoritettiin vasta lisäys- tai poisto-operaation jälkeen erillisellä tasapainotusvaiheella. Rinnakkaisia järjestelmiä tarkasteltaessa ylhäältä alaspäin etenevä tasapainotus takaa sen, että solmuja tarvitsee lukita ainoastaan vakiomäärä, kun taas alhaalta ylöspäin etenevässä tasapainotuksessa lukkojen lukumäärä on pahimmassa tapauksessa suhteessa puun korkeuteen. Siispä ylhäältä alaspäin etenevä tasapainotus mahdollistaa prosessien tehokkaamman rinnakkaisen suorittamisen. Tässä työssä luodaan katsaus B-, B+-, Blink- ja (a, b)-puihin ja niissä sovellettaviin tasapainotusmenetelmiin sekä selvitetään nykyisin tunnettuja intervallipoisto-operaation toteutustapoja. Työssä esitellään yksityiskohtaisesti ylhäältä alaspäin etenevä yksivaiheinen intervallipoistoalgoritmi, joka suorittaa vakiomäärän tasapainotusoperaatioita tasoitetun vaativuuden mielessä. Työssä esitellään myös kokeellinen osuus, jossa pyritään vertailemaan algoritmin suorituskykyä muihin lähestymistapoihin ja hakemaan kokeellista tukea esitetylle teorialle. Työn uusi tulos on ylhäältä alaspäin tasapainottava yksivaiheinen intervallipoistoalgoritmi. |
| ED: | 2005-06-30 |
INSSI tietueen numero: 28972
+ lisää koriin
« edellinen | seuraava »
INSSI