Kimppulisäykset (a,b)-puissa

Abstract

Talletettaessa tietoja tietokantaan tieto talletuspaikasta sijoitetaan yleensä erilliseen indeksirakenteeseen. Indeksointi pyritään suorittamaan siten, että indeksiin tehtävät päivitykset voidaan suorittaa mahdollisimman tehokkaasti. Indeksointi toteutetaan yleensä jonkin puurakenteen avulla, joka pyritään pitämään tasapainossa, jolloin tiedon haku voidaan suorittaa tehokkaasti. Päivitysoperaatiot muuttavat puun rakennetta usein epäedulliseksi, jolloin rakenne voidaan korjata niin sanottujen tasapainotusoperaatioiden avulla. Päivitykset pyritäänkin suorittamaan siten, että rakennetta korjaavia tasapainotusoperaatioita joudutaan suorittamaan mahdollisimman vähän.

Tässä tutkielmassa käsitellään tietokannan avaintietojen lisäämisessä käytettävän kimppulisäysoperaation suorittamista (a,b)-puurakenteelle. (a,b)-puu on yleinen tietokantojen indeksoinnissa käytettävä puurakenne. Kimppulisäyksessä talletettavista avaimista muodostetaan joukkoja (kimppuja), jotka talletetaan puurakenteeseen kerralla. Tällä tavoin voidaan vähentää tarvittavien tasapainotusoperaatioiden lukumäärää ja suorittaa lisäykset nopeammin, kuin jos avaimet lisättäisiin puuhun yksitellen.

Tutkielmassa esitetään kaksi yleistä tapaa suorittaa algoritmin vaativuusanalyysi. Yleisimmät puurakenteet ja niiden ominaisuudet käydään läpi. Kimppulisäysalgoritmi sekä sen vaativuus- ja oikeellisuusanalyysi esitetään. Lisäksi kimppulisäysalgoritmi ja (a,b)-puu toteutetaan ja algoritmin toimivuutta testataan käytännössä.

Tutkielman osana tehdyn testauksen tulokset tukevat kimppulisäysalgoritmille suoritettuja analyysejä tasapainotusoperaatioiden lukumäärästä. Testauksen aikana ilmeni joitakin algoritmin toteuttamiseen liittyviä erityispiirteitä, joiden perusteella algoritmiin voidaan ehdottaa tarkennuksia.