Í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 agrupamentos
- 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
- Modelos de Implementação:
  - Agrupamento (Clustering)
  - 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:

O tipo de dado do campo pode ser Texto, Memorando, Número, Data/Hora, Auto numeração, Moeda, Sim/Não ou Hiperlink
Pode-se procurar por valores armazenados no campo.
É possível classificar com base nos valores dos campos.
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?

Uma diferença é que com índices comuns sempre há uma pesquisa sequencial dentro de um arquivo de índice até encontrar o chave procurada. Devido a esse procedimento quanto mais para o final do índice a chave procurada estiver, maior será o tempo de localização. Por isso, os programadores criam dois índices "ascendente" e "descendente" para facilitar pesquisas com campos do tipo data, para realizar buscas nos dois sentidos. Apesar da idéia ser boa, sempre requer criação de índices extras.
Já em bases com índices BTree, as informações são dispostas de forma diferente, cada tipo de informação é pesquisa aprofundando-se nos "nós" (Depth nodes) que possuem alguma semelhanca (seletividade) com o item a ser pesquisado. De fato, pode-se aprofundar em "nós" até um ponto máximo e será nesse ponto máximo que estará os limites onde efetuar-se-à pesquisa. Não há necessidade de varrer um índice inteiro, apenas uma parte do índice.
A vantagem do BTree está apenas sobre enormes bases de dados, pois uma base de dados pequena usando índice BTree possui quantidade de acessos físicos bem superior a índices comuns.

fonte: [1]

2. O que é balanceamento de índices?

O balanceamento de índices é avaliar o custo-benefício de cada índice, evitando que sejam criados aqueles que não serão usados, ou que sejam duplicados, com alto custo de manutenção ou mesmo mal formulados. Além disso, o balanceamento de índices se trata do processo de manutenção destes índices, isto é, como eles estão, geralmente, estruturados em árvores balanceadas, devido às inúmeras operações de inserção, atualização e deleções, com o tempo os índices se tornam "desbalanceados", necessitando de desfragmentação, reindexação, realinhamento.

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

Uma página IAM (Index Allocation Map) mapeia as extensões em uma parte de 4 gigabytes (GB) de um arquivo de banco de dados usada por uma unidade de alocação.
Uma unidade de alocação deve ser de um dos três tipos:
- IN_ROW_DATA : ** Partição de um heap ou indice
- LOB_DATA: ** Tipos de dados xml, varchar (objetos grandes)
- ROW_OVERFLOW_DATA : ** Comprimento variavel e grande
Se a unidade de alocação contiver extensões de mais de um arquivo, ou mais de um intervalo de 4 GB de um arquivo, haverá várias páginas IAM vinculadas com uma cadeia de IAM
Portanto, cada unidade de alocação tem pelo menos uma página IAM para cada arquivo no qual tem extensões. Também poderá haver mais de uma página IAM em um arquivo, se o intervalo das extensões no arquivo alocado à unidade de alocação exceder o intervalo que uma única página IAM pode registrar.
Ref: [ref]

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

A tabela hash é uma estrutura de dados especial, que associa chaves de pesquisa a valores através de uma função. Essa função é chamada de função de espalhamento ou função de dispersão. O ideal para a função de espalhamento é que sejam sempre fornecidos índices únicos para as chaves de entrada. A função perfeita seria a que, para quaisquer entradas A e B, sendo A diferente de B, fornecesse saídas diferentes. Quando as entradas A e B são diferentes e, passando pela função de espalhamento, geram a mesma saída, acontece o que chamamos de colisão. Por causa das colisões, muitas tabelas de dispersão são aliadas com alguma outra estrutura de dados, tal como uma lista encadeada ou até mesmo com árvores balanceadas. Em outras oportunidades a colisão é solucionada dentro da própria tabela.
Um exemplo de função de dispersão é o: Método da divisão (método da congruência linear)

 h(k) = k * mod(m)

Onde:
Potências de dois devem ser evitadas para valores de m.
m deve ser um numero primo distante de pequenas potencias de dois.

Exemplo: k = 10028; m = 5013; h(10028) = 10028 * mod(5013) -> h(10028) = 2.

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

Os índices podem ser alocados nas tabelas nas seguintes situações:

 - Um arquivo separado por objeto do banco de dados (como no Postgre);
 - Todos os objetos de um mesmo "database" num único arquivo sem workspaces internamente (como no Firebird) ;
 - Todos os "databases" dentro de um único arquivo (que passa a chamar-se "device") e cada database com seus próprios objetos (como no SQLServer).

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

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.

BDA - Aula 17 - 2014/2