Índice de banco de dados
Content
Uso
Suporte para pesquisa rápida
A maioria dos softwares de banco de dados inclui a tecnologia de indexação que permite a pesquisa de tempo sub-linear para melhorar o desempenho, pois a pesquisa linear é ineficiente para grandes bancos de dados.
Suponha que um banco de dados contenha n itens de dados e seja preciso 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 poderá parar quando encontrar esse item único, mas se houver várias correspondências, ele deverá 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 fim. Existem trade-offs de design complexos envolvendo desempenho de pesquisa, tamanho do índice e desempenho de atualização indexada. Muitos designs de índices exibem desempenho logarítmico logarítmico (O (log (n))) e, em alguns aplicativos, é possível obter desempenho plano (O (1)).
Policiando as restrições de banco de dados
Os índices são usados para policiar restrições de banco de dados, como exclusivo, exclusão, chave primária e chave estrangeira. Um índice pode ser declarado exclusivo, 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 chave primárias, e alguns são capazes de usar um índice já existente para policiar essa restrição. Muitos sistemas de banco de dados exigem que os conjuntos de colunas de referência e referência de colunas em uma restrição de chave estrangeira sejam indexados, melhorando assim o desempenho de inserções, atualizações e exclusão das 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 é para nenhum outro registro. Isso pode ser usado para implementar uma restrição exclusiva (com predicado de igualdade) ou restrições mais complexas, como garantir que nenhum intervalos de tempo sobreposto ou nenhum objetos de geometria que se cruze sejam armazenados na tabela. É necessário um índice que apoie os registros rápidos que satisfazem o predicado para policiar essa restrição.
Métodos de arquitetura e indexação de índice
Não agrupado
Os dados estão presentes na 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 agrupada contém as teclas de índice em ordem classificada, com o nível foliar do índice contendo o ponteiro do registro (página e o número da linha na página de dados nos motores organizados pela página; deslocamento da linha nos motores organizados por arquivo ).
Em um índice não agrupado,
The physical order of the rows is not the same as the index order.The indexed columns are typically non-primary key columns used in JOIN, WHERE, and ORDER BY clauses.Pode haver mais de um índice não agrupado em uma tabela de banco de dados.
Agrupado
O cluster altera o bloco de dados em uma certa ordem distinta para corresponder ao índice, resultando nos dados da linha que estão sendo armazenados em ordem. Portanto, apenas um índice cluster pode ser criado em uma determinada tabela de banco de dados. Os índices em cluster podem aumentar bastante a velocidade geral da recuperação, mas geralmente apenas quando os dados são acessados sequencialmente na mesma ordem ou reversa do índice em cluster ou quando um intervalo de itens é selecionado.
Como os registros físicos estão nessa ordem de classificação no disco, o próximo item da linha na sequência é imediatamente antes ou depois do último, e são necessárias tão menos leituras de bloco de dados. A característica principal de um índice em cluster é, 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 bloqueios de dados e índices em arquivos separados, outros colocam dois blocos de dados completamente diferentes nos mesmos arquivos físicos.
Conjunto
Quando vários bancos de dados e várias tabelas são unidos, é chamado de cluster (não deve ser confundido com o índice cluster descrito anteriormente). Os registros para as tabelas que compartilham o valor de uma chave de cluster devem ser armazenados juntos nos mesmos blocos de dados ou próximos. Isso pode melhorar as junções dessas tabelas na chave do cluster, pois os registros correspondentes são armazenados juntos e menos E/S é necessária para localizá -las. A configuração do cluster define o layout de dados nas tabelas que são partes do cluster. Um cluster pode ser digitado com um índice B-Tree ou uma tabela de hash. O bloco de dados em que o registro da tabela é armazenado é definido pelo valor da chave do cluster.
Ordem da coluna
A ordem que a definição de í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 ou maior coluna indexada.
Por exemplo, em uma lista telefônica organizada pela cidade primeiro, depois pelo sobrenome e depois pelo primeiro nome, em uma cidade em particular, pode -se extrair facilmente a lista de todos os números de telefone. No entanto, seria muito tedioso encontrar todos os números de telefone para um sobrenome específico. Alguém teria que procurar na seção de cada cidade para as entradas com esse sobrenome. Alguns bancos de dados podem fazer isso, outros simplesmente não usarão 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 é mínimo - mas se fornecermos os valores para a cidade e o primeiro_name , a pesquisa usa apenas o campo da cidade para recuperar todos os registros correspondentes. Em seguida, uma pesquisa seqüencial verifica a correspondência com o primeiro_name. Portanto, para melhorar o desempenho, é preciso garantir que o índice seja criado na ordem das colunas de pesquisa.
Aplicações e limitações
Os índices são úteis para muitos aplicativos, mas vêm com algumas limitações. Considere a seguinte declaração SQL: selecione First_Name de pessoas onde last_name = 'Smith';. Para processar essa instrução sem um índice, o software do banco de dados deve observar a coluna Last_Name em cada linha da tabela (isso é conhecido como varredura de tabela completa). Com um índice, o banco de dados simplesmente segue a estrutura de dados do índice (normalmente uma árvore B) até que a entrada do Smith tenha sido encontrada; Isso é muito menos caro computacionalmente caro que uma varredura completa.
Considere esta instrução SQL: selecione Email_Address de clientes em que email_address como '%@wikipedia.org';. Essa consulta produziria um endereço de e -mail para todos os clientes cujo endereço de email termina com "@wikipedia.org", mas mesmo que a coluna Email_Address tenha sido indexada, o banco de dados deve executar uma digitalização 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 não pode usar a estrutura de dados do índice subjacente (em outras palavras, a cláusula não é sargável). Esse problema pode ser resolvido através da adição de outro índice criado no reverso (email_address) e uma consulta SQL como esta: selecione email_address de clientes onde reverse (email_address) como reverse ('%@wikipedia.org');. Isso coloca o curinga na parte mais à direita da consulta (agora gro.aidepikiw@%), que o índice no reverso (email_address) pode satisfazer.
Quando os caracteres curinga são usados nos dois lados da palavra de pesquisa como %wikipedia.org %, o índice disponível neste campo não é usado. Em vez disso, apenas uma pesquisa seqüencial é realizada, que leva o 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 bitwise nesses bitmaps. Os índices mais usados, como as árvores B+, são mais eficientes se os valores que eles indexam não repetir ou repetir um pequeno número de vezes. Por outro lado, o índice de bitmap foi projetado para casos em que os valores de uma variável repetem com muita frequência. Por exemplo, o campo sexual em um banco de dados de clientes geralmente contém no máximo três valores distintos: masculino, feminino ou desconhecido (não registrado). Para essas variáveis, o índice de bitmap pode ter uma vantagem significativa de desempenho sobre as árvores comumente usadas.
Índice denso
Um índice denso nos bancos de dados é um arquivo com pares de chaves e ponteiros para cada registro no arquivo de dados. Cada chave nesse arquivo está associada a um ponteiro específico a um registro no arquivo de dados classificado. Em índices em cluster com teclas duplicadas, o índice denso aponta para o primeiro registro com essa chave.
Índice esparso
Um índice esparso nos bancos de dados é um arquivo com pares de chaves e ponteiros para cada bloco no arquivo de dados. Cada chave nesse arquivo está associada a um ponteiro específico para o bloco no arquivo de dados classificado. Nos índices em cluster com teclas duplicadas, o índice escasso aponta para a chave de pesquisa mais baixa em cada bloco.
Índice reverso
Um índice de chave reversa reverte o valor da chave antes de digitá-lo no índice. Por exemplo, o valor 24538 se torna 83542 no índice. A reversão do valor da chave é particularmente útil para indexar dados como números de sequência, onde novos valores -chave aumentam monotonicamente.
ÍNDICE PRIMÁRIO
O índice primário contém os campos-chave da tabela e um ponteiro para os campos que não são de 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 pedem campos nem campos -chave (não há garantia de que o arquivo esteja organizado no campo -chave ou no campo de chave primária). Uma entrada de índice para cada tupla no arquivo de dados (índice densa) 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 equilibradas, árvores B+ e hashes.
No Microsoft SQL Server, o nó foliar do índice em cluster corresponde aos dados reais, não apenas um ponteiro para dados que residem em outros lugares, como é o caso de um índice não agrupado. Cada relação pode ter um único índice em cluster e muitos índices não classificados.
Controle de simultaneidade do índice
Um índice normalmente está sendo acessado simultaneamente por várias transações e processos e, portanto, precisa de controle de simultaneidade. Enquanto, em princípios, os índices podem utilizar os métodos de controle de simultaneidade de banco de dados comuns, existem métodos especializados de controle de concorrência para índices, que são aplicados em conjunto com os métodos comuns para um ganho de desempenho substancial.
Índice de cobrança
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 retornar dados.
Um índice de cobertura é um caso especial em que o próprio índice contém os campos de dados necessários e pode responder aos dados necessários.
Considere a tabela a seguir (outros campos omitidos):
IDNameOther Fields12Plug...13Lamp...14Fuse...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 necessário e elimina a necessidade de procurar o registro.
Os índices de cobertura são cada um para uma tabela específica. As consultas que ingressam/ acesso em várias tabelas podem considerar potencialmente cobrir í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 diminuem a inserção e a atualização dos dados. Para reduzir esse tamanho de í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 incluídos apenas no nível da folha, permitindo um índice de cobertura com menos tamanho geral do índice.
estandardização
Nenhum padrão define como criar índices, porque o padrão ISO SQL não cobre aspectos físicos. Os índices são uma das partes físicas da concepção de banco de dados, entre outros, como armazenamento (espaço de tabela ou agrupamentos de arquivo). Todos os fornecedores do RDBMS fornecem uma sintaxe Create Index com algumas opções específicas que dependem dos recursos de seu software.