Indicizzazione nei DBMS: Cos'è, Tipologie di Indici con ESEMPI

Cos'è l'indicizzazione?

Indicizzazione è una tecnica di struttura dati che consente di recuperare rapidamente i record da un file di database. Un indice è una piccola tabella con solo due colonne. La prima colonna contiene una copia della chiave primaria o candidata di una tabella. La sua seconda colonna contiene un insieme di puntatori contiene l'indirizzo del blocco del disco in cui è memorizzato quello specifico valore della chiave.

Un indice:

• Accetta come input una chiave di ricerca.
• Restituisce in modo efficiente una raccolta di record corrispondenti.

Senza un indice, il database deve scansionare ogni riga per rispondere a una query. Con un indice, invece, passa direttamente al blocco corrispondente, ed è per questo che il tipo di indice scelto ha un impatto significativo sulle prestazioni.

Tipi di indicizzazione nei DBMS

L'indicizzazione in un database è definita in base ai suoi attributi di indicizzazione. I due principali tipi di metodi di indicizzazione sono:

• Indicizzazione primaria
• Indicizzazione secondaria

Indice primario nel DBMS

Un indice primario è un file ordinato di lunghezza fissa con due campi. Il primo campo corrisponde alla chiave primaria, mentre il secondo punta a quello specifico blocco di dati. Nell'indice primario, esiste sempre una corrispondenza uno a uno tra le voci della tabella indice.

L'indice primario è ulteriormente suddiviso in due tipologie:

• Indice denso
• Indice sparse

Indice denso

In un indice denso, viene creato un record per ogni valore della chiave di ricerca nel database. Questo consente ricerche più veloci, ma richiede più spazio per memorizzare i record dell'indice. In questo metodo, i record contengono il valore della chiave di ricerca e puntano al record effettivo sul disco.

Indice sparse

Un indice sparso è un record di indice che appare solo per alcuni dei valori nel file. L'indice sparso aiuta a risolvere i problemi dell'indicizzazione densa in DBMSIn questa tecnica, una serie di colonne di indice memorizzano lo stesso indirizzo del blocco di dati e, quando è necessario recuperare i dati, viene recuperato tale indirizzo del blocco.

Un indice sparso memorizza i record dell'indice solo per alcuni valori della chiave di ricerca. Richiede meno spazio e minori costi di manutenzione per inserimenti ed eliminazioni, ma è più lento di un indice denso nella ricerca dei record.

Di seguito è riportato un esempio di indice di database sparso.

Indice di densità vs indice di sparsità

Le due principali varianti dell'indice presentano compromessi opposti, riassunti di seguito.

Aspetto	Indice denso	Indice sparse
Inserimenti	Uno per ogni chiave di ricerca	Uno per blocco
lo spazio	altro	Less
Velocità di ricerca	Faster	Più lentamente
Manutenzione	Più elevato	Abbassare

Indice secondario nel DBMS

L'indice secondario in un DBMS può essere generato da un campo che ha un valore univoco per ogni record e dovrebbe essere una chiave candidata. È anche noto come indice non clusterizzato.

Questa tecnica di indicizzazione del database a due livelli viene utilizzata per ridurre la mappaping dimensione del primo livello. Per il primo livello viene selezionata una vasta gamma di numeri, quindi la mappaping le dimensioni rimangono sempre piccole.

Esempio di indice secondario

Comprendiamo l'indicizzazione secondaria con un esempio di indice di database. In un database di conti bancari, i dati vengono memorizzati in sequenza in base al numero di conto (acc_no), ma potresti voler trovare tutti i conti di una specifica filiale della banca ABC.

Qui è possibile avere un indice secondario per ogni chiave di ricerca. Il record dell'indice punta a un bucket che contiene puntatori a tutti i record con quello specifico valore di chiave di ricerca.

ClusterIndice nel DBMS

In un indice cluster, nell'indice vengono memorizzati i record stessi, non i puntatori. Talvolta l'indice viene creato su colonne non chiave primaria, che potrebbero non essere univoche per ogni record. In tal caso, è possibile raggruppare due o più colonne per ottenere valori univoci e creare un indice, chiamato indice cluster. Questo permette anche di identificare il record più rapidamente.

Esempio: Supponiamo che un'azienda abbia assunto molti dipendenti in diversi reparti. In questo caso, è necessario creare un indice di clustering per tutti i dipendenti appartenenti allo stesso reparto.

Sono considerati come un unico cluster e l'indice punta al cluster nel suo complesso. In questo caso, Department_no è una chiave non univoca.

Che cos'è un indice multilivello?

L'indicizzazione multilivello viene creata quando un indice primario non può essere contenuto in memoria. Con questo tipo di metodo di indicizzazione, è possibile ridurre il numero di accessi al disco per raggiungere qualsiasi record. I record vengono memorizzati su disco come un file sequenziale e su tale file viene creato un indice sparso.

Indice B-Tree

L'indice B-tree è la struttura dati più utilizzata per l'indicizzazione basata su alberi nei DBMS. È un formato multilivello di indicizzazione basata su alberi che utilizza un indice bilanciato. alberi di ricerca binariTutti i nodi foglia dell'albero B contengono i puntatori ai dati effettivi.

Inoltre, tutti i nodi foglia sono interconnessi tramite una lista concatenata, il che consente a un albero B di supportare sia l'accesso casuale che quello sequenziale.

• I nodi foglia devono avere da 2 a 4 valori.
• Ogni percorso dalla radice a una foglia ha, nella maggior parte dei casi, la stessa lunghezza.
• I nodi non foglia, a parte il nodo radice, hanno da 3 a 5 nodi figli.
• Ogni nodo che non è una radice o una foglia ha tra n/2 e n figli.

Dove predominano le ricerche a corrispondenza esatta e le scansioni di intervallo sono rare, hashing può rappresentare un'alternativa più veloce a un indice B-tree.

Vantaggi dell'indicizzazione

I principali vantaggi dell'indicizzazione sono:

• Contribuisce a ridurre il numero totale di operazioni di I/O necessarie per recuperare i dati, evitando così di dover accedere direttamente a una riga della tabella.
• Offre agli utenti una ricerca e un recupero dei dati più rapidi.
• Può ridurre lo spazio occupato dalla tabella, perché non è necessario memorizzare il ROWID nell'indice per ogni riga collegata.
• I dati nei nodi foglia sono già ordinati in base al valore della chiave.

Svantaggi dell'indicizzazione

I principali svantaggi dell'indicizzazione sono:

• Per eseguire l'indicizzazione, è necessaria una chiave primaria sulla tabella con un valore univoco.
• Non è possibile creare un altro indice su dati già organizzati nello stesso modo.
• Non è consentito partizionare una tabella organizzata per indice.
• L'indicizzazione riduce le prestazioni delle query INSERT, DELETE e UPDATE.

DOMANDE FREQUENTI