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 individuarliOverview of Clusters Oracle® Database Concepts 10g Release 1 (10.1). 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.