Indexes

download Indexes

of 8

  • date post

    30-Oct-2014
  • Category

    Business

  • view

    12
  • download

    4

Embed Size (px)

description

A lecture about database indexes.

Transcript of Indexes

  • 1. Structurile de indexare pentru fiiere n cele ce urmeaz, se descriu structurile de acces, numite indeci, care sunt folosite pentru accelerarea prelucrrii nregistrrilor ca rspuns la anumite condiii de cutare. Anumite tipuri de indeci, denumii ci de acces secundare, nu afecteaz aezarea fizic a nregistrrilor pe disc; mai degrab asigur ci alternative de cutare bazat pe cmpuri de indexare pentru o localizare mai eficient a nregistrrilor. Alte tipuri de indeci pot fi construite pentru un fiier doar cu o organizare primar particular. Ideea din spatele unei structuri ordonate de acces bazat pe indexare este asemntoare ideii de indeci folosii n manuale. Un index al unui manual este o list ce conine termeni importani ordonai alfabetic i se afl la sfritul crii. Fiecare termen este nsoit de o list de numere de pagini unde apare. Se poate cuta n index pentru a afla o list de adrese - numere de pagini n acest caz - i folosi aceste adrese pentru a localiza termenul n manual, cutnd la paginile specificate. Alternativa, dac nici o alt ndrumare nu e dat, este s se examineze ncet prin tot manualul, cuvnt cu cuvnt, pentru a gsi termenul care ne intereseaz; acest lucru corespunde unei cutri liniare ntr-un fiier. Bineneles, cele mai multe cri au informaii suplimentare, cum ar fi titlurile capitolelor sau seciunilor, care ne ajut s gsim un termen fr a fi nevoii s cutm n toat cartea. Oricum, indexul este singura indicaie exact referitoare la apariia n carte a fiecrui termen. O structur indexat de acces este de obicei definit pe un singur cmp al unui fiier, numit cmp de indexare. Indexul de obicei reine fiecare valoare a cmpului de indexare alturi de o list de pointeri ctre toate blocurile discului care conin nregistrri, avnd valoarea acelui cmp. Valorile din index sunt ordonate astfel nct s se poat face o cutare binar asupra indexului. Fiierul de index este mult mai mic dect fiierul de date, astfel cutarea binar prin index este rezonabil de eficient. Exist cteva tipuri de indeci ordonai. Un index primar este un index specificat n cmpul cheie de ordonare dintr-un fiier ordonat de nregistrri. Un cmp cheie de ordonare este folosit la ordonarea fizic pe disc a fiierului de nregistrri, i fiecare nregistrare are o valoare unic pentru acest cmp. Dac cmpul de ordonare nu este un cmp cheie - asta dac mai multe nregistrri din fiier au aceeai valoare ca i pentru cmpul cheie se poate folosi un alt tip de index, numit index grupat. A se observa c un fiier poate avea cel mult un cmp fizic de ordonare, deci poate avea cel mult un index primar sau un index grupat, dar nu pe amndou. Al treilea tip de index, numit index secundar, poate fi specificat pentru orice cmp sau fiier neordonat. Un fiier poate avea civa indeci secundari pe lng metoda sa primar de acces. In urmtoarele trei subseciuni, se vor discuta aceste trei tipuri de indeci. Indeci primariUn index primar este un fiier ordonat ale crui nregistrri sunt de lungime fix cu dou cmpuri. Primul cmp este de acelai tip de dat ca i cmpul cheie de ordonare al fiierului de date, i al doilea cmp este un pointer ctre un bloc pe disc - un bloc de adresa. Cmpul cheie de ordonare este denumit cheia primar a fiierului de date. Exist o intrare index (sau nregistrare index) n fiierul de index pentru fiecare bloc din fiierul de date. Fiecare intrare index cuprinde valoarea cmpului cheii primare pentru prima nregistrare dintr-un bloc i un pointer ctre acel bloc ca cele dou cmpuri de valori. Se va face referire la cele dou cmpuri de valori ale intrrii index i ca .

2. Pentru a crea un index primar pentru fiierul ordonat artat n figura 1, se folosete cmpul NUME ca i cheie primar, deoarece acesta este cmpul cheie de ordonare al fiierului (presupunnd c fiecare valoare pentru NUME este unic). Fiecare nregistrare nou n index are o valoare pentru NUME i un pointer. Primele trei intrri index sunt dup cum urmeaz: Figura 1 ilustreaz acest index primar. Numrul total de intrri n index este acelai ca i numrul blocurilor de disc din fiierul ordonat de date. Prima nregistrare din fiecare bloc al fiierului de date este numit nregistrarea ancor a blocului, sau mai simplu blocul ancor (se poate folosi o schem similar celei descrise aici, cu ultima nregistrare n fiecare bloc (n loc de prima) ca i bloc ancor. Aceasta mbuntete puin eficiena algoritmului de cutare.Un index primar este un exemplu de index non-dens: conine o intrare pentru fiecare bloc de disc al fiierului de date mai degrab dect pentru fiecare nregistrare din fiierul de date. Un index dens, pe de alt parte, conine o intrare pentru fiecare nregistrare din fiier.Figura1: Un exemplu de index primar Fiierul de index pentru un index primar are nevoie de mult mai puine blocuri dect pentru fiierul de date, din dou motive. In primul rnd, sunt mai puine intrri index dect sunt nregistrri n fiierul de date, deoarece o intrare apare pentru fiecare bloc ntreg din fiierul de date i nu pentru fiecare nregistrare. In al doilea rnd, fiecare intrare index este n mod caracteristic mai mic n dimensiune dect o nregistrare de date, deoarece are doar dou cmpuri; n consecin, mai multe intrri index dect nregistrri de date pot ncpea ntr-un 3. bloc. Deci o cutare binar n fiierul de index necesit mai puine accese la un bloc dect o cutare binar n fiierul de date.O nregistrare a crei cheie primar este K se gsete n blocul a crui adres este P(i), unde K(i)K. Intrrile sunt ordonate dup valoarea lui K(i), astfel se poate efectua o cutare binar asupra indexului. Deoarece nregistrrile din fiierul de date nu sunt ordonate fizic dup valorile cmpului cheii secundare, nu se pot folosi blocurile ancor. Din acest motiv este creat mai degrab o intrare index pentru fiecare nregistrare din fiierul de date, i nu pentru fiecare bloc ca n cazul indexului primar. Figura 4 ilustreaz un index secundar n care pointerii P(i) din intrrile index sunt pointeri la bloc, nu pointeri la nregistrri. Odat ce blocul potrivit este transferat n memoria principal, poate fi realizat o cutare pentru nregistrarea dorit din blocul respectiv.Un index secundar necesit de obicei mai mult spaiu de stocare i un timp mai lung de cutare dect indexul primar, datorit numrului mare de intrri. Oricum, se realizeaz mbuntirea timpului de cutare a unei nregistrri arbitrar alese, din moment ce am fi avut de fcut o cutare linear n fiierul de date dac indexul secundar nu ar fi existat.De asemenea putem crea un index secundar bazat pe un cmp non-cheie dintr-un fiier. In acest caz, numeroase nregistrri din fiierul de date pot avea aceeai valoare pentru cmpul de indexare. Exist cteva opiuni pentru implementarea unui astfel de index: Opiunea 1 este s se includ cteva intrri index cu aceeai valoare K(i) - una pentrufiecare nregistrare. Acesta ar fi un index dens. Opiunea 2 este s avem nregistrri cu dimensiune variabil pentru intrrile index, cuun cmp repetitiv pentru pointer. inem o list de pointeri

nintrarea index pentru K(i) - un pointer pentru fiecare bloc care conine o nregistrarepentru care valoarea cmpului de indexare este egal cu K(i). n oricare dintreopiunile 1 sau 2, algoritmul de cutare binar n index trebuie s fie modificatconvenabil. Opiunea 3, care este cea mai folosit, este s fie meninut o dimensiune fix pentruintrrile index i s existe o singur intrare pentru fiecare valoare a cmpului deindexare, dar s se creeze un nivel extra de indirectare pentru a trata pointerii multipli.In aceast schem non-dens, pointerul P(i) din intrarea index indicctre un bloc de pointeri la nregistrri; fiecare pointer la nregistrare din acel blocindic ctre una dintre nregistrrile fiierului de date cu valoarea K(i) pentru cmpulde indexare. Dac o anume valoare K(i) apare n prea multe nregistrri, astfel nctpointerii la respectiva nregistrare nu pot ncpea ntr-un singur bloc de disc, estefolosit o list nlnuit de blocuri. Aceast tehnic este ilustrat n figura 5.Regsirea prin intermediul indexului necesit un bloc adiional de acces datorit 7. nivelului extra, dar algoritmii de cutare n index i (mult mai important) de inserarede noi nregistrri n fiierul de date sunt uurai. Mai mult, cutrile complexe deselecie pot fi tratate prin referin la pointeri, fr a fi nevoii s se gseasc fiiere cunregistrri multe i inutile. Se observ c un index secundar furnizeaz o ordonare logic a nregistrrilor dup cmpul de indexare. Dac accesm nregistrrile n ordinea intrrilor n indexul secundar, le obinem n ordinea cmpului de indexare. Figura 4: Index secundar non-dens pe un cmp cheie 8. Figura 5: Un index secundar (cu pointeri de nregistrare) pe un cmp care nu este cheie, implementat folosind un nivel de indirectare astfel nct intrrile din index sunt de lungime fix i au valori unice.