7/31/2019 12 - Fisiere indexate

1/19

Algoritmi de prelucrare

? ? ??

7/31/2019 12 - Fisiere indexate

2/19

Fiier indexat = o pereche de fiiere fiier index (secvenial, sortat) fiier de date (secvenial)

Fiiere organizate indexat

IS Nr.rel. Cheie

Cmpuri de date

Fiier index

Fiier de date

0 1 2 3 4 5 6 7 8 9 10 11 12 13

3 - aaaa 6 - aaab 0 - aaac 12 - aaba 8 - abaa 13 - abba 4 - baaa 7 - baca

Articole terse

(logic)

7/31/2019 12 - Fisiere indexate

3/19

Accesul la articole: prin intermediul fiierului index Tipuri de acces:

Secvenial urmtorul articol

Direct dup cheie

Fiiere organizate indexat

Fiier index

Fiier de date

0 1 2 3 4 5 6 7 8 9 10 11 12 13

3 - aaaa 6 - aaab 0 - aaac 12 - aaba 8 - abaa 13 - abba 4 - baaa 7 - baca

7/31/2019 12 - Fisiere indexate

4/19

Operaii de prelucrare Creare n acces secvenial

n ordinea cheilor, scriere n acces secvenial cheie invalid

Creare n acces direct scriere n acces direct

cheie invalid

Consultare n acces secvenial n ordinea cheilor

citire n acces secvenial, detectare sfrit fiier

Consultare n acces direct cheie invalid

Fiiere organizate indexat

7/31/2019 12 - Fisiere indexate

5/19

Operaii de prelucrare Consultare n acces mixt

domeniu de chei /sfrit fiier

Adugare (acces direct) scriere n acces direct

cheie invalid

Modificare citire (acces secvenial sau direct), modificare rescriere

tergere n acces secvenial/ direct

Fiiere organizate indexat

7/31/2019 12 - Fisiere indexate

6/19

Operaii de baz (implementate prin subprograme) Deschidere ca fiier nou (creare) Deschidere ca fiier existent

nchidere fiier Cutare cheie Citire articol n acces secvenial Citire articol n acces direct

Scriere articol n acces secvenial Scriere articol n acces direct tergere articol n acces secvenial tergere articol n acces direct Sortare (i curare) tabel index

Fiiere organizate indexat

7/31/2019 12 - Fisiere indexate

7/19

Fiiere organizate indexat

Fiier nou (nume)

nume_i=nume+.idx

nume_d=nume+.dat

Stop

deschide nume_i, wb

deschide nume_d, wb

Deschide (nume)

nume_i=nume+.idx

nume_d=nume+.dat

Stop

deschide nume_i, rb+

deschide nume_d, rb+

Creare fiier nou Deschiderefiier existent

nchidere fiier

nchide

Stop

nchide nume_i

nchide nume_d

7/31/2019 12 - Fisiere indexate

8/19

Fiiere organizate indexat

Cutare cheieCauta_cheie(cheie, gsit)

gsit = 0

Calcul nr. articole din

fiierul index n

ls = 0, ld = n - 1

ls cheie

ld = m - 1ls = m + 1

DaNu

7/31/2019 12 - Fisiere indexate

9/19

Fiiere organizate indexat

citire_sec(a, r)

feof( ind ) DaNu

Stop

Articol din

index (ind) ai

Poziionare n fi.

de date (f) la

poziia indicat de

art. citit din fi.

index (ind) ai.poz

Articol din

fi. date (f) a

r = 1

r = 0

citire_cheie(a, cheie, r)

Succes? DaNu

Stop

Poziionare n fi. de date (f)la poziia indicat de art. citit

din fi. index (ind) ai.poz

Articol dinindex (ind) ai

r = 1

r = 0

Cutare cheienindex

Articol din fi.de date (f) a

Citire naccessecvenial

Citire naccesdirect

7/31/2019 12 - Fisiere indexate

10/19

Scriere articol n acces secvenial Articol a, cheia bacb

Fiiere organizate indexat

Fiier index

Fiier de date

0 1 2 3 4 5 6 7 8 9 10 11 12 13

3 - aaaa 6 - aaab 0 - aaac 12 - aaba 8 - abaa 13 - abba 4 - baaa 7 - baca

14

14 - bacb

baca < bacb

7/31/2019 12 - Fisiere indexate

11/19

Scrie_sec(a, r)

Calcul nr. articole dinfiierul index n

n > 0

Da

Nu

Stop

Poziionare nindex la poziia n-1

Articol dinindex ai

ai.cheie >= a.cheieDaNu

r = 0

ai.is = 1ai.cheie = a.cheie

ai.poz = nd

Calcul nr. art. dinfiierul de date nd

r = 1

Articol ain indexArticol an fi. de date

ai.is = 1ai.cheie = a.cheie

ai.poz = nd

Calcul nr. art. dinfiierul de date nd

r = 1

Articol ain indexArticol an fi. de date

Fiiere organizate indexat

Scriere naccessecvenial

7/31/2019 12 - Fisiere indexate

12/19

Scriere articol n acces direct

Articol a, cheia abab

Fiiere organizate indexat

Fiier index

Fiier de date

0 1 2 3 4 5 6 7 8 9 10 11 12 13

3 - aaaa 6 - aaab 0 - aaac 12 - aaba 8 - abaa 13 - abba 4 - baaa 7 - baca

14

14 - abab

Fiier index

Fiier de date

0 1 2 3 4 5 6 7 8 9 10 11 12 13

3 - aaaa 6 - aaab 0 - aaac 12 - aaba 8 - abaa 13 - abba 4 - baaa 7 - baca14 - abab

14

7/31/2019 12 - Fisiere indexate

13/19

Fiiere organizate indexat

Scrie_cheie(a, r)

Succes? DaNu

Stop

r = 0

ai.is = 1ai.cheie = a.cheie

ai.poz = nd

Calcul nr. art. din

fiierul de date nd

r = 1

Articol ain indexArticol an fi. de date

Cutare a.cheienindex

Poziionare n

index la sfrit

Sortare index

Scriere nacces direct

7/31/2019 12 - Fisiere indexate

14/19

tergere articol n acces secvenial

Fiiere organizate indexat

Fiier index

Fiier de date

0 1 2 3 4 5 6 7 8 9 10 11 12 13

3 - aaaa 6 - aaab 0 - aaac 12 - aaba 8 - abaa 13 - abba 4 - baaa 7 - baca

Fiier index

Fiier de date

0 1 2 3 4 5 6 7 8 9 10 11 12 13

3 - aaaa 6 - aaab 0 - aaac 12 - aaba 13 - abba 4 - baaa 7 - baca

is = 0

8

7/31/2019 12 - Fisiere indexate

15/19

tergere naccessecvenial

terge_sec(r)

feof( ind ) DaNu

Stop

r = 0

ai.is = 0

r = 1

Articol ai n index

Calcul poziie

curent n indexpos

Sortare index

Articol aidin index

Poziionare n

index la poziiapos

Fiiere organizate indexat

7/31/2019 12 - Fisiere indexate

16/19

tergere nacces direct

Fiiere organizate indexat

terge_cheie(cheie,r)

Succes? DaNu

Stop

r = 0

Cutare cheien

index

terge_sec(r)

7/31/2019 12 - Fisiere indexate

17/19

Fiiere organizate indexat

Sortare()

Stop

Creare fiier temporar (temp)

Copiere articole valide din

index (ind) n temp

nchidere index

Sortare tempdup cmpul cheie

terge index vechi (ind)

Redenumete temp cu numelefiierului index vechi

Sortare (i curare)fiier index

7/31/2019 12 - Fisiere indexate

18/19

Fiiere organizate indexat

Alte probleme de rezolvat (tem) Recuperare articole terse

Adugarea unui articol n fiierul index, apoi sortare

Compactare fiier de date (eliminare articole terse) Parcurgere index, cu copierea articolelor de date ntr-un fiier nou i

actualizarea articolelor din fiierul index cu noile poziii

mbuntirea sortrii fiierului index La tergere: e suficient copierea articolelor valide ntr-un fiier nou La adugare: e suficient mutarea unui grup de articole i inserarea articolului

nou pe poziia corect n cazul tergerii repetate n acces secvenial, sortarea e necesar doar o

dat, la sfrit

7/31/2019 12 - Fisiere indexate

19/19

Prelucrarea fiierelor indexateAlgoritmi de prelucrare

Ho,Ho,

Ho!