B trees

Memoria

Memoria principale “Piccola” e “veloce” (chips, silicio)

Mb 10-8 / 10-9 sec.

Memoria secondaria “Grande” e “lenta” (dischi magnetici) Gb 10-3 / 10-4 sec.

Blocchi di memoria

Memoria principaleUn blocco contiene k bytes, k=1, ... , 64

Memoria secondariaUn blocco contiene k Kb (kiloBytes = 1024 bytes) k=64, ... , 1024

Problema

Minimizzare il numero di accessi alla memoria secondaria

Soluzione

Strutture dati ad hoc, specifiche per questo problema.

Dischi magnetici

Dall’alto

rotazionetraccia

settore

testina di lettura/scrittura

cilindri

I dischi memorizzano molti dati ma sono lenti.

Trovare una pagina richiede tempo (posizionamento testina più tempo di rotazione, 5-10ms), la lettura è veloce

Conviene leggere i dati in pagine (blocchi) di 2-16 Kb ciascuno.

Tempo di esecuzione

Spesso il tempo necessario per accedere ad una pagina su disco è superiore al tempo necessario all’elaboratore per esaminare tutta l’informazione letta.

Tempo di esecuzione:

• numero di accessi a disco

• tempo (di calcolo) della CPU

Il num. di accessi a disco è misurato in numero di pagine lette/scritte. Non è costante, però ...

Operazioni sui dati

Per accedere alle strutture dati non si fa riferimento a indirizzi in memoria centrale ma a locazioni su file.Sia x è un puntatore ad un oggetto:se x è nella memoria principale, gli si accede ad es. con key[x]se è su disco, la procedura DiskRead(x) copia l’oggetto in memoria (DiskWrite(x) lo ricopia su disco)

B-treeUn B-tree è un albero di radice root(T) in cui ogni nodo x è strutturato come segue:

X=

n[x] = numero delle chiavi (key) del nodo x

leaf[x]: booleano, vero se x è foglia

Chiavi memorizzate in ordine non-decrescente

key1 ≤ key2 ≤ key3 ≤ ... ≤ keyn

n

leafkey1

key2

... keyn

B-tree

If leaf[x]= false (x è un nodo interno)c1[x], c2[x], ... , cn[x]+1[x] sono puntatori ai nodi

figli

I campi keyi[x] definiscono gli intervalli delle chiavi memorizzate in ciascun sottoalbero: se ki è una chiave memorizzata nel sottoalbero di radice ci[x] allora si ha che:k1≤key1[x] ≤ k2≤key2[x] ≤... ≤keyn[x][x]≤ kn[x]+1

Ogni foglia ha la stessa profondità, che è quiandi anche l’altezza dell’albero.

B-tree

ai ≤ key1 ≤ bi ≤ key2 ≤ di ≤ key3 ≤ ei

Il num. di chiavi memorizzabili in un nodo è limitato in funzione di un intero t, t ≥ 2, chiamato grado minimox ≠ root n[x] ≥ t-1 n[x] ≤ 2t-1x = root n[x] ≥ 1Un nodo x è pieno se n[x] = 2t-1

c1 key1 c2 key2 c3 key3 c4

ai bi di ei

B-tree

1 nodo 1.000 chiavi

1.001 nodi 1.001.000 chiavi

1.002.001 nodi 1.002.001.000 chiavi

Più di un miliardo di chiavi!h=2num. accessi ≤ 2 !!!

root[T]

1000

1000 1000 1000

1000 1000 1000

...

...

B-treeAlberi di ricerca bilanciati (balanced search tree, BST)I nodi dei B-tree possono avere molti figli (migliaia)Profondità = O(log n)Generalizzano naturalmente i BST

M

D,H Q,T,X

B,C F,G J,K,L N,P R,S V,W Y,Z

Altezza di un B-treeSe n ≥ 1, allora per ogni B-tree T (con n chiavi) di altezza h, di grado minimo t ≥ 2, vale che: h ≤ logt((n+1)/2)

1

t - 1 t - 1

t - 1 t - 1 t - 1…

tt

t - 1 t - 1 t - 1…

0 1

1 2

2 2t

livello#di nodi

( ) ( ) 121

1121211

1

1 −=⎟⎟⎠

⎞⎜⎜⎝

⎛

−

−−+=−+≥ ∑

=

− hhh

i

i tt

ttttn

Analisi tempi di esecuzione

numero di accessi a disco: O(logt n)

CPU time: O(t logt n)

trovato

trovato

non trovato

Operazioni sui B-tree

Assunzioni:

•La radice di un B-tree è sempre in memoria centrale

•Quando si modifica la root bisogna effettuare una scrittura su disco (DiskWrite)

•Qualsiasi nodo venga passato come parametro deve già essere in memoria centrale, a seguito di una Disk-Read.

Operazioni sui B-tree

Le operazioni da realizzare sono:

•Ricerca di una chiave (semplice)

•Creazione di un nuovo albero vuoto (semplice)

•Inserimento di nuove chiavi (complessa)

•Cancellazione di chiavi (complessa)

B-tree search(x,k)

B-Tree-Search(x,k)

i=1

while i ≤ n[x] and k>keyi[x]

do i=i+1

if i ≤ n[x] and k=keyi[x]

then return(x,i)

if (foglia[x])

then return(nil)

else DISK-READ(ci[x])

return(B-tree search(ci[x],k)

Operazione di ricerca su B-tree, parametri:x: radice di un sottoalberok: chiave da cercare

Creazione di un B-tree vuoto

B-Tree-Create(T)

x = AllocateNode()

leaf[x]=true

n[x]=0

DiskWrite(x)

root[T]=x

num accessi a pagina: O(1)tempo CPU: O(1)

Inizialmente si crea un nodo radice vuoto con la B-Tree-Create, poi lo si riempie con la B-Tree-Insert.Entrambe utilizzano la Allocate-Node che crea un nuovo nodo e gli assegna una pagina di disco in tempo O(1).

Divisione di un nodo

I nodi si riempiono e raggiungono la loro capacità massima di 2t – 1 chiavi.Per poter inserire una nuova chiave è necessario “fare spazio”, cioè dividere (split) il nodo.La divisione avviene in corrispondenza della sua chiave mediana.Risultato: una chiave di x sale di un livello + 2 nodi con t-1 chiavi.

Split di un nodo

P Q R S T V W

T1 T8...

... N W ...

y = ci[x]

key i-1[x

]

key i[x

]

x

... N S W ...

key i-1[x

]

key i[x

]

x key i+

1[x

]

P Q R T V W

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

Mediano!

t=4, 2t-1=7

non pieno

pieno

B-Tree-Split-ChildB-Tree-Split-Child(x,i,y)z AllocateNode()leaf[z] leaf[y]n[z] t-1for j 1 to t-1 keyj[z] keyj+t[y]if not leaf[y] then for j 1 to t cj[z] cj+t[y]n[y] t-1for j n[x]+1 downto i+1 cj+1[x] cj[x]

ci+1[x] zfor j n[x] downto i keyj+1[x] keyj[x]

keyi[x] keyt[y]n[x] n[x]+1DiskWrite(y)DiskWrite(z)DiskWrite(x)

x: nodo padrey: nodo da spezzare (figlio di x)i: indice in xz: nuovo nodo

P Q R S T V W

T1 T8...

... N W ...

y = ci[x]

key i-1[x

]

key i[x

]

x

Split: tempo di CPU

Lo split è un’operazione locale che non percorre l’albero

Tempo di CPU (t): I due loop vengono eseguiti t volte

3 operazioni di I/O

Inserimento di elementi

Inserimento effettuato ricorsivamente: si inizia dalla radice e si percorre ricorsivamente l’albero fino al livello delle foglie

E’ necessario scendere ad un livello inferiore se il nodo corrente contiene 2t – 1 elementi

Inserimento di elementi (2)

Caso particolare: la radice è piena (BtreeInsert)

B-Tree-Insert(T)r root[T]if n[r] == 2t – 1 then s AllocateNode() root[T] s leaf[s] FALSE n[s] 0 c1[s] r B-Tree-Split-Child(s,1,r) B-Tree-Insert-Non-Full(s,k)else B-Tree-Insert-Non-Full(r,k)

Lo split della radice richiede la creazione di nuovi nodi

L’albero cresce (verso l’alto invece che verso il basso).

Split della radice

A D F H L N P

T1 T8...

root[T]r

A D F L N P

H

root[T]s

r

Inserimento di elementi

BInsertTreeNonFull cerca di inserire un elemento k in un nodo x, che si assume essere non pieno quando la procedura viene chiamata

BTreeInsert e la ricorsione in BTreeInsertNonFull garantiscono che l’assunzione sia vera.

Inserimento di elementi: Pseudo Codice

B-Tree-Insert-Non-Full(x,k)i n[x]if leaf[x] then

while i 1 and k < keyi[x]

keyi+1[x] keyi[x] i i - 1 keyi+1[x] = k n[x] n[x] + 1 DiskWrite(x)

else while i 1 and k < keyi[x] i i - 1 i i + 1 DiskRead ci[x]

if n[ci[x]] = 2t – 1 then

BTreeSplitChild(x,i,ci[x])

if k > keyi[x] then i i + 1 BTreeInsertNonFull(ci[x],k)

inserimento di una foglia

nodo interno: attraversamento dell’albero

Inserimento: esempio

G M P X

A C D E J K R S T U VN O Y Z

G M P X

A B C D E J K R S T U VN O Y Z

G M P T X

A B C D E J K Q R SN O Y ZU V

albero iniziale (t = 3)

inserimento di B

inserimento di Q

Inserimento: esempio (2)

G M

A B C D E J K L Q R SN O Y ZU V

T X

P

C G M

A B J K L Q R SN O Y ZU V

T X

P

D E F

inserimento di L

inserimento di F

Inserimento: tempo di CPU

I/O su disco: O(h), dato che vengono eseguiti solo O(1) accessi a disco durante le chiamate ricorsive a BTreeInsertNonFull

CPU: O(th) = O(t logtn)

In ogni momento sono presenti O(1) pagine disco in memoria principale

Cancellazione di elementi

Effettuata ricorsivamente, iniziando dalla radice e percorrendo l’albero ricorsivamente fino al livello delle foglie

Si scende ad un nuovo livello dell’albero se il nodo corrente contiene t-1 elementi (mentre per l’inserimento 2t – 1 elem.)

B-tree-Delete gestisce tre diversi casi:– Caso 1: elemento k trovato in una foglia– Caso 2: elemento k trovato in un nodo

interno– Caso 3: elemento k probabilmente in un

nodo di livello inferiore

Caso 1: se l’elemento k è nel nodo x, e x è una foglia, cancella k da x

Cancellazione (2)

C G M

A B J K L Q R SN O Y ZU V

T X

P

D E F

albero iniziale

C G M

A B J K L Q R SN O Y ZU V

T X

P

D E

F cancellato: caso 1

x

cancellazione (3)

Caso 2: se la chiave k è nel nodo x, e x non è una foglia, cancella k da x

a) Sia y il figlio di x che precede k. Se y ha almeno t chiavi, trova il predecessore k’’ di k nel sottoalbero di radice in y. Ricorsivamente cancella k’’ e sostituisci k con k’’ in x.

b) Simmetricamente per il nodo sucessore z

c) se sia y che z hanno t-1 chiavi, si inserisce in y sia k che tutti i figli di z (che diventano figli di y). Il nodo y ha 2t-1 chiavi. Ricorsivamente, si elimina k da y.

Cancellazione (4)

C L

A B D E J K Q R SN O Y ZU V

T X

PG cancellato: caso 2c

y = k + z - k

x - k

C G L

A B J K Q R SN O Y ZU V

T X

P

D E

M cancellato: caso 2a

x

y

Cancellazione - distribuzioneCaso 3: se k non è nel nodo interno x, trova il sottoalbero di

radice ci[x] che potrebbe contenere k.

Se ci[x] ha solo t – 1 elementi, ci si assicura di scendere in un nodo che abbia almeno dimensione t; poi si chiama ricorsivamente l’operazione sul sottoalbero scelto.

Possibili due casi.

a) se ci[x] ha solo t-1 chiavi, ma ha un fratello con almeno t chiavi, aggiungi a ci[x] un altra chiave prendendola da x, poi sposta una chiave dal fratello immediatamente a destra o a sinistra di ci[x] in x e sposta l’opportuno figlio dal fratello in ci[x] (distribuzione).

Cancellazione – distribuzione (2)

C L P T X

A B E J K Q R SN O Y ZU Vci[x]

x

fratello

cancella B

B cancellato: E L P T X

A C J K Q R SN O Y ZU V

... k’ ...

... k

A B

ci[x]

x ... k ...

...

k’

A

ci[x]

B

Cancellazione - fusione

b) Se ci[x] e tutti i suoi fratelli hanno t – 1 elementi, allora fondi (merge) ci con un fratello, spostando un elemento da x nel nuovo nodo unione e facendolo così diventare il mediano di quel nodo

x ... l’ m’ ...

...l k m ... A B

x ... l’ k m’...

... l

m …

A B

ci[x]

Cancellazione – fusione (2)

l’altezza dell’albero diminuisce

D cancellato: C L P T X

A B E J K Q R SN O Y ZU V

C L

A B D E J K Q R SN O Y ZU V

T X

P

cancella D

ci[x] fratello

Cancellazione: tempo di CPU

La maggior parte degli elementi sono nelle foglie, quindi la cancellazione avviene più spesso nelle foglie.

In questo caso la cancellazione avviene in un’unica discesa verso il livello delle foglie

La cancellazione di un nodo interno può richiedere un ritorno verso l’alto (caso 2)

I/O su disco: O(h), dato che si effettuano solo O(1) operazioni su disco durante le chiamate ricorsive

Tempo di CPU: O(th) = O(t logtn)

Altri metodi di accesso

Varianti dei B-tree: B+-tree, B*-treeB+-tree: usati nei data base management systems (DBMS)Schema generale dei metodi di accesso (comune ai B+-tree):

– Gli elementi contenenti dati sono memorizzati solo nelle foglie

– Gli elementi sono raggruppati in nodi foglie– Ogni elmento in un nodo interno memorizza:

• un puntatore a un sottoalbero• una descrizione compatta dell’insieme di elementi

memorizzati nel sottoalbero