Como funcionam os índices do MySQL?

402

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.

good_evening
fonte
Esta é uma questão muito ampla. Se você tiver um exemplo específico de uma consulta que não usará um índice e não souber o porquê, poderá publicá-la e as pessoas poderão ajudar.
Hammerite
SELECT * FROM members WHERE id = '1'- então, por que com o índice funciona mais rápido? O que esse índice faz aqui?
good_evening
2
Parece uma consulta que procura apenas um registro indexado específico (talvez identificado pela chave primária). O índice torna isso mais rápido porque é armazenado na memória, a linha correspondente do índice pode ser vista e contém um ponteiro para onde os dados reais são armazenados. Portanto, o MySQL pode ir para o local exato da tabela sem ter que verificar a tabela.
Hammerite
Muito bem, obrigada!
Lightness Races em órbita

Respostas:

513

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.
Piskvor saiu do prédio
fonte
3
Você está explicando o que é, não como tecnicamente funciona internamente.
quer
@ Tutu Kumari: Veja as revisões da pergunta; sinta-se à vontade para revisar também a resposta para atender à pergunta atual (observe os vários mecanismos e tipos de índice - consulte, por exemplo, a documentação aqui: dev.mysql.com/doc/refman/8.0/en/index-btree-hash.html )
Piskvor saiu de prédio
259

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.

claretes
fonte
2
As consultas a seguir terão vantagens no caso acima? SELECT last_name, first_name FROM person WHERE last_name= "Constantine" 2.SELECT last_name, first_name FROM person WHERE last_name LIKE "%Constantine"
Akshay Taru 30/11/2013
11
Primeira consulta será, segunda consulta não. Use EXPLAIN: dev.mysql.com/doc/refman/5.5/en/explain.html Para indexar a segunda consulta com o MySQL, você deve usar o FULLTEXT INDEX: dev.mysql.com/doc/refman/5.5/en/fulltext- search.html
Emilio Nicolás
5
Eu votei em você porque você tinha 127 anos e a resposta nº 1 foi em 256. Não pude evitar tornar tudo agradável e limpo, em termos binários.
Pbarney # 11/16
Esta foi uma nova informação para mim "pedir que você consulte esses campos é muito importante". obrigado.
Khatri
11
@pbarney depois de três anos, eles estão perto de 256 e 512, respectivamente, é o que eu chamo de aumento binário!
Nanocv
43

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.

Joshua
fonte
29
Isso é chamado de pesquisa binária.
ddlshack
Obrigado, finalmente, uma resposta que explica por que é mais rápido e não apenas como o db funciona com índices.
Gershon Herczeg
O número real de etapas depende muito dos dados - número de valor e distribuição exclusivos em seu intervalo. 7 é o máximo teórico para 100 valores. Discussão completa de como calcular o número de etapas aqui stackoverflow.com/questions/10571170/…
Joshua
O índice MySQL mais comum é uma árvore B +, que funciona de maneira semelhante a uma pesquisa binária, mas não é a mesma coisa. A complexidade algorítmica é a mesma, mas a maneira como ela pesquisa não é. Veja en.wikipedia.org/wiki/B-tree
Matt
4

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 ...

Abe Miessler
fonte
2
Bom artigo. Não conheço o SQL Server, mas o funcionamento básico parece muito semelhante. (metanote: desabilitar estilos CSS no 2º artigo vinculado oculta o conteúdo)
Piskvor saiu do prédio
3

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)
shahirnana
fonte
11
Bem-vindo ao Stack Overflow! Observamos que todas as suas respostas estão vinculadas aos seus próprios vídeos. Observe que a autopromoção aberta não é permitida .
SL Barth - Reinstate Monica
Ele quer promover seus vídeos. LOL
Ilyas karim
1

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.

WoodrowShigeru
fonte
1

Adicionando alguma representação visual à lista de respostas. insira a descrição da imagem aqui

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

Anush
fonte
1

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.

sendon1982
fonte