Hyppää sisältöön
    • Suomeksi
    • In English
  • Suomeksi
  • In English
  • Kirjaudu
Näytä aineisto 
  •   Etusivu
  • OSUVA
  • Pro gradu -tutkielmat ja diplomityöt
  • Näytä aineisto
  •   Etusivu
  • OSUVA
  • Pro gradu -tutkielmat ja diplomityöt
  • Näytä aineisto
JavaScript is disabled for your browser. Some features of this site may not work without it.

Kimppulisäykset (a,b)-puissa

Mannila, Markus (2003)

 

Aineistoon ei liity tiedostoja.


Mannila, Markus
2003
Näytä kaikki kuvailutiedot

Kuvaus

Kokotekstiversiota ei ole saatavissa.
Tiivistelmä
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.
Kokoelmat
  • Pro gradu -tutkielmat ja diplomityöt [6298]
https://osuva.uwasa.fi
Ota yhteyttä | Tietosuoja | Saavutettavuusseloste
 

 

Tämä kokoelma

TekijäNimekeAsiasanaYksikkö / TiedekuntaOppiaineJulkaisuaikaKokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy
https://osuva.uwasa.fi
Ota yhteyttä | Tietosuoja | Saavutettavuusseloste