Organizzazione logica di un disco

Indici con gli alberi

Alberi perfettamente bilanciati per

indici su memorie di massa: B-alberi

Indici su memorie secondarie

Spesso i dati da ordinare sono in quantità tale da richiedere dispositivi di

memoria secondaria, come i dischi

Organizzazione logica di un disco

blocco (record fisico)

settore traccia (cilindro)

testina

I dischi sono

strutturati in blocchi adiacenti detti pagine Ogni accesso ha un

tempo di latenza

Un albero binario impaginato

Queste pagine hanno dimensione costante: ora sono piene

Un albero di ricerca impaginato

15

7 23

5

2 6

11

9 12

18

16 20

30

25 31

7 15 23

2 5 6 9 11 12 16 18 20 25 30 31

B-alberi

Un B-albero è un albero perfettamente bilanciato (rami tutti della stessa lunghezza) di “pagine” di dimensione fissata, tali che:

1. le pagine sono sempre riempite almeno per metà, ad eccezione della radice;

2. se una pagina ha r chiavi e non è un foglia, allora ha r + 1 figli;

3. le chiavi nelle pagine sono ordinate, e la relazione con le chiavi dei sottoalberi è quella degli alberi di ricerca.

Un B-albero è un albero perfettamente bilanciato (rami tutti della stessa lunghezza) di “pagine” di dimensione fissata, tali che:

1. le pagine sono sempre riempite almeno per metà, ad eccezione della radice;

2. se una pagina ha r chiavi e non è un foglia, allora ha r + 1 figli;

3. le chiavi nelle pagine sono ordinate, e la relazione con le chiavi dei sottoalberi è quella degli alberi di ricerca.

B-alberi da Bayer (che li ha inventati con McCreight) o forse da “bilanciato”

Un B-albero

25

10 20 30 40

2 5 7 8 13 14 15 18 41 42 45 46 26 27 28 32 35 38 41 42 45 46

In un nodo (diverso dalla radice) ci sono t ≤ i ≤ 2t chiavi:

t è il grado dell’albero (= 1/2 max numero delle chiavi in un nodo)

L’altezza di un B-albero

Teorema. Se un B-albero di grado t ed altezza h contiene n chiavi, allora h ≤ log _t+1 (n + 1)/2

Teorema. Se un B-albero di grado t ed altezza h contiene n chiavi, allora h ≤ log _t+1 (n + 1)/2

1

t

t ^{t + 1} t

t

t ^{t + 1} t

t + 1 t + 1 t + 1 t + 1

Questo è il peggior rapporto tra h e n

t 2 1

) 1 (

2t t + )2

1 (

2t t +

chiavi

L’altezza di un B-albero

Teorema. Se un B-albero di grado t ed altezza h contiene n chiavi, allora h ≤ log _t+1 (n + 1)/2

Teorema. Se un B-albero di grado t ed altezza h contiene n chiavi, allora h ≤ log _t+1 (n + 1)/2

: dunque chiavi,

) 1 (

2 sono ci

livello

Sul i t t + ⁱ⁻¹

1 )

1 (

1 2 )

1 2 (

1

) 1 (

2 1 )

1 (

2

1 ¹

0 1

1

− +

− = + +

=

+ +

= +

+

≥

∑ ∑

=

=

−

h h

h i h i

i

i

t t t t

t t

t t

n

h è O(log_t n): quindi la costante moltiplicativa è tanto minore quanto maggiore è t

Ricerca in un B-albero

Search(k, T)

// Post: true sse k è una chiave in T if T = ∅ then return false

else (y, b) ← Src(k, root(T)) return b

Src(k, x)

// Pre: x ≠ nil

// Post: ritorna (y, b) dove y è un nodo dell’albero T t.c. x = root(T), // se k è in y allora b = true

// se k non è in y allora b = false e y è una foglia

Ricerca in un B-albero

Src(k, x) sia x =

if k ∈ {k₁, …, k_r} then return (x, true) else if x è una foglia then return (x, false) else if k < k₁ then return Src(k, x₁)

else sia i ∈ 1 .. r t.c. k ∈ k_i .. k_i+1 (posto k_r+1 = +∞) return Src(k, x_i+1)

x₁ k₁ x₂ … x_r k_r x_r+1

È una generalizzazione della ricerca in un albero

binario di ricerca

Inserimento

I B-alberi “crescono” dalle foglie: quando non c’è più

posto si innesca un

meccanismo di propagazione delle suddivisioni dei nodi

Divisione di un nodo

10 30

35 40 22 26

7 10 15 18 20

26 30 35 40 7 10 15 18

22

Caso in cui l’inserimento di una chiave avviene in un nodo pieno diverso dalla radice

Divisione della radice

26 52 79 91 22

a b c d e

a′ ^{16 a”}

a

22

Divisione della radice

52

16 26

b c d e

a′ ^a”

79 91

Questo è il solo caso in cui l’altezza aumenta

Inserimento

Insert(k, T) // Pre: il grado di T è t; Post: T risulta dall’inserimento di k in T if T = ∅ then T ← [nil, k, nil]

else (x, b) ← Src(k, root(T)), u ← nil, v ← nil

while not b do // se b = true allora non c’è più nulla da fare

sia x = [y₁ k₁ y₂ … y_r k_r y_r+1], i t.c. k ∈ k_i .. k_i+1 (posto k_r+1 = +∞) z ← [y₁ k₁ y₂ … k_r u k v k_i+1 … y_r k_r y_r+1]

if r < 2t then x ← z, b ← true // c’è posto in x

else // r = 2t i.e. x era pieno e z ha una chiave in più sia z = [y’₁ k’₁ y’₂ … y’_r k’_r y’_r+1]

k ← k’_t+1, u ← [y’₁ k’₁ y’₂ … y’_t k’_t y’_t+1]

v ← [y’_t+2 k’_t+2 y’_t+3 … y’_r k’_r y’_r+1] if x = root(T) then root(T) ← [u, k, v], b ← true

Cancellazione

Per cancellare la chiave k distinguiamo i casi:

1. La chiave k è in una foglia

2. La chiave k è in un nodo interno

Cancellazione

La chiave k è in una foglia x:

1. Il nodo x rimane con almeno t chiavi: OK 2. Tolta k, x ha t – 1 chiavi (e non è una foglia,

altrimenti OK):

k’

x y

t – 1 r > t

Caso:

Cancellazione

La chiave k è in una foglia x:

1. Il nodo x rimane con almeno t chiavi: OK 2. Tolta k, x ha t – 1 chiavi (e non è una foglia,

altrimenti OK):

min(y)

y – {^min(y)}

x, k’

(risultato)

Cancellazione

La chiave k è in una foglia x:

1. Il nodo x rimane con almeno t chiavi: OK 2. Tolta k, x ha t – 1 chiavi (e non è una foglia,

altrimenti OK):

k’

x y

t – 1 t – 1

Caso:

Cancellazione

La chiave k è in una foglia x:

1. Il nodo x rimane con almeno t chiavi: OK 2. Tolta k, x ha t – 1 chiavi (e non è una foglia,

altrimenti OK):

max(y)

x, k’, y – ^max(y) (risultato)

Cancellazione

k k’

x y

> t

Caso:

max(x) k’

x – max(x) y

(risultato)

bilanciamento

La chiave k è in un nodo interno

Cancellazione

La chiave k è in un nodo interno

k k’

x y

Caso:

t – 1 t – 1

Ma ora dobbiamo controllare se qui ci sono ancora ≥ t

chiavi

k’

x, y fusione

Analisi della complessità

• Le operazioni di ricerca, inserimento e cancellazione sono O(h)

• h è O(log_t n) = O(log n) (ma t conta in pratica: meglio t grande)

• gli accessi al disco (e i tempi di latenza) sono O(h)

2 X 2

Meglio fermarsi = 5

qui: buon weekend