Indice (basi di dati)

Un indice (nel campo dei database) è una struttura dati realizzata per migliorare i tempi di ricerca (query) dei dati.

Se una tabella non ha indici, ogni ricerca obbliga il sistema a leggere tutti i dati presenti in essa. L'indice consente invece di ridurre l'insieme dei dati da leggere per completare la ricerca.

Ad esempio, se si ha un insieme di dati disordinato, è possibile crearne un "indice" in ordine alfabetico, e sfruttare le proprietà dell'ordine alfabetico per arrivare prima al dato o ai dati cercati. Si potrebbe pensare, ad esempio, di applicare una ricerca binaria all'indice ordinato per reperire in tempi più brevi le informazioni richieste.

Gli indici hanno anche degli effetti negativi in quanto rendono più lente le operazioni di inserimenti e modifica (update), ed aumentano l'uso della memoria di massa.

Prima di definire su quali campi creare gli indici occorre valutare quali siano le operazioni di selezione più frequenti. La giusta scelta degli indici in uno schema può migliorare le prestazioni dell'operazione di lettura anche dell'80%. Strumenti idonei all'individuazione degli indici spesso sono disponibili quali strumenti dei DBMS. In particolare, data una query di selezione (abbastanza complessa), lo strumento di ottimizzazione degli indici individua eventuali indici da creare ed effettua una stima percentuale del miglioramento che potrebbe essere ottenuto. Al contrario una errata scelta può comportare un degrado delle prestazioni del sistema dovuto all'overhead introdotto per il mantenimento delle informazioni corrette, infatti ad ogni operazione di inserimento, aggiornamento e cancellazione di record indicizzati il dbms deve intervenire anche sul/sui file indice.

Un indice si può pensare nella forma <Ki,Pi> dove Ki è il valore dell'attributo chiave e Pi è il puntatore al record di dati. Generalmente il file indice è ordinato secondo i valori del campo Ki affinché sia possibile effettuare una ricerca binaria.

Le tipologie di indice sono le seguenti:

• Indici primari: I DBMS tendono a far ricadere, erroneamente, in questa categoria gli indici definiti su attributi a valore univoco (ovvero su una chiave), in realtà gli indici primari, a differenza di quelli secondari, contengono direttamente i dati (o sono realizzati su file ordinati sugli stessi campi su cui è definito l'indice stesso). Sono detti primari poiché non solo garantiscono l'accesso in base alla chiave, ma anche le locazioni fisiche necessarie per memorizzare i dati.
• Indici secondari: Sono gli indici che hanno lo scopo di favorire gli accessi ai dati senza contenere i dati stessi. Sono generalmente definiti su attributi che possono avere valori ripetuti.
• Indici clustered: Sono gli indici definiti sull'attributo secondo i cui valori il file di dati è ordinato
• Indici unclustered: Sono gli indici definiti sull'attributo secondo i cui valori il file di dati non è ordinato
• Indici densi: Sono gli indici il cui numero di coppie <Ki,Pi> è uguale al numero di valori chiave dei record
• Indici sparsi: Sono gli indici il cui numero di coppie <Ki,Pi> è inferiore al numero di valori chiave dei record

Esistono vari tipi di indici in base al tipo di DBMS, tipo di tabella utilizzata, ad esempio: hash, btree, rtree, ecc...

Utilizzo

Supporto per la ricerca rapida

La maggior parte dei software di database include la tecnologia di indicizzazione che consente la ricerca temporale sub-lineare per migliorare le prestazioni, poiché la ricerca lineare è inefficiente per i database di grandi dimensioni.

Supponiamo che un database contenga N elementi di dati e che uno debba essere recuperato in base al valore di uno dei campi. Una semplice implementazione recupera ed esamina ogni elemento in base al test. Se c'è un solo elemento corrispondente, questo può interrompersi quando trova quel singolo elemento, ma se ci sono più corrispondenze, deve testare tutto. Ciò significa che il numero di operazioni nel caso medio è O (N) o tempo lineare. Poiché i database possono contenere molti oggetti e poiché la ricerca è un'operazione comune, è spesso desiderabile migliorare le prestazioni.

Un indice è qualsiasi struttura di dati che migliora le prestazioni della ricerca. Ci sono molte diverse strutture di dati utilizzate per questo scopo. Esistono compromessi di progettazione complessi che coinvolgono le prestazioni di ricerca, le dimensioni dell'indice e le prestazioni di aggiornamento dell'indice. Molti progetti di indice mostrano prestazioni di ricerca logaritmiche ( O (log (N))) e in alcune applicazioni è possibile ottenere prestazioni piatte ( O (1)).

Controllo dei vincoli del database

Gli indici vengono utilizzati per controllare i vincoli del database, come UNIQUE, EXCLUSION, PRIMARY KEY e FOREIGN KEY. Un indice può essere dichiarato come UNICO, il che crea un vincolo implicito sulla tabella sottostante. I sistemi di database di solito creano implicitamente un indice su un insieme di colonne dichiarate PRIMARY KEY e alcuni sono in grado di utilizzare un indice già esistente per controllare questo vincolo. Molti sistemi di database richiedono che siano indicizzati sia i set di colonne referenziati che quelli referenziati in un vincolo FOREIGN KEY, migliorando così le prestazioni di inserimenti, aggiornamenti ed eliminazioni nelle tabelle che partecipano al vincolo.

Alcuni sistemi di database supportano un vincolo EXCLUSION che garantisce che, per un record appena inserito o aggiornato, un certo predicato non sia valido per nessun altro record. Questo può essere utilizzato per implementare un vincolo UNICO (con predicato di uguaglianza) o vincoli più complessi, come garantire che nella tabella non vengano memorizzati intervalli di tempo sovrapposti o oggetti geometrici intersecanti. Per controllare tale vincolo è necessario un indice che supporti la ricerca rapida di record che soddisfano il predicato.

Architettura dell'indice e metodi di indicizzazione

Non raggruppato ("non-clustered")

I dati sono presenti in ordine arbitrario, ma l'ordine logico è specificato dall'indice. Le righe di dati possono essere distribuite in tutta la tabella indipendentemente dal valore della colonna o dell'espressione indicizzata. L'albero dell'indice non raggruppato (non-clustered) contiene le chiavi dell'indice in ordine ordinato, con il livello foglia dell'indice contenente il puntatore al record (pagina e il numero di riga nella pagina dati nei motori organizzati per pagina; offset di riga nei motori organizzati per file).

In un indice non raggruppato

• L'ordine fisico delle righe non è lo stesso dell'ordine dell'indice.
• Le colonne indicizzate sono in genere colonne chiave non primaria utilizzate nelle clausole JOIN, WHERE e ORDER BY.

Può esserci più di un indice non raggruppato in una tabella di database.

Raggruppato ("clustered")

Il clustering altera il blocco di dati in un certo ordine distinto in modo che corrisponda all'indice, con il risultato che i dati della riga vengono archiviati in ordine. Pertanto, è possibile creare un solo indice cluster su una determinata tabella di database. Gli indici raggruppati (clustered) possono aumentare notevolmente la velocità complessiva di recupero, ma di solito solo quando si accede ai dati in modo sequenziale nello stesso ordine o inverso dell'indice raggruppato o quando viene selezionato un intervallo di elementi.

Poiché i record fisici sono in questo ordinamento su disco, l'elemento di riga successivo nella sequenza è immediatamente prima o dopo l'ultimo, quindi sono necessarie meno letture di blocchi di dati. La caratteristica principale di un indice cluster è quindi l'ordinamento delle righe di dati fisici in base ai blocchi dell'indice che puntano ad esse. Alcuni database separano i blocchi di dati e di indice in file separati, altri inseriscono due blocchi di dati completamente diversi all'interno degli stessi file fisici.

Gruppo ("cluster")

Quando più database e più tabelle vengono uniti, viene chiamato cluster (da non confondere con l'indice cluster descritto in precedenza) traducibile in "gruppo". I record per le tabelle che condividono il valore di una chiave cluster devono essere archiviati insieme negli stessi blocchi di dati o vicini. Ciò può migliorare i join di queste tabelle sulla chiave cluster, poiché i record corrispondenti vengono archiviati insieme ed è necessario meno I / O per individuarli. La configurazione del cluster definisce il layout dei dati nelle tabelle che fanno parte del cluster. Un cluster può essere codificato con un indice B-Tree o una tabella hash. Il blocco dati in cui è archiviato il record della tabella è definito dal valore della chiave cluster.

Ordine delle colonne

L'ordine in cui la definizione dell'indice definisce le colonne è importante. È possibile recuperare una serie di identificatori di riga utilizzando solo la prima colonna indicizzata. Tuttavia, non è possibile o efficiente (sulla maggior parte dei database) recuperare il set di identificatori di riga utilizzando solo la seconda o una colonna indicizzata superiore.

Ad esempio, in una rubrica telefonica organizzata prima per città, poi per cognome e poi per nome, in una determinata città, si può facilmente estrarre l'elenco di tutti i numeri di telefono. Tuttavia, sarebbe molto noioso trovare tutti i numeri di telefono per un determinato cognome. Si dovrebbe cercare nella sezione di ogni città le voci con quel cognome. Alcuni database possono farlo, altri semplicemente non useranno l'indice.

Nell'esempio della rubrica telefonica con un indice composto creato sulle colonne (city, last_name, first_name), se si esegue la ricerca fornendo valori esatti per tutti e tre i campi, il tempo di ricerca è minimo, ma se si forniscono i valori per citye solo first_name, la ricerca utilizza solo il campo city per recuperare tutti i record corrispondenti. Quindi una ricerca sequenziale controlla la corrispondenza con first_name. Quindi, per migliorare le prestazioni, è necessario assicurarsi che l'indice venga creato nell'ordine delle colonne di ricerca.

Applicazioni e limitazioni

Gli indici sono utili per molte applicazioni ma presentano alcune limitazioni. Si consideri il seguente SQL dichiarazione: SELECT first_name FROM people WHERE last_name = 'Smith';. Per elaborare questa istruzione senza un indice, il software del database deve esaminare la colonna last_name su ogni riga della tabella (questa operazione è nota come scansione completa della tabella). Con un indice, il database segue semplicemente la struttura dei dati dell'indice (tipicamente un albero B) finché non viene trovata la voce di Smith; questo è molto meno costoso dal punto di vista computazionale rispetto a una scansione completa della tabella.

Considerate questa istruzione SQL: SELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org';. Questa query produrrebbe un indirizzo email per ogni cliente il cui indirizzo email termina con "@ wikipedia.org", ma anche se la colonna email_address è stata indicizzata, il database deve eseguire una scansione completa dell'indice. Questo perché l'indice è costruito partendo dal presupposto che le parole vadano da sinistra a destra. Con un carattere jolly all'inizio del termine di ricerca, il software del database non è in grado di utilizzare la struttura dei dati dell'indice sottostante (in altre parole, la clausola WHERE non è selezionabile). Questo problema può essere risolto aggiungendo un altro indice creato su reverse(email_address)e una query SQL come questa:SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org');. Questo mette il carattere jolly nella parte più a destra della query (ora gro.aidepikiw@%), che l'indice al contrario (email_address) può soddisfare.

Quando i caratteri jolly vengono utilizzati su entrambi i lati della parola di ricerca come % wikipedia.org%, l'indice disponibile in questo campo non viene utilizzato. Piuttosto viene eseguita solo una ricerca sequenziale, che richiede tempo O (N).

Tipi di indici

Indice bitmap

Un indice bitmap è un tipo speciale di indicizzazione che memorizza la maggior parte dei dati come matrici di bit (bitmap) e risponde alla maggior parte delle query eseguendo operazioni logiche bit a bit su queste bitmap. Gli indici più comunemente usati, come gli alberi B +, sono più efficienti se i valori che indicizzano non si ripetono o si ripetono un numero limitato di volte. Al contrario, l'indice bitmap è progettato per i casi in cui i valori di una variabile si ripetono molto frequentemente. Ad esempio, il campo sesso in un database di clienti di solito contiene al massimo tre valori distinti: maschio, femmina o sconosciuto (non registrato). Per tali variabili, l'indice bitmap può avere un vantaggio significativo in termini di prestazioni rispetto agli alberi comunemente usati.

Indice denso

Un indice denso nei database è un file con coppie di chiavi e puntatori per ogni record nel file di dati. Ogni chiave in questo file è associata a un puntatore particolare a un record nel file di dati ordinato. Negli indici raggruppati con chiavi duplicate, l'indice denso punta al primo record con quella chiave.

Indice sparso

Un indice sparso nei database è un file con coppie di chiavi e puntatori per ogni blocco nel file di dati. Ogni chiave in questo file è associata a un puntatore particolare al blocco nel file di dati ordinato. Negli indici raggruppati con chiavi duplicate, l'indice sparso punta alla chiave di ricerca più bassa in ogni blocco.

Indice inverso

Un indice di chiave inversa inverte il valore della chiave prima di inserirlo nell'indice. Ad esempio, il valore 24538 diventa 83542 nell'indice. L'inversione del valore della chiave è particolarmente utile per l'indicizzazione di dati come i numeri di sequenza, dove i nuovi valori della chiave aumentano in modo monotono.

Indice principale

L'indice primario contiene i campi chiave della tabella e un puntatore ai campi non chiave della tabella. L'indice primario viene creato automaticamente quando la tabella viene creata nel database.

Indice secondario

Viene utilizzato per indicizzare i campi che non sono né campi di ordinamento né campi chiave (non vi è alcuna garanzia che il file sia organizzato sul campo chiave o sul campo chiave primaria). Una voce di indice per ogni tupla nel file di dati (indice denso) contiene il valore dell'attributo indicizzato e il puntatore al blocco o al record.

Implementazioni dell'indice

Gli indici possono essere implementati utilizzando una varietà di strutture di dati. Gli indici popolari includono alberi bilanciati, alberi B + e hash.

In Microsoft SQL Server, il nodo foglia dell'indice cluster corrisponde ai dati effettivi, non semplicemente un puntatore a dati che risiedono altrove, come nel caso di un indice non raggruppato. Ogni relazione può avere un singolo indice cluster e molti indici non raggruppati.

Controllo della concorrenza dell'indice

In genere si accede a un indice contemporaneamente da più transazioni e processi e pertanto è necessario il controllo della concorrenza. Mentre in linea di principio gli indici possono utilizzare i metodi di controllo della concorrenza del database comuni, esistono metodi di controllo della concorrenza specializzati per gli indici, che vengono applicati insieme ai metodi comuni per un sostanziale miglioramento delle prestazioni.

Indice di copertura

Nella maggior parte dei casi, viene utilizzato un indice per individuare rapidamente i record di dati da cui vengono letti i dati richiesti. In altre parole, l'indice viene utilizzato solo per individuare i record di dati nella tabella e non per restituire i dati.

Un indice di copertura è un caso speciale in cui l'indice stesso contiene i campi dati richiesti e può rispondere ai dati richiesti.

Considera la seguente tabella (altri campi omessi):

ID	Nome	Altri campi
12	Spina	...
13	Lampada	...
14	Fusibile	...

Per trovare il nome per l'ID 13, è utile un indice su (ID), ma il record deve ancora essere letto per ottenere il nome. Tuttavia, un indice su (ID, Nome) contiene il campo dati richiesto ed elimina la necessità di cercare il record.

Gli indici di copertura sono ciascuno per una tabella specifica. Le query che UNISCONO / accedono su più tabelle, possono potenzialmente considerare la copertura di indici su più di una di queste tabelle.

Un indice di copertura può accelerare notevolmente il recupero dei dati, ma potrebbe essere di grandi dimensioni a causa delle chiavi aggiuntive, che rallentano l'inserimento e l'aggiornamento dei dati. Per ridurre tale dimensione dell'indice, alcuni sistemi consentono di includere campi non chiave nell'indice. I campi non chiave non fanno parte dell'ordinamento dell'indice ma sono inclusi solo a livello foglia, consentendo un indice di copertura con una dimensione dell'indice inferiore.

Standardizzazione

Nessuno standard definisce come creare indici, perché lo standard ISO SQL non copre gli aspetti fisici. Gli indici sono una delle parti fisiche della concezione del database, tra gli altri come l'archiviazione (tablespace o filegroup). I fornitori di RDBMS forniscono tutti una sintassi CREA INDICE con alcune opzioni specifiche che dipendono dalle capacità del loro software.