B-alberi

dizionari in memoria secondaria

ASD - B-tree 2

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

ASD - B-tree 3

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

ASD - B-tree 4

modello di costo/2

• Occorre considerare modelli di costo diversi dal modello RAM se il costo dominante della computazione è costituito dagli accessi in memoria secondaria.

• Ex: # di accessi a disco x seek time + tempo di trasferimento dei dati da disco a memoria principale

ASD - B-tree 5

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

ASD - B-tree 6

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

ASD - B-tree 7

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

ASD - B-tree 8

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

ASD - B-tree 9

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

ASD - B-tree 10

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

ASD - B-tree 11

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

ASD - B-tree 12

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

ASD - B-tree 13

BST paginato

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

m -ario?

ASD - B-tree 14

B-tree di ordine m• radice con 0 o p > 1 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• 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• Nota: le foglie contengono puntatori a blocchi

di elementi

ASD - B-tree 15

B-tree di ordine 456

22 41 66 87

2 14 26 34 59 61 71 77 90 92 98 /46 5144

è anche un B-tree di ordine 3?

Nota: si sono indicate solo le chiavi

ASD - B-tree 16

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

• Ogni blocco di elementi è memorizzato in un blocco su disco (dim. B)– Se max. L bit per elemento al più B/L elem./blocco

• Obiettivo: avere alberi di altezza piccola (es. 4)

ASD - B-tree 17

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)

ASD - B-tree 18

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

ASD - B-tree 19

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

q

qq0

1

1

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

ASD - B-tree 20

Scelte progettuali/2• 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 E’ possibile avere alberi con altezza piccola in casi di interesse pratico

– radice spesso mantenuta in RAM

ASD - B-tree 21

rappresentazione nodi (RAM)class BTreeNode {

int m;boolean leaf; /* true se nodo è foglia */int keyTally; /* No. di chiavi presenti */int keys = new int[m-1];BTreeNode references[] = new BTreeNode[m];BtreeNode(int key) {…} /* Costruttore */

}/* Nota: si assumono chiavi intere *//* keys può essere un array di oggetti contenenti coppie <chiave. rif. a mem. secondaria> */

ASD - B-tree 22

Rappresentazione con riferimenti

ASD - B-tree 23

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)

ASD - B-tree 24

ricerca in un B-treepublic BTreeNode BTReeSearch(int key) {

return BTreeSearch(key, root)}protected BTreeNode BTreeSearch(int key, BTreeNode node) {

if (node != null) {int i=1;while ((i<=node.keyTally)&&(node.keys[i-1]< key)) {i++;if ((i>node.keyTally) || (node.keys[i-1]>key))return BTreeSearch(key, nodereferences[i-1];else return node;}else return null;

}

ASD - B-tree 25

Ricerca chiave di valore 51

56

22 41 66 87

2 14 26 34 59 61 71 77 90 92 98 /46 5144

ASD - B-tree 26

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

ASD - B-tree 27

Inserimento in foglia non piena

Un albero B prima (a) e dopo (b) l’inserimentodella chiave 7 in una foglia avente celle disponibili

ASD - B-tree 28

Inserimento in foglia piena

Inserimento della chiave 6 in una foglia piena

ASD - B-tree 29

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 (nell’esempio, m=5)

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

ASD - B-tree 30

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

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

ASD - B-tree 31

InserimentoAlgorithm BTreeInsert(k) {

<trova foglia in cui inserire k> /* Sia essa node */

<trova pos. adeguata per k nell’array keys>

if (<nodo non pieno) {

<inserisci k ed incrementa keyTally>

return;

}

else {

<suddividi node in node1 e node2>;

<distribuisci chiavi e rif. equamente tra node1 e node2>

<aggiorna node1.keyTally e node2.keyTally>

<k = ultima chiave in node1>

}

/* Continua prossima slide */

ASD - B-tree 32

Inserimento/* Continua da slide precedente */

if (<node era la radice>) {<crea nuova radice con figli node1 e node2><inserisci k e rif. a node1 e node2 nella radice>root.keyTally=1;return;

}else

<genitore di node2 = genitore di node>}

ASD - B-tree 33

costo inserimento

• discesa radice – foglia – O(logm/2 n ) I/O

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

• #split– O(logm/2 n )

• costo totale: O(logm/2 n )

ASD - B-tree 34

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

ASD - B-tree 42

costo eliminazione

• discesa radice – foglia – O(logm/2 n ) I/O

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

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

• #fusioni– O(logm/2 n )

• costo totale: O(logm/2 n )

ASD - B-tree 43

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