Un compito importante della progettazione fisica è quello di definire le strutture di memorizzazione delle tabelle (si parla di organizzazione primaria dei dati) e le strutture ausiliarie di accesso ai dati (organizzazione secondaria dei dati).
Una struttura di memorizzazione per una tabella è una struttura di dati che consente di salvare in memoria i dati della tabella. La memoria degli attuali calcolatori di divide in memoria primaria e memoria secondaria:
Una base di dati viene tipicamente memorizzata in memoria secondaria, e in particolare su dischi magnetici. I motivi sono i seguenti:
Un disco magnetico memorizza una singola unità di informazione (bit) magnetizzando opportunamente un'area del disco. In tal modo è possibile distinguere il valore 0 dal valore 1. I bit sono organizzati in byte, normalmente formati da 8 bit. Il disco è suddiviso in tracce concentriche le quali sono suddivise in blocchi di dimensione fissa che contengono i byte di informazione (di solito da 512 a 8192 byte). Il blocco è l'unità elementare di trasferimento di dati tra la memoria secondaria e principale. Ciò significa che ogni trasferimento di dati coinvolge uno o più blocchi, ma non una frazione. Per leggere un blocco, una testina deve posizionarsi sulla traccia del blocco, aspettare che il disco ruoti sul blocco da leggere, e infine trasferire il contenuto del blocco in memoria centrale. Un blocco è quindi identificato da un indirizzo fisico formato da un numero di traccia e un numero di blocco all'interno della traccia.
La lettura di un blocco coinvolge operazioni meccaniche (lo spostamento della testina, la rotazione del disco) e dunque è una operazione molto lenta rispetto ad una lettura in memoria primaria. Per questo le letture su disco rappresentano il collo di bottiglia delle applicazioni per basi di dati. Scopo della progettazione fisica è trovare le opportune strutture di dati per memorizzare e accedere ai dati che minimizzano il numero di accessi al disco.
Una tabella viene memorizzata per righe su un insieme di blocchi. Nel contesto della progettazione fisica delle strutture di memorizzazione, un attributo viene chiamato campo, una riga viene chiamata record e una tabella viene chiamata file. Un file è dunque un insieme di record formati da campi. I record possono avere dimensione fissa o variabile all'interno del file. Un record a dimensione variabile contiene campi a dimensione variabile (ad esempio, di tipo varchar), oppure campi opzionali, cioè che possono assumere il valore nullo. In questi casi viene usato un separatore per indicare la terminazione del campo.
L'allocazione dei record nei blocchi può essere unspanned, in cui ogni record è interamente contenuto in un blocco, oppure spanned, in cui è possibile allocare un record a cavallo di più blocchi. L'allocazione spanned può essere adottata per risparmiare spazio di memoria (evitando che si formino aree di blocco inutilizzate qualora la dimensione del blocco non è un multiplo della dimensione dei record) e deve essere adottata quando la dimensione dei record è maggiore della dimensione dei blocchi.
L'allocazione dei blocchi di un file su disco può essere:
Ogni file è dotato di un descrittore che contiene l'informazione necessaria alle applicazioni per accedere ai record del file. Questa informazione include gli indirizzi dei blocchi che contengono i record e il formato dei record.
Esistono tre metodi principali per organizzare i record nei file:
Una struttura ausiliaria di accesso, più comunemente detta indice, è una struttura di dati che serve a velocizzare l'accesso ai record in risposta a certe interrogazioni. Gli indici sono strutture ausiliarie e opzionali rispetto alle strutture di memorizzazione dei file e non vanno ad influire sull'organizzazione primaria dei record nei file. Un indice è definito su uno o più attributi di una tabella e, in generale, le interrogazioni che coinvolgono gli attributi indice beneficiano di una maggiore efficienza. Infatti, al fine di trovare un record di cui è noto il valore del campo indice, invece di scandire il file dei dati, è possibile cercare nel file indice, di dimensione molto inferiore rispetto al file di dati, l'indirizzo del blocco che contiene il record. Il relativo blocco è poi caricato in memoria centrale e il record viene cercato nel blocco in memoria centrale.
Il principio su cui si basano gli indici è simile a quello dell'indice analitico di un libro di testo, cioè una lista ordinata di termini associati alle pagine in cui tali termini compaiono nel testo. Per trovare nel testo un certo argomento, è possibile scandire sequenzialmente il libro, oppure, più efficientemente, trovare il termine nell'indice, recuperare il numero di pagina (indirizzo) e infine accedere direttamente alla pagina (blocco) nel testo (file). L'accesso tramite l'indice è più veloce per almeno due ragioni: l'indice contiene meno informazioni del testo. Inoltre i termini nell'indice sono ordinati, dunque è possibile usando una ricerca dicotomica (binaria). Si ricordi che il fattore critico dell'accesso alle basi di dati è il numero di accessi a blocchi del disco. Un indice è sostanzialmente più leggero del relativo file e dunque può essere memorizzato in meno blocchi di disco. L'accesso ai record tramite indice riduce dunque il numero letture su disco.
Si noti che in questo caso tutti i termini del testo compaiono nell'indice. Questo tipo di indici viene detto denso. Inoltre, i termini nel testo non sono ordinati, ad esempio il termine 'relazione' può essere contenuto in una pagina precedente al termine 'entità'. Dunque l'indice è definito su un campo non di ordinamento del file. Indici su campi non di ordinamento vengono detti indici secondari.
Se la struttura primaria di memorizzazione è un file ordinato rispetto ad un campo, un indice sul campo di ordinamento può migliorare comunque l'efficienza dell'accesso ai dati. Prendiamo l'esempio di un dizionario in cui i termini sono inseriti in ordine. Supponiamo di creare un indice analitico dei termini. Nell'indice inseriamo, in modo ordinato, il primo termine di ogni pagina e la relativa pagina. Quindi i termini inseriti nell'indice sono un sottoinsieme dei termini dei dizionario di cardinalità pari al numero delle pagine del dizionario. La ricerca di un termine può dunque avvenire in due modi: mediante una ricerca dicotomica nel dizionario, oppure cercando, mediante una ricerca dicotomica nell'indice, la pagina del termine e successivamente cercando il termine nella relativa pagina del dizionario (anche in quest'ultimo caso si può usare una ricerca dicotomica). Il secondo metodo è più efficiente in quanto l'indice contiene meno termini e, per ogni termine, l'indice contiene meno informazione. Anche in questo caso l'indice occupa meno blocchi di disco e dunque l'accesso tramite indice riduce il numero di letture su disco. Indici su campi di ordinamento vengono detti indici primari. Un indice primario è anche detto sparso in quanto contiene un parte dei valori del campo presenti nel file.
Gli indici visti fin ora sono detti indici di singolo livello. Gli indici multi-livello nascono dalla seguente osservazione. Un indice non è altro che un file ordinato di dati. In particolare, deve essere memorizzato su un insieme di blocchi del disco. Se l'indice è grande, nulla vieta di creare un indice (primario) definito sull'indice stesso. L'indice ottenuto è detto di secondo livello ed è lui stesso un file ordinato di dati. Il processo può essere iterato finchè l'ultimo livello dell'indice è contenuto interamente in un blocco. La struttura risultante assume la forma di un albero in cui la radice è l'ultimo livello e le foglie stanno al primo livello dell'indice. Gli indici multi-livello possono essere definiti a partire da indici primari o secondari e vengono implementati da una struttura di dati nota come B-tree.
Riprendendo l'esempio del dizionario, supponiamo che l'indice analitico occupi più pagine. E' dunque possibile creare un indice dell'indice. L'indice di secondo livello contiene il primo termine per ogni pagina dell'indice di primo livello e la rispettiva pagina nell'indice di primo livello. Supponiamo che l'indice di secondo livello sia contenuto in un'unica pagina, e dunque che il processo di indicizzazione per livelli possa terminare. Per accedere ad un termine del dizionario, procedo come segue: cerco il termine nell'indice di secondo livello ottenendo la pagina relativa all'indice di primo livello, quindi cerco il termine in questa pagina, ottenendo la pagina relativa al dizionario, infine cerco il termine nella pagina del dizionario. Questo processo sembra complicato per un umano ma in realtà per una macchina risulta più efficiente.
E' infine possibile creare indici basati sulla struttura di dati hash. In generale, dato un file, è possibile definire un solo indice primario (di singolo o multi-livello) sul campo di ordinamento (se esiste) e altri indici secondari (di singolo o multi-livello) su campi diversi da quello di ordinamento.
Le interrogazioni più frequenti in una base di dati sono quelle che coinvolgono operazioni di selezione di tuple che soddisfano un certo predicato e operazioni di join tra due tabelle. Ha quindi senso definire degli indici per velocizzare queste operazioni. Ad esempio, consideriamo un tipico esempio di selezione:
select nome, cognome from dipendente where cf = 'ABCDEF89'
Supponiamo che sulla tabella dipendente non vi siano indici. La ricerca del dipendente con codice dato deve necessariamente procedere in modo sequenziale leggendo, nel caso peggiore, tutti i blocchi occupati dalla tabella. Supponiamo ora che vi sia un indice sul campo cf di dipendente. In tal caso, è possibile trovare velocemente il record associato al dipendente con codice dato accedendo all'indice. Nel caso peggiore, solo i blocchi occupati dall'indice più quello che contiene il record cercato vengono letti.
Vediamo un esempio di join:
select lavoro.teatro, dipendente.nome, dipendente.cognome, from lavoro join dipendente on (lavoro.dipendente = dipendente.codice)
Supponiamo che non vi siano indici sulle tabelle lavoro e dipendente. In tal caso, per ogni riga della tabella lavoro devo scandire linearmente la tabella dipendente cercando la riga corrispondente. Occorre dunque leggere tutti i blocchi di disco di entrambe le tabelle. Inoltre, il costo computazionale in memoria centrale di questa strategia è pari al prodotto delle cardinalità delle due tabelle coinvolte.
Supponiamo ora che vi sia un indice sul campo codice, chiave primaria della tabella dipendente. Posso scandire la tabella lavoro e per ogni riga accedere alla tabella dipendente sfruttando l'indice definito sul capo codice. Vi è un risparmio sia in termini di letture su disco (l'indice è più piccolo della tabella e accedo alla tabella dipendente solo per i record che soddisfano la condizione di join) che in termini di costo computazionale in memoria centrale (ad esempio, nel caso di indice di singolo livello, il costo è pari alla cardinalità della tabella lavoro per il logaritmo della cardinalità della tabella dipendente).
Se inoltre vi fosse un indice anche sul campo dipendente, chiave esterna della tabella lavoro, potrei scorrere tale indice invece di scandire la tabella lavoro e accedere ai blocchi della tabella lavoro solo per i record che soddisfano la condizione di join. Avrei dunque un ulteriore riduzione degli accessi al disco.
Vediamo un esempio di ordinamento:
select nome, cogmome, dataDiNascita from dipendente order by dataDiNascita
Se non vi sono indici, le righe della tabella dipendente devono essere ordinate per data di nascita. La presenza di un indice sul campo dataDiNascita implica che i record nell'indice sono ordinati secondo questo campo e dunque non è necessario ordinare le righe della tabella dipendente.
Infine un esempio selezione di tuple in un intervallo:
select nome, cogmome, dataDiNascita from dipendente where dataDiNascita > '1970-01-01'
Se vi è un indice sul campo dataDiNascita, è possibile trovare il primo record che corrisponde alla data '1970-01-01' e poi fornire in risultato tutti i record da questo in poi secondo l'ordine dell'indice.
Si badi bene che gli indici, in quanto strutture ausiliarie, devono essere mantenuti aggiornati qualora la tabella venga aggiornata in modifica, inserimento e cancellazione. In generale gli indici usano strutture di dati, come i B-tree o le tabelle hash, che permettono di implementare in modo efficiente sia la ricerca che le operazioni di aggiornamento dei record. Dunque gli indici favoriscono le interrogazioni di ricerca ma sfavoriscono quelle di aggiornamento (che non coinvolgono ricerche).
Concludiamo con alcuni consigli generali sull'uso degli indici:
Lo standard SQL non prevede comandi per la definizione di strutture di memorizzazione e di indici. Il motivo è che queste strutture sono strettamente legate all'implementazione del sistema e dunque difficilmente uniformabili. Naturalmente, ogni DBMS offre una varietà di strutture di memorizzazione e di indicizzazione e inoltre permette di usare comandi SQL (non standard) per definire entrambi. Generalmente, la struttura di memorizzazione di una tabella viene associata in fase di creazione della tabella. Un indice viene creato col comando create index seguito dal nome dell'indice, nome della tabella e lista degli attributi da indicizzare e rimosso col comando drop index seguito dal nome dell'indice.