Baze de date4

Baze de date Curs 4 1

Cuprins

1. Definire index

2. Tipuri de indecsi

3. Index primar

4.4. Index secundarIndex secundar

5.5. Index de grup (cluster)Index de grup (cluster)

6.6. Index multinivel (arbori B, arbori B+)Index multinivel (arbori B, arbori B+)


1. 1. Definire index

Acest capitol trateaza structurile de date aditionale, numite si indexindex, ce sint stocate pe disc si sunt utilizate pentru accesul la inregistrari.

Ideea structurii de acces indexate este similara cu cea utilizata uzual in textele din carti. O carte, listeaza la sfirsit termenii importanti aranjati in ordine alfabetica.

La fiecare termen din aceasta lista este furnizata o succesiune a numarului paginilor la care termenul apare si este explicat.

Utilizind indexul se gaseste lista adreselor (in cazul de fata numarul paginii) de localizare a termenului in carte.

In concluzie, scopul indexarii este de a indica adresa exacta a datei de interes.

• Un index este construit uzual dupa un singur cimp al fisierului numit si cimp indexcimp index, ce asociaza la fiecare valoare a cimpului index o lista de pointeri catre toate blocurile ce contin inregistrarea cu valoarea specificata. Avantajul indexarii rezida in faptul ca valorile in index sint ordonate, asa ca aici pot fi aplicate metode de cautare binara. Cum structura index este mult mai redusa decit tabela de date, eficienta cautarii binare in acesta structura creste.


2. Tipuri de indecsi

• Index primar.Index primar. Un index primar este realizat pe baza unui atribut Un index primar este realizat pe baza unui atribut cheie la o tabela ordonata dupa campul cheie.cheie la o tabela ordonata dupa campul cheie.

• Indexul secundarIndexul secundar poate fi construit dupa un camp cheie al tabelei de poate fi construit dupa un camp cheie al tabelei de date, insa tabela nu este ordonata dupa acest campdate, insa tabela nu este ordonata dupa acest camp

• Index de grup.Index de grup. Daca cimpul de indecsare nu este un cimp cheie, Daca cimpul de indecsare nu este un cimp cheie, putand avea pentru mai multe inregistrari aceeasi valoare structura putand avea pentru mai multe inregistrari aceeasi valoare structura aditionala de acces poarta denumirea de index de grup (clustering aditionala de acces poarta denumirea de index de grup (clustering index). La o tabela de date se pot construii oricate structuri de index index). La o tabela de date se pot construii oricate structuri de index de grup functie de atributele utilizate pentru constructia sa.de grup functie de atributele utilizate pentru constructia sa.

• Index multinivelIndex multinivel atunci cand indexul se trateaza ca o tabela la care atunci cand indexul se trateaza ca o tabela la care se construieste index in continuare. Exista mai multe metode de se construieste index in continuare. Exista mai multe metode de implementare prin arbori B sau arbori B+.implementare prin arbori B sau arbori B+.

ObsObs. Trebuie inteleasa diferenta majora intre indexare si sortare. . Trebuie inteleasa diferenta majora intre indexare si sortare. Indexarea este o metoda de acces logic pe cand sortarea se refera Indexarea este o metoda de acces logic pe cand sortarea se refera la reorganizarea tabelei pentru a forma o alta ordine fizica.la reorganizarea tabelei pentru a forma o alta ordine fizica.


3. 3. Index primar

Un index primarindex primar este un fisier ordonat cu inregistrari de lungime fixa avind doua cimpuri. Primul cimp al indexului este de acelasi tip cu un cimp cheie ordonat al tabelei de date, al doilea cimp este un pointer catre un bloc de date (o adresa a blocului). Cimpul cheie de ordonare se mai numeste si cheia primaracheia primara a tabelei de date. Asociatia celor doua cimpuri formeaza intrarea indexintrarea index sau inregistrarea index, pentru fiecare bloc al tabelei de date. Cum tabela de date este ordonat dupa valorile cimpului index in fisierul index valoarea primului cimp este data de valoarea cimpului index de la prima inregistrare a blocului. Al doilea cimp, cel ce semnifica un pointer este de tip intreg si indica adresa blocului. Se poate descrie structura fisierului index ca fiind formata din perechi de forma < K(i) , P(i) >, pentru i luind valori de la 1 la numarul blocurilor in care este stocata tabela de date.

Numarul total al intrarilor index in fisierul index este egal cu numarul blocurilor disc folosite pentru stocarea tabelei de date. Valoarea cimpului index al primei inregistrari dintr‑un bloc al tabelei de date se mai numeste si valoare de ancorarevaloare de ancorare si inregistrarea, inregistrare inregistrare de ancorarede ancorare a blocului.


• Un index primar este un exemplu de index nondens datorita faptului ca are cite o intrare pentru fiecare bloc, fata de indexul dens ce asociaza cite o intrare pentru fiecare inregistrare a tabelei de date.

Indexul primar necesita mai putine blocuri pentru stocare datorita faptului ca;

• asociaza cite o singura inregistrare unui bloc de date;• o inregistrare index ocupa mult mai putini octeti decit o inregistrare a

tabelei de date. Ca efect cautarea intr‑un fisier index este mult mai rapida decit intr-o tabela de date, putind fi utilizate si metode de cautare binara.

• O inregistrare pentru care valoarea cheii primare este k se gaseste in blocul i daca este indeplinita conditia k(i)<=k<k(i+1). Adresa blocului i este P(i) si inregistrarile in acest bloc sint fizic ordonate dupa cimpul cheie.


Exemplu de index primar

TABELA DE DATENume Ssn ………………. Dep_nr

Fisier index Abrudan Cheie Pointer ancorare bloc

Acosta Abrudan Adam Adam

Vovc Vovc


• Pentru a evalua avantajele indexarii primare se considera o tabela de date ordonat dupa un cimp cheie, ce contine r=30000 inregistrari. Tabela este stocata pe disc in blocuri avind dimensiunea B=1024 octeti. Toate inregistrarile sint de lungime fixa si ocupa R=100 octeti fiecare. Se calculeaza mai intii numarul de blocuri necesare pentru memorarea tabelei de date. Astfel numarul de inregistrari pe bloc se calculeaza ca fiind bfr=[B/R]=[1024/100], obtinind bfr=10. Pentru toata tabela se va obtine numarul de blocuri b=[r/bfr]=[30000/10]=3000. O cautare binara in tabela de date necesita aproximativ [log2b] +1 operatii de citire bloc, deci [log23000] + 1=13 blocuri.

• Se considera ca lungimea cimpului cheie de ordonare a fisierului este de 9 octeti si ca un pointer catre un bloc poate fi stocat pe 6 octeti, deci dimensiunea unei intrari index este Ri=V+P=9+6=15 octeti. Numarul intrarilor index dintr‑un bloc devine bfri=[B/Ri]=[1024/15]=68, numarul de inregistrari index este dat de numarul blocurilor tabelei de date, in cazul de fata ri=3000. Ca urmare pentru stocarea indexului sint necesare un numar de blocuri bi=[ri/bfri]+1=[3000/68]+1=46. Cautarea binara in fisierul index necesita aproximativ [log2bi] operatii de citire bloc, adica [log245]+1=6. In total pentru a se gasi inregistrarea va fi necesara citirea a 7 blocuri, 6 apartinind fisierului index si unul apartinind tabelei de date, cel in care se afla sau nu inregistrarea cautata.


4. Index secundar

• Metoda de indexare secundara se aplica la tabele neordonate, Metoda de indexare secundara se aplica la tabele neordonate, campul de indexare fiind camp cheie.campul de indexare fiind camp cheie.

• Se considera mai intii un index secundar dupa un cimp cheie din Se considera mai intii un index secundar dupa un cimp cheie din tabela de date. Un astfel de cimp este numit si cheie secundara a tabela de date. Un astfel de cimp este numit si cheie secundara a tabelei. Acesta are o intrare index pentru fiecare inregistrare din tabelei. Acesta are o intrare index pentru fiecare inregistrare din tabela de date. Se obtine astfel un index dens, avind cite o intrare tabela de date. Se obtine astfel un index dens, avind cite o intrare pentru fiecare inregistrare din tabela primara. pentru fiecare inregistrare din tabela primara.

• Pornind de la faptul ca indexul secundar are structura <K(i),P(i)> si Pornind de la faptul ca indexul secundar are structura <K(i),P(i)> si ca inregistrarile index sint ordonate prin valoarea K(i) se pot folosi ca inregistrarile index sint ordonate prin valoarea K(i) se pot folosi metodele de cautare binara. Din cauza ca inregistrarile de date in metodele de cautare binara. Din cauza ca inregistrarile de date in tabele de date nu sint ordonate dupa cimpul cheie nu poate fi tabele de date nu sint ordonate dupa cimpul cheie nu poate fi utilizata tehnica de ancorare bloc, iar intrarile index sint create utilizata tehnica de ancorare bloc, iar intrarile index sint create pentru fiecare inregistrare din tavela de date, nu pentru bloc ca la pentru fiecare inregistrare din tavela de date, nu pentru bloc ca la indexul primar. indexul primar.

• Indexul secundar ocupa mai mult spatiu decit indexul primar datorita Indexul secundar ocupa mai mult spatiu decit indexul primar datorita numarului mult mai mare de intrari. Oricum timpul de cautare in numarului mult mai mare de intrari. Oricum timpul de cautare in tabele noordonate fara index este mult marit pentru ca nu se poate tabele noordonate fara index este mult marit pentru ca nu se poate utiliza decit metoda cautarii liniare, ceea ce presupune citirea pe utiliza decit metoda cautarii liniare, ceea ce presupune citirea pe rind a blocurilor pina la gasirea inregistrarii de interes, numarul rind a blocurilor pina la gasirea inregistrarii de interes, numarul mediu al blocurilor citite fiind aproximativ b/2. mediu al blocurilor citite fiind aproximativ b/2.


Pentru analiza performantelor se considera ca si la indexarea primara Pentru analiza performantelor se considera ca si la indexarea primara o tabela cu r=30000 inregistrari fiecare cu marimea R=100 octeti, cu o tabela cu r=30000 inregistrari fiecare cu marimea R=100 octeti, cu marimea unui bloc de 1024 octeti. Tabela necesita pentru stocare marimea unui bloc de 1024 octeti. Tabela necesita pentru stocare b=3000 blocuri, iar la o cautare liniara se citesc b/2 deci 1500 de b=3000 blocuri, iar la o cautare liniara se citesc b/2 deci 1500 de blocuri. Se considera un index secundar pentru un cimp neordonat blocuri. Se considera un index secundar pentru un cimp neordonat al fisierului, cu valoarea reprezentata pe V=9 octeti si cu P=6 octeti. al fisierului, cu valoarea reprezentata pe V=9 octeti si cu P=6 octeti. Dimensiunea unei inregistrari din fisierul index este Dimensiunea unei inregistrari din fisierul index este Ri=V+P=9+6=15 octeti. Numarul de inregistrari index pe bloc va fi Ri=V+P=9+6=15 octeti. Numarul de inregistrari index pe bloc va fi bfri=[1024/15]=68. Cum numarul inregistrarilor index este egal cu bfri=[1024/15]=68. Cum numarul inregistrarilor index este egal cu numarul inregistrarilor tabelei de date, in cazul de fata 30000 se numarul inregistrarilor tabelei de date, in cazul de fata 30000 se obtine bi=[ri/bfri]+1=[30000/68]+1=443. Fiindca fisierul index obtine bi=[ri/bfri]+1=[30000/68]+1=443. Fiindca fisierul index secundar este ordonat, cautarea unei inregistrari se poate face prin secundar este ordonat, cautarea unei inregistrari se poate face prin matode de cautare binara necesitind citirea a [logmatode de cautare binara necesitind citirea a [log22bi]bi]+1=[log+1=[log22442]+1=9 blocuri. La cele 9 blocuri mai este necesar sa se 442]+1=9 blocuri. La cele 9 blocuri mai este necesar sa se adauge un bloc ce reprezinta blocul de date in interiorul caruia se adauge un bloc ce reprezinta blocul de date in interiorul caruia se procedeaza la cautare liniara.procedeaza la cautare liniara.


Exemplu index secundar

TABELA DE DATEDep_nr Nume Ssn ……………….

Fisier index 5 Cheie Pointer 2 ancorare bloc 1

102 1 2 31 3 1042 4 3 5 312

1042 513 4


5. Index de grup (cluster)5. Index de grup (cluster)

Astfel de indexi sint folositi cind inregistrarile tabelei de date sint ordonate fizic dupa un cimp noncheie, sau neordonate dupa un camp noncheie.

Tabela ordonata



2 1 2 2 3 3 4 3 5 4

102 102


Tabela nordonata



7 1 3 3 7 21 21 23

1234 3


• Sint posibile mai multe optiuni de implementare a indexului secundar. Se dau mai jos citeva din aceste posibilitati.

1. Includerea mai multor intrari in fisierul index ce au aceeasi valoare pentru cimpul K(i), cite una pentru fiecare inregistrare a tabelei de date.

2. Includerea in fisierul index a unor inregistrari cu lungime variabila, cu un cimp al valorii K(i) si o lista a pointerilor <P(i,1),P(i,2),...,P(i,j)> ce indica toate blocurile ce contin inregistrari ce au valoarea cimpului K(i). Desigur ca la aceste optiuni algoritmii de cautare se modifica in mod corespunzator.

• Varianta cea mai des utilizata este de a folosi intrari index de lungime fixa, cu o singura intrare pentru fiecare valoare distincta a cimpului index. Pointerul P(i) indica un nou nivel de redirectare continind pointeri multiplii catre toate blocurile ce contin inregistrari cu valoarea K(i). Deci intrarea index are structura <K(i),P(i)>, iar blocurile inregistrarilor pointer au structura <P(i,1),P(i,2),...,P(i,j)>. Daca inregistrarile cu valoarea cimpului K(i) ocupa mai mult de un bloc se poate utiliza o lista de inlantuire blocuri.


6. Index multinivel (arbori B, arbori B+)Index multinivel (arbori B, arbori B+)

Metodele de indexare descrise pina in prezent opereaza cu un fisier index ordonat. Aupra fisierului index se aplica metode de cautare binara pentru localizarea inregistrarilor cu valoarea specificata in cimpul index. Cautarea binara cere aproximativ log2bi operatii de acces la blocuri pentru un index cu bi blocuri. Se observa ca la fiecare pas algoritmul reduce numarul inregistrarilor pe care le exploreaza la jumatate (prin impartirea la 2). Esenta metodei de indexare multinivel este de a reduce de bfri ori, la fiecare pas, numarul inregistrarilor din index ce sint explorate, pornind de la faptul ca de regula bfri este mai mare decit 2. Valoarea bfri este numita si ""fan‑outfan‑out"" al indexului multinivel si va fi notata cu fo. Astfel intr‑un index multinivel numarul operatiilor de acces la blocuri este de aproximativ [logfobi], care este mult mai mica decit in cazul cautarii binare daca fo este mai mare decit 2.


Exemplu de index multinivel


Top index Index 1 Cheie Pointer nivel 1 21 ancorare bloc 22

1 7 1 3 21 4 3

7 4

2122

1032


Arbori B

Un arbore B de ordin p, construit dupa un cimp cheie al fisierului de date satisface urmatoarele restrictii:

1. Fiecare nod intern in arborele B are structura <P1,<K1,Pr1>,P2,<K2,Pr2>,...,<Kq‑1,Prq‑1>,Pq> cu q<=p, in care, Pi este un pointer la un nou nod arbore numit si pointer pointer

arborearbore, pointerii Pri fiind pointeri datapointeri data, pointeri catre blocuri in tabela de date ce contin inregistrarea cu cheia k.

2 In fiecare nod K1<K2<....<Kq‑1Valoarea inregistrarii cu cheia X in subarborele punctat de Pi este data

de conditiile Ki‑1<X<Ki pentru 1<i<q, X<Ki pentru i=1 si Ki‑1<X pentru i=q

4. Fiecare nod are cel mult p pointeri arbore 5. Fiecare nod exceptind radacina si nodurile frunza au cel putin [p/2]

pointeri arbore. Nodul radacina are cel putin doi pointeri. 6. Un nod cu q pointeri arbore, q<=p, contine q‑1 valori ale cimpului

cheie, deci q‑1 pointeri data 7. Toate nodurile frunza sint la acelasi nivel, au aceeasi structura

exceptind faptul ca toti pointeri arbore Pi sint nuli.


Structura nod intern

< P1 , K1 , Pr1, P2... , Ki-1 , Pri-1 , Pi, Ki , .. , Kq-1 , Prq-1, Pq >

Index X X X -------- ----------- ---------- X<K1 Ki-1<X<Ki Kq-1<X

Pointer arbore Pointer data


Exemplu de arbore B

* 5,o * 8,o * o pointer data * pointer arbore

pointer null

1,o 3,o 6,o 7,o 9,o 12,o


Arbori B+

1. Fiecare nod intern are structura <P1,K1, P2,K2,...,Pq‑1,Kq‑1, Pq>unde q<=p si fiecare Pi reprezinta un pointer arbore. 2. In fiecare nod este indeplinita conditia K1<K2<....<Kq‑1, q<=p 3. Pentru toate valorile cimpului de cautare X in subarborele punctat prin Pi

se indeplineste relatia Ki‑1<X=Ki pentru 1<i<q, X<=Ki pentru i=1 si Ki‑1<X pentru i=q 4. Fiecare nod intern are cel mult p pointeri arbore. 5. Fiecare nod intern exceptind radacina are cel putin [p/2] pointeri arbore.

Nodul radacina are cel putin doi pointeri arbore daca este un nod intern si q<=p pointeri data daca este nod frunza.

6. Un nod intern cu q pointeri, q<=p, are q‑1 valori ale cimpului de cautare.Pentru nodurile frunza sint indeplinite urmatoarele restrictii 1. Fiecare nod frunza este de forma<<K1,Pr1>,<K2,Pr2>,...,<Kq‑1,Pq‑1>,Pnext>unde q<=p, fiecare Pri este un pointer data si Pnext indica urmatorul nod frunza

al arborelui B+. 2. In fiecare nod frunza este indeplinita conditia K1<K2<,...,<Kq‑1, q<=p


Arbore B+

< P1 , K1 , P2 ... , Ki-1 , Pi , Ki , .. , Kq-1 , Pq , ... >

Index X X X -------- ----------- ---------- XK1 Ki-1<XKi Kq-1<X

< K1 , Pr1, K2... , Ki-1 , Pri-1 , Ki , .. , Kq-1 , Prq-1, Pnest >

Pointer data Pointer spre nod frunza


Operare arbore B+

Arbore initial 5 o 8 o inserare 1

* 5 * inserare 3 si 7

1 o 5 o 8 o

* 3 * 5 *

1 o 3 o 5 o 7 o 8 o

Baze de date4

Documents

Transcript of Baze de date4