Cardinalidade do Índice MySQL - Desempenho vs Eficiência de Armazenamento

Question

Digamos que você tenha uma tabela MySQL 5.0 Myisam com 100 milhões de linhas, com um índice (exceto a chave primária) em duas colunas inteiras.

Do meu entendimento reconhecidamente fraco da estrutura da árvore B, acredito que um mais baixo A cardinalidade significa que a eficiência de armazenamento do índice é melhor, porque há menos nós pais. Enquanto que um mais alto cardinalidade significa armazenamento menos eficiente, mas mais rápido ler Desempenho, porque precisa navegar por menos ramificações para obter os dados que procurar para restringir as linhas para a consulta.

(Nota - por "Low" vs "High", não quero dizer, por exemplo, 1 milhão vs 99 milhões para uma tabela de 100 milhões de fileiras. Quero dizer mais como 90 milhões vs 95 milhões)

Meu entendimento está correto?

Pergunta relacionada - como a cardinalidade afeta Escreva atuação?

Answer 1

Enquanto uma cardinalidade mais alta significa armazenamento menos eficiente, mas mais rápido, o desempenho de leitura, porque precisa navegar por menos ramificações para obter os dados que procurar para restringir as linhas para a consulta.

Cardinalidade mais alta significa melhor desempenho de leitura porque, por definição, há menos registros para ler.

Para processar uma consulta como esta:

SELECT  *
FROM    mytable
WHERE   indexed_col = @myvalue

, o motor deve fazer as seguintes etapas:

1. Encontre a primeira entrada satisfazendo a condição.

   Isso é feito atravessando o B-Tree, começando na entrada da raiz.

   Nas páginas, a pesquisa é realizada seguindo B-Tree links; Dentro de uma página, a pesquisa é executada usando a pesquisa binária (a menos que suas teclas sejam compactadas; nesse caso, é uma pesquisa linear).

   Esse algoritmo é a mesma eficiência para colunas de alta cardinalidade e de baixa cardinalidade. Encontrando o primeiro 3 (em oposição a qualquer 3) nessas listas:

   1  2  3  4  5  6  7  8  9  10
   
   3  3  3  3  3  3  3  3  4  4
   

   requer o mesmo O(log(n)) degraus.

2. Percorrendo o índice até que o valor da chave mude. Isso, é claro, requer tempo linear: quanto mais registros você tiver, mais você precisa atravessar.

Se você precisar apenas do primeiro registro:

SELECT  *
FROM    mytable
WHERE   indexed_col = @myvalue
LIMIT 1

, a cardinalidade da coluna não afeta o desempenho da leitura.

Como a cardinalidade afeta o desempenho da gravação?

Cada chave de índice possui um valor adicional oculto: um ponteiro de registro. Esse é o objetivo de ter um índice: você precisa saber qual registro isso aponta.

Como um ponteiro de registro, por definição, é único, cada chave de índice também é única. As entradas do índice que compartilham o mesmo valor de chave são classificadas pelo ponteiro de registro.

Isso é para tornar o índice sustentável: se você excluir um registro com um valor de uma coluna indexada compartilhada por um milhão de outros registros, o registro de índice correspondente também deve ser excluído. Mas todo o milhão dos registros de índice não está sendo analisado: em vez disso, o ponteiro de registro é usado como uma condição de pesquisa adicional.

Cada chave de índice é de fato exclusiva (mesmo se você não definir o índice como exclusivo) e, portanto, tem a máxima cardinalidade possível.

Portanto, a resposta para suas perguntas é: não, a cardinalidade da coluna não afeta o desempenho da gravação do índice.