Principi di funzionamento degli indici: struttura dati e algoritmi di ricerca

Oggi andiamo un po' più a fondo nell’architettura degli indici e vediamo come funzionano davvero sotto il cofano. Perché conoscere come è fatto un indice aiuta non solo a capire perché le query vanno più veloci, ma anche a scegliere gli indici migliori per ogni situazione.

Quando parliamo di struttura di un indice, intendiamo come sono organizzati i dati all’interno dell’indice per garantire una ricerca rapida. Immagina un armadio pieno di documenti. Se i documenti sono buttati tutti insieme, trovare quello giusto è un casino. Ma se l’armadio è ordinato in ordine alfabetico, la ricerca diventa molto più semplice. Gli indici funzionano proprio così: ordinano i dati in modo che trovare quello che ti serve sia il più veloce possibile.

Struttura dell’indice B-TREE

B-TREE (balanced tree — albero bilanciato) è il tipo di indice più usato in PostgreSQL. In pratica è una struttura ad albero, dove i dati sono organizzati in nodi e la ricerca avviene navigando dalla radice dell’albero fino alle foglie.

Come appare:

         Radice
          /       |       \
      Nodo 1    Nodo 2    Nodo 3
     /   \       |       /   \
Foglia1 Foglia2   Foglia3  Foglia4 Foglia5

Ogni nodo contiene valori chiave che permettono di indirizzare la ricerca. Per esempio, se il nodo radice contiene i valori [10, 20, 30], allora:

• Tutti i dati minori di 10 stanno in Foglia 1.
• Tutti i dati tra 10 e 20 — in Foglia 2, e così via.

Vantaggi dell’indice B-TREE:

• Ricerca veloce dei dati: la complessità della ricerca è O(log n), molto più rapida rispetto a una ricerca lineare.
• Perfetto per ricerche su intervalli (tipo trovare tutti i valori tra 10 e 50).

Esempio: supponiamo di avere una tabella students con una colonna age. Quando creiamo un indice B-TREE su questa colonna:

CREATE INDEX age_idx ON students (age);

PostgreSQL crea un albero bilanciato per i valori dell’età, così puoi trovare velocemente studenti di una certa età o in un certo intervallo di età.

Algoritmo di ricerca nel B-TREE

Quando fai una query, PostgreSQL usa l’indice per cercare i dati così:

1. Determina la chiave di ricerca (tipo età 25).
2. Parte dal nodo radice.
3. Confronta la chiave con gli intervalli di valori del nodo e va nel nodo figlio giusto.
4. Ripete il passo 3 finché non arriva a una foglia.
5. Restituisce i dati dalla foglia che corrisponde alla chiave.

Esempio di query:

SELECT * FROM students WHERE age = 25;

L’indice riduce il numero di dati da scansionare, garantendo una ricerca veloce.

Algoritmi di ricerca e performance

Gli indici velocizzano la ricerca perché riducono il numero di righe da scansionare. Senza indice, PostgreSQL scansiona tutta la tabella (si chiama scansione sequenziale, o Seq Scan). Con l’indice invece si fa una scansione tramite indice (Index Scan), che è molto più rapida.

Confronto tra scansione sequenziale e scansione tramite indice

• Scansione sequenziale (Seq Scan):

  • PostgreSQL legge ogni riga della tabella, controlla le condizioni della query e restituisce le righe che vanno bene.
  • Si usa se non c’è un indice o se la query prende quasi tutte le righe della tabella.

• Scansione tramite indice (Index Scan):

  • PostgreSQL usa l’indice per trovare le righe giuste e poi va a prenderle nella tabella solo per quelle.
  • Molto più veloce sulle tabelle grandi, se la query prende solo una piccola parte dei dati.

Esempio: senza indice, ricerca per età

SELECT * FROM students WHERE age = 25;

il risultato potrebbe richiedere la lettura di 1 milione di righe. Con l’indice B-TREE il sistema, per esempio, legge solo 100 righe.

Impatto della struttura dell’indice sulle performance

Gli indici sono più veloci perché riducono la quantità di dati da scansionare. Per esempio, se una tabella ha milioni di righe, l’indice le organizza in modo che la query debba leggere solo pochi nodi invece di tutta la tabella.

È fondamentale capire la struttura dell’indice. Sapere come funzionano davvero gli indici aiuta a capire perché certe query sono lente e come velocizzarle.

Inoltre è importante capire quali indici usare. Per ricerche su intervalli va bene B-TREE. Per array o JSONB — GIN. Scegliere l’indice sbagliato può rallentare il database.

Esempi reali

Dai, vediamo come gli indici ci aiutano davvero nel lavoro.

Indice per l’ordinamento

CREATE INDEX salary_idx ON employees (salary);
SELECT * FROM employees ORDER BY salary;

Con l’indice B-TREE PostgreSQL può restituire i dati già ordinati direttamente dall’indice, senza doverli riordinare dopo.

Indice per intervalli

CREATE INDEX price_idx ON products (price);
SELECT * FROM products WHERE price BETWEEN 100 AND 500;

L’indice B-TREE permette di trovare velocemente le righe che stanno nell’intervallo richiesto.

Domande frequenti e insidie

Perché non sempre conviene usare gli indici? Gli indici occupano spazio su disco e rallentano le operazioni di inserimento, aggiornamento e cancellazione, perché bisogna aggiornare anche la struttura dell’indice. Quindi è meglio creare indici solo sulle colonne che usi spesso nelle query.

Quando gli indici non aiutano? Per query che prendono quasi tutta la tabella (tipo WHERE true), PostgreSQL preferisce il Seq Scan, perché leggere i nodi dell’indice non porta vantaggi.