BDA - Aula 09 - 2013/1

Í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 ficarcom 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 é Texto, Memorando, Número, Data/Hora, Auto numeração, Moeda, Sim/Não ou Hiperlink.
2. Você espera procura por valores armazenados no campo.
3. Você espera classificar por valores no campo.
4. Você espera armazenar 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.