Comments
Description
Transcript
Corso di Basi di Dati
Basi di Dati Sistemi per BD Relazionali: Modello Fisico Concetti Avanzati versione 2.0 Questo lavoro è concesso in uso secondo i termini di una licenza Creative Commons (vedi ultima pagina) G. Mecca – [email protected] – Università della Basilicata DBMS Relazionali – Modello Fisico >> Sommario Concetti Avanzati Obiettivo Indici multilivello Indici e tabelle ISAM B+ Tree (cenni) Indici Hash File hash Indice hash In Pratica G. Mecca - [email protected] - Basi di Dati 2 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Obiettivo Obiettivo Strategia di accesso ideale inserimenti e cancellazioni efficienti (t. cost ?) ricerca binaria evitare ordinamenti del file Gli indici rappresentano un passo avanti Problemi la ricerca si può migliorare gli inserimenti nei file ordinati sono un pb. G. Mecca - [email protected] - Basi di Dati 3 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Indici multiliv. Indici Multilivello Possono migliorare i tempi di ricerca Intuizione un indice è un file ordinato di record (chiave, puntatore) se i valori della chiave sono distinti, posso costruire un indice primario per l’indice posso proseguire costruendo vari livelli di indice G. Mecca - [email protected] - Basi di Dati 4 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Indici Multiliv. Indici Multilivello 3122 QueloPaolo Sci 2 3122 4123 … … … 7488 … 8770 8770 … 9934 (NB/bfr)/bfr blocchi NB/bfr blocchi G. Mecca - [email protected] - Basi di Dati … .. 4123 Birillo Giulio Let 2 4771 Verdi Luigi Sci 3 … 7488 1 blocco … 5990 6102 … … 3554 Rossi Mario Ing 1 3122 3122 3456 Rossi Maria null 3 … … 5990 3453 Mous Michi Agr 1 5765 Neri Paolo Sci 2 … … … … 5876 Caio Tizio Ing .. 2 … 9934 Busti Lina Let 2 … .. … … … NB blocchi 5 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Indici multiliv. Indici Multilivello Dinamica logaritmica: logbfr(NB) livelli di indice ricerca logaritmica con base bfr>2 Esempio dimblocco=2048, dimrecord=58, dimfile=2G NB=1M, bfr=204 (fattore di blocco dell’indice) I livello = ceil(1M/204) = 5141 (ceil: p.te intera sup.) II livello = ceil (29960/204) = 26 ricerca in ceil(log204(1M)) + 1 accessi = 4 Attenzione: tutti i valori devono essere distinti G. Mecca - [email protected] - Basi di Dati 6 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Indici multiliv. Indici Secondari Multiliv. 3122 QueloPaolo Sci 2 3453 Mous Michi Agr 1 3456 Rossi Maria null 3 Birillo … … … … Busti 6554 Rossi Mario Ing 1 .. Caio … 7123 Birillo Giulio Let 2 … 7771 Verdi Luigi Sci 3 8765 Neri Paolo Sci 2 … … Pinco 9876 Caio Tizio Ing … … … .. 2 Rossi … Verdi valori distinti blocco di puntatori G. Mecca - [email protected] - Basi di Dati 9934 Busti Lina Let 2 … .. … … … 7 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Indici multiliv. Il Problema degli Inserimenti Tutti i livelli sono file ordinati costo degli inserimenti Due possibili soluzioni strutture ordinate “statiche” ISAM strutture ordinate “dinamiche” B Tree e B+ Tree G. Mecca - [email protected] - Basi di Dati 8 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> ISAM Strutture Ordinate Statiche Strutture multilivello in cui spazio per i blocchi allocato staticamente file ordinato con blocchi contigui inserimenti effettuati ordinatamente finchè c’e’ spazio file disordinato di trabocco (“overflow”) periodiche riorganizzazioni globali con fusione del file primario e del file di trabocco ISAM: Indexed Sequential Access Method G. Mecca - [email protected] - Basi di Dati 9 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> ISAM Struttura ISAM 3122 QueloPaolo Sci 2 3453 Mous Michi Agr 1 3122 3122 3456 Rossi Maria null 3 3333 Stop John Sci 3 4123 … 3442 Mira Lanza Ing 2 5888 3554 Rossi Mario Ing 1 5990 4123 Birillo Giulio Let 2 6102 4771 Verdi Luigi Sci 3 7402 5765 Neri Paolo Sci 2 5777 Caro Pino Ing 3 … … … .. 5990 3122 7412 6442 … 7488 7488 8122 8770 … … … … … 5876 Caio Tizio Ing 8770 .. 2 … 8880 Blocchi contigui del disco 9934 G. Mecca - [email protected] - Basi di Dati 9934 Busti Lina Let 2 … .. … … … Blocchi di overflow 10 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> ISAM Struttura ISAM Principali vantaggi allocazione contigua dei blocchi (“località”) la struttura non viene toccata Svantaggi possono essere necessarie ristrutturazioni Adatta a tabelle con dinamica limitata pochi inserimenti G. Mecca - [email protected] - Basi di Dati 11 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> B+ Tree Strutture Ordinate Dinamiche Strutture multilivello in cui file ordinato con rappresentazione collegata allocazione dinamica dei blocchi i blocchi sono sempre parzialmente pieni algoritmi di inserimento opportuni riorganizzazioni locali (fusioni e divisioni dei blocchi) B Tree, B+ Tree G. Mecca - [email protected] - Basi di Dati 12 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> B+ Tree B+ Tree In sintesi, albero di ricerca di apertura n>2 Nodi al più n-1 val. della chiave ed n punt. a sottoal. <p1, k1, p2, k2, p3, … pm-1, km-1, pm>, m<=n, k1< k2 < …< km-1 Sottoalberi i valori del primo sottoalbero sono minori o ug. di k1 tutti i valori X del sottoalbero i sono compresi tra ki-1 e ki (ki-1 < X <= ki per i da 2 a m-1) i valori dell’ultimo sottoalbero sono maggiori di km-1 G. Mecca - [email protected] - Basi di Dati 13 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> B+ Tree 1100 QueloPaolo Sci 2 B+ Tree ……… 1240 1240 Rossi Mario Ing 1 3121 1241 Birillo Giulio Let 2 ……… 3121 Verdi Luigi Sci 3 3599 4128 7552 7400 3122 Neri Paolo Sci 2 ……… 3599 Caio Tizio Ing 2 3600 Busti Lina Let 2 ……… Esempio: Ricerca di 4400 7800 4128 Rossi Maria Let 2 8900 4129 Mous Michi Agr 1 ……… 7400 Pinco Palla Ing 2 … G. Mecca - [email protected] - Basi di Dati 14 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> B+ Tree B+ Tree Vincoli aggiuntivi l’albero deve essere bilanciato l’occupazione dei blocchi deve essere almeno il 50% Algoritmi di inserimento e cancellazione rispettare i vincoli fusioni e divisioni (possono coinvolgere vari livelli) A regime blocchi pieni per i 2/3 (67% circa) G. Mecca - [email protected] - Basi di Dati 15 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> B+ Tree Radice B+ Tree 2 3 5 13 13 14 16 17 19 17 20 24 30 24 25 27 30 33 34 38 39 inserimento del valore 4 Nuova Radice 17 4 2* 3* 4* 24 13 5* 13* 14* 16* G. Mecca - [email protected] - Basi di Dati 19* 20* 24* 30 25* 27* 30* 33* 34* 38* 39* 16 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> B+ Tree B+ Tree in Pratica Ordine tipico: 200 numero medio di puntatori 133 (molto alto) Capacità di Indicizzazione: profondità 4: 1334 = 312.900.700 blocchi profondità 3: 1333 = 2.352.637 blocchi I livelli più alti possono essere tenuti nel buffer: Livello 1: Livello 2: Livello 3: 1 blocco = al più 8 Kbyte 133 blocchi = al più 1 Mbyte 17.689 blocchi = al più 133 MBytes G. Mecca - [email protected] - Basi di Dati 17 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> B+ Tree B+ Tree Vantaggi inserimenti logaritmici meno costosi che in un file ordinato ricerche rapide accesso ordinato secondo la chiave di ordinamento è possibile aggiungere indici secondari In generale ha prestazioni migliori della struttura ISAM è utilizzata dalla maggior parte dei DBMS (VSAM) G. Mecca - [email protected] - Basi di Dati 18 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing Hashing E’ possibile ottenere tempo di inserimento costante ? tempo di ricerca costante ? es: matricola=1234 in tempo costante Hashing ricerche in tempo lineare nella lunghezza della chiave File Hash Indice Hash G. Mecca - [email protected] - Basi di Dati 19 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing File Hash Idea è possibile utilizzare una funzione di hash per inserire i record nel file e poterli recuperarli in tempo praticamente costante successivamente organizzazione alternativa ai file heap e ai file ordinati Hashing statico (simile a ISAM) Hashing dinamico (simile a B+ Tree) G. Mecca - [email protected] - Basi di Dati 20 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing File Hash 3122 QueloPaolo Sci 2 4775 Mous Michi Agr 1 9876 Rossi Maria null 3 h(k) Valore della chiave k 0 … … … … 1 5442 Rossi Mario Ing 1 .. 2 3 h 2112 Birillo Giulio Let 2 7771 Verdi Luigi Sci 3 3425 Neri Paolo Sci 2 … N-1 Funzione di hash h puntatori ad N blocchi es: (a+k*b) mod N G. Mecca - [email protected] - Basi di Dati … … … 6779 Caio Tizio Ing .. 2 … 1234 Busti Lina Let 2 … .. … … … 21 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing File Hash Organizzazione alternativa a file heap e file ordinati File hash statici Numero di bucket = N N Blocchi iniziali per il file allocati staticamente Blocchi di overflow G. Mecca - [email protected] - Basi di Dati 22 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing File Hash Statico 3122 QueloPaolo Sci 2 4775 Mous Michi Agr 1 h(k) Valore della chiave k 9876 Rossi Maria null 3 8663 Stop John Sci 3 0 … 3442 Mira Lanza Ing 2 1 5442 Rossi Mario Ing 1 9777 Caro Pino Ing 3 … … … .. 2 3 h 2112 Birillo Giulio Let 2 7771 Verdi Luigi Sci 3 3425 Neri Paolo Sci 2 … N-1 Puntatori agli N blocchi tipicamente in RAM G. Mecca - [email protected] - Basi di Dati … … … 6779 Caio Tizio Ing .. 2 … 1234 Busti Lina Let 2 … .. … … … 23 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing File Hash Dinamico (Cenni) Il numero di blocco può crescere dinamicamente N Blocchi iniziali per il file Quando un blocco si riempie, il numero di blocchi viene raddoppiato Servono funzioni di hash appropriate G. Mecca - [email protected] - Basi di Dati 24 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing Indice Hash Indice per un file primario File primario tipicamente heap Indice memorizzato con organizzazione hash su una chiave di ricerca Vantaggi inserimenti e ricerche molto efficienti utile per correlazioni tra tabelle diverse es: nome degli studenti che hanno sostenuto l’esame di analisi G. Mecca - [email protected] - Basi di Dati 25 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing Indice Hash h(k) Valore della chiave k 5442 3122 QueloPaolo Sci 2 9876 4775 Mous Michi Agr 1 2112 9876 Rossi Maria null 3 0 6779 … 1 8723 5442 Rossi Mario Ing 1 2 9112 3 h … … … … .. 2112 Birillo Giulio Let 2 7771 Verdi Luigi Sci 3 N-1 4775 3425 Neri Paolo Sci 2 3122 … 1234 6779 Caio Tizio Ing … 7771 … … .. 2 … 9543 3224 G. Mecca - [email protected] - Basi di Dati 1234 Busti Lina Let 2 … .. … … … 26 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> In pratica In Pratica File ordinati + Indici Multilivello ricerche logaritmiche (con base molto alta) ordinamento inserimenti logaritmici (con ristrutturazioni nel caso di B+ tree) File heap + Indici Hash inserimenti efficienti ricerche efficienti non supporta l’ordinamento In sintesi: non esiste l’organizzazione ideale G. Mecca - [email protected] - Basi di Dati 27 DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> In pratica In Pratica MySQL tabelle ISAM, MyISAM, Heap (+ InnoDB, BDB) indici B+ Tree, Hash PostgreSQL tabelle in file ordinati indici B+ Tree, Hash (+ R Tree) operatore CLUSTER G. Mecca - [email protected] - Basi di Dati 28 DBMS Relazionali – Modello Fisico >> Sommario Concetti Avanzati Obiettivo Indici Multilivello Indici e tabelle ISAM B+ Tree Indici Hash File hash Indice hash In Pratica G. Mecca - [email protected] - Basi di Dati 29 Termini della Licenza Termini della Licenza This work is licensed under the Creative Commons AttributionShareAlike License. To view a copy of this license, visit http://creativecommons.org/licenses/by-sa/1.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA. Questo lavoro viene concesso in uso secondo i termini della licenza “Attribution-ShareAlike” di Creative Commons. Per ottenere una copia della licenza, è possibile visitare http://creativecommons.org/licenses/by-sa/1.0/ oppure inviare una lettera all’indirizzo Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA. G. Mecca - [email protected] - Basi di Dati 30