Organizzazione dei file e indici
Strutture fisiche di accesso
Organizzazione dei file e indici
1. Introduzione agli indici
2. Diverse strutture dati per gli indici
Antonella Poggi
Dipartimento di Informatica e Sistemistica “Antonio Ruberti”
Università di Roma “La Sapienza”
3. Confronto tra diverse organizzazioni di file
Anno Accademico 2003/2004
http://www.dis.uniroma1.it/∼lenzerini/didattica/sistemigestionebasidati/
Antonella Poggi
Organizzazione dei file e indici
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 3
Richiamo: Organizzazione di file
¾ La più semplice organizzazione di file è quella di un
file disordinato (file heap).
1. Introduzione agli indici
2. Diverse strutture dati per gli indici
3. Confronto tra diverse organizzazioni di file
ƒ I data record sono memorizzati in ordine casuale attraverso
le pagine del file.
→ Efficienza dell’inserimento di un nuovo data record
→ Pb: Costo della ricerca di un data record in particolare
¾ E’ anche possibile memorizzare il file in modo tale
che sia ordinato (file ordinato).
→ Efficienza della ricerca di un data record, o di un intervallo di
data record
→ Pb: Costo dell’inserimento di un nuovo data record
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 2
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 4
1
1.1. Indice
1.2. Data Entry
¾ Un indice è una struttura dati ausiliaria che organizza
i record nel disco in modo tale da ottimizzare le
operazioni di estrazione dei dati base al valore di un
campo chiave di ricerca dell’indice.
¾ Un indice contiene una collezione di data entry,
dove un data entry k* contiene l’informazione
sufficiente ad estrarre i record che hanno k come
valore del campo chiave di ricerca.
ƒ Un qualsiasi sottoinsieme dei campi di una relazione può
essere il campo di ricerca chiave dell’indice nella relazione.
ƒ Una chiave di ricerca NON è da confondere con la chiave
della relazione (insieme minimale di campi che identifica
univocamente un record in una relazione).
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 5
Antonella Poggi
1.1. Indice (continua)
¾ Un indice è anche detto struttura di accesso in
quanto permette di localizzare, in modo più efficiente,
i data record di interesse.
™ Si può organizzare il file dei data record sugli impiegati in
base all’età. Il file costituisce un indice il cui campo chiave di
ricerca è l’età degli impiegati. Si può poi creare un indice
basato sullo stipendio che permette di localizzare i data
record che soddisfano una certa query sullo stipendio.
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 6
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 7
1.2. Data Entry (continua)
¾ 3 principali modi di memorizzare un data entry:
1) k* è un data record (con chiave di ricerca pari a k)
→indice è un caso particolare di organizzazione di file
2) k* è una coppia (k,rid), dove rid è l’identificatore di un data
record con chiave di ricerca pari a k
→indice indipendente dall’organizzazione del file
3) k* è una coppia (k, rid-lista), dove rid-lista è una lista di
identificatori di data record con chiave di ricerca pari a k
→indice indipendente dall’organizzazione del file; migliore
utilizzazione dello spazio ma data entry di lunghezza
variabile
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 8
2
1.3. Indici clusterizzati
¾ Dicesi che un indice è clusterizzato quando l’ordine
dei suoi data entry è identico (o simile) all’ordine dei
data record nel file che permette di accedere.
CLUSTERIZZATO
NON CLUSTERIZZATO
Data entry
1.3. Indici clusterizzati (continua)
¾ Ci può essere un unico indice clusterizzato per data
file!
N.B. Nella pratica, i file non sono che raramente mantenuti in
ordine (troppo costoso: a fronte di inserimenti o cancellazione è
necessario mantenere l’ordine!). Pertanto, tipicamente, un
indice clusterizzato è un indice che usa l’alternativa 1), mentre
gli altri tipi di indici non sono clusterizzati.
Data entry
File indice
File di data
record
Data record
Antonella Poggi
Sistemi di gestione di basi di dati
Data record
Strutture fisiche di accesso - 9
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 11
1.3. Indici clusterizzati (continua)
1.4. Indici primari e secondari
¾ Un indice i cui data entry sono memorizzati come
nell’alternativa 1) è clusterizzato per definizione.
¾ Per le altre alternative, un indice è clusterizzato solo
se i data record sono ordinati in base al campo
chiave di ricerca.
¾ Forte variazione del costo di estrazione di un
intervallo di valori, a seconda che il file sia
clusterizzato o meno.
¾ Dicesi indice primario un indice su di un insieme di
campi che include la chiave primaria di una relazione.
Altrimenti un indice è detto indice secondario.
¾ Diconsi duplicati due data entry che hanno lo stesso
valore per il campo chiave di ricerca.
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 10
→ Un indice primario non può contenere duplicati
→ Un indice secondario può contenere duplicati
→ Se non esistono duplicati in un indice secondario, allora il
campo chiave di ricerca contiene una chiave candidata: si
dice che l’indice è unique.
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 12
3
1.5. Indici sparsi e indici densi
¾ Si dice che un indice è denso se ogni valore del
campo chiave di ricerca presente sul data file ha
almeno un corrispondente data entry. Altrimenti si
dice che l’indice è sparso.
1.5. Indici sparsi e indici densi (continua)
¾ Un indice i cui data entry sono memorizzati come
nell’alternativa 1) è denso per definizione.
¾ Un indice sparso è più piccolo di un indice denso!
¾ Un indice sparso è per forza clusterizzato!
→ al massimo un indice sparso per data file!
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 13
Antonella Poggi
1.5. Indici sparsi e indici densi (esempio)
Azzurri, 20,3000
Bianchi, 50,5004
Gialli, 28,3500
Azzurri, 20,3000
Lilla, 30,4000
Viola, 26,5000
Indice sparso
sul nome
Lilla, 30,4000
Neri, 40,6003
Rosa, 35,4500
Rossi, 44,3000
Verdi, 22,6003
40
20
28
50
35
44
22
30
Viola, 26,5000
Data File
Antonella Poggi
Sistemi di gestione di basi di dati
Indice denso
sull’età
Strutture fisiche di accesso - 14
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 15
1.6. Indici semplici e composti
¾ Dipende da quanti campi formano la chiave di
ricerca:
ƒ chiave di ricerca semplice se un solo campo, altrimenti
composta.
¾ Se chiave composta, allora una query in base a
criterio di uguaglianza (equality query) è una query in
cui il valore di ogni campo della chiave è fissato,
mentre una query in base ad un intervallo di valori
(range query) è una query che fissa solo alcuni campi
e lascia libero il valore per i campi non specificati.
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 16
4
1.6. Inidici semplici e composti (esempio)
20,4000
22,6003
30,3000
40,6003
Azzurri, 20,4000
<età, stip>
Bianchi, 30,3000
3000,30
4000,20
6003,22
6003,40
Verdi, 22, 6003
20
22
30
40
3000
4000
6003
6003
<stip, età>
<stip>
Data entry in indice
ordinato in base <stip,età>
Data entry in indice
ordinato in base <stip>
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 17
1.6. Indici semplici e composti
(osservazioni)
¾ Un indice composto supporta un maggior numero di
query ed, inoltre, dato che l’indice contiene più
campi, attraverso l’accesso al solo indice si riesce ad
estrarre più informazione (cf. index-only evaluation).
¾ Un indice composto necessita più di frequente di
essere aggiornato (a seguito di ogni operazione che
modifica uno qualsiasi dei suoi campi).
Antonella Poggi
Sistemi di gestione di basi di dati
1. Introduzione agli indici
2. Diverse strutture dati per gli indici
<età>
Neri, 40, 6003
Data records ordinati
in base al nome
Organizzazione dei file e indici
Strutture fisiche di accesso - 18
3. Confronto tra diverse organizzazioni di file
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 19
2.1. Indice che utilizza una funzione di hash
¾ Data entry organizzati in gruppi, chiamati bucket.
¾ Un bucket consiste in:
ƒ una pagina, chiamata pagina primaria
ƒ eventualmente, ulteriori pagine (dette di pagine di overflow)
collegate alla pagina primaria.
¾ Il bucket a cui un data entry appartiene può essere
determinato applicando una funzione detta di hash
alla chiave di ricerca.
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 20
5
2.1. Indice che utilizza una funzione di hash
(continua)
2.1.1. Esempio (continua)
¾ Numero fissato N di pagine primarie (N=numero di
bucket)
ƒ allocate sequenzialmente
ƒ mai de-allocated
ƒ pagine in overflow se necessario.
età
¾ h(k) mod N = bucket a cui appartiene il data entry con
chiave k
h(k) mod N
chiave k
h(età)=00
h1
Rossi, 44,3000
3000
Neri, 40,6003
5004
....
….
Bianchi, 50,5004
6003
h(età)=10
0
2
Verdi, 22,6003
Data file
sugli impiegati
h
h(stip)=00
h2
stipendio
h(stip)=11
6003
File di data entry
(stip,rid)
N.B. Uno o più campi qualsiasi possono rappresentare la chiave di
N-1
Pagine primarie
Antonella Poggi
Pagine in overflow
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 21
ricerca di un indice: non è necessario che identifichi in maniera
univoca un data record!
™ Nell’indice sullo stipendio due data entry hanno la stessa chiave
6003.
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 23
2.1.1. Esempio
2.1.2. Osservazioni
™ File di data record sugli impiegati organizzato
secondo la funzione di hash h1 (alternativa 1), dove
h1 restituisce le 2 cifre meno significative dell’età
tradotta in binario.
™ Ulteriore indice (alternativa 2) in cui i data entry sono
coppie (stipendio,rid)
¾ La presenza delle pagine di overflow rallenta il tempo
di ricerca in quanto è necessario richiedere
un’operazione di ingresso-uscita per ogni pagina a
partire da quella primaria.
ƒ rid rappresenta il puntatore al data record con chiave pari a
stip
ƒ utilizza h2 (simile ad h1) per localizzare i data entry
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 22
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 24
6
2.1.2. Osservazioni (continua)
¾ L’hashing è la tecnica più efficiente per accedere a
dati in base a predicati di uguaglianza con valori
definiti nell’uguaglianza.
¾ Inefficiente per interrogazioni che richiedono
l’accesso ad intervalli di valori.
2.2. Indice che utilizza una struttura ad
albero (continua)
¾ La struttura tipica di ciascun nodo intermedio di un
albero (inclusa la radice) è la seguente:
P0
K1
P1
K2
Km
Pm
ƒ Sequenza di m+1 puntatori separati da diversi valori ordinati
della chiave di ricerca.
ƒ Il puntatore Pi-1 alla sinistra della chiave Ki (1 ≤ i ≤ m) punta
al sottoalbero che contiene solo data entry relativi a valori di
chiave strettamente inferiori a Ki.
ƒ Il puntatore Pi alla sinistra della chiave Ki punta al sottoalbero
che contiene solo data entry con chiavi superiori a Ki.
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 25
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 27
2.2. Indice che utilizza una struttura ad
albero
2.2. Indice che utilizza una struttura ad
albero (continua)
¾ I data entry sono organizzati in diverse pagine in
base al valore del campo chiave di ricerca.
¾ Le ricerche sono dirette verso la pagina corretta dei
data entry, mediante l’utilizzo di una struttura dati
gerarchica di ricerca.
¾ Il numero medio di figli per un nodo intermedio è
detto fan-out dell’albero.
¾ Con buona approssimazione, dato un albero con
altezza h e fan-out F, si ha che il numero di foglie è
pari a Fh.
ƒ Ogni nodo coincide con una pagina.
ƒ Le pagine con i data entry costituiscono le foglie dell’albero.
ƒ Tutte le ricerche cominciano dalla radice e finiscono su una
foglia: importante usare alberi con altezza minima!
ƒ I legami fra nodi vengono stabiliti da puntatori che collegano
fra loro le pagine.
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 26
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 28
7
2.2.1. Struttura ad albero di tipo B+-tree
2.2.2. Ricerca con indice ad albero di tipo
B+-tree: osservazioni
¾ Alberi bilanciati (in altezza), in cui la lunghezza del
cammino dalla radice ad una foglia è la stessa per
tutte le foglie.
¾ Ogni nodo contiene un numero paragonabile di tuple
m, con d <= m <= 2d tuple, dove d è chiamato
ordine dell’albero.
¾ Foglie collegate da lista in base all’ordine sulla chiave
¾ Il numero di operazioni di ingresso-uscita che
occorrono durante una ricerca è al più pari alla
lunghezza del cammino dalla radice alle foglie:
logFN, con N numero totale di foglie
¾ Si fa in modo che ogni nodo abbia un numero di
discendenti grande (che dipende dalla dimensione
della pagina):
→ Utile per le interrogazioni in cui il predicato definisce un
intervallo di valori ammissibili:
• si accede al primo valore dell’intervallo (con una normale
ricerca)
• si scandiscono uno dopo l’altro i nodi foglia dell’albero
fino a trovare valori di chiave maggiori dell’estremo
superiore dell’intervallo.
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 29
→ tipicamente il fan-out è almeno pari a 100
→ alberi con numero limitato di livelli
→ maggioranza delle pagine occupata da nodi foglia
Antonella Poggi
2.2.2. Ricerca con indice ad albero di tipo
B+-tree: esempio
™ Si cercano i data entry con 24 < età ≤ 44
→ Ricerca diretta verso foglia con primo data entry di interesse.
→ Tutte le foglie sono collegate da una lista: si recuperano così
quei data entry in F2 e F3 che soddisfano il criterio di
ricerca.
Inizio ricerca
12
età < 12
3
78
12 ≤ età < 78
19
9
età > 78
56
86
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 31
2.2.3. Osservazioni
¾ Gli alberi di tipo B+-tree costituiscono la tecnica
ideale per accedere a dati compresi in un intervallo di
valori.
¾ Sono anche buoni per accedere a dati in base a
predicati di uguaglianza con valori definiti
nell’uguaglianza.
94
19 ≤ età < 56
…
…
F1
FOGLIE
Verdi, 22,6003
Viola, 26,5000
Antonella Poggi
… …
33
44
…
…
… …
F2
F3
Neri, 40, 6003
Rossi, 44,3000
Bianchi, 50,5004
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 30
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 32
8
Organizzazione dei file e indici
1. Introduzione agli indici
2. Diverse strutture dati per gli indici
3.2. Modello di costo
(in termini di tempo di esecuzione)
¾ B: numero di pagine non vuote del data file.
¾ R: numero di data record per pagina.
¾ D: tempo medio di scrittura/lettura di una pagina su
disco.
ƒ Tipicamente (oggi): 15 ms
3. Confronto tra diverse organizzazioni di file
¾ C: tempo medio di elaborazione di un data record
(es. confronto di un campo con costante di
selezione).
ƒ Tipicamente (oggi): 100 ns
→operazioni di I/O dominanti!
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 33
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 35
3.1. Setting di confronto
3.2. Modello di costo (continua)
¾ Confronto sul costo di semplici operazioni su diverse
organizzazioni di file per una collezione di data
record sugli impiegati di una società.
¾ In caso di file con struttura di accesso, il costo delle
operazioni di selezione viene calcolato assumendo
che l’indice sia composto e che le operazioni vertano
su almeno il primo campo della chiave di ricerca
composta (altrimenti costo uguale al caso di file non
ordinato)
¾ Modello che si concentra sui costi delle operazioni di
ingresso-uscita (I/O).
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 34
ƒ C semplicisticamente considerata costante.
¾ I sistemi reali devono considerare anche:
ƒ Tempi di CPU
ƒ Costi delle trasmissioni via rete nelle basi di dati distribuite
¾ Costo delle operazioni di I/O basato sul numero di
pagine lette/scritte su disco
ƒ Semplicistico: tipicamente è possibile accedere ad un blocco
di pagine contigue mediante una singola operazione di I/O.
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 36
9
4.1. Setting di confronto:
semplici operazioni sui dati
1. Scansione di tutti i data record di un file.
ƒ
ƒ
Costo del caricamento delle pagine del file nel buffer
Costo CPU per localizzare ogni data record nella pagina
2. Selezione in base a predicati di uguaglianza.
ƒ
ƒ
Caricamento delle pagine con data record di interesse
Localizzazione dei data record di interesse nelle pagine
caricate
3. Selezione in base a predicati che vertono su di un
intervallo di valori.
ƒ
idem
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 37
3.3.A. Heap file
1. Scansione:
B(D+RC)
ƒ
ƒ
Per ogni pagina (B) non vuota del file: caricamento
Per ogni data record (R): elaborazione (C)
2. Selezione in base a criterio di uguaglianza:
B(D+RC)
→ il data record può essere assente o può essercene più di
uno
3. Selezione in base ad un intervallo di valori:
B(D+RC)
Antonella Poggi
4.1. Setting di confronto:
semplici operazioni sui dati (continua)
ƒ
Costo dell’identificazione della pagina nel file
ƒ
Caricamento della pagina
ƒ
Modifica della pagina
ƒ
Scrittura su disco della pagina modificata
ƒ
Eventualmente, caricamento, modifica e scrittura di altre
pagine
idem
Sistemi di gestione di basi di dati
3.3.A. Heap file (continua)
ƒ
ƒ
ƒ
caricamento dell’ultima pagina
inserimento nell’ultima pagina
scrittura
5. Cancellazione
5. Cancellazione di un data record.
Antonella Poggi
Strutture fisiche di accesso - 39
4. Inserimento: D+C+D
4. Inserimento di un data record.
ƒ
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 38
Se dato record identificato dall’rid: D+C+D (pagina identificata
direttamente da rid)
ƒ Se data record specificato in base a criterio di uguaglianza o
intervallo di selezione: B(D+RC)+XC+YD
• X numero di data record da cancellare
• Y numero di pagine con almeno un data record da cancellare
N.B. Abbiamo considerato trascurabile il tempo necessario a
compattare file in seguito a nuovo spazio libero.
ƒ
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 40
10
3.3.B. File ordinato
1. Scansione: B(D+RC)
2. Selezione basata su criterio di uguaglianza:
D log2B+C log2R (caso peggiore)
ƒ
ƒ
Ricerca binaria della pagina con (primo) data record di
interesse (se pagine memorizzate sequenzialemente)
• log2B passi per localizzare la pagina
• ad ogni passo, operazione di I/O + 2 confronti (che
rispetto all’operazione di I/O si possono trascurare)
Ricerca binaria del (primo) data record di interesse: C log2R
3. Selezione in base ad un intervallo di valori:
ƒ
ƒ
Ragionamento analogo
Eventuale costo di caricamento di ulteriori pagine (se data
record che soddisfano criterio riempiono più pagine)
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 41
3.3.B. File ordinato (continua)
4. Inserimento:
D log2B+C log2R + C+ 2B (D+RC)
ƒ
ƒ
ƒ
ƒ
Caso peggiore: in prima posizione, nella prima pagina
Costo di ricerca della corretta posizione nel file (cf.
selezione in base a criterio di uguaglianza): D log2B+C
log2R
Inserimento del data record: C
Caricamento e scrittura di tutte le altre pagine: 2B(D+RC)
5. Cancellazione:
ƒ
ƒ
Sistemi di gestione di basi di dati
Premesse:
studi empirici hanno dimostrato che in un data file
clusterizzato, le pagine sono riempite per il 67%
→ numero di pagine diventa B’=1.5B
ƒ F è il numero di fan-out della struttura ad albero
ƒ
1. Scansione: 1.5B(D+RC)
2. Selezione basata su criterio di uguaglianza:
DlogF(1.5B)+Clog2R
localizzazione della (prima) pagina con data record di
interesse
ƒ localizzazione del (primo) data record con ricerca binaria
N.B. Nella pratica, la radice è sempre nel buffer in quanto è
acceduta di frequente → si risparmia un’operazione di I/O!
ƒ
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 43
3.3.C. File clusterizzato con struttura di
accesso ad albero B+-tree (continua)
3. Selezione in base ad un intervallo di valori:
ƒ
ƒ
come per selezione in base a criterio di uguaglianza
eventualmente ulteriori operazioni di I/O se data record di
interesse comprese in altre foglie (collegate)
4. Inserimento: DlogF(1.5B)+Clog2R+C+D
ƒ
ƒ
costo di ricerca + inserimento + scrittura
ignoriamo costi aggiuntivi che si presentano quando
l’inserimento deve avvenire in una pagina piena (casi rari!)
5. Cancellazione
Ragionamento analogo
Se condizione di cancellazione basata su criterio di
uguaglianza o appartenenza ad un intervallo di valori, costo
dipende dal numero di data record da cancellare.
Antonella Poggi
3.3.C. File clusterizzato con struttura di
accesso ad albero B+-tree
Strutture fisiche di accesso - 42
ƒ
ƒ
come per l’inserimento (se un solo data record da
cancellare)
eventualmente ulteriori operazioni di cancellazione e di I/O
se più data record da cancellare comprese in altre foglie
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 44
11
3.3.D. Heap file con indice ad albero non
clusterizzato
Premesse:
Un data entry di una foglia dell’indice ha una dimensione
pari a un decimo di un data record sugli impiegati
→ numero di foglie dell’indice: 0.1(1.5B)=0.15B
→ numero di data entry in una pagina di indice:
10(0.67R)=6.7R
ƒ F è il numero di fan-out della struttura ad albero
ƒ
1. Scansione: 0.15B(D+6.7RC) + BR(D+C)
ƒ scansione di tutte i data entry dell’indice: 0.15B(D+6.7RC)
→ costo trascurabile!
ƒ ogni data entry in una foglia dell’indice può puntare ad una
pagina differente: BR(D+C)
→ costo proibitivo!
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 45
3.3.D. Heap file con indice ad albero non
clusterizzato (continua)
2. Selezione in base a criterio di uguaglianza:
DlogF(0.15B)+Clog2(6.7R)+XD
localizzazione della (prima) pagina dell’indice con data entry di
interesse: DlogF(0.15B)
ƒ ricerca binaria del (primo) data entry: Clog2(6.7R)
ƒ X: numero di data record che soddisfano il criterio
→ un’operazione di I/O per ognuna
ƒ
3. Selezione basata su di un intervallo di valori:
ƒ ragionamento analogo
N.B.
→ Costo dipende dal numero di data record da selezionare (può
diventare proibitivo!)
→ Sia per la scansione che per la selezione, a volte può convenire non
utilizzare l’indice, ordinare il file ed effettuare le operazioni
direttamente sul file!
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 46
3.3.D. Heap file con indice ad albero non
clusterizzato (continua)
4. Inserimento:
2D+C+ DlogF(0.15B)+Clog2(6.7R)+D
ƒ
ƒ
ƒ
inserimento nel file di data record (non ordinato): 2D+C
ricerca della posizione corretta nell’indice per inserire il data
entry: DlogF(0.15B)+Clog2(6.7R)
scrittura della corrispondente pagina dell’indice: D
5. Cancellazione (caso di un solo data record ):
DlogF(0.15B)+Clog2(6.7R)+D+2(C+D)
ƒ
ƒ
ƒ
ricerca del data entry: DlogF(0.15B)+Clog2(6.7R)
caricamento della pagina con data record da cancellare: D
modifica+scrittura delle pagine modificate dell’indice e del
file: 2(C+D)
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 47
3.3.E. Heap file non clusterizzato con indice
basato su funzione di hash
Premesse:
Data entry di dimensione pari ad un decimo di un data
record
ƒ Trascuriamo le pagine in overflow
ƒ Pagine primarie piene all’80% (per lasciare spazio a futuri
inserimenti)
→ numero di pagine dell’indice: 1.25(0.10B)=0.125B
→ numero di data entry in una pagina: 10(0.80R)=8R
ƒ H tempo di calcolo della funzione di hash
ƒ
1. Scansione: BR(D+C)+0.125B(D+8RC)
→ costo proibitivo!
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 48
12
3.3.E. Heap file non clusterizzato con indice
basato su funzione di hash (continua)
2. Selezione in base a criterio di uguaglianza:
H+D+8RC+XD
ƒ
ƒ
ƒ
ƒ
→
calcolo della pagina dell’indice con corretto data entry: H
caricamento della pagina con data entry: D
scansione dei data entry nella pagina: 8RC (caso peggiore)
caricamento delle pagine con data record di interesse: XD
costo dipende dal numero di data record da selezionare
3. Selezione in base ad intervallo di valori:
B(D+RC)
ƒ
indice non utile →scansione dell’intero file!
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 49
3.4. Tabella riassuntiva sul confronto
Tipo di file
Scansione
Ricerca con
criterio di
uguaglianza
Ricerca con
intervallo di
valori
Inserimento
Cancellazione
Heap file
BD
BD
BD
2D
Ricerca
+
D
File ordinato
BD
Dlog2B
Dlog2B +
# pagine
interessate
Ricerca
+
2BD
Ricerca
+
2BD
Indice
clusterizzato
1.5BD
DlogF(1.5B)
DlogF(1.5B) +
# pagine
interessate
Ricerca
+
D
Ricerca
+
D
Indice ad
albero non
clusterizzato
BD(R+
0.15)
D(logF(0.15B)
+ # data rec.
di interesse)
D(logF(0.15B)
+ # data rec.
di interesse)
D(3+
logF(0.15B))
Ricerca
+
2D
Indice con
hashing non
clusterizzato
BD(R+
0.125)
D(1+
# data rec. di
interesse)
BD
4D
Ricerca
+
2D
Antonella Poggi
Sistemi di gestione di basi di dati
3.3.E. Heap file non clusterizzato con indice
basato su funzione di hash (continua)
¾ Inserimento: H+2D+C+2D+C
¾ Cancellazione (caso di un solo data record):
H+D+8RC+D+2(C+D)
calcolo della corretta pagina dell’indice: H
caricamento della pagina con data entry: D
localizzazione del data entry: 8RC (caso peggiore)
caricamento della pagina con data record da cancellare: D
modifica+scrittura delle pagine modificate dell’indice e del
file: 2(C+D)
Antonella Poggi
Sistemi di gestione di basi di dati
3.5. Conclusioni
¾ Heap file:
ƒ calcolo della corretta pagina dell’indice: H
ƒ inserimento del data record nel file non ordinato: 2D+C
ƒ lettura/modifica/scrittura della pagina dell’indice con il data
entry di interesse: 2D+C
ƒ
ƒ
ƒ
ƒ
ƒ
Strutture fisiche di accesso - 51
Strutture fisiche di accesso - 50
ƒ efficiente in termini di occupazione di spazio
ƒ scansione e inserimento veloci
ƒ ricerche e cancellazione lente
¾ File ordinato:
ƒ efficiente in termini di occupazione di spazio
ƒ inserimento e cancellazione lente
ƒ ricerche più veloci rispetto al caso dei file disordinati
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 52
13
3.5. Conclusioni (continua)
¾ Indice clusterizzato:
ƒ piccolo overhead in termini di spazio di occupazione
ƒ inserimento e cancellazione efficienti
ƒ ricerche più veloci rispetto al caso dei file ordinati, tranne
quando vertono su di un grande numero di data record
contigui (grazie ad accesso a blocchi di memoria)
¾ Indici non clusterizzati:
ƒ ricerca con criterio di uguaglianza, inserimento e
cancellazione veloci
ƒ scansione e ricerca con largo intervallo di valori lente
ƒ hashing un pò più veloce con criterio di uguaglianza, ma non
supporta criterio di intervallo di valori!
→ Nessuna organizzazione di file è uniformemente
superiore in tutte le situazioni!
Antonella Poggi
Sistemi di gestione di basi di dati
Strutture fisiche di accesso - 53
14