Índice de banco de dados - Database index

Um índice de banco de dados é uma estrutura de dados que melhora a velocidade das operações de recuperação de dados em uma tabela de banco de dados ao custo de gravações adicionais e espaço de armazenamento para manter a estrutura de dados do índice. Os índices são usados ​​para localizar dados rapidamente sem ter que pesquisar cada linha em uma tabela de banco de dados sempre que uma tabela de banco de dados é acessada. Os índices podem ser criados usando uma ou mais colunas de uma tabela de banco de dados , fornecendo a base para pesquisas aleatórias rápidas e acesso eficiente de registros ordenados.

Um índice é uma cópia de colunas de dados selecionadas, de uma tabela, projetada para permitir uma pesquisa muito eficiente. Um índice normalmente inclui uma "chave" ou link direto para a linha original de dados da qual foi copiado, para permitir que a linha completa seja recuperada com eficiência. Alguns bancos de dados estendem o poder da indexação, permitindo que os desenvolvedores criem índices em valores de coluna que foram transformados por funções ou expressões . Por exemplo, um índice poderia ser criado em upper(last_name), que armazenaria apenas as versões em maiúsculas do last_namecampo no índice. Outra opção às vezes suportada é o uso de índices parciais , onde as entradas de índice são criadas apenas para os registros que satisfazem alguma expressão condicional. Um outro aspecto da flexibilidade é permitir a indexação em funções definidas pelo usuário , bem como em expressões formadas a partir de uma variedade de funções integradas.

Uso

Suporte para pesquisa rápida

A maioria dos softwares de banco de dados inclui tecnologia de indexação que permite a pesquisa de tempo sublinear para melhorar o desempenho, já que a pesquisa linear é ineficiente para grandes bancos de dados.

Suponha que um banco de dados contenha N itens de dados e um deva ser recuperado com base no valor de um dos campos. Uma implementação simples recupera e examina cada item de acordo com o teste. Se houver apenas um item correspondente, isso pode parar quando encontrar aquele único item, mas se houver várias correspondências, ele deve testar tudo. Isso significa que o número de operações no caso médio é O (N) ou tempo linear . Como os bancos de dados podem conter muitos objetos e como a pesquisa é uma operação comum, geralmente é desejável melhorar o desempenho.

Um índice é qualquer estrutura de dados que melhora o desempenho da pesquisa. Existem muitas estruturas de dados diferentes usadas para esse propósito. Existem compromissos complexos de design que envolvem desempenho de pesquisa, tamanho de índice e desempenho de atualização de índice. Muitos designs de índice exibem desempenho de pesquisa logarítmica ( O (log (N))) e, em alguns aplicativos, é possível obter desempenho uniforme ( O (1)).

Policiando as restrições do banco de dados

Os índices são usados ​​para policiar as restrições do banco de dados , como UNIQUE, EXCLUSION, PRIMARY KEY e FOREIGN KEY . Um índice pode ser declarado como UNIQUE, o que cria uma restrição implícita na tabela subjacente. Os sistemas de banco de dados geralmente criam implicitamente um índice em um conjunto de colunas declaradas PRIMARY KEY, e alguns são capazes de usar um índice já existente para policiar essa restrição. Muitos sistemas de banco de dados requerem que os conjuntos de colunas referenciados e referenciados em uma restrição FOREIGN KEY sejam indexados, melhorando assim o desempenho de inserções, atualizações e exclusões nas tabelas que participam da restrição.

Alguns sistemas de banco de dados suportam uma restrição de EXCLUSÃO que garante que, para um registro recém-inserido ou atualizado, um determinado predicado não seja válido para nenhum outro registro. Isso pode ser usado para implementar uma restrição UNIQUE (com predicado de igualdade) ou restrições mais complexas, como garantir que nenhum intervalo de tempo sobreposto ou nenhum objeto geométrico de interseção seja armazenado na tabela. Um índice que dê suporte à busca rápida de registros que satisfaçam o predicado é necessário para policiar tal restrição.

Arquitetura de índice e métodos de indexação

Não agrupado

Os dados estão presentes em ordem arbitrária, mas a ordem lógica é especificada pelo índice. As linhas de dados podem ser espalhadas por toda a tabela, independentemente do valor da coluna ou expressão indexada. A árvore de índice não agrupado contém as chaves de índice em ordem classificada, com o nível folha do índice contendo o ponteiro para o registro (página e o número da linha na página de dados em mecanismos organizados por página; deslocamento de linha em mecanismos organizados por arquivo )

Em um índice não agrupado,

  • A ordem física das linhas não é igual à ordem do índice.
  • As colunas indexadas são normalmente colunas de chave não primária usadas nas cláusulas JOIN, WHERE e ORDER BY.

Pode haver mais de um índice não agrupado em uma tabela de banco de dados.

Aglomerado

O armazenamento em cluster altera o bloco de dados em uma determinada ordem distinta para corresponder ao índice, resultando nos dados da linha sendo armazenados em ordem. Portanto, apenas um índice clusterizado pode ser criado em uma determinada tabela de banco de dados. Os índices agrupados podem aumentar muito a velocidade geral de recuperação, mas geralmente apenas quando os dados são acessados ​​sequencialmente na mesma ordem ou na ordem inversa do índice agrupado, ou quando um intervalo de itens é selecionado.

Como os registros físicos estão nesta ordem de classificação no disco, o próximo item de linha na sequência é imediatamente anterior ou posterior ao último e, portanto, menos leituras de bloco de dados são necessárias. O principal recurso de um índice clusterizado é, portanto, a ordem das linhas de dados físicos de acordo com os blocos de índice que apontam para eles. Alguns bancos de dados separam os dados e os blocos de índice em arquivos separados, outros colocam dois blocos de dados completamente diferentes no (s) mesmo (s) arquivo (s) físico (s).

Cacho

Quando vários bancos de dados e várias tabelas são unidos, isso é chamado de cluster (não deve ser confundido com o índice clusterizado descrito anteriormente). Os registros das tabelas que compartilham o valor de uma chave de cluster devem ser armazenados juntos no mesmo bloco de dados ou em blocos próximos. Isso pode melhorar as junções dessas tabelas na chave de cluster, uma vez que os registros correspondentes são armazenados juntos e menos E / S é necessária para localizá-los. A configuração do cluster define o layout dos dados nas tabelas que fazem parte do cluster. Um cluster pode ser codificado com um índice B-Tree ou uma tabela hash . O bloco de dados onde o registro da tabela está armazenado é definido pelo valor da chave do cluster.

Ordem das colunas

A ordem em que a definição do índice define as colunas é importante. É possível recuperar um conjunto de identificadores de linha usando apenas a primeira coluna indexada. No entanto, não é possível ou eficiente (na maioria dos bancos de dados) recuperar o conjunto de identificadores de linha usando apenas a segunda coluna indexada ou superior.

Por exemplo, em uma lista telefônica organizada primeiro por cidade, depois pelo sobrenome e, em seguida, pelo primeiro nome, em uma determinada cidade, pode-se facilmente extrair a lista de todos os números de telefone. No entanto, seria muito tedioso encontrar todos os números de telefone de um determinado sobrenome. Seria preciso procurar dentro da seção de cada cidade as entradas com esse sobrenome. Alguns bancos de dados podem fazer isso, outros simplesmente não usam o índice.

No exemplo da lista telefônica com um índice composto criado nas colunas ( city, last_name, first_name), se pesquisarmos fornecendo valores exatos para todos os três campos, o tempo de pesquisa será mínimo - mas se fornecermos os valores para citye first_nameapenas, a pesquisa usará apenas o citycampo para recuperar todos os registros correspondentes. Em seguida, uma pesquisa sequencial verifica a correspondência com first_name. Portanto, para melhorar o desempenho, deve-se garantir que o índice seja criado na ordem das colunas de pesquisa.

Aplicativos e limitações

Os índices são úteis para muitos aplicativos, mas apresentam algumas limitações. Considere o seguinte SQL declaração: SELECT first_name FROM people WHERE last_name = 'Smith';. Para processar essa instrução sem um índice, o software de banco de dados deve examinar a coluna last_name em cada linha da tabela (isso é conhecido como varredura completa da tabela ). Com um índice, o banco de dados simplesmente segue a estrutura de dados do índice (normalmente uma árvore B ) até que a entrada Smith seja encontrada; isso é muito menos dispendioso em termos computacionais do que uma varredura completa da tabela.

Considere esta instrução SQL: SELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org';. Essa consulta geraria um endereço de e-mail para cada cliente cujo endereço de e-mail termine com "@ wikipedia.org", mas mesmo que a coluna email_address tenha sido indexada, o banco de dados deve executar uma varredura completa do índice. Isso ocorre porque o índice é construído com a suposição de que as palavras vão da esquerda para a direita. Com um curinga no início do termo de pesquisa, o software de banco de dados é incapaz de usar a estrutura de dados do índice subjacente (em outras palavras, a cláusula WHERE não é sargável ). Este problema pode ser resolvido através da adição de um outro índice criado em reverse(email_address)e uma consulta SQL como esta: SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org');. Isso coloca o curinga na parte mais à direita da consulta (agora gro.aidepikiw@%), que o índice reverso (email_address) pode satisfazer.

Quando os caracteres curinga são usados ​​em ambos os lados da palavra de pesquisa como % wikipedia.org% , o índice disponível neste campo não é usado. Em vez disso, apenas uma pesquisa sequencial é realizada, o que leva tempo O (N).

Tipos de índices

Índice de bitmap

Um índice de bitmap é um tipo especial de indexação que armazena a maior parte de seus dados como matrizes de bits (bitmaps) e responde à maioria das consultas executando operações lógicas bit a bit nesses bitmaps. Os índices mais comumente usados, como árvores B + , são mais eficientes se os valores que eles indexam não se repetem ou se repetem um pequeno número de vezes. Em contraste, o índice de bitmap é projetado para casos em que os valores de uma variável se repetem com muita frequência. Por exemplo, o campo sexo em um banco de dados de cliente geralmente contém no máximo três valores distintos: masculino, feminino ou desconhecido (não registrado). Para tais variáveis, o índice de bitmap pode ter uma vantagem significativa de desempenho sobre as árvores comumente usadas.

Índice denso

Um índice denso em bancos de dados é um arquivo com pares de chaves e ponteiros para cada registro no arquivo de dados. Cada chave neste arquivo está associada a um ponteiro específico para um registro no arquivo de dados classificados. Em índices agrupados com chaves duplicadas, o índice denso aponta para o primeiro registro com essa chave.

Índice esparso

Um índice esparso em bancos de dados é um arquivo com pares de chaves e ponteiros para cada bloco no arquivo de dados. Cada chave neste arquivo está associada a um determinado ponteiro para o bloco no arquivo de dados classificados. Em índices agrupados com chaves duplicadas, o índice esparso aponta para a chave de pesquisa mais baixa em cada bloco.

Índice reverso

Um índice de chave reversa inverte o valor da chave antes de inseri-lo no índice. Por exemplo, o valor 24538 torna-se 83542 no índice. Reverter o valor da chave é particularmente útil para indexar dados, como números de sequência, onde os novos valores da chave aumentam monotonicamente.

Índice primário

O índice primário contém os campos-chave da tabela e um ponteiro para os campos não-chave da tabela. O índice primário é criado automaticamente quando a tabela é criada no banco de dados.

Índice secundário

É usado para indexar campos que não são campos de ordenação nem campos-chave (não há garantia de que o arquivo seja organizado no campo-chave ou no campo-chave primário). Uma entrada de índice para cada tupla no arquivo de dados (índice denso) contém o valor do atributo indexado e o ponteiro para o bloco ou registro.

Índice de hash

Implementações de índice

Os índices podem ser implementados usando uma variedade de estruturas de dados. Os índices populares incluem árvores balanceadas , árvores B + e hashes .

No Microsoft SQL Server , o nó folha do índice clusterizado corresponde aos dados reais, não simplesmente um ponteiro para dados que residem em outro lugar, como é o caso de um índice não clusterizado. Cada relação pode ter um único índice clusterizado e muitos índices não clusterizados.

Controle de concorrência de índice

Um índice normalmente está sendo acessado simultaneamente por várias transações e processos e, portanto, precisa de controle de simultaneidade . Embora, em princípio, os índices possam utilizar os métodos comuns de controle de simultaneidade do banco de dados, existem métodos especializados de controle de simultaneidade para índices, que são aplicados em conjunto com os métodos comuns para um ganho de desempenho substancial.

Índice de cobertura

Na maioria dos casos, um índice é usado para localizar rapidamente os registros de dados dos quais os dados necessários são lidos. Em outras palavras, o índice é usado apenas para localizar registros de dados na tabela e não para retornar dados.

Um índice de cobertura é um caso especial em que o próprio índice contém os campos de dados obrigatórios e pode responder aos dados obrigatórios.

Considere a seguinte tabela (outros campos omitidos):

EU IRIA Nome Outros Campos
12 Plugue ...
13 Luminária ...
14 Fusível ...

Para encontrar o Nome para o ID 13, um índice em (ID) é útil, mas o registro ainda deve ser lido para obter o Nome. No entanto, um índice em (ID, Nome) contém o campo de dados obrigatório e elimina a necessidade de consultar o registro.

Os índices de cobertura são, cada um, para uma tabela específica. As consultas que JOIN / acessam em várias tabelas podem considerar a cobertura de índices em mais de uma dessas tabelas.

Um índice de cobertura pode acelerar drasticamente a recuperação de dados, mas pode ser grande devido às chaves adicionais, que tornam a inserção e atualização de dados mais lenta. Para reduzir o tamanho do índice, alguns sistemas permitem a inclusão de campos não-chave no índice. Os campos não-chave não fazem parte da ordem do índice, mas apenas incluídos no nível folha, permitindo um índice de cobertura com menor tamanho de índice geral.

estandardização

Nenhum padrão define como criar índices, porque o padrão ISO SQL não cobre os aspectos físicos. Os índices são uma das partes físicas da concepção do banco de dados, entre outras, como armazenamento (espaço de tabela ou grupos de arquivos). Todos os fornecedores de RDBMS fornecem uma sintaxe CREATE INDEX com algumas opções específicas que dependem dos recursos de seu software.

Veja também

Referências