Document

1.2 - Índice Hash

A técnica de hash tem por objetivo separar um grande conjunto em conjuntos menores, dessa forma, uma pesquisa linear posterior pode ser feita com maior performance.

Essa técnica é indicada para campos grandes onde um índice b-tree geraria um arquivo muito grande.

Vamos ver um exemplo. Suponha que tenhamos uma tabela para cadastro de Boletos Bancários. Os campos mais comuns de um boleto bancário são:

Número do código de barras (geralmente com 44 caracteres),
data de vencimento e
valor.

Se fôssemos criar um índice b-tree para o campo de código de barras, esse arquivo teria 44 bytes para o registro do número do código de barras e mais 8 bytes para a localização do bloco. Perceba que cada registro precisa de 52 bytes. Uma linha de registro da tabela de boletos bancários possui 4 bytes para a chave primária, 44 bytes para o código de barras, 4 bytes para a data de vencimento e 4 bytes para o valor, totalizando 56 bytes. Veja que o tamanho do índice (52 bytes por linha) é praticamente o mesmo tamanho do registro da tabela (56 bytes por linha). Assim, o uso do índice pode não ser tão eficiente quanto o desejado, pois uma pesquisa teria que varrer um arquivo muito grande.

É nesse contexto que entra a ideia do índice hash. Ao invés de ter apenas um arquivo de índice grande, o algoritmo do hash identifica uma forma de quebrar esse arquivo em vários arquivos de índice menores. Dessa forma, a pesquisa é feita em um arquivo pequeno.

Veja a seguir como isso é feito.