9. Indexação e Hashing

9.1. Indexação

Visando minimizar o tempo de consulta de determinado dado no Banco de Dados, utilizamos Índices e Funções de Hashing. Devemos considerar diversas técnicas para Hashing e Indexação, porém, cada técnica precisa ser avaliada tendo por base:

·      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.

O atributo ou o conjunto de atributos usados para buscar os registros em um arquivo denomina-se chave de busca. Cada estrutura de índice está associada a uma chave de busca particular. Se um arquivo for ordenado seqüencialmente, e se escolhermos incluir diversos índices em diferentes chaves de busca, o índice cuja chave de busca especifica a ordem seqüencial do arquivo é o Índice Primário.  Os outros índices são chamados Índices Secundários.  A chave de busca de um Índice Primário é usualmente a Chave Primária.

Existem índices Densos e Esparsos, onde geralmente é mais rápido localizar um registro se temos um índice denso em vez de um índice esparso. No entanto, índices esparsos tem uma vantagem sobre índices densos, pois requerem menos espaço e impõem menos sobrecarga de manutenção para inserções e remoções.

Independente da forma de índice usada, todo índice precisa ser atualizado sempre que um registro for inserido ou removido do arquivo. Abaixo, descrevemos alguns algoritmos para atualizar índices de nível único.

·      Remoção:

1°) Localizar o registro a ser removido

2°) Se o registro removido for o último registro com o valor dado para a chave de busca, então removermos o valor chave de busca do índice.

3°) Para índices densos, removemos um valor da chave de busca da mesma forma que removemos um registro de arquivo.

4°) Para índices esparsos, removemos um valor da chave substituindo sua entrada no índice (se existir) com o próximo valor da chave de busca (na ordem desta).

5°) Se o próximo valor da chave de busca já é uma entrada no índice, removemos essa entrada.

·      Inserção:

1°) Faz-se uma busca usando o valor da chave de busca que aparece no registro a ser inserido.

2°) Se o índice é denso, e o valor chave de busca não aparece no índice, ele é inserido.

3°) Se o índice é esparso, nenhuma mudança precisa ser feita no índice, a menos que um novo bloco seja criado. Nesse caso, o primeiro valor da chave de busca (na ordem desta) que aparece no novo bloco é inserido no banco de dados.

v     Arquivos Indexados com Árvore-B+

É a estrutura de arquivo mais largamente utilizada dentre as diversas estruturas que mantêm sua eficiência independentemente da inserção e da remoção de dados. Um índice em forma de Árvore-B+  toma a forma de uma árvore balanceada em que todo caminho da raiz a uma folha da árvore é do mesmo tamanho. Esta estrutura impõe algumas sobrecargas na inserção e remoção bem como algum espaço adicional.

Tal sobrecarga é aceitável para arquivos com uma alta freqüência de modificação uma vez que o custo da reorganização de arquivo é evitado.

Um nó típico de uma Árvore-B+ é mostrado no exemplo abaixo. Ela contém até n-1 valores da chave de busca K1, K2, ..., Kn-1 e n ponteiros P1, P2, ... , Pn. Os valores da chave de busca dentro de um nó são mantidos em ordem crescente;

P1   K1   P2              ...       Pn-1   Kn-1 Pn

                 Ex.: Um nó típico de uma Árvore-B+

Cada nó da Árvore-B+ é formado por N conjuntos (ponteiro/chave). Não pode existir em um nó menos que (N+1)/2 conjuntos de (p, c).

Os ponteiros nos nós não-folhas apontam para outros nós, enquanto que os dos nós-folhas apontam para o arquivo de dados ou bucket.

Na estrutura da Árvore-B+ os nós-folhas são ligados por ponteiros para permitir o acesso seqüencial.

O comprimento de cada caminho da raiz para um nó folha é o mesmo. Essa propriedade é uma exigência para uma Árvore-B+. Realmente, o “B” na Árvore-B+ é entendido como abreviatura de “balanceamento”. É a propriedade do balanceamento das Árvore-B+ que asseguram bom desempenho para busca, inserção e remoção.

Processamento das Consultas:

As consultas partem do nó raiz, identificando o menor valor de chave de busca que seja maior que o registro procurado. Seguindo o Ponteiro, seguimos para o nó imediatamente seguinte, e assim por diante até que encontremos o nó folha, que nos indicará o registro desejado.

Processamento de Atualização:

A inserção e a remoção são mais complicadas do que a busca, uma vez que pode ser necessário dividir (“split”) um nó que se torne demasiadamente grande devido ao resultado de uma inserção, ou combinar nós caso um nó torne-se muito pequeno. Além do mais, quando um nó é dividido ou um par de nós é combinado, precisamos assegurar que o balanceamento seja preservado.

Inserção:

·      Usando a mesma técnica da busca, encontramos o nó folha no qual o valor da chave de busca apareceria.

·      Se o valor da chave de busca já esta no nó folha, adicionamos o novo registro e se necessário , um ponteiro para o bucket.

·      Se o valor da chave de busca não é encontrado, inserimos o valor no nó folha, e o posicionamos de tal forma que as chaves de busca estejam ainda em ordem.

·      Então inserimos o novo registro no arquivo e, se necessário, criamos um novo bucket com o ponteiro apropriado.

Remoção:

·      Usando a mesma técnica da busca, encontramos o registro a ser removido e o removemos do arquivo.

·      O valor da chave de busca é removido do nó folha se não existir nenhum bucket associado a esse valor, ou se o bucket se torna vazio como resultado de uma remoção.

v     Arquivos Indexados com Árvore-B

Índices em forma de Árvore-B são similares a índices em forma de Árvore-B+. A principal diferença entre essas duas abordagens é que uma Árvore-B elimina o armazenamento redundante de valores da chave de busca. Na Árvore-B+ , dos exemplos citados acima, as chaves de busca “Downtown”, “Mianus”, “Redwood” e “Perryridge” aparecem duas vezes. Todo valor da chave de busca aparece em algum nó folha.

Nessa forma de indexação, as chaves de busca aparecem apenas uma vez. Uma vez que essas chaves de busca não são repetidas, a quantidade de nós na árvore tende a ser menor. No entanto, uma vez que chaves de busca que aparecem em nós não-folha não aparecem em nenhum outro lugar na Árvore-B, somos forçados a incluir um ponteiro adicional para cada chave de busca em um nó não-folha. Estes ponteiros adicionais apontam para registros ou para buckets do arquivo para a chave de busca associada.

Nó folha de uma Árvore-B. Os ponteiros P1, P2 são os três ponteiros que usamos também para Árvore-B+.

P1                             K1     P2      ...      Pn-1     Kn-1      Pn

Nó não-folha de uma Árvore-B. Os ponteiros B1  são ponteiros para buckets ou para registros do arquivo.

P1                             B1      K1     P2      B2     ...      Pn-1     Bn-1       Kn-1      Pn

As Árvore-B oferecem uma vantagem adicional sobre Árvore-B+, além da ausência do armazenamento redundante de chaves de busca. Em uma busca na Árvore-B+, é sempre necessário atravessar um caminho de uma raiz da árvore até algum nó folha. No entanto, em uma Árvore-B, às vezes é possível encontrar o valor desejado antes de ler um nó folha.

9.2. Hashing

v     Hashing Estáticas

A técnica do Hashing permite-nos evitar o acesso a uma estrutura de índice. O endereço do bucket que contém um ponteiro para o item de dado desejado é obtido diretamente pela computação de uma função usando o valor da chave de busca do registro desejado.

O princípio subjacente do Hashing é que, embora o conjunto K de todos os valores de chave de busca possíveis seja grande (talvez infinito), o conjunto {K1, K2,..., Kn} dos valores da chave de busca atualmente armazenado no banco de dados é muito menor do que K. Escolhemos o número de buckets correspondente ao número de valores da chave de busca que esperamos ter armazenados no banco de dados. É a função de Hashing que define a atribuição de valores da chave de busca para buckets particulares.

A função de Hashing requer um projeto cuidadoso, pois uma má função de Hashing pode resultar em buscas tomando tempo proporcional ao número de chaves de busca no arquivo. Hashing Estáticas devem ser definidas quando implementamos o sistema e não podemos mudá-las facilmente mais tarde.

v     Hashing Dinâmicas

O Hashing estático deve fixar o conjunto de endereços de buckets no momento da definição do sistema, porém como a tendência é o crescimento do tamanho dos bancos de dados com o tempo, o uso dessa técnica pode se tornar complicada a longo prazo.

Diversas técnicas de Hashing permitem que a função seja modificada dinamicamente a fim de acomodar o crescimento ou encolhimento do banco de dados. Estas técnicas são chamadas Funções de Hashing Dinâmico.

Uma das formas de Hashing Dinâmico é o Hashing Extensível. Este enfrenta mudanças no tamanho do banco de dados agrupando e dividindo os buckets à medida que o banco de dados cresce e encolhe. Como resultado, é sacrificada a eficiência de espaço. Além disso, uma vez que a reorganização é feita em um bucket de cada vez, a sobrecarga no desempenho é aceitavelmente baixa.

v     Comparação entre Indexação e Hashing

Existem vários esquemas de Indexação e de Hashing. Para fazer uma escolha acertada, o projetista do banco de dados deve considerar:

1) É aceitável reorganização?

2) Qual a freqüência das Inclusões/Exclusões?

3) Como otimizar a média dos tempos de acesso?

4) Quais tipos de consulta serão realizadas?