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 i0 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