ISAM in B+ drevesa .... 16.3.2010

BAZE_FRI_16.03-2010

-> ISAM za indeksiranje datotek
Od prejšnjič:
Podatki logično shranjeni v tabelah, fizično v datotekah. Vedno imam opravka z stranmi. Datotečne organizacije: urejene/ neurejene / razpršene.
-hash datoteke: razpršene: Imasmo neko funkcijo, ki nam izračuna kam bomo upisali neko stran. (na katero mesto)
-odprto naslavljanje ne/povezane dodatne strani, večkratna razpršitev: se večkrat zgodi. Če poda naslov, ki je že zaseden, jo izvedemo ponovno.
-prednosti in slabosti hash datoteke
-indeksi na splošno ; terminologija

Indekse realiziramo s pomočjo podatkovne strukture v obliki na glavo obrnjenega drevesa. 2 indeksa: Isam B+ drevo
ISAM: Statičen. Iskanje po datotekah, dolgotrajno. Ima prazne prostore, kjer brišemo podatke. Prosto se ne uporabi ponovno.

Od danes:
ISAM indeks sestavljajo dve vrsti strani:
-listi : strani z podatki
-vozlišča : nepodatkovne strani
-isam se ne spreminja, v celoti statičen (pri b+ drevesu se drevo spreminja)
-ko se inddeksna datoteka kreira, so vse strani v listih urejene zaporedno, po iskalnem ključu
-ko dodajamo nov zapis le-ta pride kamor pride.
3 operacije v ISAM drevesu:
Iskanje:
Začnemo v korenu. Podatki v indeksnih vozliščih nam dajo smer kamor naj gremo. Tako pridemo do lista. Če podatka ni v listu, iščemo v dodatnih straneh.
Dodajanje:
Stran v listih, kamor zapis sodi poiščemo enako kot pri iskanju. Če je mesto v listu prosto ga tja dodamo, sicer kreiramo novo stran. Zapis dodamo na prvo prosto mesto.
Vse overflow strani nniso nič urejene. V prmarnih listih so podatki za razliko urejeni.
Brisanje:
Podatke za brisanje iščemo enako, kot pri iskanju.
Če je zapis na dodatni strani in gre za zadnji zapis na strani, stran zbrišemo.
Če je zapis na primarni strani in je zadnji, stran pustimo. Služi za prazno mesto za kasnejše zapise. Lahko se zgodi da zapis nastopa v indeksnem delu v podatkovnem pa ne.
Problem ISAM strukture se pokaže, ko naraste število dodatnih strani. Problem omilimo tako, da na začetku, ko izradimo indeks, pustimo nekaj praznega prostora v listih. Druga možnost: periodično obnavljamo indeks.

B+ indeks/ B+ drevo:
V praksi bolj uporaben. Je dimaičen. Povečuje učinkovitost. B+drevo je uravnoteženo drevo. Ker se b+ drevo dinamično spreminja listi niso urejeni. So pa listi povezani s dvosmernim seznamom. Lastnosti: drevo je uravnoteženo tako da je vsako vozlišče z izjemo korena vsaj 50 procentno zasedeno. Iskanje zahteva sprehod od korena do lista. Večja kot je globina več je avput input opreracij. Vsaka pot od korena do vozlišča je enako dolga. Pravimo ji višina drevesa. ( D je parameter B+ drevesa. Predstavlja polovico zasedenosti drevesa.) B+ drevo ima prednost, da je dobro poleg iskanja tudi za dodajanje in brisanje. (Ponavadi se te operacije med seboj izključujejo) Algolitem za iskanje deluje podobno kot pri ISAM strukturi. Imao funkcijo, ki išče nek kluč z vrednostjo k. Deluje pa rekuzivno. Funkcija koišče searc key tako da začne pri nekem pointerju. V začetku je ta nek korek, nato se premakne v vozlišče. Ko ga najde rekurzivno pokliče sama sebe.
Druge funkcije pri B+ drevesih:
/ Iskanje : enako kot pri ISAMdrevesu /
Dodajanje: poiščemo list kamo bi dodatek sodil. Če je list prost podatek dodamo vanj. Če list ni prost, ga razdelimo na 2 dela. Če moramo zardi razpolovitve lista dodati k v vozlišče, ki je že polno, se delitev ponovi.....Delitveni ključ premaknemo na en nivo višje. (Delitev v vozliščih ni enako za podatkovni in indeksni del.)
 Dodajanje:
– Dodajamo podatek k*
– Poiščemo list, kamor k* spada
– Če je v listu še prostor, k* dodamo, sicer moramo list razdeliti na dva dela.
– Če moramo zaradi razpolovitve lista dodati k* v vozlišče, ki je že polno, se delitev ponovi.
– V splošnem moramo vozlišče, ki ni list, razpoloviti, ko je polno  vsebuje 2d ključev in 2d+1 kazalcev
– Z dodatnim indeksnim poljem k* imamo 2d+1 ključev in 2d+2 kazalcev  lahko razdelimo na dva minimalno zasedena vozlišča (vsak po d ključev in d+1 kazalcev ter dodaten ključ, ki smo ga izbrali kot delitveni ključ.
– Delitveni ključ skupaj s kazalcem na drugi del razdeljenega vozlišča premaknemo eno raven višje.





Redestribucija podatkov ali razceplanje strani: glej prosojnico!!!
– v primeru, ko dodajamo v vozlišče N, ki je polno, uporabimo postopek redistribucije podatkov ali razcepljanje strani.
– Redistribucija se nanaša na vozlišče N in na vozlišči, ki sta njen levi in desni sosed in hkrati pripadata istemu nad-vozlišču.
Stroški redestribucije: Koliko nas časovno stane?
– Stroški redistribucije v indeksnem delu se ne splačajo. Redko kdaj dobimo prosto mesto v indeksnem delu. Da ugotovimo, ali je redistribucija možna, moramo preveriti sosede (do 2 I/O operaciji). Če so sosedi polni, je razdelitev vseeno potrebna.
– Stroški redistribucije v indeksnem delu
 Preverjanje možnosti redistribucije v povprečju poveča število I/O operacij, saj se redko zgodi, da bi bila redistribucija možna  se ne splača.
– Stroški redistribucije v podatkovnem delu
 Če je potrebno razdeliti list, moramo vseeno prebrati sosedno vozlišče, da popravimo kazalce.
 Redistribucija se splača: če je list zaseden, preberi soseda. Če je prosto mesto, dodaj, sicer razpolovi.
Brisanje: če se zasedenost lista, v katerem je bil podatek, pade pod mejo, moramo izvest ustrezno redistribucijo s sosednimi listi ali pa združiti več listov skupaj.
– Če podatke redistribuiramo med dve vozlišči, moramo ustrezno spremeniti vsebino nad-vozlišča.
– Če podatke združimo iz dveh vozlišč, moramo vsebino njunih nad-vozlišč spremeniti tako, da brišemo indeksno polje za drugo vozlišče.
Pri združevanju listov se ključ premakne en noivo navzgor. Pri zruževanju indeksov se ključ premakne iz zgornjega na nivo nižje.
Primer redistribucije v indeksem delu: glej shemo na prosojnici!!!
– Stroški brisanja: Pri brisanju pogledamo najprej samo enega soseda
 Če ima odvečna polja, naredimo redistribucijo, sicer združitev
Redestribucija je cenejša od združevanja. Algoritem za brisanje deluje podobno kot algolitem za dodajanje.
Dublikati: lahko imamo več vrednosti, ki imajo isti ključ. Iskanje: lahko rešimo z dodatnimi stranmi. Alholitem poišče najbolj levo polje v listu in po potrebi pregleda še dodatne strani.
Prijemi za pospešitev iskanja:
Pri drevesu na učinkovitost iskanja najbolj vpliva: manjča kot je višina lai globina drevsa hitreje pridemo do rezultata. Drevo moramo čimbolj razvejati.
Stiskanje ključev:
Za povečanje učinkovitosti iskanja skušamo maximalno povečati parameter razvejanosti. ( Prefix Key Compresion)
Komercialni sistemi:
– IBM DB2, Informix, Microsoft SQL Server, Oracle, Sybase ASE – vsi sistemi podpirajo indekse na osnovi B+ dreves; razlike predvsem v obravnavi duplikatov in postopku brisanja.

Sybase ASE: Tako rešitev uporablja veliko SUPBjev
Združevanje (če zasedenost pod mejo) ali
 Označitev zapisa, da je brisan. Občasno se požene postopek (garbage collection scheme), ki sprosti nezaseden prostor.


Oracle: omogoča on-line obnovitev sistema
-pri brisanju se zapis označi kot brisan. Obnovitev indeksa možna on-line (ko je indeks v uporabi) ali na kopiji indeksa z združevanjem nepolnih vozlišč.
– Informix: pri brisanju se zapis označi kot brisan.
– IBM DB2, Microsoft SQL Server: pri brisanju se zapis dejansko briše. Če pade zasedenost vozlišča pod mejo, se uporabi združevanje.


Bitni indeksi
Uporabljajo se za polja, ki imajo majhno število vrednosti. (stolpci v tabelah)
Prednosti bitnega indeksa v primerjavi z B+ drevesi: -kompatiblinost –večja učinkovitost pri iskanju po več predikatih

Stični indeks
Deluje podobno kot bitni. Uporablja za specifične naloge, npr. podatkovna središča. Uporablja se za tabele, ki imajo skupna polja.

Gruče
Fizično združene relacije na disku. Omogočajo zelo hitro iskanje. Za ključ gruče glej prosojnice.

Smernice za izbero datotečne organizacije:
Glej prosojnice!!!