B-alberi dizionari in memoria secondaria. giugno 2002ASD - B-tree3 dizionari su memoria secondaria...

B-alberi

dizionari in memoria secondaria

giugno 2002 ASD - B-tree 3

dizionari su memoria secondaria

• la memorizzazione su memoria secondaria risponde a due esigenze– permanenza dell’informazione

• la RAM è volatile

– grande quantità di dati• la RAM è limitata

• memoria secondaria: disco


modello di costo

• il costo in termini di tempo per accedere al disco (scrittura/lettura) domina in maniera sostanziale il costo di elaborazione in RAM– parti meccaniche in movimento con costanti di

tempo dell’ordine delle decine di millisecondi– una CPU esegue un’istruzione elementare in

pochi colpi di clock– ad es., copia di un dato dalla RAM a un registro

• supp. 10 colpi di clock, CPU a 1GHz• 10 ns per copia RAM->registro• 20 ns per un’assegnazione


modello di costo/2

• non ha più senso attribuire un costo approssimativamente costante ad ogni operazione eseguita

• il modello basato sull’operazione dominante è inadeguato


modello di costo/3• l’accesso al disco

avviene per blocchi (o pagine fisiche )– tutti i blocchi hanno

la stessa dimensione (da 512B ad alcuni KB)

– ciascun blocco è definito da tre coordinate: cilindro (o traccia ), settore, faccia

cilindro

settoretraccia

faccia


modello di costo/4

• tempo di accesso al disco = somma di tre componenti– seek time

• per posizionare la testina sul cilindro corretto

– latency time• attesa necessaria affinché il settore desiderato

transiti sotto la testina

– tempo di trasferimento• dati scambiati fra RAM e disco


esempio

• seek time– ~15-20ms

• latency time– valore atteso: 50% del

tempo di rotazione• in un disco a

7200rpm, poco più di 4ms

• tempo di trasferimento– velocità: alcuni MB/s

• blocco di 4KB, seek 15 ms, 10000rpm, velocità di trasferimento 2MB/s

• tempo (ms) di accesso al blocco ≈ 15 + 3 + 2 ms/blocco = 20ms/blocco

• costo (ammortizzato) per byte ≈ 20ms/4096B ≈ 4.9µs/B


esempio/2

• nel caso di accesso a più blocchi contigui vengono pagati un solo seek e un solo latency

• la convenienza aumenta all’aumentare del numero di blocchi contigui– “bulk access” vs.

”random access”

• blocco di 4KB, seek 15 ms, 10000rpm, velocità di trasferimento 2MB/s

• tempo (ms) di accesso a due blocchi contigui ≈ 15 + 3 + 2·2 ms/blocco = 22ms/blocco

• costo (ammortizzato) per byte ≈ 22ms/8192B ≈ 2.7µs/B


esempio/3

tempo accesso (ms)

0,00

20,00

40,00

60,00

80,00

100,00

120,00

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39

#blocchi contigui

ms


ammortizzazione

tempo (microsec.) ammortizato per byte

0,00

1000,00

2000,00

3000,00

4000,00

5000,00

6000,00

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39

# blocchi contigui

mic

ros

ec

.

la contiguità premia


modello di costo/5

• costo (tempo): # di I/O su disco– blocco ha dimensione B– RAM ha dimensione M – disco ha dimensione ∞

• tempo di CPU trascurabile– buona approssimazione in molti casi


1

dizionari in memoria secondaria

8 13 19 24 35 40 51 58 62 67 74 78 83 88 98

4 17 28 46 60 70 80 91

11 37 64 86

22 77

54

idea: paginare un albero di ricerca


BST paginato

• l’albero non è più binario• si può definire un albero di ricerca

m -ario?


B-tree di ordine m

• radice con 0 o 1 < p m figli• ogni nodo interno (non radice) con

k – 1 chiavi e k figli, m /2 k m– non lo stesso k per ciascun nodo!

• foglie con k-1 chiavi, m /2 k m e tutte allo stesso livello

• albero di ricerca– ad ogni chiave è associato un sottoalbero

destro di chiavi inferiori ed uno sinistro di chiavi superiori

• m è il max numero di figli


B-tree di ordine 456

22 41 66 87

2 14 26 34 59 61 71 77 90 92 9846 5144

è anche un B-tree di ordine 3?


altezza di un B-tree

• quali sono le altezze minime e massime di un B-tree di ordine m con n chiavi?– altezza max ottenuta quando ogni nodo

interno ha il min numero di figli (albero spoglio)

• la radice ha 2 figli ed ogni altro nodo interno ha m /2 figli

– altezza min quando ogni nodo interno ha il max numero (m ) di figli (albero frondoso)


altezza di un B-tree spoglio

• sia q = m /2 • 1 chiave nella radice• q - 1 chiavi in ogni altro nodo• livello 2: 2 nodi• livello 3: 2q nodi• livello 4: 2q 2 nodi• livello i : 2q i –2 nodi


altezza di un B-tree spoglio/2

• # chiavi in un B-tree spoglio di altezza h

12

1log

1211

)1(21)1(21

)1(2)1(2)1(2)1(21

11

2

0

22

n

h

nqq

qqqq

qqqqqqq

q

hh

h

i

i

h

p

i

pi

qq

q0

1

11

D.: qual è l’altezza di un B-tree frondoso?


scelte progettuali

• un nodo = un blocco• chiave c bit• riferimento a sottoalbero r bit• in ogni nodo rm + c (m - 1) bit• m = (B + c )/(r + c )

– se B = 4KB, c = r = 32 bitm ≈ 64

– con n = 10ML chiavi h 6– radice spesso mantenuta in RAM


rappresentazione nodi (RAM)

class BTreeNode {int m;boolean leaf;int keyTally;int keys = new int[m-1];BTreeNode references[] = new BTreeNode[m];BtreeNode(int key) {…}

}


cenno alla rappresentazione dei nodi

su disco• file a sé stanti, ciascuno di un blocco

– più semplice da realizzare– i riferimenti ai sottoalberi sono nomi di file– overhead per il sistema operativo

• tutti in un unico file– soluzione compatta, ma più complessa– riferimenti ai sottoalberi

• offset relativi all’inizio di un file (file frammentato, solo accessi random)

• indirizzi assoluti (cilindro+settore+faccia, file non portatili)


operazioni su un B-tree

• le tre operazioni dei dizionari– membership, inserimento,

cancellazione

• interrogazioni di range– dato un intervallo (range), elencare o

contare le chiavi che appartengono all’intervallo


ricerca in un B-tree• si percorre un ramo partendo dalla radice,

scendendo nei sottoalberi– come in un “normale” BST– costo logaritmico Algorithm BTreeSearch(key, node) {

if(node != null) {int i = 1;for(; i <= node.keyTally && node.keys[i-1] < key; i+

+);if((i > node.keyTally) || node.keys[i-1] > key)

return BTreeSearch(key, node.references[i-1]);else return node;

} else return null;}


inserimento in B-tree

• come nei BST, si effettua una ricerca della chiave da inserire

• si tenta dapprima di inserire la chiave in una foglia (appropriata)– se la foglia non è piena il processo termina– se la foglia è piena (ha già m – 1 chiavi)

abbiamo una situazione di overflow e possiamo scinderla in due

• la scissione può determinare altre scissioni


gestione degli overflow

• gestione dell’overflow tramite scissione (o divisione o split)– allocazione di un nuovo nodo (foglia)– le m chiavi vengono così ripartite:

(m – 1) / 2 nella foglia in overflow, (m – 1) / 2 nella nuova e una (la mediana fra le m ) viene inserita nel genitore per separare le due foglie

• se il genitore va in overflow si usa la stessa tecnica


gestione degli overflow/2

• gli overflow si possono propagare verso l’alto fino a coinvolgere la radice

• se la radice va in overflow questa deve venire scissa ed occorre creare una nuova radice, che conterrà la chiave mediana fra le m coinvolte nell’operazione– in questo caso l’albero aumenta la propria

altezza

• dimostrazione (tratta da http://shell.uriel.net/~mozart/File/btree.html)

http://shell.uriel.net/~mozart/File/btree.html



algoritmo di inserimento

Algorithm BTreeInsert(k) {trova foglia f in cui inserire kwhile(true) {trova posizione adeguata per k in keysif(f non è piena) {inserisci k ed incrementa keyTallyreturn

} else {suddividi f in f1 e f2distribuisci le chiavi ed i riferimenti in modo

eguale fra f1 e f2


algoritmo di inserimento/2

inizializza i loro keyTallyk = ultima chiave di f1if(f era radice) {crea nuova radice, genitore di f1 e f2inserisci k e i riferimenti a f1 e f2 in radiceimposta keyTally di radice a 1return

} else f = genitore(f)} // fine while(true)

}


costo inserimento

• discesa radice – foglia – O(log n ) I/O (log in base m /2)

• split– O(1) I/O (3 o 4)

• #split– O(log n )

• costo totale: O(log n )


eliminazione da un B-tree

• si effettua una ricerca della chiave da inserire• se la chiave è in una foglia, la si elimina dalla

stessa e si verifica se il numero di chiavi rimanenti sia comunque non inferiore a m / 2 - 1 – se rimangono troppe poche chiavi si ha underflow, che

richiede una gestione specifica

• se la chiave è in un nodo interno la si sostituisce con il predecessore (o il successore), che è in una foglia, e ci si riconduce al caso precedente– simile alla tecnica usata nei BST


gestione degli underflow

• un nodo in underflow ha m / 2 - 2 chiavi• si tenta dapprima una ridistribuzione delle

chiavi fra nodo e un fratello, coinvolgendo la chiave che li separa nel genitore– occorre un fratello con almeno m / 2 chiavi

• se non è disponibile un fratello per operare la ridistribuzione occorre effettuare la fusione (o merge) fra nodo in underflow e un fratello– richiede una gestione specifica


fusione di nodi

• due nodi fratelli possono essere fusi se uno di essi è in underflow e l’altro ha il numero di chiavi minimo m / 2 - 1

• la fusione consiste nell’inserire in un solo nodo tutte le chiavi presenti nei due nodi, oltre a quella del genitore che separava i due nodi– la fusione permette di liberare risorse precedentemente

allocate a un nodo– richiede l’eliminazione di una chiave dal genitore, che a

sua volta, può andare in underflow, divenendo oggetto di attenzione da parte del gestore dell’underflow


fusione di nodi/2

• se i nodi oggetto di fusione sono i due unici figli della radice, questa scompare e il risultato della fusione diviene la nuova radice– in tal caso vengono liberate risorse allocate

a due nodi– l’albero diminuisce l’altezza

• dimostrazione (tratta da http://shell.uriel.net/~mozart/File/btree.html)












algoritmo di eliminazione

Algorithm BTreeDelete(k) {node = BTreeSearch(k, root)if(node != null) {if(node non è foglia) {trova foglia con successore s di kcopia s su k in nodenode = foglia contenente selimina s da node

} else elimina k da node


algoritmo di eliminazione/2

while(true) {if(node non in underflow) returnelse if (c’è un fratello di node con abbastanza

chiavi) {ridistribuisci chiavi fra node e fratelloreturn

} else if (genitore(node) è radice) {if radice ha una chiavefondi node, fratello e genitore,

formando nuova radice


algoritmo di eliminazione/3

else fondi node e suo fratelloreturn

else {fondi node e suo fratellonode = genitore(node)

}}

}}


costo eliminazione

• discesa radice – foglia – O(log n ) I/O (log in base m /2)

• ridistribuzione– O(1) I/O (3 o 4)

• fusione– O(1) I/O (3 o 4)

• #fusioni– O(log n )

• costo totale: O(log n )


B+-tree

• chiavi solo nelle foglie• nodi interni contengono solo

informazioni di “branching” e costituiscono un vero e prorpio indice

• le foglie sono collegate orizzontalmente• algoritmi di gestione simili a quelli per il

B-tree– una differenza notevole è nello split di una

foglia: la chiave separatrice viene copiata (e non spostata) nel genitore

B-alberi dizionari in memoria secondaria. giugno 2002ASD - B-tree3 dizionari su memoria secondaria...

Documents

Transcript of B-alberi dizionari in memoria secondaria. giugno 2002ASD - B-tree3 dizionari su memoria secondaria...