1

I B+ Alberi

R. Basili(Basi di Dati, a.a. 2002-3)

Sommario

• Indici organizzati secondo B+-alberi• Motivazioni ed Esempio• Definizione

• Ricerca in un B+-albero• Esempio

• Vantaggi

• Inserimento/Cancellazione in un B+-albero

• Osservazioni

• B+-alberi in pratica

• Riassunto

2

Motivazioni

• Un ISAM fornisce una struttura statica

• => sottoutilizzo (molte cancellazioni)

• => sovrautili zzo (pagine di overflow)

• Pagine per i dati in ordine sequenziale (Range Search)

• Ipotesi:

• Bilanciamento => riorganizzazione dinamica

• Indici nelle Foglie e stessa ricerca nei nodi intermedi

• Link sequenzile garantito per le foglie (Range Search)

Esempioindici

data entries

FILE

27 …

…………… ……………

18

………………x*≤≤18 18<x*≤≤27

… _ _45 56 81 105 505

… …78 500

518 _

No overlflow list!

3

Definizione• Un B-albero e’ un albero con radice e ordine

d (>1) tale che:• ogni nodo x contiene al piu’ 2d-1 chiavi, k[ i]

• ogni nodo x contiene al piu’ 2d puntatori ai figli, p[ i](indefiniti per le foglie)

• per ogni nodo x si ha:• (detta ki una generica chiave memorizzata in un figlio p[ i] di x)

k0 ≤ k[1] ≤ k1 ≤ k[2] ≤ … ≤ k2d-2 ≤ k[2d-1] ≤ k2d-1

• tutte le foglie sono alla stessa profondita’ (h)• ogni nodo (tranne le radice) deve avere almeno d-1

chiavi e d figli 8678 _

2518 77 8079 84 9390 _

d=2

Definizione (2)• Se le foglie di un B-albero vengono organizzate in

una lista doppiamente collegata allora la strutturaprende il nome di B+-albero• Foglie (Sequence list)

• Generalmente, le foglie non contengono i dati(cioè, data entries ≠ data records) ma indiciaggregati (densi o sparsi)

• La radice risiede sistematicamente in memoriacentrale

_78 _

25*18* 78*

d=2

89*79* 96* …….

4

Ricerca in un B+-albero

Nodo *trova( Nodo *n, Key k, int d )

if foglia(n) then return( n )

else

i=0;

while (i<2*d-1) and (k>n->k[i+1]);

i=i+1;

return(trova(n->p[i], k, d))

Ricerca (Esempio)

50 7128

12* 18* _ 32* 47* _ 55* 56* 67* 84* 96* 97*

k=47 ⇒⇒ 28≤≤k<50k=47 ⇒⇒ k>28

⇒⇒ i=1 ××n→→p[1]

5

Proprieta’• Altezza di un B+-Albero

• Se l’ordine di un albero n e’ d nel caso di minimaoccupazione dell’albero abbiamo

• li v=1 ⇒ 2 nodi• li v=2 ⇒ 2d nodi• li v=3 ⇒ 2d2 nodi• …• li v=i ⇒ 2d(i-1) nodi

• Quindi per il numero totale N di chiavi in n vale:

• cioe’

1d2

1d

1d)1d(1d2)1d(1N

h

h

1i

h1i

−=

=

−−−+=−+≥ ∑

=

−

2

1Nlogh d

+≤

B+-alberi: Vantaggi

• I nodi intermedi (solo chiavi, k[i], e pt, P[i])richiedono una pagina (1 operazione I/O) anchecon d grande

• Costo delle operazioni di ricerca proporzionale adh, cioe’ logaritmico (base d) in N

• Il branching factor f dei nodi: d ≤ f ≤ 2d

• Occupazione media: 60% - no overflow chains

• Le foglie (collegate) supportano operazioni di“ ricerca per intervallo” (anch’esse logaritmiche)

• I costi delle operazioni diinserimento/cancellazione sono logaritmici (segue)

6

Inserimento: ESEMPIO

50 7128

12* 18* 21* 32* 47* _ 55* 56* 67* 84* 96* 97*

insert( newk,n )

newk=8

8* 12* _ 18* 21* _

12

(a) split foglia: copia (b) split generico: muovi_su

_ _50

28 _12 _ _71

18* 21* _8* 12* _

h = h + 1

Cancellazione: ESEMPIO

_ _50

28 _12 _ _71

18* 21* _8* 12* _ 55* 56* 67* 84* 96* 97*

cancel( newk,n )

newk=56newk=18

_ _50

28 _12 _ _71

21* _ _8* 12* _ 55* 57* _ 84* 96* 97*

7

Cancellazione: ESEMPIO (2)

cancel( newk,n )

newk=21

_ _50

28 _12 _ _71

21* _ _8* 12* _ 55* 57* _ 84* 96* 97*

_ _50

28 _8 _ _71

12* _ _8* _ _ 55* 57* _ 84* 96* 97*

Ridistribuzione:

max

32* 47* _

Cancellazione: ESEMPIO (3)

cancel( newk,n )

newk=12

_ _50

28 _8 _ _71

12* _ _8* _ _ 55* 57* _ 84* 96* 97*

_ _50

_ _28 _ _71

8* _ _ 55* 57* _ 84* 96* 97*

Fusione (leaf merge):

32* 47* _

32* 47* _

8

Cancellazione: ESEMPIO (3)

71 _50Fusione (non-leaf merge):

_ _50

_ _28 _ _71×A B C D+

A B+ C D

Osservazioni• Implementazioni

• Compressione di chiavi• Spazio libero nei nodi (~50%) => minore d• Cancellazione vs. marcatura+garbage collection

• Svantaggi:• elevata dinamicità dei nodi intermedi =>

svantaggiosa per la concorrenza• chiavi multiple

• Costruzione del B+-albero

• Inserimenti ripetuti• Smart loading: Sorting e bottom-up add/split

9

Sommario

• B+-alberi ottimizzano le operazioni di search erange-search

• Sono indici dinamici che si adattano allevariazioni di taglia dei dati

• L’ordine d di un albero vincola superiormente edinferiormente il fattore di ramificazione

• L’altezza dell ’albero cresce logaritmicamente conil numero delle chiavi

• La ricerca di elementi ha un costo (disk I/O) pariad h

Sommario• Durante gli inserimenti le catene di overflow sono

evitate tramite operazioni di split dei nodi pieni

• Tali split possono far crescere l’altezza h

• Durante le cancellazioni le operazioni di merge tranodi possono far decrescere l’altezza dell ’albero

• L’ordine dipende• organizzazione dei record

• organizzazione degli indici (data entries)

• compressione delle chiavi

• Svantaggi per l’uso concorrente dei dati: dinamicadell ’accesso ai nodi intermedi

10

Cosa sapere

• Def. ed Indicizzazione basata su B+-alberi

• Costi delle Operazioni di

• Ricerca

• Ricerca per Intervallo

• Inserimento e Cancellazione

• Confronto tra ISAM e B+-alberi