Pergunta

Dado que a indexação é tão importante à medida que o tamanho do seu conjunto de dados aumenta, alguém pode explicar como a indexação funciona em um nível independente de banco de dados?

Para obter informações sobre consultas para indexar um campo, confira Como indexar uma coluna do banco de dados.

Foi útil?

Solução

Por que é necessário?

Quando os dados são armazenados em dispositivos de armazenamento baseados em disco, eles são armazenados como blocos de dados.Esses blocos são acessados ​​em sua totalidade, tornando-os a operação de acesso ao disco atômico.Os blocos de disco são estruturados da mesma maneira que as listas vinculadas;ambos contêm uma seção para dados, um ponteiro para a localização do próximo nó (ou bloco) e ambos não precisam ser armazenados de forma contígua.

Devido ao fato de que vários registros só podem ser classificados em um campo, podemos afirmar que a pesquisa em um campo que não está classificado requer uma Pesquisa Linear que requer N/2 bloquear acessos (em média), onde N é o número de blocos que a tabela abrange.Se esse campo for um campo não-chave (ou seja,não contém entradas exclusivas), então todo o espaço de tabela deve ser pesquisado em N bloquear acessos.

Já com um campo ordenado, pode ser utilizada uma Pesquisa Binária, que tem log2 N bloquear acessos.Além disso, como os dados são classificados em um campo não-chave, o restante da tabela não precisa ser pesquisado em busca de valores duplicados, uma vez encontrado um valor mais alto.Assim, o aumento de desempenho é substancial.

O que é indexação?

A indexação é uma forma de classificar vários registros em vários campos.A criação de um índice em um campo de uma tabela cria outra estrutura de dados que contém o valor do campo e um ponteiro para o registro ao qual ele se relaciona.Essa estrutura de índice é então ordenada, permitindo que pesquisas binárias sejam realizadas nela.

A desvantagem da indexação é que esses índices requerem espaço adicional no disco, uma vez que os índices são armazenados juntos em uma tabela usando o mecanismo MyISAM, esse arquivo pode atingir rapidamente os limites de tamanho do sistema de arquivos subjacente se muitos campos dentro da mesma tabela forem indexados .

Como funciona?

Primeiramente, vamos delinear um exemplo de esquema de tabela de banco de dados;

Field name       Data type      Size on disk
id (Primary key) Unsigned INT   4 bytes
firstName        Char(50)       50 bytes
lastName         Char(50)       50 bytes
emailAddress     Char(100)      100 bytes

Observação:char foi usado no lugar de varchar para permitir um tamanho preciso no valor do disco.Este banco de dados de amostra contém cinco milhões de linhas e não é indexado.O desempenho de diversas consultas será agora analisado.Estas são uma consulta usando o eu ia (um campo-chave classificado) e um usando o primeiro nome (um campo não classificado sem chave).

Exemplo 1 - campos classificados vs não classificados

Dado nosso banco de dados de amostra de r = 5,000,000 registros de tamanho fixo dando um comprimento recorde de R = 204 bytes e eles são armazenados em uma tabela usando o mecanismo MyISAM que usa o tamanho de bloco padrão B = 1,024 bytes.O fator de bloqueio da tabela seria bfr = (B/R) = 1024/204 = 5 registros por bloco de disco.O número total de blocos necessários para manter a mesa é N = (r/bfr) = 5000000/5 = 1,000,000 blocos.

Uma pesquisa linear no campo id exigiria uma média de N/2 = 500,000 bloquear acessos para encontrar um valor, visto que o campo id é um campo chave.Mas como o campo id também é classificado, uma pesquisa binária pode ser realizada exigindo uma média de log2 1000000 = 19.93 = 20 bloquear acessos.Instantaneamente podemos ver que esta é uma melhoria drástica.

Agora o primeiro nome O campo não é classificado nem é um campo-chave, portanto, uma pesquisa binária é impossível, nem os valores são exclusivos e, portanto, a tabela exigirá uma pesquisa até o final por um valor exato N = 1,000,000 bloquear acessos.É esta situação que a indexação pretende corrigir.

Dado que um registro de índice contém apenas o campo indexado e um ponteiro para o registro original, é lógico que ele será menor que o registro multicampo para o qual aponta.Portanto, o próprio índice requer menos blocos de disco do que a tabela original, o que requer menos acessos de bloco para iterar.O esquema para um índice no primeiro nome campo está descrito abaixo;

Field name       Data type      Size on disk
firstName        Char(50)       50 bytes
(record pointer) Special        4 bytes

Observação:Os ponteiros no MySQL têm 2, 3, 4 ou 5 bytes de comprimento, dependendo do tamanho da tabela.

Exemplo 2 - indexação

Dado nosso banco de dados de amostra de r = 5,000,000 registros com um comprimento de registro de índice de R = 54 bytes e usando o tamanho de bloco padrão B = 1,024 bytes.O fator de bloqueio do índice seria bfr = (B/R) = 1024/54 = 18 registros por bloco de disco.O número total de blocos necessários para manter o índice é N = (r/bfr) = 5000000/18 = 277,778 blocos.

Agora uma pesquisa usando o primeiro nome campo pode utilizar o índice para aumentar o desempenho.Isso permite uma pesquisa binária do índice com uma média de log2 277778 = 18.08 = 19 bloquear acessos.Para encontrar o endereço do registro real, que requer mais um bloco de acesso para leitura, elevando o total para 19 + 1 = 20 acessos em bloco, muito longe dos 1.000.000 de acessos em bloco necessários para encontrar um primeiro nome correspondência na tabela não indexada.

Quando deve ser usado?

Dado que a criação de um índice requer espaço em disco adicional (277.778 blocos extras do exemplo acima, um aumento de aproximadamente 28%) e que muitos índices podem causar problemas decorrentes dos limites de tamanho dos sistemas de arquivos, deve-se pensar cuidadosamente para selecionar o índice correto. campos para indexar.

Como os índices são usados ​​apenas para acelerar a busca por um campo correspondente nos registros, é lógico que a indexação de campos usados ​​apenas para saída seria simplesmente um desperdício de espaço em disco e tempo de processamento ao fazer uma operação de inserção ou exclusão e, portanto, Deveria ser evitado.Dada também a natureza de uma pesquisa binária, a cardinalidade ou exclusividade dos dados é importante.A indexação em um campo com cardinalidade 2 dividiria os dados pela metade, enquanto uma cardinalidade de 1.000 retornaria aproximadamente 1.000 registros.Com uma cardinalidade tão baixa, a eficácia é reduzida a uma classificação linear, e o otimizador de consulta evitará usar o índice se a cardinalidade for inferior a 30% do número do registro, tornando efetivamente o índice uma perda de espaço.

Outras dicas

A primeira vez que li isso foi muito útil para mim.Obrigado.

Desde então, obtive alguns insights sobre as desvantagens da criação de índices:se você escrever em uma tabela (UPDATE ou INSERT) com um índice, você tem na verdade duas operações de gravação no sistema de arquivos.Um para os dados da tabela e outro para os dados do índice (e o recurso deles (e - se agrupado - o recurso dos dados da tabela)).Se a tabela e o índice estiverem localizados no mesmo disco rígido, isso custará mais tempo.Assim, uma tabela sem índice (um heap) permitiria operações de gravação mais rápidas.(se você tivesse dois índices, acabaria com três operações de gravação e assim por diante)

No entanto, definir dois locais diferentes em dois discos rígidos diferentes para dados de índice e dados de tabela pode diminuir/eliminar o problema do aumento do custo de tempo.Isso requer a definição de grupos de arquivos adicionais com os arquivos correspondentes nos discos rígidos desejados e a definição da localização da tabela/índice conforme desejado.

Outro problema com os índices é a sua fragmentação ao longo do tempo à medida que os dados são inseridos. REORGANIZE ajuda, você deve escrever rotinas para que isso seja feito.

Em certos cenários, um heap é mais útil do que uma tabela com índices,

por exemplo: - Se você tem muitas gravações rivais, mas apenas uma leitura noturna fora do horário comercial para relatórios.

Além disso, uma diferenciação entre índices clusterizados e não clusterizados é bastante importante.

Me ajudou:- O que realmente significam índices clusterizados e não clusterizados?

Um índice é apenas uma estrutura de dados que agiliza a busca por uma coluna específica em um banco de dados.Essa estrutura geralmente é uma árvore b ou uma tabela hash, mas pode ser qualquer outra estrutura lógica.

Exemplo clássico "Índice em livros"

Considere um “Livro” de 1000 páginas, dividido por 100 seções, cada seção com X páginas.

Simples, né?

Agora, sem uma página de índice, para encontrar uma seção específica que comece com a letra “S”, você não tem outra opção a não ser percorrer todo o livro.ou seja:1000 páginas

Mas com uma página de índice no início, você está lá.E mais, para ler qualquer seção específica que seja importante, você só precisa dar uma olhada na página de índice, repetidas vezes, sempre.Depois de encontrar o índice correspondente, você pode pular com eficiência para a seção pulando outras seções.

Mas então, além de 1.000 páginas, você precisará de mais cerca de 10 páginas para exibir a página de índice, totalizando 1.010 páginas.

Assim, o índice é uma seção separada que armazena valores da coluna indexada + ponteiro para a linha indexada em uma ordem classificada para pesquisas eficientes.

As coisas são simples nas escolas, não é?:P

Agora, digamos que queremos executar uma consulta para encontrar todos os detalhes de qualquer funcionário chamado ‘Abc’?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

O que aconteceria sem um índice?

O software de banco de dados teria literalmente que examinar cada linha da tabela Employee para ver se o Employee_Name dessa linha é ‘Abc’.E, como queremos cada linha com o nome ‘Abc’ dentro dela, não podemos simplesmente parar de procurar quando encontrarmos apenas uma linha com o nome ‘Abc’, porque pode haver outras linhas com o nome Abc.Portanto, cada linha até a última linha deve ser pesquisada – o que significa que milhares de linhas neste cenário terão que ser examinadas pelo banco de dados para encontrar as linhas com o nome ‘Abc’.Isso é o que se chama verificação completa da tabela

Como um índice de banco de dados pode ajudar no desempenho

O objetivo de ter um índice é acelerar as consultas de pesquisa, essencialmente reduzindo o número de registros/linhas em uma tabela que precisam ser examinados.Um índice é uma estrutura de dados (mais comumente uma árvore B) que armazena os valores de uma coluna específica em uma tabela.

Como funciona o índice de árvores B?

A razão pela qual as árvores B são a estrutura de dados mais popular para índices é devido ao fato de que elas são eficientes em termos de tempo – porque pesquisas, exclusões e inserções podem ser feitas em tempo logarítmico.E outro motivo importante pelo qual as árvores B são mais comumente usadas é porque os dados armazenados dentro da árvore B podem ser classificados.O RDBMS normalmente determina qual estrutura de dados é realmente usada para um índice.Mas, em alguns cenários com determinados RDBMSs, você pode realmente especificar qual estrutura de dados deseja que seu banco de dados use ao criar o próprio índice.

Como funciona um índice de tabela hash?

A razão pela qual os índices hash são usados ​​é porque as tabelas hash são extremamente eficientes quando se trata apenas de procurar valores.Portanto, consultas que comparam a igualdade com uma string podem recuperar valores muito rapidamente se usarem um índice hash.

Por exemplo, a consulta que discutimos anteriormente poderia se beneficiar de um índice hash criado na coluna Employee_Name.A maneira como um índice hash funcionaria é que o valor da coluna seria a chave na tabela hash e o valor real mapeado para essa chave seria apenas um ponteiro para os dados da linha na tabela.Como uma tabela hash é basicamente uma matriz associativa, uma entrada típica seria algo como “Abc => 0x28939″, onde 0x28939 é uma referência à linha da tabela onde Abc está armazenado na memória.Procurar um valor como “Abc” em um índice de tabela hash e recuperar uma referência à linha na memória é obviamente muito mais rápido do que examinar a tabela para encontrar todas as linhas com o valor “Abc” na coluna Employee_Name.

As desvantagens de um índice hash

As tabelas hash não são estruturas de dados classificadas e há muitos tipos de consultas nas quais os índices hash nem sequer podem ajudar.Por exemplo, suponha que você queira descobrir todos os funcionários com menos de 40 anos.Como você poderia fazer isso com um índice de tabela hash?Bem, não é possível porque uma tabela hash só é boa para procurar pares de valores-chave – o que significa consultas que verificam a igualdade

O que exatamente está dentro de um índice de banco de dados?Então, agora você sabe que um índice de banco de dados é criado em uma coluna de uma tabela e que o índice armazena os valores nessa coluna específica.Porém, é importante entender que um índice de banco de dados não armazena os valores nas demais colunas da mesma tabela.Por exemplo, se criarmos um índice na coluna Employee_Name, isso significa que os valores das colunas Employee_Age e Employee_Address também não serão armazenados no índice.Se apenas armazenássemos todas as outras colunas no índice, seria como criar outra cópia da tabela inteira – o que ocuparia muito espaço e seria muito ineficiente.

Como um banco de dados sabe quando usar um índice?Quando uma consulta como “SELECT * FROM Employee WHERE Employee_Name = ‘Abc’” é executada, o banco de dados verificará se há um índice na(s) coluna(s) que está(m) sendo consultada(s).Supondo que a coluna Employee_Name tenha um índice criado nela, o banco de dados terá que decidir se realmente faz sentido usar o índice para encontrar os valores que estão sendo pesquisados ​​– porque existem alguns cenários em que é realmente menos eficiente usar o índice do banco de dados e mais eficiente apenas para verificar a tabela inteira.

Qual é o custo de ter um índice de banco de dados?

Ocupa espaço – e quanto maior for a sua tabela, maior será o seu índice.Outro impacto no desempenho dos índices é o fato de que sempre que você adicionar, excluir ou atualizar linhas na tabela correspondente, as mesmas operações terão que ser feitas em seu índice.Lembre-se de que um índice precisa conter os mesmos dados atualizados que o que quer que esteja na(s) coluna(s) da tabela que o índice cobre.

Como regra geral, um índice só deve ser criado em uma tabela se os dados da coluna indexada forem consultados com frequência.

Veja também

  1. Quais colunas geralmente constituem bons índices?
  2. Como funcionam os índices do banco de dados

Descrição simples!!!!!!!!!!!!

O índice nada mais é do que uma estrutura de dados que armazena os valores de uma coluna específica de uma tabela.Um índice é criado em uma coluna de uma tabela.

Exemplo, temos uma tabela de banco de dados chamada Usuário com três colunas – Nome, Idade e Endereço.Suponha que a tabela User tenha milhares de linhas.

Agora, digamos que queremos executar uma consulta para encontrar todos os detalhes de qualquer usuário chamado ‘John’.Se executarmos a seguinte consulta.

SELECT * FROM User 
WHERE Name = 'John'

O software de banco de dados teria literalmente que examinar cada linha da tabela Usuário para ver se o nome dessa linha é ‘John’.Isso levará muito tempo.
É aqui que o índice nos ajuda "o índice é usado para acelerar as consultas de pesquisa, essencialmente reduzindo o número de registros/linhas em uma tabela que precisa ser examinada".
Como criar um índice

CREATE INDEX name_index
ON User (Name)

Um índice consiste em valores de coluna (por exemplo:John) de uma tabela e que esses valores sejam armazenados em uma estrutura de dados.
Portanto, agora o banco de dados usará o índice para localizar funcionários chamados John porque o índice provavelmente será classificado em ordem alfabética pelo nome do usuário.E, por ser classificado, significa que a busca por um nome é muito mais rápida porque todos os nomes que começam com “J” estarão um ao lado do outro no índice!

Apenas uma sugestão rápida..Como a indexação custa gravações adicionais e espaço de armazenamento, se seu aplicativo exigir mais operações de inserção/atualização, você pode querer usar tabelas sem índices, mas se exigir mais operações de recuperação de dados, você deve optar pela tabela indexada.

Pense no Índice do Banco de Dados como o Índice de um livro.Se você tem um livro sobre cães e deseja encontrar informações sobre, digamos, pastores alemães, você pode, é claro, folhear todas as páginas do livro e encontrar o que procura, mas é claro que isso consome tempo e não muito rápido.Outra opção é que você pode simplesmente ir até a seção Índice do livro e encontrar o que procura usando o nome da entidade que está procurando (neste caso, pastores alemães) e também olhando o número da página para encontre rapidamente o que procura.No Banco de Dados, o número da página é referido como um ponteiro que direciona o banco de dados para o endereço no disco onde a entidade está localizada.Usando a mesma analogia com o Pastor Alemão, poderíamos ter algo assim (“Pastor Alemão”, 0x77129) onde 0x77129 é o endereço no disco onde os dados da linha do Pastor Alemão estão armazenados.

Resumindo, um índice é uma estrutura de dados que armazena os valores de uma coluna específica de uma tabela para agilizar a pesquisa da consulta.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top