B-alberi
dizionari in memoria secondaria
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
2
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
3
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
4
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
faccia
traccia
ASD - B-tree
settore
5
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
6
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
7
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
8
esempio/3
tempo accesso (ms)
120,00
100,00
ms
80,00
60,00
40,00
20,00
0,00
1 3
5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
#blocchi contigui
ASD - B-tree
9
ammortizzazione
la contiguità premia
tempo (microsec.) ammortizato per byte
6000,00
microsec.
5000,00
4000,00
3000,00
2000,00
1000,00
0,00
1 3
5 7
9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
# blocchi contigui
ASD - B-tree
10
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
11
dizionari in memoria
secondaria
idea: paginare un
albero di ricerca
54
22
77
11
4
1
37
17
8
28
64
46
60
86
70
80
91
13 19 24 35 40 51 58 62 67 74 78 83 88 98
ASD - B-tree
12
BST paginato
• l’albero non è più binario
• si può definire un albero di ricerca
m -ario?
ASD - B-tree
13
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
14
B-tree di ordine 4
56
22 41
2 14
26 34
66 87
44 46 51
59 61
71 77
90 92 98 /
Nota: si sono indicate solo le chiavi
è anche un B-tree di ordine 3?
ASD - B-tree
15
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 bit
m ≈ 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
16
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
17
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
18
altezza di un B-tree spoglio/2
• # chiavi in un B-tree spoglio di
altezza h >=
1  2(q  1)  2q (q  1)  2q 2 (q  1)    2q h 2 (q  1) 
q h 1  1
h 2 i
 1  2(q  1)i 0 q  1  2(q  1)
 2q h 1  1  n
q 1
n 1
 h  logq
1
2
p 1
1
i0 q  q  1
p
D.: qual è l’altezza di
un B-tree frondoso?
ASD - B-tree
i
q
19
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 bit
m ≈ 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
20
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
21
Rappresentazione con
riferimenti
ASD - B-tree
22
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
23
ricerca in un B-tree
public 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
24
Ricerca chiave di valore 51
56
22 41
2 14
26 34
66 87
44 46 51
59 61
ASD - B-tree
71 77
90 92 98 /
25
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
26
Inserimento in foglia non
piena
Un albero B prima (a) e dopo (b) l’inserimento
della chiave 7 in una foglia avente celle disponibili
ASD - B-tree
27
Inserimento in foglia piena
Inserimento della chiave 6 in una foglia piena
ASD - B-tree
28
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
29
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.h
tml
ASD - B-tree
30
Inserimento
Algorithm 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
31
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
32
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
33
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
34
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
42
+
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 Btree
– una differenza notevole è nello split di una
foglia: la chiave separatrice viene copiata (e non
spostata) nel genitore
ASD - B-tree
43