• Tweet

• Tweet

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.