Como funcionam os índices do MySQL?

Estou realmente interessado em como os índices do MySQL funcionam, mais especificamente, como eles podem retornar os dados solicitados sem verificar a tabela inteira?

É fora de tópico, eu sei, mas se houver alguém que possa me explicar isso em detalhes, eu ficaria muito agradecido.

Basicamente, um índice em uma tabela funciona como um índice em um livro (é daí que o nome veio):

Digamos que você tenha um livro sobre bancos de dados e deseja encontrar algumas informações sobre, por exemplo, armazenamento. Sem um índice (assumindo nenhuma outra ajuda, como um índice), você teria que percorrer as páginas uma por uma, até encontrar o tópico (que é um full table scan). Por outro lado, um índice possui uma lista de palavras-chave; portanto, você deve consultar o índice e ver o storagemencionado nas páginas 113-120.231 e 354. Em seguida, você pode alternar diretamente para essas páginas, sem pesquisar (é uma pesquisa com um índice, um pouco mais rápido).

Obviamente, a utilidade do índice depende de muitas coisas - alguns exemplos, usando o símile acima:

• se você tivesse um livro sobre bancos de dados e indexasse a palavra "banco de dados", veria que ele é mencionado nas páginas 1-59,61-290 e 292 a 400. Nesse caso, o índice não é de muita ajuda e pode seja mais rápido percorrer as páginas uma a uma (em um banco de dados, isso é "baixa seletividade").
• Para um livro de 10 páginas, não faz sentido criar um índice, pois você pode acabar com um livro de 10 páginas prefixado por um índice de 5 páginas, o que é simplesmente bobo - basta digitalizar as 10 páginas e pronto. .
• O índice também precisa ser útil - geralmente não há sentido em indexar, por exemplo, a frequência da letra "L" por página.

A primeira coisa que você deve saber é que os índices são uma maneira 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 eles 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 Árvore B +, que armazena os elementos em uma ordem classificada. 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 é muito importante .

Portanto, 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 proveito 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 a first_namecoluna primeiro e ela 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

Esse é 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 utilizará com muita frequência. O principal caso em que posso pensar agora é aquele em que você cria uma tabela temporária na memória com um conjunto de resultados de outra seleção e executa várias outras seleções nessa tabela temporária usando índices de hash.

Se você tiver um VARCHARcampo grande , poderá "emular" o uso de um índice de hash ao usar uma Árvore B, criando outra coluna e salvando um hash do grande valor nela. Digamos que você esteja armazenando um URL em um campo e os valores sejam bastante grandes. Você também pode criar um campo inteiro chamado url_hashe usar uma função hash como CRC32ou qualquer outra função hash para fazer o hash do URL ao inseri-lo. 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, como a CRC32função gera um hash bem pequeno, você terá muitas colisões nos valores do hash. Se você precisar de valores exatos, poderá corrigir esse problema da seguinte maneira:

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

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

Infelizmente, usando essa técnica, você ainda precisa acertar a tabela para comparar o urlcampo.

Embrulhar

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

1. A comparação inteira é muito mais rápida que a comparação de strings. Pode ser ilustrado com o exemplo sobre a emulação do índice de hash em InnoDB.

2. Talvez, adicionar etapas adicionais em um processo o torne mais rápido, e não mais lento. Isso pode ser ilustrado pelo fato de que você pode otimizar um SELECTdividindo-o em duas etapas, fazendo com que o primeiro armazene valores em uma tabela de memória criada recentemente e execute as consultas mais pesadas nessa segunda tabela.

O MySQL também possui outros índices, mas acho que o B + Tree é o mais usado já e o hash é uma coisa boa a saber, mas você pode encontrar os outros na 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.

Basicamente, um índice é um mapa de todas as suas chaves que está classificado em ordem. Com uma lista em ordem, em vez de verificar todas as chaves, ele pode fazer algo assim:

1: Vá para o meio da lista - é maior ou menor do que o que estou procurando?

2: Se estiver mais alto, vá para o meio do caminho entre o meio e o fundo, se estiver mais baixo, o meio e o topo

3: É maior ou menor? Ir para o ponto do meio novamente, etc.

Usando essa lógica, você pode encontrar um elemento em uma lista classificada em cerca de 7 etapas, em vez de verificar todos os itens.

Obviamente, existem complexidades, mas isso fornece a idéia básica.

Dê uma olhada neste link: http://dev.mysql.com/doc/refman/5.0/en/mysql-indexes.html

Como eles funcionam é um assunto muito amplo para ser abordado em uma postagem do SO.

Aqui está uma das melhores explicações de índices que eu já vi. Infelizmente é para o SQL Server e não para o MySQL. Eu não tenho certeza de como os dois são semelhantes ...

Veja estes vídeos para obter mais detalhes sobre indexação

Indexação simples Você pode criar um índice exclusivo em uma tabela. Um índice exclusivo significa que duas linhas não podem ter o mesmo valor de índice. Aqui está a sintaxe para criar um índice em uma tabela

CREATE UNIQUE INDEX index_name
ON table_name ( column1, column2,...);

Você pode usar uma ou mais colunas para criar um índice. Por exemplo, podemos criar um índice tutorials_tblusando tutorial_author.

CREATE UNIQUE INDEX AUTHOR_INDEX
ON tutorials_tbl (tutorial_author)

Você pode criar um índice simples em uma tabela. Apenas omita a palavra-chave UNIQUE da consulta para criar um índice simples. Índice simples permite valores duplicados em uma tabela.

Se você deseja indexar os valores em uma coluna em ordem decrescente, é possível adicionar a palavra reservada DESC após o nome da coluna.

mysql> CREATE UNIQUE INDEX AUTHOR_INDEX
ON tutorials_tbl (tutorial_author DESC)

Quero adicionar meus 2 centavos. Estou longe de ser um especialista em banco de dados, mas recentemente li um pouco sobre esse tópico; o suficiente para eu tentar dar um ELI5. Então, aqui está a explicação do leigo.

Entendo assim que um índice é como um mini-espelho da sua tabela, praticamente como uma matriz associativa. Se você alimentá-lo com uma chave correspondente, basta saltar para essa linha em um "comando".

Mas se você não tiver esse índice / matriz, o interpretador de consulta deverá usar um loop for para percorrer todas as linhas e verificar se há uma correspondência (a varredura de tabela completa).

Ter um índice tem a "desvantagem" de armazenamento extra (para esse mini-espelho), em troca da "vantagem" de procurar conteúdo mais rapidamente.

Observe que (dependendo do mecanismo db), a criação de chaves primárias, estrangeiras ou exclusivas também configura automaticamente um respectivo índice. Esse mesmo princípio é basicamente o porquê e como essas chaves funcionam.

Adicionando alguma representação visual à lista de respostas.

O MySQL usa uma camada extra de indireção: os registros de índice secundário apontam para registros de índice primário, e o próprio índice primário mantém os locais das linhas em disco. Se um deslocamento de linha for alterado, apenas o índice primário precisará ser atualizado.

Advertência: a estrutura de dados do disco parece plana no diagrama, mas na verdade é uma árvore B +.

Fonte: link

No MySQL InnoDB, existem dois tipos de índice.

1. Chave primária que é chamada de índice clusterizado. As palavras-chave do índice são armazenadas com dados reais de registro no nó da folha B + Tree.

2. Chave secundária que não é um índice agrupado. Esses índices armazenam apenas as palavras-chave da chave primária, juntamente com suas próprias palavras-chave no nó folha B + Tree. Portanto, ao pesquisar no índice secundário, ele primeiro encontrará suas palavras-chave do índice da chave primária e varrerá a Árvore B + da chave primária para encontrar os registros de dados reais. Isso tornará o índice secundário mais lento em comparação com a pesquisa de índice primário. No entanto, se todas as selectcolunas estiverem no índice secundário, não será necessário procurar novamente o índice primário B + Tree. Isso é chamado de índice de cobertura.