Download - Indexes

Transcript
Page 1: Indexes

Structurile de indexare pentru fişiere

În cele ce urmează, se descriu structurile de acces, numite indecşi, care sunt folosite pentru accelerarea prelucrării înregistrărilor ca răspuns la anumite condiţii de căutare. Anumite tipuri de indecşi, denumiţi căi de acces secundare, nu afectează aşezarea fizică a înregistrărilor pe disc; mai degrabă asigură căi alternative de căutare bazată pe câmpuri de indexare pentru o localizare mai eficientă a înregistrărilor. Alte tipuri de indecşi pot fi construite pentru un fişier doar cu o organizare primară particulară.

Ideea din spatele unei structuri ordonate de acces bazată pe indexare este asemănătoare ideii de indecşi folosiţi în manuale. Un index al unui manual este o listă ce conţine termeni importanţi ordonaţi alfabetic şi se află la sfârşitul cărţii. Fiecare termen este însoţit de o listă de numere de pagini unde apare. Se poate căuta î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, căutând la paginile specificate. Alternativa, dacă nici o altă îndrumare nu e dată, este să se examineze încet prin tot manualul, cuvânt cu cuvânt, pentru a găsi termenul care ne interesează; acest lucru corespunde unei căutări liniare într-un fişier. Bineînţeles, cele mai multe cărţi au informaţii suplimentare, cum ar fi titlurile capitolelor sau secţiunilor, care ne ajută să găsim un termen fără a fi nevoiţi să căutăm în toată cartea. Oricum, indexul este singura indicaţie exactă referitoare la apariţia în carte a fiecărui termen.

O structură indexată de acces este de obicei definită pe un singur câmp al unui fişier, numit câmp de indexare. Indexul de obicei reţine fiecare valoare a câmpului de indexare alături de o listă de pointeri către toate blocurile discului care conţin înregistrări, având valoarea acelui câmp. Valorile din index sunt ordonate astfel încât să se poată face o căutare binară asupra indexului. Fişierul de index este mult mai mic decât fişierul de date, astfel căutarea binară prin index este rezonabil de eficientă.

Există câteva tipuri de indecşi ordonaţi.Un index primar este un index specificat în câmpul cheie de ordonare dintr-un fişier

ordonat de înregistrări. Un câmp cheie de ordonare este folosit la ordonarea fizică pe disc a fişierului de înregistrări, şi fiecare înregistrare are o valoare unică pentru acest câmp.

Dacă câmpul de ordonare nu este un câmp cheie - asta dacă mai multe înregistrări din fişier au aceeaşi valoare ca şi pentru câmpul cheie – se poate folosi un alt tip de index, numit index grupat. A se observa că un fişier poate avea cel mult un câmp fizic de ordonare, deci poate avea cel mult un index primar sau un index grupat, dar nu pe amândouă.

Al treilea tip de index, numit index secundar, poate fi specificat pentru orice câmp sau fişier neordonat. Un fişier poate avea câţiva indecşi secundari pe lângă metoda sa primară de acces. In următoarele trei subsecţiuni, se vor discuta aceste trei tipuri de indecşi.

Indecşi primari

Un index primar este un fişier ordonat ale cărui înregistrări sunt de lungime fixă cu două câmpuri. Primul câmp este de acelaşi tip de dată ca şi câmpul cheie de ordonare al fişierului de date, şi al doilea câmp este un pointer către un bloc pe disc - un bloc de adresa. Câmpul cheie de ordonare este denumit cheia primară a fişierului de date. Există o intrare index (sau înregistrare index) în fişierul de index pentru fiecare bloc din fişierul de date. Fiecare intrare index cuprinde valoarea câmpului cheii primare pentru prima înregistrare dintr-un bloc şi un pointer către acel bloc ca cele două câmpuri de valori. Se va face referire la cele două câmpuri de valori ale intrării index i ca <K(i), P(i)>.

Page 2: Indexes

Pentru a crea un index primar pentru fişierul ordonat arătat în figura 1, se foloseşte câmpul NUME ca şi cheie primară, deoarece acesta este câmpul cheie de ordonare al fişierului (presupunând că fiecare valoare pentru NUME este unică). Fiecare înregistrare nouă în index are o valoare pentru NUME şi un pointer. Primele trei intrări index sunt după cum urmează:<K(1)=(Alamita,Bogdan), P(1)=adresa blocului 1><K(2)=(Barbu, Dragos), P(2)=adresa blocului 2><K(3)=(Gavrila, Florin), P(3)=adresa blocului 3>

Figura 1 ilustrează acest index primar. Numărul total de intrări în index este acelaşi ca şi numărul blocurilor de disc din fişierul ordonat de date. Prima înregistrare din fiecare bloc al fişierului 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 îmbunătăţeşte puţin eficienţa algoritmului de căutare.

Un index primar este un exemplu de index non-dens: conţine o intrare pentru fiecare bloc de disc al fişierului de date mai degrabă decât pentru fiecare înregistrare din fişierul de date. Un index dens, pe de altă parte, conţine o intrare pentru fiecare înregistrare din fişier.

Figura1: Un exemplu de index primar

Fişierul de index pentru un index primar are nevoie de mult mai puţine blocuri decât pentru fişierul de date, din două motive. In primul rând, sunt mai puţine intrări index decât sunt înregistrări în fişierul de date, deoarece o intrare apare pentru fiecare bloc întreg din fişierul de date şi nu pentru fiecare înregistrare. In al doilea rând, fiecare intrare index este în mod caracteristic mai mică în dimensiune decât o înregistrare de date, deoarece are doar două câmpuri; în consecinţă, mai multe intrări index decât înregistrări de date pot încăpea într-un

Page 3: Indexes

bloc. Deci o căutare binară în fişierul de index necesită mai puţine accese la un bloc decât o căutare binară în fişierul de date.

O înregistrare a cărei cheie primară este K se găseşte în blocul a cărui adresă este P(i), unde K(i)K<K(i+1). Al i-lea bloc din fişierul de date conţine toate înregistrările de acest tip datorită ordonării fizice a fişierului de înregistrări după câmpul cheii primare. Pentru a găsi o înregistrare, fiind dată valoarea K a câmpului cheii primare, se face o căutare binară în fişierul de index pentru a găsi intrarea index i potrivită, şi apoi se găseşte blocul fişierului de date a cărui adresă este P(i). A se observa că formula de mai sus nu este corectă dacă fişierul de date ar fi ordonat după un câmp non-cheie, care permite ca multiple înregistrări să aibă aceeaşi valoare a câmpului de ordonare. In acest caz, aceeaşi valoare de index ca şi cea din blocul ancoră poate fi repetată în ultimele înregistrări ale blocului anterior. Exemplul 1 ilustrează economisirea acceselor la blocuri, obţinută când un index este folosit pentru căutarea unei înregistrări.

EXEMPLU 1: Se presupune că avem un fişier ordonat cu=30.000 înregistrări stocate pe un disc cu dimensiunea unui bloc B=1024 octeţi. Înregistrările din fişier au dimensiune fixă şi sunt nedistanţate, cu lungimea unei înregistrări R=100 octeţi. Factorul de blocare pentru fişier este bfr = (B/R) = (1024/100) = 10 înregistrări per bloc. Numărul blocurilor necesare pentru un fişier este b = (r/bfr) = (30.000/10) = 3000 blocuri. O căutare binară în fişierul de date ar avea nevoie de aproximativ (log2b) = (log23000) = 12 accese la blocuri.

Acum să presupunem că câmpul cheie de ordonare al fişierului este V = 9 octeţi lungime, un pointer la bloc este P = 6 octeţi lungime, şi am construit un index primar pentru fişier. Dimensiunea fiecărei intrări index este Ri = (9+6) = 15 octeţi, astfel factorul de blocare pentru index este bfri = (B/Ri) = (1024/15) = 68 intrări per bloc. Numărul total de intrări index ri este egal cu numărul blocurilor din fişierul de date, care este 3000. Numărul de blocuri necesare pentru index este deci bi = (ri/bfri) = (3000/68) = 45 de blocuri. Pentru executarea unei căutări binare în fişierul de index ar fi necesare (log2bi) = (log245) = 6 accese la blocuri. Pentru aa căuta o înregistrare folosind indexul, este necesar în plus un acces la bloc către fişierul de date pentru un total de 6+1 = 7 accese la bloc - o îmbunătăţire faţă de căutarea binară într-un fişier de date, care necesita 12 accese la bloc.

O problemă majoră a indexului primar - ca a oricărui fişier ordonat - este inserarea şi ştergerea unor înregistrări. Cu un index primar, problema este compusă, deoarece, dacă se încearcă inserarea unei înregistrări în poziţia sa corectă în cadrul fişierului de date, ar trebui mutate înregistrări pentru a crea spaţiu pentru noua înregistrare, dar ar trebui şi să fie schimbate unele intrări index, din moment ce mutarea înregistrărilor va schimba înregistrările ancoră ale unor blocuri. Poate fi folosit un fişier de depăşire neordonat pentru a reduce această problemă.

O altă variantă este să se folosească o listă înlănţuită de înregistrări de depăşiri pentru fiecare bloc din fişierul de date. Aceasta este asemănătoare cu metoda tratării înregistrărilor de depăşire descrise cu tabele de dispersie. Înregistrările din fiecare bloc şi lista sa înlănţuită pot fi sortate pentru îmbunătăţirea timpului de găsire.

Ştergerea înregistrării este tratată folosind marcatori de ştergere.

Page 4: Indexes

Indecşi grupaţi

Dacă înregistrările unui fişier sunt ordonate fizic după un câmp non-cheie care nu are o valoare distinctă pentru fiecare înregistrare, acel câmp este denumit câmpul de grupare.

Se poate crea un tip diferit de index, numit index grupat, pentru accelerarea găsirii înregistrărilor care au aceeaşi valoare pentru câmpul de grupare. Acesta diferă de indexul primar, care necesită ca câmpul de ordonare al fişierului de date să aibă o valoare distinctă pentru fiecare înregistrare.

Un index grupat este de asemenea un fişier ordonat cu două câmpuri; primul câmp este de acelaşi tip ca şi câmpul de grupare) al fişierului de date, şi câmpul al doilea este un pointer la bloc. Există o intrare în indexul grupat pentru fiecare valoare distinctă a câmpului de grupare, conţinând valoarea şi un pointer la primul bloc din fişierul de date care are o înregistrare cu acea valoare pentru câmpul său de grupare. Figura 2 arată un exemplu unui fişier de date cu un index grupat.

Se observă că inserarea şi ştergerea unei înregistrări încă ridică probleme, deoarece înregistrările de date sunt ordonate fizic. Pentru uşurarea problemei inserării, se obişnuieşte să se reţină un întreg bloc pentru fiecare valoare a câmpului de grupare; toate înregistrările cu acea valoare sunt puse în acel bloc. Dacă sunt necesare mai multe blocuri pentru stocarea înregistrărilor cu o valoare anume, blocuri suplimentare sunt alocate şi unite. Acest lucru face inserarea şi ştergerea relativ uşoară. Figura 3 arată această schemă.

Figura 2: Un exemplu de index grupat

Page 5: Indexes

Figura 3: Indexul grupat cu blocuri separate pentru fiecare grup de înregistrări care au aceeaşi valoare pentru câmpul de grupare

Page 6: Indexes

Indecşi secundari

Un index secundar este de asemenea un fişier ordonat cu două câmpuri. Primul câmp este de acelaşi tip de data ca unul dintre câmpurile de ne-ordonare (nonordering field) ale fişierului de date şi este denumit câmpul de indexare al fişierului. Al doilea câmp este fie un pointer la bloc, fie un pointer la înregistrare. Pot fi mulţi indecşi secundari (şi deci, câmpuri de indexare) pentru acelaşi fişier.

Prima dată considerăm o structură de acces de tip index secundar bazat pe un câmp cheie - un câmp având o valoare distinctă pentru fiecare înregistrare din fişierul de date. Un asemenea câmp este câteodată denumit cheie secundară. În acest caz există o singură intrare index pentru fiecare înregistrare din fişierul de date, care conţine valoarea cheii secundare pentru respectiva înregistrare şi un pointer fie către blocul în care este stocată înregistrarea respectivă, fie către înregistrarea însăşi. Un index secundar bazat pe un câmp cheie este un index dens: conţine o singură intrare pentru fiecare înregistrare din fişierul de date.

Din nou facem referire la cele două câmpuri de intrare index i ca fiind <K(i), P(i)>. Intrările sunt ordonate după valoarea lui K(i), astfel se poate efectua o căutare binară asupra indexului. Deoarece înregistrările din fişierul de date nu sunt ordonate fizic după valorile câmpului cheii secundare, nu se pot folosi blocurile ancoră. Din acest motiv este creată mai degrabă o intrare index pentru fiecare înregistrare din fişierul de date, şi nu pentru fiecare bloc ca în cazul indexului primar. Figura 4 ilustrează un index secundar în care pointerii P(i) din intrările index sunt pointeri la bloc, nu pointeri la înregistrări. Odată ce blocul potrivit este transferat în memoria principală, poate fi realizată o căutare pentru înregistrarea dorită din blocul respectiv.

Un index secundar necesită de obicei mai mult spaţiu de stocare şi un timp mai lung de căutare decât indexul primar, datorită numărului mare de intrări. Oricum, se realizează îmbunătăţirea timpului de căutare a unei înregistrări arbitrar alese, din moment ce am fi avut de făcut o căutare lineară în fişierul de date dacă indexul secundar nu ar fi existat.

De asemenea putem crea un index secundar bazat pe un câmp non-cheie dintr-un fişier. In acest caz, numeroase înregistrări din fişierul de date pot avea aceeaşi valoare pentru câmpul de indexare. Există câteva opţiuni pentru implementarea unui astfel de index:

Opţiunea 1 este să se includă câteva intrări index cu aceeaşi valoare K(i) - una pentru fiecare înregistrare. Acesta ar fi un index dens.

Opţiunea 2 este să avem înregistrări cu dimensiune variabilă pentru intrările index, cu un câmp repetitiv pentru pointer. Ţinem o listă de pointeri <P(i,1), ..., P(i,k)> în intrarea index pentru K(i) - un pointer pentru fiecare bloc care conţine o înregistrare pentru care valoarea câmpului de indexare este egală cu K(i). În oricare dintre opţiunile 1 sau 2, algoritmul de căutare binară în index trebuie să fie modificat convenabil.

Opţiunea 3, care este cea mai folosită, este să fie menţinută o dimensiune fixă pentru intrările index şi să existe o singură intrare pentru fiecare valoare a câmpului de indexare, 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 <K(i), P(i)> indică către un bloc de pointeri la înregistrări; fiecare pointer la înregistrare din acel bloc indică către una dintre înregistrările fişierului de date cu valoarea K(i) pentru câmpul de indexare. Dacă o anume valoare K(i) apare în prea multe înregistrări, astfel încât pointerii la respectiva înregistrare nu pot încăpea într-un singur bloc de disc, este folosită o listă înlănţuită de blocuri. Această tehnică este ilustrată în figura 5. Regăsirea prin intermediul indexului necesită un bloc adiţional de acces datorită nivelului extra, dar algoritmii de căutare în index şi (mult mai important) de inserare

Page 7: Indexes

de noi înregistrări în fişierul de date sunt uşuraţi. Mai mult, căutările complexe de selecţie pot fi tratate prin referinţă la pointeri, fără a fi nevoiţi să se găsească fişiere cu înregistrări multe şi inutile.

Se observă că un index secundar furnizează o ordonare logică a înregistrărilor după câmpul de indexare. Dacă accesăm înregistrările în ordinea intrărilor în indexul secundar, le obţinem în ordinea câmpului de indexare.

Figura 4: Index secundar non-dens pe un câmp cheie

Page 8: Indexes

Figura 5: Un index secundar (cu pointeri de înregistrare) pe un câmp care nu este cheie, implementat folosind un nivel de indirectare astfel încât intrările din index sunt de lungime

fixă şi au valori unice.