BDA - Aula 10 - 2013/2

Índices

• Depois de evoluir no:
  • projeto ER
  • refinamento do esquema
  • definição de visões
• podemos ter os esquemas conceitual e externo para o BD

• Próximo passo:
  • escolher índices
  • fazer decisões de agrupamento
  • e (se necessário) refinar os esquemas conceitual e externo para atingir metas de desempenho.

• Função do indice:
  • No contexto do livro, serve para procurar um determinado assunto identificando o volume ou página.
  • No contexto da estrutura de dados, o índice é uma referência associada a uma chave, que é utilizada para fins de otimização, permitindo uma localização mais rápida de um registro quando efetuada uma consulta.
  • No contexto de banco de dados, um índice tem a função de permitir que os registros com dados sejam encontrados com rapidez. Também oferecem um acesso alternativo aos registros sem que a posição física seja alterada
    • Exemplo: Se precisarmos de uma lista dos alunos por ordem de CEP, é possível indexar e listar dessa maneira.

• O processo pode ser iniciado pela compreensão do ambiente (negócio) onde será implantando e definir:
  • As consultas mais importantes e a frequência com que aparecem
  • As atualizações mais relevantes a frequência com que podem ser feitas
  • O desempenho desejado para estas consultas e atualizações.

• Um índice pode ser:
  • simples: quando formado por apenas uma coluna
  • composto: referenciado por mais de uma coluna
  • interno: a chave está contida dentro da tabela
  • externo: quando existe uma tabela de chaves separada que associa ponteiros à registros de uma tabela

• Que índices deve-se criar?
  • Quais relações devem ter índices?
  • Qual(is) campo(s) devem estar na chave de pesquisa?
  • Deve-se construir vários índices?

• Devemos fazer mudanças no esquema conceitual?
  • Considerar esquemas normalizados alternativos?
  • Há várias escolhas na decomposição em formas normais, etc
  • Devemos “desfazer” alguns passos da decomposição e ficar com uma forma normal mais baixa?
  • Desnormalização?

• Considerações para Seleção de Índice:
  • É necessária a criação do índice?
  • Escolha da chave de busca
  • Utilizar múltiplos atributos na chave de busca
  • É necessário o agrupamento?
  • Devo usar hash ou árvore?
    • Hash:Permite inserção de novos elementos mas ocupa maior quantidade de espaço
    • Árvore: No caso de árvore binária, da busca é muito eficiente mas a tabela deve estar em ordem crescente ou decrescente.
  • Balanceamento do custo de manutenção do índice.

• Os campos utilizados na definição dos índices denominam-se campos de indexação
• Os índices não contém dados propriamente ditos e sim valor de campo de indexação e ponteiros que direcionam para o registro adequado dentro da tabela
  • Inserindo ou excluindo o registro, força também uma alteração nos índices
• Em alguns sistemas, os índices encontram-se separados do arquivo de dados

Exemplos

• Como o MySQL Utiliza Índices Os índices são utilizados para encontrar registros com um valor específico de uma coluna rapidamente
• Sem um índice o MySQL tem de iniciar com o primeiro registro e depois ler através de toda a tabela até que ele encontre os registros relevantes
• Quanto maior a tabela, maior será o custo
• Se a tabela possui um índice para as colunas em questão, o MySQL pode rapidamente obter uma posição para procurar no meio do arquivo de dados sem ter que varrer todos os registros. Se uma tabela possui 1000 registros, isto é pelo menos 100 vezes mais rápido do que ler todos os registros sequencialmente
• Note que se você precisar acessar quase todos os 1000 registros, seria mais rápido acessá-los sequencialmente porque evitaria acessos ao disco.

• Todos os índices do MySQL (PRIMARY, UNIQUE e INDEX) são armazenados em árvores B. Strings são automaticamente compactadas nos espaços finais e prefixados.

Access

• Na medida em que consultas de certos dados vão sendo realizadas, registros sendo classificados por um campo específico, que com frequência é utilizado como referência, torna-se necessário utilizá-lo como índice em uma tabela
• O Microsoft Office Acces procura o local dos dados através do índice e em alguns casos como em chaves primárias esta indexação é feita de maneira automática visando melhorar o desempenho do banco de dados. No entanto, alguns casos é provável que a definição do índice deverá ser feita manualmente

• O índice auxilia o MS Office Access a localizar e classicar os registros com mais rapidez. Tal índice armazena o local dos registros com base no(s) campo(s) escolhido(s) para ser(em) indexado(s). Após obter a localização do índice, os dados poderão ser recuperados.

• A criação de índices pode ser baseada em um único campo ou em vários. Os campos mais propensos à indexação são aqueles citados em várias pesquisas, campos associados a campos de outras tabelas.

• Se de uma forma os índices agilizam as pesquisas e consultas, de outra pode comprometer o desempenho na medida em que dados vão sendo criados ou atualizados. Quando os dados são inseridos em uma tabela que contém um ou mais campos indexados, o Access atualiza os índices cada vez que um registro é adicionado ou modificado. A adição de registros através de uma consulta acréscimo ou do acréscimo de registros importados provavelmente também será mais lenta se a tabela de destino contiver índices.

• Para a indexação de um campo, alguns critérios deverão ser levados em consideração e as condições abaixo devem aplicáveis:

1. O tipo de dado do campo pode ser Texto, Memorando, Número, Data/Hora, Auto numeração, Moeda, Sim/Não ou Hiperlink
2. Pode-se procurar por valores armazenados no campo.
3. É possível classificar com base nos valores dos campos.
4. Provê o armazenamento de diversos valores diferentes no campo. Se muitos dos valores no campo forem iguais, provavelmente o índice não poderá acelerar significativamente as consultas.

Oracle

• Oferece vários tipos de índices disponibilizando boas alternativas para todos os tipos de sistemas e processamentos no banco de dados

• Índices B-Trees: Índice padrão que o Oracle tem usado desde as primeiras versões. A fim de gerenciar corretamente os blocos, o Oracle controla o alocamento dos ponteiros dentro de cada bloco dos dados
  • Uma “árvore de blocos” (analogia à forma com a qual o Oracle aloca os blocos de dados) cresce através da inserção de linhas na tabela. Quando um bloco é preenchido, o mesmo “racha”, a fim de criar novos “galhos”, ou se preferir, blocos de dados. É ai que entra o índice do tipo B-Tree, controlando ponteiros dentro dos blocos de dados.
  • Um bloco de índice do Oracle pode conter dois tipos de ponteiros:
    • Ponteiro para um outro nó de blocos de dados de índices
    • Ponteiros para linhas específicas da tabelas ou ROWID (endereço físico do registro , informando em qual arquivo e setor o dado se encontra).

• Índice Bitmapped:
  • Lista dos valores distintos da coluna chave, onde cada um desses valores recebe um bitmap contendo um bit para cada linha da tabela
  • O bit ligado indica que a linha específica contém o valor da coluna chave
  • Sua estrutura, então, é apropriada para colunas chaves com pequena cardinalidade e com grande quantidade de linhas porém, a modificação dos valores da coluna chave revela o ponto fraco desse índice, uma vez que essa operação leva ao reajuste de grandes porções do bitmap e ao conseqüente bloqueio – lock – de uma grande quantidade de linhas da tabela, comprometendo a concorrência do ambiente

• Índice Baseado em Função:
  • O algoritmo do otimizador dos SGBD comerciais desconsidera, na montagem do plano de acesso, o índice associado a uma coluna chave referenciada em uma função como, por exemplo, TO_CHAR ou TO_NUMBER
  • Para suplantar essa limitação, os índices B-tree ou Bitmapped podem ser criados com a inclusão de uma função – padrão SQL ou construída pelo desenvolvedor – ou mesmo uma expressão aritmética, conforme a sentença de criação do índice necessário.

PostgreSQL

• B-Tree:
  • Índices baseados em árvores B pois este padrão facilita consultas utilizando a igualdade de valores ou intervalos de valores (>= > = < <=).
• Hash:
  • Índices que organizam um BD baseando-se em funções. Funciona em comparações de igualdade (=)
  • Apresenta resultados melhores que as B-tree mas possuem a limitação acima. Demandam a reorganização manual de índices após falhas no BD e muitos desencorajam seu uso

• GiST - Índices GiST (Generalized Search Tree) oferecem uma infra-estrutura sobre a qual podem ser implementadas consultas
  • Geram uma árvore de pesquisa balanceada versátil similar a uma árvore B que pode ser utilizada com estruturas de dados definidas pelo usuário e em implementações diversas como em busca em texto
  • Internamente é composta por nós que apresentam pares (Valor, ponteiro para dado indexado ou para outro nó).

• GIN - Índices GIN(Generalized Inverted Index) são estruturas invertidas que permitem acesso a dados com mais de uma chave, como arrays
  • Composto por uma lista de registros tipo (chave, lista de linhas que contém o valor da chave). Internamente cada índice GIN contém uma árvore B com base no valor da chave indexada, cujas folhas apontam para os valores das linhas relacionadas à chave.