Bulk Indexing on Flash Devices

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Saikkonen, Riku
dc.contributor.author Lehtonen, Jonas
dc.date.accessioned 2014-06-25T08:40:43Z
dc.date.available 2014-06-25T08:40:43Z
dc.date.issued 2014-06-02
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/13476
dc.description.abstract In database applications, bulk operations which affect multiple records at once are common. They are performed when operations on single records at a time are not efficient enough. They can occur in several ways, both by applications naturally having bulk operations (such as a sales database which updates daily) and by applications performing them routinely as part of some other operation. While bulk operations have been studied for decades, their use with flash memory has been studied less. Flash memory, an increasingly popular alternative/complement to magnetic hard disks, has far better seek times, low power consumption and other desirable characteristics for database applications. However, erasing data is a costly operation, which means that designing index structures specifically for flash disks is useful. This thesis will investigate flash memory on data structures in general, identifying some common design traits, and incorporate those traits into a novel index structure, the bulk index. The bulk index is an index structure for bulk operations on flash memory, and was experimentally compared to a flash-based index structure that has shown impressive results, the Lazy Adaptive Tree (LA-tree for short). The bulk insertion experiments were made with varying-sized elementary bulks, i.e. maximal sets of inserted keys that fall between two consecutive keys in the existing data. The bulk index consistently performed better than the LA-tree, and especially well on bulk insertion experiments with many very small or a few very large elementary bulks, or with large inserted bulks. It was more than 4 times as fast at best. On range searches, it performed up to 50 % faster than the LA-tree, performing better on large ranges. Range deletions were also shown to be constant-time on the bulk index. en
dc.description.abstract Tietokantasovelluksissa kimppuoperaatiot jotka vaikuttavat useampaan alkioon kerralla ovat yleisiä, ja niitä käytetään tehostamaan tietokannan toimintaa. Niitä voi käyttää kun data lisätään tietokantaan suuressa erässä (esimerkiksi myyntidata jota päivitetään kerran päivässä)tai osana muita tietokantaoperaatioita. Kimppuoperaatioita on tutkittu jo vuosikymmeniä, mutta niiden käyttöä flash-muistilla on tutkittu vähemmän. Flash-muisti on yleistyvä muistiteknologiajota käytetään magneettisten kiintolevyjen sijaan tai niiden rinnalla. Sen tietokannoille hyödyllisiin ominaisuuksiin kuuluvat mm. nopeat hakuajat ja alhainen sähkönkulutus. Kuitenkin datan poisto levyltä on työläs operaatio flash-levyillä, mistä johtuen tietorakenteet kannattaa suunnitella erikseen flash-levyille. Tämä työ tutkii flashin käyttöä tietorakenteissa ja koostaa niistä flashille soveltuvia suunnitteluperiaatteita. Näitä periaatteita edustaa myös työssä esitetty uusi rakenne, kimppuhakemisto (bulk index). Kimppuhakemisto on tietorakenne kimppuoperaatioille flash-muistilla, ja sitä verrataan kokeellisesti LA-puuhun (Lazy Adaptive Tree, suom. laiska adaptiivinen puu), joka on suoriutunut hyvin kokeissa flash-muistilla. Kokeissa käytettiin vaihtelevan kokoisia alkeiskimppuja, eli maksimaalisia joukkoja lisätyssä datassa jotka sijoittuvat kahden olemassaolevan avaimen väliin. Kimppuhakemisto oli nopeampi kuin LA-puu, ja erityisen paljon nopeampi kimppulisäyksissä pienellä määrällä hyvin suuria tai suurella määrällä hyvin pieniä alkeiskimppuja, tai suurilla kimppulisäyksillä. Parhaimmillaan se oli yli neljä kertaa nopeampi. Välihauissa se oli jopa 50 % nopeampi kuin LA-puu, ja parempi suurten välien kanssa. Välipoistot näytettiin vakioaikaisiksi kimppuhakemistossa. fi
dc.format.extent 73
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.title Bulk Indexing on Flash Devices en
dc.title Tietuekimppujen indeksointi flash-muistilla fi
dc.type G2 Pro gradu, diplomityö en
dc.contributor.school Perustieteiden korkeakoulu fi
dc.subject.keyword index structures en
dc.subject.keyword database en
dc.subject.keyword search trees en
dc.subject.keyword B-tree en
dc.subject.keyword group update en
dc.subject.keyword bulk update en
dc.subject.keyword group deletion en
dc.subject.keyword bulk deletion en
dc.subject.keyword group insertion en
dc.subject.keyword bulk insertion en
dc.subject.keyword interval deletion en
dc.subject.keyword range deletion en
dc.subject.keyword flash memory en
dc.subject.keyword hakemistorakenne fi
dc.subject.keyword indeksointi fi
dc.subject.keyword hakupuu fi
dc.subject.keyword B-puu fi
dc.subject.keyword kimppupäivitys fi
dc.subject.keyword kimppupoisto fi
dc.subject.keyword kimppulisäys fi
dc.subject.keyword intervallipoisto fi
dc.subject.keyword tietokanta fi
dc.subject.keyword avainvälipoisto fi
dc.subject.keyword flash-muisti fi
dc.identifier.urn URN:NBN:fi:aalto-201406252208
dc.programme.major Tietojenkäsittelytiede fi
dc.programme.mcode IL3010 fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Diplomityö fi
dc.contributor.supervisor Soisalon-Soininen, Eljas
dc.programme Tietotekniikan koulutusohjelma fi


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse