Mihaela Elena Breabn

FII 2014-2015

Indeci

BAZE DE DATE

Indeci Cuprins

Stocarea fizica a datelor

Indexare - motivatie

Indeci ordonai

Indeci secveniali

B+-Arbori

Hashing

Hashing static

Hashing dinamic

Acces multi-cheie i Indeci Bitmap

Definirea indecilor n standardul SQL

Indeci n Oracle

2

Stocarea fizica a datelor

3

Viteza de citire a unui bloc este data de:

Viteza de miscare a bratului (pozitionare pe cilindru)

Viteza de rotatie a platanelor

Timpul de transfer

Indexare - Motivaie

Bazele de date consum mult timp cutnd

SELECT * FROM Student

WHERE sID=40;

Cum putem regsi rezultatul n urmtoarele situaii:

sID sNume medie

20 Ioana 9.5

40 Andrei 8.66

10 Tudor 8.55

30 Maria 8.33

70 Alex 9.33

sID sNume medie

10 Tudor 8.55

20 Ioana 9.5

30 Maria 8.33

40 Andrei 8.66

70 Alex 9.33

a) Ordine aleatoare a datelor b) Date secveniale/ordonate

4

Indexare Motivaie

Cutarea binar

Complexitate: log2(N)

(log2(100 000)=17)

SELECT * FROM Student

WHERE sNume=Ioana;

Cum putem rezolva si aceasta interogare eficient?

Solutia: Construirea unei structuri auxiliare care s ajute la localizarea unei

nregistrri

Mecanismele de indexare sunt utilizate pentru a mri viteza de acces la datele

dorite

5

Concepte de baz

Un index este asociat cu o cheie de cutare = atribut sau set de atribute

dintr-un fiier/tabel/relaie utilizate pentru a cuta nregistrri n fiier

Fiier index const din nregistrri index de forma

Fiier de date secventa de blocuri de memorie ce contine inregistrarile

unui tabel

Sortare:

a indexului pe baza cheii de cutare

a fiierului/tabelei/relaiei stocate -> cheie de sortare = atribut care da

ordonarea fisierului de date

Un fiier de date poate avea asociai mai muli indeci

Fiierele index sunt de obicei de dimensiuni mult mai mici dect fiierul

original cu date

valoare cheie de cutare pointer

6

Metrici de evaluare a indecilor

Timpul de acces

Timpul de inserare

Timpul de tergere

Spaiul necesar

Tipurile de acces suportate eficient influeneaz alegerea indexului

nregistrri cu o valoare specificat a atributului

nregistrri cu valoarea atributului inclus ntr-un interval specificat

7

Tipuri de indeci

Indeci ordonai: valorile cheii de cutare sunt stocate ntr-o

anumit ordine

Indeci hash: valorile cheii de cutare sunt distribuite uniform

n bucket-uri cu ajutorul unei funcii hash

Bucket: o unitate de stocare coninnd una sau mai multe nregistrri

Indeci bitmap: asociai cheilor de cutare de tip atribute

discrete, codifica distribuia valorilor sub form de matrice

binar

8

Indecsi ordonati:

fisiere secventiale

9

Indeci secveniali (fisiere secventiale)

Intrrile index sunt sortate dup cheia de cutare

Ex: catalogul cu autori ntr-o bibliotec

Index primar: indexul a crui cheie de cutare definete i ordonarea

secvenial a fiierului/tabelei/relaiei

denumit i index de grupare (clustering/clustered index)

cheia de cutare a unui index primar este de obicei cheia primar dar nu

e obligatoriu

o tabel poate avea cel mult un index primar

Index secundar (nonclustering/nonclustered): index a crui cheie de cutare

specific o ordonare diferit de ordonarea secvenial a fiierului cu date

Fiier index-secvenial: combinaia fiier ordonat secvenial cu un index

primar

10

Fiiere index dense

Index dens: exist nregistrri index pentru fiecare valoare a cheii de

cutare n fiier/tabel/relaie

Dac indexul e primar va pstra cte un singur pointer-doar la prima

intrare cu valoarea respectiv

Dac indexul e secundar vor fi necesari mai muli pointeri la o singur

valoare a cheii de cutare

11

Index dens primar: cheia de cautare coincide cu cheia de

sortare a fisierului de date

Fiiere index rare

Index rar: conine intrri doar pentru unele valori a cheii de cutare

Aplicabil doar cnd nregistrrile sunt ordonate secvenial dup cheia de cutare

Balansul timp-spaiu

De obicei o intrare in index corespunde unui bloc din fisierul de date

Pentru a localiza o nregistrare cu valoarea k a cheii de cutare:

Se determin nregistrarea index cu cea mai mare valoare a cheii de cutare

Indeci multi-nivel

Index multi-nivel: index asociat unui alt index

Dac indexul primar nu ncape n memorie accesul devine costisitor

Soluia: indexul primar pstrat pe disc este tratat ca un fiier secvenial i

se construiete un index rar pentru el

Indexul extern un index rar al indexului primar

Index intern fiierul index primar

Dac i indexul extern este prea mare pentru a ncpea n memorie, se

creeaz un index pe un nou nivel, etc

Indecii de pe toate nivelele trebuiesc actualizai la inserare i tergere n

fiierul cu date

13

Indeci multi-nivel

14

Indeci secundari

n relaia Studenti sortat dup nume, care sunt studentii ce locuiesc in Cluj?

Soluia: index secundar (dens!)

Pentru a implementa relaia de tip unu-la-multi dintre index i datele

destinaie se utilizeaz referine la bucket-uri de pointeri

15

Actualizarea indecilor secveniali tergere

Stergerea inregistrarii din fisierul cu date atrage modificari asupra indexului

Dac nregistrarea tears este singura care conine o valoare particular a

cheii de cutare, aceasta este tears i din index

tergerea n

Indeci deni: similar tergerii din fiierul cu date

Indeci rari:

dac exist o intrare a cheii de cutare n index aceasta este nlocuit cu urmtoarea

valoare a cheii de cutare din fiier (n ordinea cheii de cutare)

dac urmtoarea valoare a cheii de cutare deja are o intrare n index, este efectuat

tergerea.

16

Actualizarea indecilor secveniali Inserare

Este necesar localizarea valorii cheii de cutare ce apare n tuplul inserat

Indeci deni: dac valoarea nu apare n index se va insera

Indeci rari: dac indexul pstreaz o intrare pentru fiecare bloc al fiierului

nu sunt necesare modificri dect dac un nou bloc este creat (prima

valoare a cheii de cutare ce apare n noul bloc este inserat n index)

Inserarea in fisierul cu date ordonat si in indexul secvential poate necesita

crearea unor blocuri de exces -> degenerarea structurii secventiale

Inserarea (i tergerea) pentru indeci multi-nivel sunt extensii simple a

algoritmilor uni-nivel prezentai

17

Indecsi ordonati:

B+-arbori

18

Fiiere index de tip B+-arbori Motivaie

Organizarea secvenial a indecilor se degradeaz pe msur ce

dimensiunea crete

Reconstruirea indecilor la intervale de timp e necesar ns costisitoare

Indexul B+-arbore

mrete viteza de localizare i elimin necesitatea constant de

reorganizare

utilizai extensiv

19

Structura B+-arbore

(1)

Un arbore balansat astfel nct fiecare drum de la rdcin la frunze are

aceeai lungime

Un nod tipic

Ki sunt valori a cheii de cutare

Pi sunt pointeri ctre

noduri copil/descendente (noduri care nu sunt frunze)

nregistrri sau bucket-uri de nregistrri (noduri frunz)

Arborele este definit de o constant m care specific numrul maxim de

valori dintr-un nod (numarul maxim de pointeri /descendenti este m+1)

De obicei dimensiunea unui nod e cea a unui bloc

Valorile cheii de cutare ntr-un nod sunt ordonate

K1 < K2 < K3 < . . . < Km

20

Noduri care nu sunt frunze n B+-arbore

formeaz un index rar multi-nivel pentru nodurile frunz

Pentru un nod cu n pointeri:

Toate valorile cheii de cutare din subarborele spre care P1 indic sunt

mai mici dect K1

Pentru Pi, 2 i n 1, toate valorile cheii de cutare din subarborele

spre care indic sunt mai mari sau egale cu Ki1 i mai mici dect Ki

Toate valorile cheii de cutare din subarborele spre care indic Pn sunt

mai mari sau egale cu Kn1

21

Structura B+-arbore

(2)

Nodurile nu sunt complet ocupate pt. a evita reorganizari frecvente:

nodul radacina are cel putin doi si cel mult m + 1 pointeri/descendenti (corespunzator,

cel putin una si cel mult m valori, ordonate crescator)

fiecare nod de pe un nivel intermediar are cel putin (m+1)/2 si cel mult m + 1 pointeri/descendenti (corespunzator, cel putin m/2 si cel mult m valori ordonate crescator)

fiecare nod frunza are cel putin m/2 si cel mult m valori; toti pointerii fac trimitere catre fisierul de date, cu exceptia ultimului pointer care face trimitere catre urmatorul nod

frunza (cu valori mai mari).

22

B+-arbore

Exemplu

1 bloc memorie = 1024 octeti

Cheia de cautare = sir de max. 20 caractere (1 caracter=1octet)

1pointer = 8 octeti

Numarul maxim de intrari in nod?

Cea mai mare valoare m cu proprietatea 20m + 8(m + 1)

B+-arbori

Observaii

Fiindc conexiunile dintre noduri se realizeaz prin pointeri, blocuri

apropiate logic nu trebuie s fie apropiate i fizic

Nivelele diferite de nivelul frunz formeaz o ierarhie de indeci rari

Ultimul nivel = index secvential dens

B+-arborele conine un numr relativ mic de nivele

Cel mult log(m+1)/2(K) pentru k valori a cheii de cutare

Nivelul imediat urmtor rdcinii: cel puin 2 noduri

Urmatorul: 2* (m+1)/2 noduri

Urmtorul: cel puin 2* (m+1)/2 * (m+1)/2

etc

Inserrile i tergerile se fac eficient, restructurarea indexului necesitnd

timp logaritmic

24

Interogri pe B+-arbori Algoritm

Determinarea tuturor nregistrrilor cu valoarea k a cheii de cutare

1. N=rdcina

2. Repet

Caut n N cea mai mic valoare a cheii de cutare >k

Dac aceasta exist i e egal cu Ki, atunci N = Pi

Altfel N = Pn (k Kn1)

Pn N este nod frunz

3. Dac exist Ki = k, pointerul Pi indic nregistrarea dorit

4. Altfel nu exist nregistrarea cu cheia de cutare k

25

Interogari

26

Cheia de cauare - stocheaza numerele impare intre 1-19

Intrarea 15?

Interogri pe B+-arbori Observaii

27

Ex:

Un nod este n general de aceeai dimensiune ca a unui bloc pe disc - 4Kbytes

Pp. m=100

Fiecare acces al unui nod poate necesita o localizare pe disc (

Actualizri n B+-arbori Inserarea

28

1. Determin nodul frunz n care va aprea valoarea cheii de cutare

2. Dac valoarea e deja prezent ntr-un nod frunz

1. Adaug nregistrarea n fiier/tabel/relaie

2. Adaug un pointer n bucket

3. Dac nu e prezent valoarea

1. Adaug nregistrarea n fiier/tabel/relaie

2. Dac e loc n nodul frunz insereaz perechea (valoare cheie, pointer)

3. Altfel divide nodul

Actualizri n B+-arbori Inserarea: divizarea nodurilor

29

Divizarea unui nod frunz

1. Se iau cele n perechi (inclusiv cea care urmeaz a fi inserat) ordonate.

n nodul original se pun primele n/2 perechi iar restul ntr-un nod

nou

2. Fie p noul nod i k cea mai mic valoare din p. Insereaz (k,p) n

printele nodului care se divide

3. Dac printele este plin acesta se divide la rndul su i divizarea se

propag n sus pn cnd un nod nu este plin. n cel mai ru caz nodul

rdcin este divizat ceea ce crete nlimea arborelui cu 1.

Divizarea unui nod plin intern N la inserarea unei perechi (k,p)

1. Se creeaz un nod temporar M cu spaiu pentru n+1 pointeri i n

valori n care se copie N i perechea (k,p)

2. Se copie P1,K1, , K n/2-1,P n/2 din M napoi n N

3. Se copie Pn/2+1,K n/2+1,,Kn,Pn+1 din M ntr-un nou nod N

4. Insereaz (K n/2,N) n printele lui N

Actualizri n B+-arbori Inserarea: Exemplu

30

Inseram valorile 14 si 16

Actualizri n B+-arbori Inserarea: Exemplu(2)

31

Inseram valorile 8 si 10

Actualizri n B+-arbori tergerea

32

1. terge nregistrarea din fiier/tabel/relaie

2. Dac nregistrarea face parte dintr-un bucket, e tears din acesta. Altfel (sau dac bucketul devine gol) terge din nodul frunz perechea (pointer, valoare cheie)

3. Dac nodul va avea prea puine intrri n urma tergerii i ele ncap ntr-un nod vecin va avea loc unirea:

1. Se insereaz toate intrrile n nodul stng i se terge cellalt

2. Se terge perechea (Ki1, Pi), unde Pi este pointerul ctre nodul ters de la printe. Dac e necesar se propag tergerea recursiv n sus. Dac nodul rdcin rmne cu un singur pointer va fi ters.

4. Altfel, dac nodurile nu ncap n vecin se redistribuie pointerii:

1. Se redistribuie astfel nct avem satisfcut condiia de minim n ambele noduri

2. Se actualizeaz valoarea cheii de cutare corespunztoare n

printe

Actualizri n B+-arbori tergerea: Exemplu (1)

33

Stergem valorile 17 si 19

Actualizri n B+-arbori tergerea: Exemplu (2)

34

Stergem valorile 5 si 7

B+-arbori

Eficiena

35

Cutare: cel mult log(m+1)/2(K) blocuri transferate

Datorit nlnuirii nodurilor frunz sunt eficieni i pt. Cutri n interval

Inserare, stergere: cel mult 2 log(m+1)/2(K) blocuri transferate

Organizarea fiierelor B+-arbore

36

B+-arborii pot fi utilizai direct pentru organizarea fiierului i

nu doar pentru indexare

Nodurile frunz stocheaz nregistrri i nu pointeri

Pentru a mbunti utilizarea spaiului sunt implicai mai muli vecini n

redistribuire pentru a evita divizarea sau unirea

3/2n

Indeci B-arbore

37

Asemntori B+-arborilor ns permit o singur apariie a

valorilor cheilor de cutare

Cheile de cutare n nodurile care nu sunt frunz nu mai apar

nicieri n arbore ceea ce necesit introducerea unui pointer

adiional

Pointerii Bi sunt pointeri ctre nregistrri sau bucketuri

Indeci B-arbore Exemplu

38

Indeci B-arbore Observaii

39

Avantaje

Pot utiliza mai puine noduri dect B+-arborele corespunztor

E posibil a se localiza valoarea cutat nainte de a ajunge la frunze

Dezavantaje

Nodurile care nu sunt frunze sunt mai mari ceea ce necesit reducerea

numrului de valori stocate; nlimea va fi mai mare

Inserrile i tergerile sunt mai complicate

Implementarea e mai dificil

Nu e posibil a fi scanat un tabel doar cu ajutorul frunzelor

Avantajele nu cntresc mai mult dect dezavantajele, B+-

arborii fiind preferai de ctre SGBD-uri

Indecsi ordonati:

indecsi multi-cheie

40

Acces multi-cheie

41

Pot fi utilizai mai muli indeci la o interogare

SELECT *

FROM studenti

WHERE judet = 'Bihor' AND an > 2010;

Strategii posibile pentru utilizarea indecilor uni-atribut:

Utilizarea indexului cu cheia de cutare judet

Utilizarea indexului cu cheia de cutare an

Utilizarea ambilor i efectuarea interseciei

Dezavantaje:

Pot exista multe nregistrri ce satisfac numai una dintre condiii

Indeci multi-cheie

42

Cheile de cutare compuse sunt chei ce conin mai mult de un atribut

Ordinea lexicografic: (a1, a2) < (b1, b2) dac

a1 < b1sau

a1=b1 i a2 < b2

Ex. (judet, an)

Pot fi rezolvate eficient condiiile de mai jos?

a) where judet = 'Bihor' AND an > 2010

b) where judet > 'Bihor' AND an = 2010

Eficiena

43

Ordinea atributelor ntr-un index multi-cheie este foarte

important

Eficiena depinde de selectivitatea atributelor

k-d arbori

44

Generalizare a arborelui binar de cautare:

k= nr. de atribute ce formeaza cheia de cautare

Fiecare nivel corespunde unui atribut din cele k

Succesiunea nivelelor reprezint iterri peste mulimea celor k atribute

Pentru a obine arbori echilibrai, la nivelul fiecrui nivel n noduri este pus valoarea median

Organizarea hash/Indecsi hash

45

Hashing

46

n organizarea de tip hash a fiierului/tabelului/relaiei

nregistrrile sunt grupate n bucketuri care pot fi localizate pe

baza valorilor cheii de cutare (un bucket ia dimensiunea unui

bloc)

Funcia hash (de dispersie) h:K->B este o funcie de la

mulimea valorilor cheii de cutare la mulimea adreselor

tuturor bucketurilor

Localizeaz nregistrrile pentru acces, inserare, tergere

nregistrri cu valori diferite ale cheii de cutare pot fi mapate

la acelai bucket

Cutare secvenial n bucket

Funcii hash

47

Cerine

Uniformitate

Caracter aleatoriu

Funciile hash tipice au la baz calcule pe reprezentarea binar intern a

cheii de cutare

Pot aprea situaii de depire a bucketului, caz n care se utilizeaz

bucketuri de exces

Organizarea de tip hash

Exemplu

48

Organizarea de tip hash utiliznd nume drept cheie:

Funcia hash: h:Dom(nume)->{0,1,2,3} - suma reprezentrilor binare modulo 4

'Acatrinei:

'1000001 1100011 1100001 1110100 1110010 1101001 1101110 1100101 1101001'

h('Acatrinei') = 34%4 = 2.

Indeci hash

49

Organizeaz cheile de cutare cu pointerii asociai ntr-o structur de tip

hash

Indeci hash

Operaii

50

Cutarea:

Sandu: 01010011 01100001 01101110 01100100 01110101

h(Sandu) =20%4=0 -> scanarea bucketului 0

Inserarea:

Ionescu: 01001001 01101111 01101110 01100101 01110011

01100011 01110101

H(Ionescu)=32%4=0 -> inseram in fisierul de date si apoi in

bucketul 0 in index

tergerea: calcul hash, scanare bucket, stergere

Indeci hash

Performana

51

Pentru cutri punctuale, n absena coliziunilor, localizarea unei valori necesit citirea unui singur bloc

Pentru cutri n interval indecii hash nu sunt eficienti, deoarece trebuie calculat hashul fiecrei valori posibile

Hash dinamic

52

Funcia h mapeaz valori ale cheii de cutare la un set fix de adrese de

bucketuri.

Dac fiierul crete apar depiri ale bucketurilor

Daca fiierul se micoreaz spaiu este alocat inutil

Soluii:

Reorganizri periodice cu o nou funcie hash (costisitoare, necesit

ntreruperea operaiunilor)

Numrul de bucketuri este modificat dinamic

Hash extensibil: funcia hash e modificat dinamic

Genereaz valori ntr-o mulime mare, tipic ntregi pe 32 bii

La un anumit moment se utilizeaz doar un prefix al funciei hash (doar primii i

bii) al crui lungime scade sau crete dup caz

Hash extensibil

Structura general

53

i=2, i2 = i3 = i, i1 = i 1

Hash extensibil

Utilizare

54

Fiecare bucket j stocheaz o valoare ij

toate intrrile care indic spre bucketul j vor avea acceai valoare pe primii ij bii

Pentru a localiz bucketul ce conine cheia de cutare Kj:

Se calculeaz h(Kj) = X

Se utilizeaz primii i bii ai lui X i se urmeaz pointerul ctre bucketul potrivit

Pentru a insera o nregistrare cu cheia de cutare Kj:

Se localizeaz bucketul j ca mai sus

Daca este spaiu n bucket se insereaz nregistrarea

Altfel bucketul este divizat i inserarea este rencercat

Hash extensibil

Divizare bucket la inserare

55

Pentru a diviza bucketul j la inserarea unei valori Kj:

Dac i > ij

1. Se aloc un nou bucket z i ij = iz = (ij + 1)

2. Se actualizeaz a doua jumtate a tabelei de adrese a bucketurilor

pentru a indica spre z

3. Se scot nregistrrile din j i sunt reinserate n j sau z

4. Se recalculeaz adresa bucketului pentru Kj i se insereaz

Dac i = ij

1. Dac se atinge o limit a lui i se utilizeaz bucketuri de exces

2. Altfel

1. Se incrementeaz i i se dubleaz dimensiunea tabelei de adrese

2. Se nlocuiete fiecare intrare n tabel cu dou intrri care indic spre acelai

bucket

3. Se recalculeaz adresa bucketului pentru Kj i se insereaz (acum i > ij )

Hash extensibil

tergere

56

Pentru a terge o nregistrare

Se localizeaz bucketul i se terge din el

Dac bucketul devine gol acesta este ters cu modificrile necesare n

tabela de adrese

Pot fi contopite bucketuri care au aceeai valoare pentru ij i acelai

prefix ij 1

Descreterea dimensiunii tabelei de adrese este posibil

Hash extensibil

Exemplu

57

structura hash iniial, dimensiune bucket = 2

Hash extensibil

Exemplu

58

Structura dup inserarea unei nregistrri Brighton i a dou nregistrri

Downtown

Hash extensibil

Exemplu

59

Dup inserarea nregistrrii Mianus

Hash extensibil

Exemplu

60

Dup inserarea a trei nregistrri Perryridge

Hash extensibil

Exemplu

61

Dup inserarea nregistrrilor Redwood i Round Hill

Hash extensibil

Observaii

62

Beneficii

Performana nu se degradeaz cu creterea fiierului

Minimizeaz consumul de memorie

Dezavantaje

Tabela de adrese a bucketurilor poate deveni foarte mare

Soluie: utilizarea unui B+-arbore pentru a localiza nregistrarea dorit n tabela de adrese

Modificarea dimensiunii tabelei de adrese este costisitoare

n funcie de tipul interogrii:

Hashingul e indicat cnd se specific o valoare a cheii de cutare

Dac se lucreaz cu intervale de valori e mai rapid indexul ordonat

n practic:

Postgres suport indecii hash

Oracle suport organizarea static de tip hash, nu i indeci hash

SQLServer suport numai B+-arbori

Indecsi bitmap

63

Indeci bitmap

64

Proiectai pentru a trata eficient interogrile cu mai multe chei de cutare

Aplicabili pentru atribute care iau un set redus de valori distincte

Tuplele relaiei sunt considerate a fi numerotate

Structura:

Un ir de bii pentru fiecare valoare a atributului

irul are lungimea numrului de nregistrri

Valoarea 1 semnific egalitate cu valoarea creia i este asociat bitmapul

Indeci bitmap Observaii

65

Interogrile sunt rezolvate utiliznd operatori pe bii:

Intersecia AND

Reuniunea OR

Complementarierea NOT

SELECT *

FROM studenti

WHERE judet IN ('Arad', 'Cluj') AND an 2010;

(Arad OR Cluj) AND NOT(2010)

Nu e necesar accesul fiierului

Utili cnd interogarea necesit numrare

Implementare eficient:

La tergere se prefer utilizarea unui bitmap de existen

Bitmapurile sunt mpachetate n cuvinte (tipul word) de 32 sau 64 bii

(operatorul and pe un cuvnt o singur instruciune CPU)

Definirea indecsilor in SQL

66

Definirea indecilor n SQL

67

Standardul nu reglementeaza, dar in practica SGBD-urile adera la aceeasi sintaxa

Creare:

create index on ()

E.g.: create index b-index on branch(branch_name)

tergere:

drop index

Majoritatea SGBD-urilor permit specificarea tipului de index

Majoritatea SGBD-urilor creeaz implicit indecsi la specificarea constrangerii unique

Uneori sunt generati indecsi la specificarea constrangerilor referentiale

Indexarea n Oracle

68

Oracle suport B+-arbori implicit la crearea indexului cu comanda SQL (in

documentatia Oracle apar ca B-arbori dar corespund in teorie B+-arborilor )

Indecii sunt suportai pe:

Atribute i liste de atribute

Rezultatul unei funcii peste atribute

Indeci bitmap sunt suportai cu declararea

create bitmap index on ()

Indeci hash nu sunt suportai dar exist suport pentru organizarea hash

static

Indexarea n Oracle

Considerente

69

Crearea indecsilor e recomandat dupa incarcarea datelor

oricand e posibil

Indexarea coloanelor potrivite:

Coloanele au valori (in proportie mare) unice

Dac selecia filtreaz un numr mic de tuple dintr-un tabel mare (selectivitate ridicata ~ 15%)

Coloanele sunt utilizate in join

Coloane cu valori distincte putine -> structura bitmap

Range query (filtrare in interval) -> B+trees

Interogari punctuale frecvente: organizare hash a fisierului

Selctie cu conditii petse functii -> indecsi definiti peste functii

Bibliografie

70

Capitolul 11 n Avi Silberschatz Henry F. Korth S. Sudarshan.

Database System Concepts. McGraw-Hill

Science/Engineering/Math; 6 edition (January 27, 2010)