Come funzionano gli indici MySQL?

La prima cosa che devi sapere è che gli indici sono un modo per evitare di scansionare l'intera tabella per ottenere il risultato che stai cercando.

Esistono diversi tipi di indici e sono implementati nel livello di archiviazione, quindi non esiste uno standard tra di loro e dipendono anche dal motore di archiviazione che stai utilizzando.

InnoDB e l'indice B+Tree

Per InnoDB, il tipo di indice più comune è l'indice basato su B+Tree, che memorizza gli elementi in un ordine ordinato. Inoltre, non è necessario accedere alla tabella reale per ottenere i valori indicizzati, il che rende la query molto più rapida.

Il "problema" su questo tipo di indice è che devi interrogare il valore più a sinistra per usare l'indice. Quindi, se il tuo indice ha due colonne, ad esempio cognome e nome, l'ordine in cui esegui query in questi campi importa molto .

Quindi, data la seguente tabella:

CREATE TABLE person (
    last_name VARCHAR(50) NOT NULL,
    first_name VARCHAR(50) NOT NULL,
    INDEX (last_name, first_name)
);

Questa query sfrutterebbe l'indice:

SELECT last_name, first_name FROM person
WHERE last_name = "John" AND first_name LIKE "J%"

Ma il seguente non lo farebbe

SELECT last_name, first_name FROM person WHERE first_name = "Constantine"

Perché stai interrogando il first_name prima la colonna e non è la colonna più a sinistra nell'indice.

Quest'ultimo esempio è anche peggio:

SELECT last_name, first_name FROM person WHERE first_name LIKE "%Constantine"

Perché ora stai confrontando la parte più a destra del campo più a destra nell'indice.

L'indice hash

Questo è un tipo di indice diverso che sfortunatamente supporta solo il back-end di memoria. È velocissimo ma utile solo per ricerche complete, il che significa che non puoi usarlo per operazioni come > , < o LIKE .

Dal momento che funziona solo per il backend di memoria, probabilmente non lo utilizzerai molto spesso. Il caso principale che mi viene in mente in questo momento è quello in cui crei una tabella temporanea nella memoria con una serie di risultati da un'altra selezione ed esegui molte altre selezioni in questa tabella temporanea usando gli indici hash.

Se hai un grande VARCHAR campo, puoi "emulare" l'uso di un indice hash quando usi un B-Tree, creando un'altra colonna e salvando un hash di grande valore su di essa. Diciamo che stai memorizzando un URL in un campo e i valori sono piuttosto grandi. Puoi anche creare un campo intero chiamato url_hash e usa una funzione hash come CRC32 o qualsiasi altra funzione hash per eseguire l'hashing dell'URL durante l'inserimento. E poi, quando devi eseguire una query per questo valore, puoi fare qualcosa del genere:

SELECT url FROM url_table WHERE url_hash=CRC32("http://gnu.org");

Il problema con l'esempio sopra è che dal CRC32 La funzione genera un hash piuttosto piccolo, ti ritroverai con molte collisioni nei valori hash. Se hai bisogno di valori esatti, puoi risolvere questo problema procedendo come segue:

SELECT url FROM url_table 
WHERE url_hash=CRC32("http://gnu.org") AND url="http://gnu.org";

Vale comunque la pena di eseguire l'hashing delle cose anche se il numero di collisione è alto perché eseguirai solo il secondo confronto (quello della stringa) con gli hash ripetuti.

Sfortunatamente, usando questa tecnica, devi ancora colpire la tabella per confrontare l'url campo.

Concludi

Alcuni fatti che potresti considerare ogni volta che vuoi parlare di ottimizzazione:

Il confronto di interi è molto più veloce del confronto di stringhe. Può essere illustrato con l'esempio sull'emulazione dell'indice hash in InnoDB .
Forse, l'aggiunta di ulteriori passaggi in un processo lo rende più veloce, non più lento. Può essere illustrato dal fatto che puoi ottimizzare un SELECT suddividendolo in due passaggi, facendo in modo che il primo memorizzi i valori in una tabella in memoria appena creata, quindi esegua le query più pesanti su questa seconda tabella.

MySQL ha anche altri indici, ma penso che quello B+Tree sia il più utilizzato in assoluto e quello hash è una buona cosa da sapere, ma puoi trovare gli altri in Documentazione MySQL .

Ti consiglio vivamente di leggere il libro "High Performance MySQL", la risposta sopra era sicuramente basata sul suo capitolo sugli indici.