B-AlberiEsercitazioni

B-Trees: alberi bilanciati di ricerca progettati per esserememorizzati su dischi magnetici.

Introduzione

Dischi magnetici molto più lenti delle memorie ad accesso casuale.

La misura dell’efficienza di un B-albero è data anche dal numero di accessi che si effettuano al disco.

Il numero di accessi al disco aumenta con l’aumentare dell’altezza dell’albero.

Mantenere bassa l’altezza del B-albero.

DISK-READ(x) DISK-WRITE(x)

Nelle applicazioni dei B-alberi viene elaborata una grande quantità di dati al punto che spesso la memoria principale non è sufficiente.

Soluzione:

viene copiato un nodo alla volta dal disco alla memoria principale: procedura DISK-READ(x).

dopo la sua elaborazione, viene riscritto nel disco se è statomodificato: procedura DISK-WRITE(x).

Esempio di B-albero

M

Q T XD H

F G J K LB C R S V WN P Y Z

root[T]

Se un nodo x di un B-albero contiene n[x] chiavi, allora xha n[x]+1 figli.

Definizione dei B-alberi (I)1. Ogni nodo x è caratterizzato dai seguenti campi o attributi:

a) n[x], numero delle chiavi memorizzate in x;

b) le n[x] chiavi sono ordinate in modo non decrescente:key1[x]<= key2[x]<=…<= keyn[x][x];

c) leaf[x], un valore boolean cheè TRUE se x è una foglia,FALSE altrimenti.

2. Un nodo interno x contiene n[x]+1 puntatori, c1[x], c2[x], …, cn[x]+1[x],ai suoi figli.

3. I campi keyi[x] definiscono gli intervalli delle chiavi memorizzate inogni sottoalbero: se ki è una qualunque chiave memorizzata nelsottoalbero, di radice ci[x], allora

k1<=key1[x]<=k2<=key2[x]<=…<=keyn[x][x]<=kn[x]+1

Definizione dei B-alberi (II)4. Tutte le foglie sono alla stessa profondità, che coincide con l’altezza

dell’albero.

5. Il numero di chiavi che un nodo può contenere è limitato(superiormente e inferiormente); dipende dal grado minimo t>=2:

a) Ogni nodo (ad eccezione della radice) deve contenere almenot-1 chiavi. Ogni nodo interno (ad eccezione della radice) deveavere almeno t figli. Se non è un albero vuoto, la radice devecontenere almeno una chiave.

b) Ogni nodo può contenere al massimo 2t-1 chiavi, quindi un nodo interno può avere al massimo 2t figli.

Definizione dei B-alberi (III)

Riassumendo:

t <= c[x] <= 2tLimite numero figli

Numero di chiavi di rootNumero di chiavi di xNumero di figli di x

Grado minimo

1 <= n[root] <= 2t-1t-1 <= n[x] <= 2t-1

c[x] = n[x]+1

t >= 2

Esercizio 1

Per quale valore di t, il seguente è un B-albero lecito?

M

Q T XD H

F G J K LB C R S V WN P Y Z

Esercizio 2 (I)

Si mostrino alcuni B-alberi leciti con grado minimo uguale a 2 che rappresentano l’insieme di chiavi {1, 2, 3, 4, 5}

t=2key={1, 2, 3, 4, 5}

t-1 <= n[x] <= 2t-1 1<= n[x] <= 3t <= c[x] <= 2t 2 <= c[x] <= 4

Esercizio 2 (II)c[x] = 2

3 4 51

2

4 51 2

3

51 2 3

4n[x] = 1

c[x] = 3n[x] = 2

31

2 4

5

Esercizio 3 (I)Si derivi un limite superiore stretto del numero delle chiavi che possono essere memorizzate in un B-albero con altezza h in funzione del grado minimo t.

Σ [(2t)2 * (2t-1)]i=0

h

Operazioni di base sui B-alberi

Si assume che:a) la radice dell’albero è sempre contenuta in memoria principale;b) tutti i nodi che vengono passati come parametro alle procedure sono già

presenti in memoria principale.

RICERCA DI UNA CHIAVE

B-Tree-Search(x, k){int i = 1;while(i<=n && k>keyi[x])

i++;if(i<=n[x] && k=keyi[x])

return (x, i)if(leaf(x))

return null;else {DISK-READ(ci[x]);

return B-Tree-Search(ci[x], k) }}

RICERCA DI UNA CHIAVE: complessità

Per ricercare una chiave all’interno di un B-albero, lo si percorre lungo un cammino che porta dalla radice alle foglie.

Il numero di accessi al disco della procedura B-Tree-Search è dato da Θ(h)= Θ(login), dove h è l’altezza e n è il numero di chiavi del B-albero.

Siccome n[x]<2t, il tempo impiegato dal ciclo while per esaminare un nodo qualsiasi è O(t), pertanto il tempo totale di CPU è O(th)=O(t*login)

CREAZIONE di un B-albero VUOTO

B-Tree-Create(){x=AllocateNode();leaf(x)=TRUE;n[x]=0;DISK-WRITE(x);root[T]=x;}

Dove AllocateNode() crea un nuovo nodo su disco.

DIVISIONE di un nodo in un B-albero (I)

Procedura necessaria quando si deve inserire una nuova chiave in un nodo: se tale nodo è pieno*, non è possibile effettuare tale operazione, quindi bisogna dividerlo.

Il nodo viene diviso all’altezza della sua chiave mediana keyt[x].

Il risultato di questa operazione è che il nodo x viene diviso in due nodi con t-1 chiavi ciascuno.

* un nodo x è pieno quando n[x]= 2t-1

DIVISIONE di un nodo in un B-albero (II)

B-Tree-Split-Child(x, i, y){z=AllocateNode();leaf(z)=leaf(y);n[z]=t-1;for(j=1; j<=t-1; j++;)

keyj[z]=keyj+t[y];if(!leaf(y))

for(j=1; j<=t; j++;)cj[z]=cj+t[y]

n[y]=t-1;for(j=n[x]+1; j>=i+1; j--;)

cj+1[x]=cj[x];ci+1[x]=z;for(j=n[x]; j>=i; j--;)

keyj+1[x]=keyj[x];keyi[x]=keyt[y];n[x]++;

DISK-WRITE(y);DISK-WRITE(z);DISK-WRITE(x);

}

Complessità: Il tempo di CPU richiesto dalla procedura B-Tree-Split-Child è di Θ(t), per la presenza dei due cicli for.

DIVISIONE di un nodo in un B-albero (III)

…N W….

P Q R S T U V

x

y=ci[x]

T1 T2 T3 T4 T5 T6 T7 T8

N S W

P Q R T U V

T1 T2 T3 T4 T5 T6 T7 T8

x

y=ci[x] z=ci+1[x]

key i-1

[x]ke

y i[x]

key i+1

[x]

key i-1

[x]ke

y i[x]

INSERIMENTO di una chiave in un B-albero (I)

Operazione che viene fatta attraverso una singola visita all’albero di altezza h, che richiede O(h) accessi al disco.

Il tempo di CPU richiesto è O(th)=O(t*logtn).

La procedura B-Tree-Insert utilizza la la procedura B-Tree-Split-Child per garantire che non si inserisca mai la chiave in un nodo già pieno.

INSERIMENTO di una chiave in un B-albero (II)B-Tree-Insert(T, k){

r =root[T];

if(n[r]==2t-1) {

s=AllocateNode();

root[T]=s;

leaf(s)=FALSE;

n[s]=0;

c1[s]=r;

B-Tree-Split-Child(s,1,r);

B-Tree-NonFull(s, k); }

else B-Tree-Insert-NonFull(r, k);

}

INSERIMENTO di una chiave in un B-albero (III)

L’operazione che divide la radice è l’unica che fa aumentare di una unità l’altezza dell’albero.

A D F H L N P

T1 T2 T3 T4 T5 T6 T7 T8

root[T]r

A D F L N P

T1 T2 T3 T4 T5 T6 T7 T8

r

Hs root[T]

B-Tree-Insert-NonFullB-Tree-Insert-NonFull(x, k){

i=n[x];if(leaf(x)){

while(i>=1 && k<keyi[x]) {keyi+1[x]=keyi[x];i--; }

keyi+1[x]=k;n[x]++;DISK-WRITE(x);}

else{while(i>=1 && k<keyi[x])

i--;i++;DISK-READ(ci[x]);if(n[ci[x]]=2t-1){

B-Tree-Split-Child(x, i, ci[x]);if(k>keyi[x])

i++; }B-Tree-Insert-NonFull(ci[x], k);}

}

ESERCIZIO 4 (I)Nel B-albero sottostante, inserire le seguenti chiavi: {B, Q, L, F}.

G M P X

J K N OA C D E R S T U V Y Z

root[T]

ESERCIZIO 4 (II)

G M P X

J K N OA B C D E R S T U V Y Z

root[T]

G M P T X

J K N OA B C D E U V Y Z

root[T]

Q R S

ESERCIZIO 4 (III)

J K L N OA B C D E U V Y Z

root[T]

Q R S

P

G M T X

J K L N OA B U V Y Z

root[T]

Q R S

P

C G M T X

D E F

ESERCIZIO 5 (I)

Si mostrino i risultati dell’inserzione della sequenza di chiavi {F, S, Q, K, C, L, H, T} per t=2.