• Tweet

• Tweet

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