Organizzazione dei file per database

Nei DBMS l'utilizzo di una memoria secondaria per il salvataggio dei dati si rende necessaria per la dimensione dei dati (nella maggior parte dei casi non c'è memoria principale sufficiente a contenere tutta la base di dati) e per mantenere la persistenza dei dati (come ben saputo, in caso di mancanza di alimentazione la memoria RAM perde i dati al suo interno).

Ma per poter lavorare con la base di dati risulta anche essenziale avere una memoria principale veloce. Il buffer manager è il componente del DBMS che si occupa della sincronizzazione delle due memorie. La struttura e gestione dei buffer e della memoria principale è trattata nella lezione del controllo di affidabilità.

Tipi di memoria secondaria

Tipicamente il disco rigido è da anni la memoria secondaria principalmente utilizzata, anche se oggi viene progressivamente sostituito dal unità a stato solido, più veloce ma non esente da problemi (la sua vita è ancora minore delle corrispondenti unità a disco, soprattutto in ambienti con carico elevato), anche se non mancano applicazioni a nastro magnetico.

Uso del filesystem

I DBMS fanno un uso molto limitato delle opzioni fornite dal filesystem. Sostanzialmente possiamo raggrupparle in:

• Creazione di file
• Eliminazione di file
• Lettura di un blocco o una sequenza di blocchi
• Scrittura di un blocco o una sequenza di blocchi

La struttura interna al blocco e la struttura dei file, sono sempre a carico del DBMS.

Paginazione

Descrizione di un blocco per DB

Ogni DBMS utilizza un sistema di paginazione e accesso alle pagine differente, ottimizzato per varie esigenze specifiche di quel DBMS. Si presenta qui una comune organizzazione generale, la cui struttura è spesso alla base di tutti i moderni DBMS.

Ogni pagina (coincidente con un blocco in memoria di massa) ha una parte identificativa di inizio e fine, dette rispettivamente block header e block trailer, di grandezza di qualche byte, contenenti informazioni riguardanti il blocco in cui è la pagina. A sua volta la pagina ha due campi di informazione che ne specificano la struttura e il contenuto, detti page header e page trailer.

Il contenuto della pagina è scritto come un'architettura a doppio stack contrapposto comprendente:

• Un page dictionary che contiene i riferimenti a tutti gli oggetti contenuti nella pagina
• I dati veri e propri

In questo modo i dati possono crescere allo stesso modo del dizionario senza dover spostare fisicamente i dati. Inoltre è presente un checksum, che verifica l'integrità dei dati.

Si definisce fattore di blocco (o in inglese block factor) il seguente rapporto:

$\lfloor S_{B}/S_{R}\rfloor$

Dove $S_{R}$ indica la dimensione del record e $S_{B}$ la dimensione del blocco. Nel caso di una tabella esso rappresenta il numero di tuple che possono essere contenute in un blocco. Non tutti i DBMS permettono alle tuple di superare la dimensione del blocco (quindi dividersi su più blocchi).

Strutture dei dati

Struttura sequenziale

In una struttura sequenziale, i file che compongono la base di dati contengono informazioni secondo una delle seguenti tre metodologie:

• Sequenza di entrata: l'ordine fisico delle tuple è dettato solo dal loro ordine di inserimento.
  • PRO: molto veloce inserimento e scansione dell'intero file; lo spazio utilizzato è ottimale (usa tutti i blocchi disponibili in maniera sequenziale senza lasciar spazi vuoti)
  • CON: ricerca di un valore particolare lenta, problemi con l'aggiornamento (se una tupla deve crescere di dimensione deve essere spostata, lasciando spazio vuoto non più utilizzabile)
• Struttura ad array: ad ogni tupla è associato un indice e ogni file può essere visto come un grande array con elementi di dimensione fissa.
  • PRO: estremamente veloce, in particolare la ricerca
  • CON: possibile solamente con tuple di dimensione fissa, per questo non usate nei DBMS moderni.
• Ordinamento sequenziale: l'ordinamento delle tuple è determinato da un valore interno alla tupla stessa (come la chiave primaria). Tradizionalmente utilizzato nelle memorie a nastro.
  • PRO: veloci le operazioni che utilizzano la chiave come riferimento
  • CON: inserimento e aggiornamento possono imporre un riordino di tutto il file (alcune varianti risolvono parzialmente il problema: uso file differenziali, alcune parti del blocco vengono lasciate libere per riordinare solo localmente e non l'intera relazione, uso di file overflow, ecc.)

Struttura ad Hash

Esempio di funzione hash senza collisioni su un campo di testo.

La struttura ad hash deriva da una modifica dell'ordinamento sequenziale. Consiste nel trasformare la chiave primaria di ogni tupla attraverso una funzione di hash in un digest utilizzabile in seguito per trovare le tuple in modo rapido (in prima approssimazione si può pensare che la funzione di hash dia un risultato che è un indice di un array che contiene la tupla stessa). Questa struttura è detta anche struttura ad accesso calcolato e si dice abbia un accesso associativo ai dati.

Lo spazio utilizzato del file non deve essere totale, pena problemi di performance. Si stima come miglior rapporto memoria sprecata/performance un utilizzo dell'80%.

Le posizioni dei blocchi sono quindi calcolate tra 0 e x, dove x è il valore massimo della funzione di hash. Nasce però il problema delle collisioni: come risaputo le funzioni hash non sono iniettive, ma se il digest ha dimensione sufficientemente grande, il numero di collisioni può considerarsi minimo. Nel nostro caso però, un digest molto grande non corrisponde solo a un aumento della dimensione dell'indirizzamento stesso, perché parte dello spazio rimarrebbe inutilizzato. A titolo di esempio, si pensi di utilizzare per assurdo la ben nota SHA1 come funzione di hash, sono necessari $2^{160}=1.46\cdot 10^{48}$ blocchi!

Possibile soluzione alle collisioni

Esempio con collisioni, un indice corrisponde a due chiavi diverse

Una possibile soluzione al problema dell'overflow può essere l'utilizzo di una catena di overflow. Il funzionamento è il seguente:

• Si utilizza una funzione di hash relativamente semplice;
• Si verifica se il blocco risultate dalla funzione di hash è già allocato o meno:
  • Se non è allocato, si alloca e il procedimento termina.
  • Se è già allocato, si verifica se nel blocco vi è ancora spazio:
    • Se vi è ancora spazio, si accoda la nuova tupla che ha generato la collisione.
    • Se lo spazio è esaurito, si alloca un nuovo blocco e si inserisce il riferimento in quello precedente ormai pieno.

Possiamo quindi definire il numero B di blocchi necessari:

$B={\frac {T}{f\times F}}$

dove:

• $T$ è il numero di tuple previsto;
• $f$ è il fattore di riempimento (= 0.8 nella situazione ottimale);
• $F$ è il fattore di blocco.

Considerazioni sulle prestazioni

La struttura ad hash presenta ottime prestazioni per l'accesso diretto attraverso la chiave primaria per la tupla. Ben diverso il discorso se si effettuano ricerche su valori non chiave o su intervalli: spesso è necessario estrarre tutte le tuple e confrontarne i valori.

Un altro problema della struttura ad hash è la sua scarsa dinamicità, al crescere della dimensione del file andrebbe modificato in real time il fattore di riempimento, onde evitare un numero di collisioni eccessivo.

Struttura ad albero

La struttura ad albero è un altro metodo classificabile come accesso associativo molto usato nei DBMS relazionali. Si introducono delle nuove chiavi, dette chiavi indice, che affiancano la chiave primaria per permettere una ricerca più efficiente sui campi non chiave primaria (ma chiave indice). A livello fisico un indice, associa un valore dei campi (eventualmente con hash) a un indirizzo di memoria fisica. Un indice è detto primario se contiene all'interno i dati a cui si riferisce, secondario altrimenti. Un file può contenere un solo indice primario, ma più indici secondari.

B-Alberi

Un esempio di un B-tree

I B-alberi sono una struttura dati usata per salvare i dati degli indici. Ogni nodo non foglia contiene una lista (eventualmente un solo elemento) di coppie chiave-puntatore, dove il primo puntatore indica direttamente al blocco che contiene la tupla corrispondente. Le foglie contengono l'effettivo puntatore alla tupla. Il secondo puntatore serve per proseguire la ricerca nel sotto-albero .Si noti che ogni nodo ha $n+1$ figli dove $n$ è il numero di chiavi.

Un esempio banale (come quello indicato in figura) consiste nel verificare partendo dal nodo radice se nella lista di chiavi è presente quella cercata oppure in quale intervallo è presente. Prendendo sempre l'esempio di figura, cercando la chiave 13, dal nodo radice sappiamo di dover cercare nel secondo figlio, a sua volta nel terzo figlio e così via fino alle foglie.

Una versione ottimizzata del B-albero consiste nell'assegnare due puntatori per ogni chiave, assegnando a uno di essi direttamente il puntatore alla chiave cercata, senza dover scorrere tutto il sottoalbero.

B+Alberi

Esempio di un B+Albero

Una variante del B-Albero molto diffusa nei DBMS moderni sono i B+Alberi. Questi differiscono dai precedenti per la struttura dell'ultimo livello dell'albero: i nodi foglia sono connessi in sequenza in base all'ordine imposto dalla chiave. Così si velocizza notevolmente le operazioni di scansione di un intervallo anziché solo quelle di uno specifico valore (nei B-Alberi è necessario scorrere l'albero molte volte per ottenere un intervallo).

Indici in SQL

Per la sintassi SQL si veda questo articolo di Wikibooks in inglese.