G. Mecca – [email protected] – Università della Basilicata Basi di Dati Sistemi per BD...
-
Upload
sandro-casini -
Category
Documents
-
view
217 -
download
0
Transcript of G. Mecca – [email protected] – Università della Basilicata Basi di Dati Sistemi per BD...
G. Mecca – [email protected] – Università della BasilicataG. Mecca – [email protected] – Università della Basilicata
Basi di Dati
Sistemi per BD Relazionali:Modello FisicoConcetti Avanzati
versione 2.0
Questo lavoro è concesso in uso secondo i termini di una licenza Creative Commons (vedi ultima pagina)
2G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
Concetti Avanzati
Obiettivo Indici multilivello
Indici e tabelle ISAMB+ Tree (cenni)
Indici HashFile hashIndice hash
In Pratica
DBMS Relazionali – Modello Fisico >> Sommario
3G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
Obiettivo
Strategia di accesso idealeinserimenti e cancellazioni efficienti (t. cost ?)ricerca binariaevitare ordinamenti del file
Gli indici rappresentano un passo avanti Problemi
la ricerca si può miglioraregli inserimenti nei file ordinati sono un pb.
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Obiettivo
4G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
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
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Indici multiliv.
5G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
Indici Multilivello
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Indici Multiliv.
3122
4123
…
9934
…
…
5990
6102
…
8770
8770
…
…
3122
5990
…
7488
NB blocchiNB/bfr blocchi
3122
…
7488
(NB/bfr)/bfr blocchi1 blocco
3554 RossiMario Ing 1
5765 Neri Paolo Sci 2
3456 RossiMaria null 3
… … … … ..
4123 Birillo Giulio Let 2
3122 QueloPaolo Sci 2
4771 Verdi Luigi Sci 3
3453 Mous Michi Agr 1
… … … … ..
5876 Caio Tizio Ing 2
9934 Busti Lina Let 2
… … … … ..
…
6G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
Indici Multilivello
Dinamica logaritmica: logbfr(NB) livelli di indicericerca logaritmica con base bfr>2
Esempiodimblocco=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) = 26ricerca in ceil(log204(1M)) + 1 accessi = 4
Attenzione: tutti i valori devono essere distinti
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Indici multiliv.
7G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
Indici Secondari Multiliv.
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Indici multiliv.
6554 RossiMario Ing 1
8765 Neri Paolo Sci 2
3456 RossiMaria null 3
… … … … ..
7123 Birillo Giulio Let 2
3122 QueloPaolo Sci 2
7771 Verdi Luigi Sci 3
3453 Mous Michi Agr 1
… … … … ..
9876 Caio Tizio Ing 2
9934 Busti Lina Let 2
… … … … ..
…
Birillo
Busti
…
Verdi
Pinco
…
Caio
Rossi
…
blocco di puntatorivalori distinti
8G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
Il Problema degli Inserimenti
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Indici multiliv.
Tutti i livelli sono file ordinaticosto degli inserimenti
Due possibili soluzionistrutture ordinate “statiche”
ISAM
strutture ordinate “dinamiche”B Tree e B+ Tree
9G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
Strutture Ordinate Statiche
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> ISAM
Strutture multilivello in cuispazio per i blocchi allocato staticamentefile ordinato con blocchi contiguiinserimenti effettuati ordinatamente finchè
c’e’ spaziofile disordinato di trabocco (“overflow”)periodiche riorganizzazioni globali con
fusione del file primario e del file di trabocco ISAM: Indexed Sequential Access Method
10G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
Struttura ISAM
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> ISAM
3122
4123
5888
9934
8880
…
5990
6102
7402
87708770
8122
…
3122
5990
6442
7488
3122
7412
7488
3554 RossiMario Ing 1
5765 Neri Paolo Sci 2
3456 RossiMaria null 3
… … … … ..
4123 Birillo Giulio Let 2
3122 QueloPaolo Sci 2
4771 Verdi Luigi Sci 3
3453 Mous Michi Agr 1
… … … … ..
5876 Caio Tizio Ing 2
9934 Busti Lina Let 2
… … … … ..
…
3333 Stop John Sci 3
3442 Mira Lanza Ing 2
5777 Caro Pino Ing 3
Blocchi di overflow
Blocchi contiguidel disco
11G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
Struttura ISAM
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> ISAM
Principali vantaggiallocazione contigua dei blocchi (“località”)la struttura non viene toccata
Svantaggipossono essere necessarie ristrutturazioni
Adatta a tabelle con dinamica limitatapochi inserimenti
12G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
Strutture Ordinate Dinamiche
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> B+ Tree
Strutture multilivello in cuifile ordinato con rappresentazione collegataallocazione dinamica dei blocchii blocchi sono sempre parzialmente pienialgoritmi di inserimento opportuniriorganizzazioni locali (fusioni e divisioni dei
blocchi) B Tree, B+ Tree
13G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
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
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> B+ Tree
14G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> B+ Tree
1240
3121
3121 Verdi Luigi Sci 3
1241 Birillo Giulio Let 2
………
3599 Caio Tizio Ing 2
3122 Neri Paolo Sci 2
………
4128 Rossi Maria Let 2
3600 Busti Lina Let 2
………
7400 Pinco Palla Ing 2
4129 Mous Michi Agr 1
………
…
1240 RossiMario Ing 1
1100 QueloPaolo Sci 2
………
4128
7400
7800
8900
3599
7552
Esempio:Ricerca di 4400
B+ Tree
15G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
B+ Tree
Vincoli aggiuntivil’albero deve essere bilanciatol’occupazione dei blocchi deve essere almeno il 50%
Algoritmi di inserimento e cancellazionerispettare i vincolifusioni e divisioni (possono coinvolgere vari livelli)
A regimeblocchi pieni per i 2/3 (67% circa)
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> B+ Tree
16G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
B+ Tree
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> B+ Tree
Radice
17 24 30
2 3 5 13 14 16 19 20 24 25 27 30 33 34 38 39
13
2* 3*
Nuova Radice
17
24 30
14* 16* 19* 20* 24* 25* 27* 30* 33* 34* 38* 39*
134
13*5*
inserimento del valore 4
17
4*
17G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
B+ Tree in Pratica
Ordine tipico: 200 numero medio di puntatori 133 (molto alto)
Capacità di Indicizzazione:profondità 4: 1334 = 312.900.700 blocchiprofondità 3: 1333 = 2.352.637 blocchi
I livelli più alti possono essere tenuti nel buffer:Livello 1: 1 blocco = al più 8 KbyteLivello 2: 133 blocchi = al più 1 MbyteLivello 3: 17.689 blocchi = al più 133 MBytes
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> B+ Tree
18G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
B+ Tree
Vantaggiinserimenti logaritmici meno costosi che in un file
ordinatoricerche rapideaccesso ordinato secondo la chiave di ordinamentoè possibile aggiungere indici secondari
In generaleha prestazioni migliori della struttura ISAMè utilizzata dalla maggior parte dei DBMS (VSAM)
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> B+ Tree
19G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
Hashing
E’ possibile otteneretempo 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
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing
20G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
File Hash
Ideaè possibile utilizzare una funzione di hash
per inserire i record nel filee poterli recuperarli in tempo praticamente
costante successivamenteorganizzazione alternativa ai file heap e ai
file ordinati Hashing statico (simile a ISAM) Hashing dinamico (simile a B+ Tree)
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing
21G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
File Hash
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing
puntatoriad N blocchi
0
1
2
3
N-1
Funzionedi hash h
h
Valoredella
chiavek
h(k)
es: (a+k*b) mod N
5442 RossiMario Ing 1
3425 Neri Paolo Sci 2
9876 RossiMaria null 3
… … … … ..
2112 Birillo Giulio Let 2
3122 QueloPaolo Sci 2
7771 Verdi Luigi Sci 3
4775 Mous Michi Agr 1
… … … … ..
6779 Caio Tizio Ing 2
1234 Busti Lina Let 2
… … … … ..
…
22G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
File Hash
Organizzazione alternativa a file heap e file ordinati
File hash staticiNumero di bucket = NN Blocchi iniziali per il file allocati
staticamenteBlocchi di overflow
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing
23G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
File Hash Statico
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing
Puntatori agliN blocchi
tipicamente in RAM
0
1
2
3
N-1
h
Valoredella
chiavek
h(k)5442 RossiMario Ing 1
3425 Neri Paolo Sci 2
9876 RossiMaria null 3
… … … … ..
2112 Birillo Giulio Let 2
3122 QueloPaolo Sci 2
7771 Verdi Luigi Sci 3
4775 Mous Michi Agr 1
… … … … ..
6779 Caio Tizio Ing 2
1234 Busti Lina Let 2
… … … … ..
…
8663 Stop John Sci 3
3442 Mira Lanza Ing 2
9777 Caro Pino Ing 3
24G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
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
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing
25G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
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 efficientiutile per correlazioni tra tabelle diverse
es: nome degli studenti che hanno sostenuto l’esame di analisi
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing
26G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
Indice Hash
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> Hashing
5442 RossiMario Ing 1
3425 Neri Paolo Sci 2
9876 RossiMaria null 3
… … … … ..
2112 Birillo Giulio Let 2
3122 QueloPaolo Sci 2
7771 Verdi Luigi Sci 3
4775 Mous Michi Agr 1
… … … … ..
6779 Caio Tizio Ing 2
1234 Busti Lina Let 2
… … … … ..
…
0
1
2
3
N-1
h
Valoredella
chiavek
h(k)
5442
9876
2112
6779
8723
9112
4775
3122
1234
7771
9543
3224
…
27G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
In Pratica
File ordinati + Indici Multilivelloricerche logaritmiche
(con base molto alta)ordinamento inserimenti logaritmici
(con ristrutturazioni nel caso di B+ tree)
File heap +Indici Hashinserimenti efficienti ricerche efficientinon supporta
l’ordinamento
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> In pratica
In sintesi: non esiste l’organizzazione ideale
28G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
In Pratica
MySQLtabelle ISAM, MyISAM, Heap
(+ InnoDB, BDB)indici B+ Tree, Hash
PostgreSQLtabelle in file ordinatiindici B+ Tree, Hash (+ R Tree)operatore CLUSTER
DBMS Relazionali – Modello Fisico >> Concetti Avanzati >> In pratica
29G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
Concetti Avanzati
Obiettivo Indici Multilivello
Indici e tabelle ISAMB+ Tree
Indici HashFile hashIndice hash
In Pratica
DBMS Relazionali – Modello Fisico >> Sommario
30G. Mecca - [email protected] - Basi di DatiG. Mecca - [email protected] - Basi di Dati
Termini della Licenza
Termini della Licenza
This work is licensed under the Creative Commons Attribution-ShareAlike 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.