Como funcionam os índices do MySQL?

A primeira coisa que você deve saber é que os índices são uma forma de evitar a varredura da tabela completa para obter o resultado que você está procurando.

Existem diferentes tipos de índices e eles são implementados na camada de armazenamento, portanto, não há um padrão entre eles e também dependem do mecanismo de armazenamento que você está usando.

InnoDB e o índice B+Tree

Para o InnoDB, o tipo de índice mais comum é o índice baseado em B+Tree, que armazena os elementos em uma ordem de classificação. Além disso, você não precisa acessar a tabela real para obter os valores indexados, o que torna sua consulta muito mais rápida.

O "problema" sobre esse tipo de índice é que você precisa consultar o valor mais à esquerda para usar o índice. Portanto, se seu índice tiver duas colunas, por exemplo, last_name e first_name, a ordem em que você consulta esses campos importa muito .

Assim, dada a seguinte tabela:

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

Esta consulta tiraria vantagem do índice:

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

Mas o seguinte não

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

Porque você está consultando o first_name coluna primeiro e não é a coluna mais à esquerda no índice.

Este último exemplo é ainda pior:

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

Porque agora você está comparando a parte mais à direita do campo mais à direita no índice.

O índice de hash

Este é um tipo de índice diferente que, infelizmente, apenas o back-end de memória suporta. É extremamente rápido, mas útil apenas para pesquisas completas, o que significa que você não pode usá-lo para operações como > , < ou LIKE .

Como ele funciona apenas para o back-end de memória, você provavelmente não o usará com muita frequência. O caso principal em que consigo pensar agora é aquele em que você cria uma tabela temporária na memória com um conjunto de resultados de outra seleção e realiza várias outras seleções nessa tabela temporária usando índices de hash.

Se você tiver um grande VARCHAR campo, você pode "emular" o uso de um índice de hash ao usar um B-Tree, criando outra coluna e salvando um hash do valor grande nela. Digamos que você esteja armazenando uma url em um campo e os valores sejam bem grandes. Você também pode criar um campo inteiro chamado url_hash e use uma função de hash como CRC32 ou qualquer outra função de hash para fazer o hash da url ao inseri-la. E então, quando você precisar consultar esse valor, poderá fazer algo assim:

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

O problema com o exemplo acima é que desde o CRC32 gerar um hash bem pequeno, você acabará com muitas colisões nos valores de hash. Se você precisar de valores exatos, poderá corrigir esse problema fazendo o seguinte:

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

Ainda vale a pena fazer o hash das coisas, mesmo que o número de colisão seja alto, porque você só executará a segunda comparação (a string) com os hashes repetidos.

Infelizmente, usando essa técnica, você ainda precisa acessar a tabela para comparar o url campo.

Encerramento

Alguns fatos que você pode considerar sempre que quiser falar sobre otimização:

A comparação de inteiros é muito mais rápida que a comparação de strings. Isso pode ser ilustrado com o exemplo sobre a emulação do índice de hash no InnoDB .
Talvez, adicionar etapas adicionais em um processo o torne mais rápido, não mais lento. Isso pode ser ilustrado pelo fato de que você pode otimizar um SELECT dividindo-o em duas etapas, fazendo com que a primeira armazene valores em uma tabela na memória recém-criada e, em seguida, execute as consultas mais pesadas nessa segunda tabela.

O MySQL também tem outros índices, mas acho que o B+Tree é o mais usado de todos os tempos e o hash é uma coisa boa de se saber, mas você pode encontrar os outros no Documentação do MySQL .

Eu recomendo que você leia o livro "High Performance MySQL", a resposta acima foi definitivamente baseada em seu capítulo sobre índices.