- L'indicizzazione viene utilizzata per ottimizzare le prestazioni di un database riducendo al minimo il numero di accessi al disco richiesti quando viene elaborata una query.
- L'indice è un tipo di struttura dati. Viene utilizzato per individuare e accedere rapidamente ai dati in una tabella di database.
Struttura dell'indice:
Gli indici possono essere creati utilizzando alcune colonne del database.
- La prima colonna del database è la chiave di ricerca che contiene una copia della chiave primaria o della chiave candidata della tabella. I valori della chiave primaria vengono memorizzati in ordine in modo che sia possibile accedere facilmente ai dati corrispondenti.
- La seconda colonna del database è il riferimento ai dati. Contiene una serie di puntatori che contengono l'indirizzo del blocco del disco in cui è possibile trovare il valore della chiave particolare.
Metodi di indicizzazione
Indici ordinati
Gli indici sono solitamente ordinati per rendere la ricerca più veloce. Gli indici ordinati sono detti indici ordinati.
Esempio : Supponiamo di avere una tabella dei dipendenti con migliaia di record e ognuno dei quali è lungo 10 byte. Se i loro ID iniziano con 1, 2, 3....e così via e dobbiamo cercare lo studente con ID-543.
- Nel caso di un database senza indice, dobbiamo cercare il blocco del disco dall'inizio fino a raggiungere 543. Il DBMS leggerà il record dopo aver letto 543*10=5430 byte.
- Nel caso di un indice, effettueremo la ricerca tramite indici e il DBMS leggerà il record dopo aver letto 542*2= 1084 byte che sono molto inferiori rispetto al caso precedente.
Indice primario
- Se l'indice viene creato sulla base della chiave primaria della tabella, si parla di indicizzazione primaria. Queste chiavi primarie sono univoche per ciascun record e contengono una relazione 1:1 tra i record.
- Poiché le chiavi primarie vengono archiviate in ordine ordinato, l'esecuzione dell'operazione di ricerca è piuttosto efficiente.
- L'indice primario può essere classificato in due tipi: indice denso e indice sparso.
Indice denso
- L'indice denso contiene un record di indice per ogni valore della chiave di ricerca nel file di dati. Rende la ricerca più veloce.
- In questo caso, il numero di record nella tabella dell'indice è uguale al numero di record nella tabella principale.
- È necessario più spazio per archiviare il record dell'indice stesso. I record dell'indice hanno la chiave di ricerca e un puntatore al record effettivo sul disco.
Indice scarso
- Nel file di dati, il record indice viene visualizzato solo per alcuni elementi. Ogni elemento punta a un blocco.
- In questo caso, invece di puntare a ciascun record della tabella principale, l'indice punta ai record della tabella principale in uno spazio vuoto.
Indice di clustering
- Un indice cluster può essere definito come un file di dati ordinato. A volte l'indice viene creato su colonne di chiave non primaria che potrebbero non essere univoche per ciascun record.
- In questo caso, per identificare il record più velocemente, raggrupperemo due o più colonne per ottenere il valore univoco e creare un indice da esse. Questo metodo è chiamato indice di clustering.
- I record che hanno caratteristiche simili vengono raggruppati e per questi gruppi vengono creati degli indici.
Esempio : supponiamo che un'azienda contenga più dipendenti in ciascun reparto. Supponiamo di utilizzare un indice di clustering, in cui tutti i dipendenti che appartengono allo stesso Dept_ID sono considerati all'interno di un singolo cluster e i puntatori dell'indice puntano al cluster nel suo complesso. Qui Dept_Id è una chiave non univoca.
Lo schema precedente crea poca confusione perché un blocco del disco è condiviso da record che appartengono a cluster diversi. Se utilizziamo blocchi del disco separati per cluster separati, si parla di tecnica migliore.
Indice secondario
Nell'indicizzazione sparsa, man mano che cresce la dimensione della tabella, cresce anche la dimensione della mappatura. Queste mappature vengono solitamente conservate nella memoria primaria in modo che il recupero degli indirizzi sia più veloce. Quindi la memoria secondaria ricerca i dati effettivi in base all'indirizzo ottenuto dalla mappatura. Se la dimensione della mappatura aumenta, il recupero dell'indirizzo stesso diventa più lento. In questo caso, l'indice sparso non sarà efficiente. Per superare questo problema, viene introdotta l'indicizzazione secondaria.
Nell'indicizzazione secondaria, per ridurre la dimensione della mappatura, viene introdotto un altro livello di indicizzazione. In questo metodo, inizialmente viene selezionato l'intervallo vasto per le colonne in modo che la dimensione della mappatura del primo livello diventi piccola. Quindi ogni intervallo viene ulteriormente suddiviso in intervalli più piccoli. La mappatura del primo livello viene memorizzata nella memoria primaria, in modo che il recupero dell'indirizzo sia più veloce. La mappatura del secondo livello ed i dati effettivi vengono archiviati nella memoria secondaria (hard disk).
Per esempio:
- Se si desidera trovare il record del rotolo 111 nel diagramma, verrà cercata la voce più alta che sia inferiore o uguale a 111 nell'indice di primo livello. Otterrà 100 a questo livello.
- Quindi nel secondo livello dell'indice, di nuovo fa max (111)<= 111 and gets 110. now using the address 110, it goes to data block starts searching each record till 111. < li>
- Ecco come viene eseguita una ricerca con questo metodo. Anche l'inserimento, l'aggiornamento o la cancellazione avviene allo stesso modo. =>