BDA - Aula 10 - 2013/2

Índices

• Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke, McGrow-Hill, 2003.

• Após o desenvolvimento inicial com a confecção do:
  • Projeto Entidade Relacionamento (DER)
  • Refinamento do esquema (Normalização)
  • Definição de visões e relatórios
• podemos definir o modelo conceitual e externo para o BD

• Na sequência:
  • Seleciona-se os índices
  • Decide-se os agrupamento s
  • E (se necessário) refinase os modelos conceitual e externo para atingir metas de desempenho.

• Função do índice:
  • 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:
    • Cadastro de Clientes
    • Chave: CPF
    • Se precisarmos de uma lista de clientes por ordem de CEP, é possível indexar e listar dessa maneira
    • Pode ser necessário também:
      • Lista por ordem de Nome
      • Lista por ordem de Estado Civil
      • Lista por ordem de Status
      • Lista por ordem de Data de Nascimento
      • Lista por ordem de Bairr
      • Lista por ordem de Data do Cadastro
      • Lista por ordem de Email

• Efetivamente, os índices são um modo comum de melhorar o desempenho do banco de dados pois permitem ao servidor de banco de dados encontrar e trazer linhas específicas muito mais rápido do que faria sem o índice
• Entretanto, os índices também produzem trabalho adicional para o sistema de banco de dados como um todo devendo, portanto, serem utilizados com sensatez.

• 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

• Preocupações:
  • 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

MySQL

• No MySQL, como em qualquer sistema, índices, estes 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 requisições ao disco.

• Todos os índices do MySQL (PRIMARY, UNIQUE e INDEX) são armazenados em árvores BTree
• 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.

Questões

1. Qual a diferença entre índices Binary Tree e índices comuns?

• Caetano

2. O que é balanceamento de índices?

• Fernando

3. O que é e como funciona um IAM (Index allocation map)?

• Hiago

4. Como funciona a questáo índices de hash (hash indexes)?

• Igor

5. Como os índices sáo alocados nas tabelas?

• Lucas

6. Quais técnicas devemos considerar para Indexação?

• Yassushi

· Tempo de Acesso: O tempo para encontrar um item de dados particular.

· Tempo de Inserção: O tempo para inserir um novo item de dado. Isto inclui o tempo para encontrar o lugar correto para inserir o novo item de dado assim como o tempo para atualizar a estrutura do índice.

· Tempo de Remoção: O tempo para remover um item de dado. Isto inclui o tempo para encontrar o item a ser removido assim como para atualizar a estrutura do índice.

· Espaço Extra: O espaço adicional ocupado por uma estrutura de índice. Se o espaço adicional é pequeno, normalmente é vantajoso sacrificar esse espaço em benefício de um melhor desempenho.