Täydentäviä kommentteja luentomateriaalin lukuun 3 (hakemistorakenteet)/ HE 25.9.2001

Hakemistoja ei tarvita periaatteessa ollenkaan, koska mikä tahansa relaatioon kuuluva tietue voidaan löytää selaamalla kaikki relaation sivut läpi. Käytännössä useimmat käsittelytarpeet vaativat hakemistoja. Se, mitä hakemistoja ylläpidetään, on tärkeä tietokannan (toteutuksen) suunnittelutehtävä. Sivun 4 esimerkkiä ja siihen liittyvää harjoitustehtävää (2.5) yleistämällä on helppo päätellä, mitä vaikutuksia olisi sillä 'äärimmäisellä' ratkaisulla, että jokaiselle attribuutille ylläpidettäisiin omaa oheishakemistoa. Luentomateriaalissa tähän palataan vielä sivulla 33.

Hakemistojen perusominaisuudet on syytä selvittää itselleen (s. 3 jne):
- yksi tai useampia tasoja,
- tiheä vai harva,
- perushakemisto, oheishakemisto, ryvästävä hakemisto.

Harvan hakemiston idea: kun ei tarvita jokaiselle tietueelle omaa hakemistotietuetta, harva hakemisto vie tiheää vähemmän tilaa - ja mahtuu ehkä jopa keskusmuistipuskuriin. Harvan hakemiston vaatimus: perustiedoston tulee olla järjestetty. Miten ne 'omaa osoitetta vailla olevat' muuten löydettäisiin hakemiston avulla??
(Samantapaisella pohdinnalla eli miettimällä, mitä osoittimia tarvitaan, selviävät jokseenkin kaikki hakemistorakenteiden ominaisuudet ...)

Monitasoisen hakemiston käsittelyn alussa mainitaan, että oikein pieni hakemisto voi olla rakenteeltaan yksinkertaisesti kasa. Tämä on aika teoreettinen vaihtoehto, mutta voi olla tietyssä erityistapauksessa riittävän tehokas: Jos tietueilla on paljon attribuutteja, tietueita mahtuu jaksoon vähän ja jaksoja on siis (läpi selattavaksi) paljon. Hakemistotietueet (avain ja osoitin) ovat kuitenkin lyhyitä eli niistä ei tule välttämättä kovin monta jaksoa. Tämä lyhyiden (hakemisto)tietueiden idea esiintyy myös sivulla 19 käsiteltäessä ISAM-rakennetta kasan päälle rakennettuna hakemistona. (Vaikka tulee yksi tavallaan ylimääräinen taso, se kompensoituu jaksojen määrän kautta.)

Monitasoisten hakemistojen 'voima' on siinä, että käytännössä kaikilla järkevillä parametriarvoilla hakemistotasojen määrä jää hyvin pieneksi (vrt. ISAM- ja B+ -puuhakemistojen tilantarvelaskelmat).

Se, ettei ISAM-hakemistoa yleensä päivitetä yksittäisten lisäysten yhteydessä, voi tuntua yllättävältä. Mutta harvan hakemiston ideaa miettimällä päivitys on helppo todeta tarpeettomaksi. Ja se, ettei päivitetä, tekee myös lisäysoperaatiot tehokkaiksi.

ISAM-rakenteen sopivuus: kysely tarkalla arvolla tai järjestykseen perustuen (avaimen alkuosa jne). Ylimääräinen pohdinnan kohde: Kuinka ISAM-tekniikalla voitaisiin helpottaa esim. 'nen'-päätteisillä nimillä varustettujen henkilöiden löytämistä?

Viitattaessa sivulla 21 (dynaamisten hakemistorakenteiden alussa) hajautukseen tarkoitetaan yksinkertaisesti luvussa 2 käsiteltyä hajautusrakennetta, joka tavallaan noudattaa hakemistorakennetta (soluhakemisto ja perustietueiden jaksot) - vaikka tätä ei olekaan luvussa 2 erikseen korostettu.

B-puun ja B+ -puun suhde: edellinen on eräänlainen perusmuoto (ensin keksitty aikanaan) ja jälkimmäinen se muoto, jota käytetään tietokannan toteutuksessa. Esitystapa voisi siten olla toinenkin (paino B+ -puussa); valitettavasti en nyt ehtinyt tehdä tällaisia muutoksia. Kummankin rakenteen ominaisuudet selviävät pitkälle edellä jo mainitun periaatteen avulla: selvitä solmurakenteista lähtien itsellesi, mitä linkkejä tasojen välillä tarvitaan.

Sivulla 23 johdatellaan B-puuhun yleisen hakupuun avulla. Ensimmäinen solmurakenne ei sisällä avaimen lisäksi muuta tietuekohtaista tietoa (eli on 'supistettu' versio; tällä rakenteella tietueen mahdollisia muita osia ei löydettäisi mitenkään). Alempana viitataan kahteen käytännölliseen tapaan: solmussa on joko koko tietue tai pari (avain, osoitin). Oppikirjoissa käytetään usein edellistä tapaa (vrt. binääripuiden solmurakenteet), mutta jälkimmäinen on käytännössä normaali. (Muuten solmuun mahtuu vain hyvin vähän tietueita; tasoja tulee paljon eli ei saavuteta monitasoisen hakemiston etua. )

Jälkimmäinen tapa näkyy sitten heti sivulla 24 B-puun sisäsolmun rakenteessa. Yleisen hakupuun ja B-puun toinen, tärkeämpi ero on siinä, että B-puulle määritellään tasapainoehdot (ehdot 4-5 (6)). Rakenteen ominaisuudet selviävät parhaiten tekemällä huolellisesti harjoitustehtävän (3.5).

B-puulle on muitakin variantteja kuin B+ -puu. B* -puuksi sanotaan sellaista B-puuta, jossa solmun tietueiden määrä on välillä (2/3*p, p) eli vaihteluväli on vähän pienempi kuin perusrakenteissa. Mitä tästä seuraa? (Lisäyksiin liittyvä solmun jako tehdään nyt niin, että kaksi täyttä solmua jaetaan kolmeksi; vastaavasti poistoon liittyvä mahdollinen yhdistäminen analogisesti. (Tällä variantilla ei ole tietokantojen osalta merkitystä; tietorakenteena ehkä ...)

Sivut 33-36 ovat luonteeltaan täydennystä tai kertausta. Oheishakemistojen merkitystä koskeva kohta on tärkein. Muut ovat 'asiaa' myös, mutta hieman irrallisia.