Databases
Architettura di un DBMS:
Struttura ad indice per i files,
B
+-Trees
2
Indici
■ Un indice consiste di coppie <K=chiave,etichetta> e supporta l’efficiente recupero di tutte le etichette con chiave K.
■ Un indice contiene informazioni ausiliarie che aiutano a localizzare in modo veloce i dati contenuti in un file.
■ Le ricerche avvengono relativamente ai valori di alcuni attributi, che formano la chiave di ricerca.
■ Si faccia attenzione alla differenza tra chiave e chiave di ricerca:
una chiave di ricerca può contenere valori duplicati.
■ In assenza di ambiguità, utilizzeremo il solo termine chiave.
Indice
Blocchi contenenti
i record
Record richiesti Valore
K
3
Rappresentare le etichette (1)
• Le etichette possono essere:
1. I dati stessi.
2. RID (record identifier) di uno dei record con chiave K.
3. Lista con i RID dei record con chiave K.
• L’alternativa è indipendente dalla tecnica utilizzata per recuperare le coppie chiave-etichetta.
10 Marco Rossi 1234567 10 Marco Verdi 3456721
10 Marco Rossi 1234567 10 Marco Verdi 3456721 10
10 10
1 2
3
10 Marco Rossi 1234567 10 Marco Verdi 3456721
4
Rappresentare le etichette (2)
Con la prima alternativa:
■ Si può avere al più un indice su una data collezione di dati.
■ Se i record di dati sono grandi, l’informazione ausiliaria nell’indice può impiegare molto spazio.
La terza alternativa:
■ È più compatta della seconda, ma le etichette sono di lunghezza variabile.
In genere si adotta la seconda alternativa (v. Elmasri, Chapter 17)
5
Creazione di indici a livello di schema in SQL
CREATE [UNIQUE] INDEX NomeIndice ON NomeTabella(ListaAttributi)
CREATE INDEX ImpPK ON Impiegato(Cognome, Nome) DROP INDEX ImpPK
DROP INDEX NomeIndice
N.B. non è SQL standard, ma è la sintassi più diffusa.
Ad ogni attributo possiamo associare anche l’ordine l’ordinamento prescelto.
6
Esempio: Indice su file sequenziale
10 20 30 40 50 60 70 80 90 100 10
20 30 40 50 60 70 80 90 100
Sequential File =
Tuple ordinante secondo primary key Index File
Una chiave di ricerca k dell’Index File e’ associata a un puntatore al
record del Data File che ha chiave di ricerca k
7
Classificazione degli indici
• Un indice è primario se la chiave di ricerca
contiene direttamente i dati, ad esempio la chiave primaria, (o se son organizzati su dati ordinati
sugli stessi campi su cui e’ definito l’indice stesso) altrimenti è detto secondario.
• Un indice è denso se contiene almeno
un’etichetta per ogni valore della chiave di ricerca nel record dei dati, altrimenti è detto sparso.
• Un indice è clustered se l’ordine dei record dei
dati è uguale o simile all’ordine delle etichette,
altrimenti è detto unclustered.
Esempio di ricerca in Indice Denso
• Immaginiamo di avere una relazione di 1.000.000 di tuple che occupano blocchi da 4096 byte per 10 record, lo spazio totale richiesto per memorizzare queste tuple e’ piu’ di 400 MB, un po’
troppo forse per essere mantenuto in memoria centrale per essere acceduto in maniera efficiente.
• Supponiamo ora che il campo chiave e’ di 30 byte e un puntatore di 8 byte, piu’ un po’ di spazio per gli header, possiamo dire che 100 coppie chiave puntatore occupano un blocco di 4096 byte
• Un indice denso occuperebbe quindi 10.000 blocchi o anche 40 MB
• Su un indice denso si puo’ usare la ricerca binaria, quindi per
trovare una chiave sull’indice del nostro esempio potrebbe essere necessario l’accesso a 13 o 14 blocchi, ottenuto da log210.000
• Se I blocchi piu’ importanti sono mantenuti in memoria centrale, possiamo trovare il record con meno di 14 disk I/O 8
9
Indice denso e clustered
10
Indice sparso e clustered
■ Lo spazio utilizzato
dall’indice è inferiore rispetto al caso denso, dove devono essere impiegate tutti i valori delle Primary Key
■ Un indice sparso può essere utilizzato per ridurre il
numero di blocchi necessario per contenere informazioni sulla posizione dei record.
Indice secondario (denso) e unclustered
11
20 40 10 20 50 30 10 50 60 20 10
10 20 20 20 30 40 50
Index File
Data File
Gli indici unclustered possono determinare accessi meno efficienti:
ad esempio i tre record con il valore 20 sono mantenuti in tre blocchi distanti.
12
Indice secondario
10 20 30 40 50 60 70 80 90 100 10
30 50 70 90
Data File Primary Index File
A
B
C D
A D C
C D
E
A A B C
D E
Secondary Index File C
C D D
■ Gli indici secondari forniscono un ulteriore metodo per accedere ai dati per i quali esiste già una via privilegiata d’accesso (Primary Index File)
■ Si possono ridurre i tempi d’accesso usando modificando la soluzione “Lista di RID” mantenendo un tempo d’accesso costante…!
13
Indice secondario (Blocchi di puntatori)
14
Dato un singolo file, quale delle seguenti affermazioni è falsa?
A) Un indice denso può essere secondario.
B) Un indice sparso può essere clustered.
C) Un indice sparso può essere unclustered.
D) Un indice secondario può essere clustered.
15
Dato un singolo file, quale delle seguenti affermazioni è vera?
A) Vi può essere al più un indice che utilizza l’alternativa “record di dati” per la rappresentazione delle etichette.
B) Non vi possono essere più indici che utilizzano l’alternativa
“RID” per la rappresentazione delle etichette.
C) L’alternativa “RID” è più compatta dell’alternativa “Lista di RID”.
D) L’alternativa “record di dati” è tanto più utile quanto maggiori sono le dimensioni dei record dati rispetto alla chiave di ricerca.
16
Più livelli di indicizzazione
10 20 30 40 50 60 70 80 90 100 10
30 50 70 90
Data File
Index File
17
■ Un indice sparso può essere utilizzato per ridurre il numero di blocchi necessario per contenere informazioni sulla posizione dei record.
■ Si possono utilizzare indici su indici.
10 20 30 40 50 60 70 80 90 100 10
30 50 70 90
Data File
Index File 10
90
Più livelli di indicizzazione
18
B+Tree
■ L’utilizzo di più livelli di indicizzazione permette l’esecuzione di ricerche effettuando un accesso per ogni livello dell’albero (più gli accessi necessari a recuperare la lista dei RID).
■ I sistemi commerciali utilizzano indici ad albero dinamici, che variano il numero di livelli di indicizzazione (altezza dell’albero) a seconda delle dimensioni dei file.
■ I B-Tree memorizzano ogni nodo in un blocco, sono
auto-bilancianti e mantengono i nodi pieni almeno per metà (a eccezione della radice).
■ Ogni B-Tree è caratterizzato da un parametro n. Ogni blocco ha spazio per n chiavi e n+1 puntatori.
■ Vedremo la variante più diffusa dei B-Tree, detti B+Tree.
19
Quanto vale n?
■ Dimensione di un blocco: 4096 B.
■ Dimensioni di una chiave: 4 B.
■ Dimensioni di un puntatore: 8 B.
■ Si assume non vi sia header nei blocchi.
A) 340 B) 4096 C) 48 D) 8
Soluzione: MAX(n) tale che 4n + 8(n+1) ≤ 4096 → n = 340
20
Caratteristiche di un B+Tree
■ Le chiavi nelle foglie sono copie delle chiavi nei dati, e sono distribuite ordinatamente da sinistra a destra.
■ Nella radice vi sono almeno due puntatori utilizzati (nel caso di almeno due chiavi distinte nei dati).
■ L’ultimo puntatore di ogni foglia punta al nodo foglia successivo. Dei rimanenti puntatori, almeno (n+1)/2 (intero inferiore) sono utilizzati e puntano ai record dati.
■ Nei nodi interni, tutti i puntatori utilizzati puntano a blocchi al livello inferiore, e almeno (n+1)/2 (intero superiore) devono essere
utilizzati.
21
B+Tree: nodi intermedi e nodi foglia
Record con chiave 57
Record con chiave 81
Record con chiave 95
Foglia successiva Record con
chiave K<57
Record con 57 ≤ K < 81
Record con 81 ≤ K < 95
Record con chiave K ≥ 95 57 81 95
57 81 95
Nodo Intermedio
Nodo Foglia
22
Un B+Tree
13
7 23
2 3 5 7 11
Record dati
31 43
13 17 19 23 29 31 37 41 43 47
23
Equality search con B+Tree (K=40)
40 13
7 23
2 3 5 7 11
31 43
13 17 19 23 29 31 37 41 43 47
24
40
40 ≥ 13 13
7 23
2 3 5 7 11
31 43
13 17 19 23 29 31 37 41 43 47
Equality search con B+Tree (K=40)
25
40
40 ≥ 13 13
7 23
2 3 5 7 11
31 43
13 17 19 23 29 31 37 41 43 47
31≤ <43
Equality search con B+Tree (K=40)
40
26
40
40 ≥ 13 13
7 23
2 3 5 7 11
31 43
13 17 19 23 29 31 37 41 43 47
31≤ <43
Equality search con B+Tree (K=40)
40
Non trovato!
40
27
Range search con B+Tree (K>40)
40 13
7 23
2 3 5 7 11
31 43
13 17 19 23 29 31 37 41 43 47
28
40
40 ≥ 13 13
7 23
2 3 5 7 11
31 43
13 17 19 23 29 31 37 41 43 47
Range search con B+Tree (K>40)
29
40
40 ≥ 13 13
7 23
2 3 5 7 11
31 43
13 17 19 23 29 31 37 41 43 47
31≤ <43
Range search con B+Tree (K>40)
40
30
40
40 ≥ 13 13
7 23
2 3 5 7 11
31 43
13 17 19 23 29 31 37 41 43 47
31≤ <43
Range search con B+Tree (K>40)
40
41 43 47
31
Inserimenti e cancellazioni:
Crescita in altezza dei B+Tree
2 3 5
32
Inserimenti e cancellazioni:
Crescita in altezza dei B+Tree
5
2 3 1
5 1
2 3 5
2 3 1
5 1
Inserimento 11
33
Inserimenti e cancellazioni:
Crescita in altezza dei B+Tree
5
2 3 1
5 1
5
2 3 5
2 3 5
2 3 1
5 1 Cancellazione 11
Inserimento 11
34
Inserimenti in B+Tree
■ Lookup:
▪ Cerchiamo la foglia in cui la chiave va inserita, e se c’è spazio la inseriamo…
■ Split:
▪ …Altrimenti, dividiamo il nodo in due e dividiamo le chiavi tra essi.
▪ In questo ultimo caso, al livello superiore deve essere inserita una nuova chiave per indicizzare il nuovo nodo creato.
■ Propagazione:
▪ Quando si divide un nodo interno, la chiave centrale non viene inserita in uno dei nuovi nodi, ma solamente propagata verso l’alto.
■ Se occorre dividere la radice, essa viene spezzata in due e una
nuova radice viene creata al livello superiore, con una chiave e due puntatori.
35
40
40 ≥ 13 13
7 23
2 3 5 7 11
31 43
13 17 19 23 29 31 37 41 43 47
31≤ <43
Inserimento della chiave 40 (look up)
40
■ Cerchiamo la foglia in cui la chiave va inserita, …
36
13
7 23
2 3 5 7 11
31 43
13 17 19 23 29 43 47
Inserimento della chiave 40 (split)
31 37 40 41
■ … dividiamo il nodo in due e dividiamo le chiavi tra essi.
■ In questo ultimo caso, al livello superiore deve essere inserita una nuova chiave per indicizzare il nuovo nodo creato.
?
37
13
7 23
2 3 5 7 11
31 43
13 17 19 23 29 43 47
Inserimento della chiave 40 (propagazione)
31 37 40 41
■ Quando si divide un nodo interno, la chiave centrale non viene inserita in uno dei nuovi nodi, ma solamente propagata verso l’alto.
40
38
13
7 23
2 3 5 7 11
31
13 17 19 23 29 43 47
Inserimento della chiave 40 (propagazione)
31 37 40 41
?
4339
13
7 23
2 3 5 7 11
31
13 17 19 23 29 43 47
Inserimento della chiave 40 (propagazione)
31 37 40 41
■ Quando si divide un nodo interno, la chiave centrale non viene inserita in uno dei nuovi nodi, ma solamente propagata verso l’alto.
43 40
40
13 40
7 23
2 3 5 7 11
31
13 17 19 23 29 43 47
Inserimento della chiave 40 (split)
31 37 40 41
■ C’è spazio nella radice per inserire 40.
43
41
Cancellazione in B+Tree
■ Cerchiamo il record e se presente lo cancelliamo dalla foglia (senza bisogno di cancellarlo dai nodi intermedi).
■ Se il nodo non soddisfa più i requisiti di riempimento minimo:
■ Se uno dei nodi adiacenti ha chiavi a sufficienza, si recupera una chiave da esso aggiornando la chiave anche nel nodo padre.
■ In caso contrario, i due nodi adiacenti contengono complessivamente non più di n chiavi. Possiamo dunque compattarli in un unico nodo.
■ In quest’ultimo caso, occorre cancellare una chiave dal padre (per esempio ponendola uguale al più piccolo valore della foglia di sx.), e ripetere ricorsivamente l’algoritmo se necessario.
■ Nel caso di riequilibrio in un nodo interno, i puntatori vanno aggiornati come nell’esempio seguente.
42
Cancellazione di 7 (look up)
13
7 23
2 3 5 7 11
31 43
13 17 19 23 29 31 37 41 43 47
7
7 < 13
7 ≥7
■ Cerchiamo il record e se presente lo cancelliamo dalla foglia…
43
Cancellazione di 7 (riequilibrio)
13
7 23
2 3 5 11
31 43
13 17 19 23 29 31 37 41 43 47
■ Se il nodo non soddisfa più i requisiti di riempimento minimo:
■ Se uno dei nodi adiacenti ha chiavi a sufficienza, si recupera una chiave da esso…
5
44
Cancellazione di 7 (riequilibrio)
13
5 23
2 3 5 11
31 43
13 17 19 23 29 31 37 41 43 47
■ Se il nodo non soddisfa più i requisiti di riempimento minimo:
■ …aggiornando la chiave anche nel nodo padre.
45
Cancellazione di 11 (lookup)
13
5 23
2 3 5 11
31 43
13 17 19 23 29 31 37 41 43 47
■ Cerchiamo il record e se presente lo cancelliamo dalla foglia…
< 13
≥5 11
11
46
Cancellazione di 11 (lookup)
13
5 23
2 3 5
31 43
13 17 19 23 29 31 37 41 43 47
■ Se il nodo non soddisfa più i requisiti di riempimento minimo:
■ Se uno dei nodi adiacenti non ha chiavi a sufficienza, i due nodi adiacenti
contengono complessivamente non più di n chiavi. Possiamo dunque compattarli in un unico nodo.
?
47
Cancellazione di 11 (lookup)
23
31
2 3 5
43
13 17 19 23 29 31 37 41 43 47
■ Nel caso di riequilibrio in un nodo interno, i puntatori vanno aggiornati…
13
23
arco
48
■ Dipende dall’altezza (numero di livelli) dell’albero.
■ Assumiamo di avere N nodi foglia, e n+1 puntatori per nodo (nel caso medio, n/2). Come varia l’altezza?
■ Al primo livello abbiamo la radice (1 nodo).
■ Al secondo livello abbiamo n+1 nodi.
■ Al terzo livello abbiamo (n+1)2 nodi.
■ Al livello L abbiamo (n+1)L-1 nodi.
■ Se (n+1)L-1 ≤ N ≤ (n+1)L allora L-1 ≤ log(n+1)N e L ≥ log(n+1)N.
log
(n+1)N ≤ L ≤ log
(n+1)N + 1
Complessità della ricerca con B+Tree (1)
49
Complessità della ricerca con B+Tree (2)
• Nell’esempio precedente, avevamo 340 coppie chiave-puntatore per nodo.
• Ogni nodo (ad eccezione della radice) contiene tra le 170 e le 340 chiavi. Assumiamo che ne contenga in media 255.
• Consideriamo un B+tree di 3 livelli, con una radice, 255 figli e 255*255 = 65.025 foglie indicizziamo più di 16 milioni di record.
• I primi due livelli occupano 4096 + 4096*255 = 1MB.
• Mantenendoli in memoria, ci basta un accesso per recuperare il RID del record ricercato.
