Como funciona a indexação de banco de dados? [fechadas]

Dado que a indexação é tão importante quanto o tamanho do seu conjunto de dados, 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, consulte Como indexar uma coluna do banco de dados .

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 ​​por inteiro, tornando-os a operação de acesso a 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 o local do próximo nó (ou bloco) e ambos não precisam ser armazenados contiguamente.

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

Enquanto que com um campo classificado, uma Pesquisa Binária pode ser usada, com log2 Nacesso a blocos. Além disso, como os dados são classificados com um campo sem chave, o restante da tabela não precisa ser pesquisado em busca de valores duplicados, uma vez que um valor mais alto é encontrado. Assim, o aumento de desempenho é substancial.

O que é indexação?

A indexação é uma maneira de classificar vários registros em vários campos. Criar um índice em um campo em 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 classificada, permitindo que pesquisas binárias sejam executadas 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 da mesma tabela forem indexados .

Como funciona?

Primeiramente, vamos descrever um esquema de tabela de banco de dados de amostra;

Nome do campo Tipo de dados Tamanho no disco
id (chave primária) INT não assinado 4 bytes
firstName Char (50) 50 bytes
lastName Char (50) 50 bytes
emailAddress Char (100) 100 bytes

Nota : char foi usado no lugar de varchar para permitir um tamanho exato no valor do disco. Este banco de dados de amostra contém cinco milhões de linhas e não é indexado. O desempenho de várias consultas agora será analisado. Trata-se de uma consulta usando o ID (um campo de chave classificada) e uma usando o firstName (um campo não classificado sem chave).

Exemplo 1 - campos classificados versus não classificados

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

Uma pesquisa linear no campo de identificação exigiria uma média de N/2 = 500,000acessos de bloco para encontrar um valor, dado que o campo de identificação é 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 = 20acessos de bloco. Instantaneamente, podemos ver que isso é uma melhoria drástica.

Agora, o campo firstName 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 para N = 1,000,000acessar exatamente um bloco. É essa situação que a indexação visa corrigir.

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

Nome do campo Tipo de dados Tamanho no disco
firstName Char (50) 50 bytes
(apontador de registro) 4 bytes especiais

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

Exemplo 2 - indexação

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

Agora, uma pesquisa usando o campo firstName 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 = 19acessos de bloco. Para localizar o endereço do registro real, que exige um acesso adicional ao bloco para leitura, elevando o total para o 19 + 1 = 20acesso a blocos, está muito distante dos 1.000.000 acessos de bloco necessários para encontrar uma correspondência firstName 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 a mais do exemplo acima, um aumento de ~ 28%) e que muitos índices podem causar problemas decorrentes dos limites de tamanho dos sistemas de arquivos, é necessário ter cuidado para selecionar a opção correta. campos para indexar.

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

Exemplo clássico "Índice nos livros"

Considere um "livro" de 1000 páginas, dividido por 10 capítulos, cada seção com 100 páginas.

Simples, né?

Agora, imagine que você deseja encontrar um capítulo específico que contenha a palavra " Alquimista ". Sem uma página de índice, você não tem outra opção senão digitalizar o livro / capítulos inteiro. ou seja: 1000 páginas.

Essa analogia é conhecida como "Verificação completa de tabela" no mundo dos bancos de dados.

Mas com uma página de índice, você sabe para onde ir! E mais, para pesquisar qualquer capítulo em particular que seja importante, basta examinar a página de índice várias vezes. Depois de encontrar o índice correspondente, você pode pular eficientemente para esse capítulo pulando o resto.

Mas, além das 1000 páginas reais, você precisará de mais ~ 10 páginas para mostrar os índices, totalizando 1010 páginas.

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

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

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

Desde então, obtive algumas dicas sobre a desvantagem da criação de índices: se você escreve em uma tabela ( UPDATEou INSERT) com um índice, na verdade possui 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 dos mesmos (e - se agrupado - o recurso dos dados da tabela)). Se tabela e índice estiverem localizados no mesmo disco rígido, isso custará mais tempo. Assim, uma tabela sem um índice (um heap) permitiria operações de gravação mais rápidas. (se você tivesse dois índices, terminaria com três operações de gravação e assim por diante)

No entanto, a definição de 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 do local da tabela / índice conforme desejado.

Outro problema com os índices é a fragmentação ao longo do tempo à medida que os dados são inseridos. REORGANIZEajuda, você deve escrever rotinas para fazê-lo.

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

por exemplo: - Se você tiver 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 agrupados e não agrupados é bastante importante.

Ajudou-me: - O que realmente significam índices agrupados e não agrupados?

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

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 literalmente precisaria examinar todas as linhas da tabela Employee para ver se o Employee_Name dessa linha é 'Abc'. E, como queremos que cada linha com o nome 'Abc' contenha, não podemos parar de procurar uma vez que encontramos apenas uma linha com o nome 'Abc', porque poderia haver outras linhas com o nome Abc . Portanto, todas as linhas até a última linha devem ser pesquisadas - o que significa que milhares de linhas nesse cenário terão que ser examinadas pelo banco de dados para encontrar as linhas com o nome 'Abc'. Isso é chamado de varredura de tabela completa

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

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

Como o índice B-trees funciona?

A razão pela qual as árvores B são a estrutura de dados mais popular para os índices se deve ao fato de serem eficientes em termos de tempo - porque pesquisas, exclusões e inserções podem ser feitas em tempo logarítmico. E, outro motivo principal 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, é possível especificar qual estrutura de dados você deseja que seu banco de dados use ao criar o próprio índice.

Como um índice de tabela de hash funciona?

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

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

As desvantagens de um índice de hash

As tabelas de hash não são estruturas de dados classificadas e existem muitos tipos de consultas com as quais os índices de hash nem podem ajudar. Por exemplo, suponha que você queira descobrir todos os funcionários com menos de 40 anos de idade. Como você pode fazer isso com um índice de tabela de hash? Bem, não é possível porque uma tabela de hash é boa apenas 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? Portanto, agora você sabe que um índice de banco de dados é criado em uma coluna em 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 outras colunas da mesma tabela. Por exemplo, se criarmos um índice na coluna Employee_Name, isso significa que os valores da coluna Employee_Age e Employee_Address também não serão armazenados no índice. Se simplesmente armazenássemos todas as outras colunas no índice, seria como criar outra cópia da tabela inteira - 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 verifica se há um índice nas colunas que estão sendo consultadas. Supondo que a coluna Employee_Name tenha um índice criado, o banco de dados precisará 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?

Ele ocupa espaço - e quanto maior a sua tabela, maior o seu índice. Outro problema de desempenho com índices é o fato de que sempre que você adiciona, exclui ou atualiza linhas na tabela correspondente, as mesmas operações terão que ser feitas no seu índice. Lembre-se de que um índice precisa conter os mesmos dados até o minuto que estiver 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 na coluna indexada forem consultados com frequência.

Veja também

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

Descrição simples!

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

Exemplo: Temos uma tabela de banco de dados chamada Usercom três colunas - Name, Agee Address. Suponha que a Usertabela 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 literalmente precisaria examinar todas as linhas da Usertabela para ver se a Namelinha é 'John'. Isso levará muito tempo.

É aqui que indexnos ajuda: o índice é usado para acelerar as consultas de pesquisa, reduzindo essencialmente 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 indexconsiste em valores de coluna (por exemplo: John) de uma tabela e esses valores são armazenados em uma estrutura de dados .

Portanto, agora o banco de dados usará o índice para encontrar funcionários chamados John, porque o índice provavelmente será classificado em ordem alfabética pelo nome de Usuários. E, por ser classificada, significa que a busca por um nome é muito mais rápida, porque todos os nomes que começam com um "J" estarão próximos um do outro no índice!

Apenas uma sugestão rápida. Como a indexação custa mais espaço para gravações e armazenamento, por isso, se seu aplicativo exigir mais operação de inserção / atualização, convém usar tabelas sem índices, mas se exigir mais operações de recuperação de dados, você deve procurar indexadas. mesa.

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, é claro que você pode folhear todas as páginas do livro e encontrar o que está procurando - mas isso obviamente consome tempo e não muito rápido.

Outra opção é que você pode simplesmente ir para a seção Índice do livro e encontrar o que está procurando, 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 em que a entidade está localizada. Usando a mesma analogia da German Shepherd, poderíamos ter algo assim (“German Shepherd”, 0x77129) onde 0x77129é o endereço no disco em que os dados da linha da German Shepherd estão armazenados.

Em resumo, um índice é uma estrutura de dados que armazena os valores para uma coluna específica em uma tabela para acelerar a pesquisa de consultas.