Trabalho Indexação E Hash

Trabalho - Indexação e Hashing, Processamento e Otimização de Consultas
Jonas Forte Silva – 27298

1. Indexação e Hashing

Para obter ordenação, e facilitar a localização de informações, a utilização de índices no armazenamento de arquivos e informações é comum e necessária. Índices baseados em hash é extremamente utilizado pela sua baixa complexidade de busca.
A idéia de usar Hashing é que esta função mapeia um valor da chave de pesquisa (atributo de uma tabela) em um registro ou balde (bucket) de registros. Índices baseados em Hashing são melhores para pesquisas por igualdade e péssimos para pesquisa por gama. A função de hash h é uma função do conjunto de todos os valores da chave k para o conjunto dos endereços de todos os baldes. A função de hash é usada para localizar registros para as operações de acesso, inserção e eliminação.

A função de hash usada para índices de hash tem as seguintes características:





O SQL Server tem uma função de hash que é usada para todos os índices de hash.
A função de hash é determinística.A mesma chave de índice sempre é mapeada para o mesmo bucket no índice de hash.
Várias chaves de índice podem ser mapeadas para o mesmo bucket de hash. A função de hash é equilibrada, o que significa que a distribuição de valores de chave do índice sobre buckets de hash geralmente segue uma distribuição de Poisson.

1.1. Balde
É uma unidade de armazenamento que contém um ou mais registros (tipicamente é um bloco do disco)
1.2. Hashing Estático
Registros com diferentes valores de chave podem ou não ser mapeados para o mesmo balde sendo assim o balde inteiro tem que ser pesquisado sequencialmente para localizar um registro específico. As páginas são alocadas sequencialmente e nunca desalocadas assim como páginas de transbordo podem ser necessárias. Longas cadeias de transbordo podem desenvolver e degradar o desempenho. Hashing extensível e Hashing linear são técnicas para consertar este problema
1.3. Hashing Extensível
Tem estruturas e