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 Fondamentali

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 Fondamentali

Introduzione Memorie

Gerarchia di memorieDischi magneticiBlocchi

Definizione di Modello fisico Strategia di gestione del disco

Paginazione

DBMS Relazionali – Modello Fisico >> Sommario



Strategia di Memorizzazione nei FileRecordFattore di bloccoDirectory del fileFile heap e file ordinati

Strategia di Accesso ai FileIndice primarioIndice secondario



Introduzione

Parliamo del modello fisico dei DBMS relazionalitecniche e strutture per la memorizzazione

permanente delle basi di daties: le tabelle sono salvate in file su disco

Indipendente dal modello logico Notevole impatto sulle prestazioni

DBMS Relazionali – Modello Fisico >> Concetti Fondamentali


Gerarchia di Memorie


CPU

Unità a NastroDisco Magnetico

I/O

…

RAMI livello

in linea, volatileacc. diretto

MB

II livelloin linea, pers. acc. diretto

GB

III livellofuori linea, pers.

acc. sequenziale TB

basedi dati copie della

base di dati


Dischi Magnetici

Superfici magneticheimpressionabili in modo persistente

Tecnologiapiatti rotanti attorno ad un asseletti da testinefissate ad un braccio mobile



Dischi Magnetici

DBMS Relazionali – Modello Fisico >> Dischi Magnetici

Testine

Movimento braccia

Braccia

Piatti


Dischi Magnetici

Organizzazione dei datiblocchi

Bloccounità di lettura e scritturadimensione tipica: 512 byte – 8 Kbyteper leggere un bit è necessario leggere tutto

il blocco in cui è contenuto Accesso diretto ai blocchi (“block id”)



Dischi Magnetici

Tempi di trasferimentomovimento delle testine + lettura

Il movimento prevale1 blocco: 12-60msblocco successivo: 1-2ms

“Clustering”raggruppamento dei dati perché siano

fisicamente vicini su disco



Modello Fisico

Memorizzazione della base di dati in file File di grandi dimensioni

verso i terabytedimensioni non compatibili con la RAM

Accesso ai datii dati devono essere conservati su discoe trasportati nella RAM solo per le elab.



Modello Fisico

Problemi legati alla persistenzaGestione del disco

come accedere efficientemente a blocchi su disco

Memorizzazione dei dati nei filecome codificare efficientemente le tabelle nei file

Ottimizzazione delle operazioni sui filecome effettuare efficientemente le ricerche e gli

aggiornamenti



Modello Fisico

Tre componentiStrategia di gestione del discoStrategia di memorizzazione nei fileStrategia di accesso

Fondamentale per le prestazionile operazioni sulle tabelle vengono

implementate dal DBMS secondo le strategie scelte



Strategia di Gestione del Disco

Buffer Managermodulo che gestisce l’accesso al discolettura e scrittura dei blocchi

Livelli superiori“dammi il blocco X del disco”

Tecnica“buffer” di blocchi in memoria RAM per

limitare l’accesso al disco





Disco Magnetico

...

#101

...

#8292

#8293

...

#16484

#16485

...

#24676

#24677

...

#32868

#32869

...

#41060

...

Buffer Manager

Memoria RAM

blocco del disco #xxx

spazio libero

spazio libero

Area destinata al Buffer

blocco del disco #yyy

blocco del disco #zzz

blocchi da 8 kByte



Algoritmi di paginazionesimili alla gestione della memoria virtuale

Percentuale di successo (“hit ratio”)percentuali di blocchi prelevati dal buffer

L’obiettivo è massimizzare l’hit ratio Parametri su cui intervenire

dimensione del bufferalgoritmi di paginazione



Strategia di Memorizzazione

Record: unità di registrazione nel file Codifica binaria di una ennupla Codifica posizionale

ordinamento degli attributimemorizzazione dei valori in sequenzarappresentazione fisica dei tipi




Dimensioni standard dei campiint, integer: 32 bit, complemento a 2real, float: 32 bit, virgola mobiledouble precision: 64 bit, virgola mobilechar: 8 bit, ASCIIchar(n): n*8 bit, ASCIIdate: 80 bit, ASCII, aaaa-mm-gg



Record, un Esempio


TABLE Studenti(matricola integer NOT NULL PRIMARY KEY, cognome char(20) NOT NULL, nome char(20) NOT NULL, facolta char(10), annoCor integer);

Studenti matricola cognome nome facolta

6554 Rossi Mario Ingegneria

8765 Neri Paolo Scienze

3456 Rossi Maria null

9283 Verdi Luisa Scienze

annoCor

1

2

3

2


Record di Lunghezza Fissa


integer char(20) char(20) char(10) integer

matricola cognome nome facolta

6554 Rossi Mario Ingegneria

annoCor

1

bit 0 31 32 191 192 351 352 431 432 463

4 byte 20 byte 20 byte 10 byte 4 byte

001…110 11010…010010 0110…0010010 1101…0010 000..001

totale: 58 byte, 464 bit



Fattore di blocconumero di record contenuti in un blocco bfr= floor(dimBlocco/dimRecord)

floor: funzione parte intera inferiore Esempio:

dimBlocco = 4096 byte dimBlocco = 512 byte

dimRecord= 58 byte dimRecord= 58 byte

bfr = 70 bfr = 8sfrido = 36 byte sfrido = 48 byte




File: sequenza di blocchi Blocco: sequenza di record Id di record: (id blocco, offset record) Struttura del file

Struttura doppiamente collegataDirectory dei Blocchi (nell’header del file)

lista di puntatori ai blocchi del file Combinazione delle due



Tipi di File

File “heap”organizzazione disordinatai record vengono inseriti in coda

File ordinatoviene mantenuto l’ordine secondo un campo

di ordinamentoi record vengono inseriti secondo l’ordine



File Heap


6554 RossiMario Ing 1

8765 Neri Paolo Sci 2

9283 Verdi Luisa Sci 2

3456 RossiMaria null 3

… … … … ..

5433 PincoPalla Agr 1

7123 Birillo Giulio Let 2

3122 QueloPaolo Sci 2

7771 Verdi Luigi Sci 3

3453 Mous Michi Agr 1

… … … … ..

9876 Caio Tizio Ing 2

record

blocco

intestazionee directory


File Ordinato per Matricola




9283 Verdi Luisa Sci 2


… … … … ..

5433 PincoPalla Agr 1

7123 Birillo Giulio Let 23122 QueloPaolo Sci 2

7771 Verdi Luigi Sci 33453 Mous Michi Agr 1

… … … … ..


intestazione



E’ necessario sceglieredimensione dei blocchiorganizzazione dei file per le tabelle

Prestazioni inaccettabiliE’ necessario avere strutture aggiuntive per

l’accesso ai fileStrategia di Accesso



Strategia di Accesso

Operazioni sul fileAggiornamenti (inserimenti, cancellazioni)Ricerche con condizione (es: annoCor=2) Ricerche in ordine (es: studenti per

matricola) Organizzazione Ideale

inserimenti e cancellazioni efficientiricerca binariaevitare ordinamenti del file



Operazioni sui File Heap

Inserimenti molto rapidiadatto per es. a tabelle temporanee

Ricerche lineari Necessario l’ordinamento

creazione di una copia ordinata1M rec di 100 byte: 15 minuti

Prestazioni inaccettabili per file di grandi dimensioni



Operazioni sui File Ordinati

Inserimenti onerosiricerche e spostamenti

Ricerche binarielog2(NB) accessi, dove NB = num. di blocchi

es: se dimBlocco=2048, dimFile=2G

NB=1M, log2(NB)=20, più ricerca lineare nel blocco

Ordinamentonon necessario per la chiave di ordinamentonecessario per le altre chiavi



Strategia di Accesso

Strutture di accessoinsieme di strutture ausiliarie di accesso al

file utilizzate per migliorare le prestazioni delle operazioni

Indici: file di riferimenti al file primarioinsieme di voci (chiave, rif.) es: indice analit.più maneggevoli perché di dim. minori



Indice sulla Matricola





… … … … ..





… … … … ..


9934 Busti Lina Let 2

… … … … ..

…

directorydell’indice

valore dellachiave di ricerca

puntatore ad un blocco

file di record

3122

7123

…

9934

…

…

puntatori aiblocchi


Indice sulla Matricola

EsempiodimBlocco=2048

dimFile=2G

NBFile =1M, log2(NBFile)=20

numero di record dell’indice = 1Mdimensione record indice = 4byte + 6 bytedimIndice=10M

NBIndice appross. 8192, log2(NBIndice)=13



Tipi di Indici

Indice primarioindice su campo chiave primariafile ordinato secondo il campouno solo per tabella

Indice secondarioindice su un campo non chiave primariafile non ordinato secondo il campovari per tabella (es: su nome e su facolta)



Indice Primario





… … … … ..





… … … … ..



… … … … ..

…

3122

7123

…

9934

…

…


Indice Secondario





… … … … ..





… … … … ..



… … … … ..

…

Birillo

Busti

…

Verdi

Rossi

…

Caio

Rossi

…

puntatori airecord

valoriripetuti

della chiave


Indice Secondario

EsempiodimBlocco=2048, dimFile=2G, dimRecord = 58NBFile =1M, numero di record del file

approssimativamente 32M ricerca lineare: 512K accessi in medianumero di record dell’indice appross. 32Mdimensione record indice = 20 byte + 7 bytedimIndice1G (più o meno la metà del file)NBIndice appr. 512K, log2(NBIndice)=19



In Sintesi

Il modello fisico è molto importanteImpatto notevole sulle prestazioni

Progettazione fisica (DBA)scelta della strategia di gestione del disco

(dimensione buffer, algoritmi di paginazione)scelta della strategia di memorizzazione

(dim. blocchi, file heap o file ordinati)scelta della strategia di accesso

(indici primari e secondari)




Introduzione Memorie

Gerarchia di memorieDischi magneticiBlocchi

Modello fisico Strategia di gestione del disco

Paginazione




Strategia di MemorizzazioneRecordFattore di bloccoDirectory del fileFile heap e file ordinati

Strategia di AccessoIndice primarioIndice secondario



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.

G. Mecca – [email protected] – Università della Basilicata Basi di Dati Sistemi per BD...

Documents

Transcript of G. Mecca – [email protected] – Università della Basilicata Basi di Dati Sistemi per BD...