Interval Deletion in B-trees

Lilja, Timo

Aaltodoc
→
1b Maisterivaiheen opinnäytetyöt / Master’s theses
→
[dipl] Teknillinen korkeakoulu / TKK
→
View Item

Interval Deletion in B-trees



Title:	Interval Deletion in B-trees B-puiden intervallipoistot
Author(s):	Lilja, Timo
Date:	2005
Language:	en
Pages:	(6) + 57
Department:	Tietotekniikan osasto
Major/Subject:	Ohjelmistotekniikka
Supervising professor(s):	Soisalon-Soininen, Eljas
Keywords:	data structures, tietorakenne, algorithms, algoritmi, search trees, hakupuu, tree, puu, group update, ryhmäpäivitys, bulk update, ryhmäpoisto, group deletion, ryhmälisäys, bulk deletion, intervallipoisto, group insertion, avainvälipoisto, bulk insertion, interval deletion, range deletion
Location:	Archive
» Show full item record
Abstract: 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.
Permanent link to this item: http://urn.fi/URN:NBN:fi:aalto-2020120451586 Email this Export to RefWorks QR Code Print BibTex Tweet

Files in this item

Name: master_Lilja_Timo_2005.pdf

Size: 19.99Mb

Format: PDF

View/Open

Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.