Patextra

Il principale scopo nell’ordinare le data entry all’interno di un indice è quello di velocizzarne la lettura. L’ordinamento all’interno di un indice non sempre è perciò, come potremmo immaginare, un ordinamento in ordine crescente o decrescente, perché questo potrebbe spesso e volentieri rallentarne la lettura.

Specialmente nel caso che il campo che stiamo ricercando sia un campo esatto (determinato da un’uguaglianza ad esempio, e non da una disuguaglianza) è utile implementare diverse strategie di ricerca delle data entry.

Facendo un esempio: se ci serve sapere quali persone in un dato file di dati hanno 30 anni, e nel mio indice ho raggruppato le persone in base all’età, in ordine crescente, potrebbe succedere che la maggior parte delle persone abbiano più di trent’anni, e in questo caso avrei velocemente la risposta alla mia interrogazione (perché le persone di trent’anni sono tutte all’inizio), ma se l’età media fosse molto inferiore ai trent’anni, sarebbe richiesta una scansione sequenziale di tutte le data entry finché non si arriva al valore 30.

In tal caso i tempi di elaborazione sarebbero molto vicini a quelli di una semplice interrogazione sequenziale al file di dati.

Per questo motivo si usano delle tecniche di indicizzazione particolari, come l’hashing, o gli indici ad albero.

Indici hash

Gli indici hash sono degli indici che fanno uso appunto delle tecniche di hashing. In parole povere l’hash non è altro che una funzione. Questa fa corrispondere ad una stringa qualsiasi, di lunghezza arbitraria, una stringa di lunghezza fissa. Perciò, supponendo di volere un risultato a 8 bit, noi potremo applicare la funzione hash a qualsiasi stringa (quindi alle nostre chiavi di ricerca per esempio) ed ottenerne un numero che va da 0 a 255.

Per questo motivo i record all’interno di un file di dati, o le data entry all’interno di un indice, possono essere organizzati secondo una funzione hash.

Ad esempio, se abbiamo un file contenente le età di un gruppo di persone, queste potranno essere ordinate secondo una funzione hash.

Noi in quest’esempio consideriamo una semplice funzione che fa corrispondere a ogni stringa il suo valore binario, e ne considera le ultime 4 cifre significative, ovvero gli ultimi 4 bit.

In questo modo potremmo dividere i dati in 16 raccolte differenti, chiamate bucket:

0000

0001

0010

0011

E così via, fino a 1111. Ogni bucket può essere composto da una o più pagine. La prima pagina sarà chiamata primaria, le seguenti saranno collegate alla primaria.

Supponiamo di voler ora cercare all’interno del nostro file le persone che hanno 75 anni. Applichiamo la funzione hash a 75: h(75) = 1011, ovvero le ultime 4 cifre significative di 75 tradotto in binario.

Perciò dovremo ricercare questo sottogruppo di persone nel bucket 1011. Il bucket dovrà essere scansionato sequenzialmente, perciò la velocità di soddisfacimento della richiesta dipenderà anche dal numero di pagine del bucket.

Ovviamente l’hashing potrà essere usato anche nel caso di indici strutturati con data entry contenenti il valore k e il rid (indirizzo del registro nel file di dati).

In tal caso sarà l’indice a essere strutturato secondo una funzione hash sulle sue chiavi di ricerca delle data entry.

Chiariamo con un altro esempio:

supponiamo di avere un indice strutturato con una data entry = ( valore della chiave di ricerca, indirizzo del registro ad esso corrispondente).

Se l’indice sarà ordinato sempre sulle età, per ogni età (valore della data entry) avremo un rid che corrisponderà alla posizione di un determinato record con quel valore di età all’interno del file di dati.

Se organizziamo l’indice in base a una funzione hashing uguale alla precedente avremo che ci saranno tanti bucket ognuno dei quali avrà una lista di data entry (k, rid).

Se noi ricerchiamo il valore 75, applicando la funzione hashing ci verrà restituito nuovamente il numero 1011, che ci indicherà in quale bucket dell’indice dovremo cercare. All’interno di questo bucket avremo delle data entry composte dall’età da noi scelta (75, ma anche altre età che finiscono in 1011 come per esempio 27 o 59) e il corrispondente rid all’interno del file di dati.

TUTTE le data entry con valore 75 saranno contenute all’interno del bucket 1011, e questo ci farà risparmiare tanto tempo rispetto a una lettura sequenziale dell’indice.

Indice ad albero

L’indice ad albero è l’alternativa più naturale che ci viene in mente per l’indirizzamento rispetto a un valore che stiamo ricercando. Si parte quindi da una chiave da ricercare che viene sottoposta ad un primo livello dell’albero, chiamato radice per l’appunto. Qui questa chiave viene confrontata con degli intervalli di valori, e a seconda dell’intervallo ove questa rientra si verrà indirizzati a un livello successivo. Qui verrà nuovamente confrontata la chiave di ricerca con dei nuovi intervalli e così via, fino ad arrivare al livello più basso, chiamato livello foglia.

Al livello più basso sono presenti le data entry, che possono essere i records che stiamo ricercando, o i rid riferiti al file dei records per quella determinata chiave di ricerca.

Un albero avrà quindi un percorso, dalla radice alla foglia, intervallato da vari nodi intermedi, ognuno dei quali avrà vari intervalli di selezione, ad ognuno dei quali corrisponderà un puntatore ad un livello inferiore, fino al livello foglia.

L’albero B+ è una struttura di indice che garantisce che il numero dei nodi dalla radice alla foglia, per qualsiasi percorso, sia sempre lo stesso. È così una struttura bilanciata in altezza. Non necessariamente lo deve essere in lunghezza, infatti i puntatori ai livelli inferiori non sono un numero fisso, ma variano a seconda del nodo. Il numero medio di questi è chiamato fan out dell’albero.

Generalmente i puntatori per ogni livello non foglia possono arrivare fino a 100. Si capisce come, in poche operazioni, si possa arrivare al livello foglia, e quindi alle data entry.

Se avessimo ad esempio un fan out pari a 50, un livello di radice ci permetterebbe di indirizzare 50 diversi nodi. Ogni nodo successivo ci permetterebbe di indirizzarne altri 50, e successivamente ancora ogni nodo permetterebbe di indirizzarne altri 50 (sempre in media). Il risultato totale è un indicizzazione totale di 50^3 pagine = 125000 pagine indicizzate in soli tre livelli.

Generalmente il fan out (che si indica con la lettera F) può arrivare anche a 100, con una conseguente indicizzazione di 1000000 di pagine in tre livelli.

Se consideriamo il fatto che ogni livello corrisponde ad un’operazione di I/O, sarà facile notare come in quest’ultimo caso, in tre operazioni più quelle corrispondenti al numero di pagine concatenate alla pagina principale indicizzata abbiamo soddisfatto la richiesta, mentre con una ricerca di tipo binario, come quella esposta a proposito delle tecniche di hashing, avremmo avuto bisogno di log2(1000000)= 20 operazioni in media.

La scelta del tipo di indice da utilizzare dipenderà comunque dal tipo di operazioni che dovremmo attuare più spesso nel nostro database, e sarà oggetto di un prossimo articolo.

In un DataBase Management System è fondamentale l’indicizzazione dei records. Questa è un’operazione che consente spesso di risparmiare tanti accessi di I/O al disco rispetto al semplice accesso sequenziale ai files di record.

Generalmente, infatti, i records sono organizzati in ordine casuale nelle pagine di un file. Questo tipo di file si chiama heap (in inglese significa ‘catasta’, termine che rende bene l’idea).

Quindi ciò che accade quando noi inseriamo ad esempio una tupla all’interno di una tabella è che questa viene inserita dal gestore di spazio su disco dove questo trova spazio, senza un ordine logico.

Quest’ordine logico è proprio ciò che si vuole creare con l’ausilio degli indici.

L’indice sarà perciò una struttura dati volta all’ottimizzazione della lettura dei records del database. L’indice ordinerà i records sul disco secondo un ordine logico che ottimizzerà l’accesso a questi.

Anche l’indice avrà perciò i suoi records, che chiameremo data entry.

Queste potranno essere organizzate diversamente, a seconda delle nostre esigenze. Ad esempio una data entry potrà essere una coppia di dati:

1) il dato in base al quale si riferisce l’indice. Ad esempio se volessimo ottimizzare la ricerca per età di un gruppo di persone potremmo pensare di creare un indice con i valori crescenti delle età delle persone: |età|persona|;

2) il record all’interno del file heap al quale il valore al punto 1 si riferisce (quindi nel caso dell’esempio fatto precedentemente sarà un puntatore a una determinata persona avente quel valore nel campo età): |puntatore a persona|

Questo è soltanto un modo di strutturare l’indice. Un modo simile potrebb’essere quello di avere un solo valore di età e tanti valori di indirizzi, che chiameremo rid. In tal modo lo spazio occupato su disco sarà generalmente inferiore (in quanto per tanti valori uguali nel campo dell’età ne memorizzeremo solo uno, con tutti i suoi indirizzi puntati), ma ci sarà l’incognita della lunghezza delle data entry, che sarà variabile, e dipenderà dal numero di record avente il valore che stiamo cercando. Avremo i dati registrati nel modo: |età|persona1|persona2|persona3|. Come si può notare lo spazio associato ad ogni data entry è variabile.

Un’altra opzione potrebb’essere quella di memorizzare i record effettivi all’interno delle data entry, ovvero creare un duplicato vero e proprio del file heap ordinato secondo un criterio da noi scelto. In tale situazione l’indice corrisponderà a un file di dati vero e proprio, ordinato su un determinato campo.

Indici clustered

Un indice, riferito a una tabella di un database, si definisce clustered quando l’ordinamento delle sue data entry corrisponde a quello del file di dati a cui si riferisce per una determinata chiave di ricerca.

Per questo motivo l’ultimo tipo di indice esposto al paragrafo precedente corrisponde proprio ad un indice clustered, per definizione: è sia un file che un indice, ordinato su un determinato campo della chiave di ricerca. Lo chiameremo per questo motivo anche file clustered.

Gli altri tipi di indice che abbiamo visto, raramente nella pratica potranno essere indici clustered. Affinchè questo avvenga è necessario che anche nel file i records siano ordinati per lo stesso valore della chiave di ricerca (file già ordinato per una chiave di ricerca), cosa estremamente rara, e comunque non sempre verificata (basterebbe l’ingresso di un nuovo dato non ordinato perchè la condizione non sia più soddisfatta).

Ovviamente la principale differenza in termini pratici tra i due indici sarà la velocità di accesso ai dati, generalmente molto inferiore nel caso di indici clustered , in quanto le pagine di cui si vorrà fare la scansione saranno contigue, mentre nel caso di indici non clustered è possibile che i rid, contigui all’interno dell’indice, puntino a pagine molto lontane tra di loro nel file di dati, creando dei tempi di attesa piuttosto lunghi.

Un’altra distinzione importante sarà quella tra indice primario e indice secondario.

L’indice primario sarà quello in cui i campi indicizzati corrispondono a una chiave primaria, mentre gli altri sono chiamati indici secondari. Un indice primario non potrà mai contenere dei duplicati (proprio in quanto la chiave primaria, per definizione, è priva di duplicati), mentre un indice secondario in generale potrebbe contenerne. Se un indice secondario corrisponde comunque a dei campi che fanno parte di una chiave candidata per una determinata relazione chiameremo l’indice unico (ma non comunque primario).

Nel prossimo articolo vedremo le tecniche di hashing e di indicizzazione ad albero