Índices Hash: Igualdade Rápida e Limites para Intervalos

O que é um índice hash (e o que ele otimiza)

Um índice hash organiza os valores de uma coluna (ou conjunto de colunas) aplicando uma função de hash que transforma a chave em um “balde” (bucket). A ideia é simples: se você procurar por um valor exato, o banco calcula o hash desse valor, vai direto ao bucket correspondente e encontra rapidamente as linhas (ou ponteiros para as linhas).

Isso torna índices hash especialmente úteis para predicados de igualdade, como = e, em alguns casos, IN (...). Em contrapartida, eles geralmente não ajudam em intervalos (range) e ordenação, porque o hash destrói a noção de “proximidade” entre valores: chaves próximas podem cair em buckets totalmente diferentes.

Quando um índice hash tende a ser útil

• Busca por igualdade: WHERE email = 'x@dominio.com'
• Chaves com boa seletividade (muitos valores distintos), reduzindo a quantidade de linhas por bucket
• Padrão de consulta estável e centrado em “encontrar um item específico”
• Junções por igualdade em algumas estratégias internas (dependendo do SGBD e do plano)

Quando um índice hash costuma não servir

• Intervalos: WHERE created_at BETWEEN ..., WHERE price > 100
• Ordenação: ORDER BY created_at, ORDER BY price
• Prefixos e padrões: LIKE 'abc%' (em geral)
• Consultas que precisam “caminhar” por valores vizinhos (top-N por faixa, paginação por ordem etc.)

Por que hash não funciona bem para range e ordenação

Em um índice que preserva ordem, valores próximos ficam próximos na estrutura, permitindo varrer uma faixa contínua. No índice hash, o valor 100 e o valor 101 não têm relação espacial: o hash pode mandar cada um para um bucket distante. Para responder a um intervalo, o banco não tem um “ponto de partida” e um “caminho” natural para percorrer apenas a faixa. Na prática, ele teria que:

• ou examinar muitos buckets (potencialmente todos),
• ou ignorar o índice e fazer outra estratégia (varredura, outro índice, etc.).

Para ORDER BY, o problema é similar: o índice hash não mantém as chaves em ordem, então não consegue produzir resultados já ordenados. Mesmo que ele ajude a localizar linhas, a ordenação ainda exigiria um passo extra (sort) sobre o conjunto retornado.

Colisões: custo médio vs pior caso (conceitualmente)

Colisão acontece quando chaves diferentes geram o mesmo hash (ou caem no mesmo bucket). Como isso é inevitável em algum grau, o índice hash precisa de uma forma de lidar com múltiplas entradas no mesmo bucket. Conceitualmente, há duas abordagens comuns:

Continue em nosso aplicativo e ...

• Ouça o áudio com a tela desligada
• Ganhe Certificado após a conclusão
• + de 5000 cursos para você explorar!

ou continue lendo abaixo...

Baixar o aplicativo

• Encadeamento (chaining): o bucket aponta para uma lista/estrutura com várias entradas.
• Endereçamento aberto: o bucket tenta achar outra posição livre seguindo uma regra (sondagem).

O ponto importante para performance é a diferença entre:

• Custo médio: com boa função de hash e distribuição uniforme, cada bucket tem poucas entradas; buscar por igualdade tende a exigir poucas comparações.
• Pior caso: se muitas chaves caem no mesmo bucket (por colisões ou distribuição ruim), a busca pode degradar para examinar muitas entradas dentro do bucket, aproximando-se de um comportamento “quase linear” naquele conjunto.

Em termos práticos, índices hash podem ser muito rápidos no cenário típico, mas são mais sensíveis a distribuição de valores e a padrões de uso que aumentem colisões efetivas (muitos registros com o mesmo valor, ou valores concentrados).

Exemplos: igualdade vs intervalo (e como cada índice responde)

Cenário de tabela

CREATE TABLE pedidos (  id BIGINT PRIMARY KEY,  cliente_id BIGINT NOT NULL,  status VARCHAR(20) NOT NULL,  created_at TIMESTAMP NOT NULL,  total NUMERIC(10,2) NOT NULL);

Imagine dois índices possíveis (conceitualmente):

• Índice hash em cliente_id (bom para igualdade).
• Índice ordenado (ex.: B-tree) em created_at (bom para intervalos e ordenação).

Consulta 1: igualdade simples

SELECT * FROM pedidos WHERE cliente_id = 42;

Consulta 2: igualdade com IN

SELECT * FROM pedidos WHERE cliente_id IN (10, 20, 30);

Com índice hash, o banco tende a fazer 3 buscas independentes (um bucket por valor). Isso pode ser bom se a lista for pequena e seletiva. Se a lista for grande, o custo pode crescer por muitas buscas aleatórias.

Consulta 3: intervalo (range)

SELECT * FROM pedidos WHERE created_at >= '2026-01-01' AND created_at < '2026-02-01';

Consulta 4: ordenação + limite (top-N)

SELECT * FROM pedidos ORDER BY created_at DESC LIMIT 50;

Índice hash não ajuda a produzir a ordem. Um índice ordenado pode entregar os 50 mais recentes diretamente (dependendo do plano e da cobertura). Com hash, o banco tende a precisar ordenar resultados após ler muitos registros.

Consulta 5: igualdade em coluna de baixa seletividade (armadilha)

SELECT * FROM pedidos WHERE status = 'PENDENTE';

Se status tem poucos valores possíveis (ex.: PENDENTE, PAGO, CANCELADO), um índice hash em status pode levar a buckets muito “cheios”. Nesse caso, mesmo sendo igualdade, o ganho pode ser pequeno porque o bucket retornará uma grande fração da tabela.

Passo a passo prático: como decidir se um índice hash faz sentido

1) Liste as consultas reais e classifique os predicados

• Quantas são igualdade (=, IN)?
• Quantas são intervalo (>, <, BETWEEN)?
• Quantas exigem ORDER BY ou paginação por ordem?

Se a maioria das consultas críticas é por igualdade em uma coluna específica, o hash entra como candidato. Se range/ordenação são comuns, hash tende a ser inadequado.

2) Verifique seletividade e distribuição de valores

Perguntas práticas:

• O valor filtrado costuma retornar poucas linhas?
• Há concentração (ex.: muitos registros com o mesmo valor)?
• Existem “hot keys” (alguns valores muito mais frequentes)?

Distribuição desigual aumenta o tamanho de alguns buckets e piora o tempo de busca nesses casos, aproximando o comportamento do pior caso para as chaves mais populares.

3) Estime o impacto de colisões (conceitualmente) pela densidade

Você não precisa calcular hashes para ter intuição: se muitos registros compartilham o mesmo valor (ou poucos valores dominam), o bucket correspondente ficará grande. Mesmo sem “colisão” de hash entre valores diferentes, o efeito prático é semelhante: muita coisa para examinar dentro do bucket.

4) Compare com alternativas para o mesmo padrão de consulta

• Para igualdade em coluna bem seletiva: hash pode ser ótimo.
• Para igualdade + necessidade frequente de ordenação por outra coluna: talvez um índice ordenado (ou composto) seja mais útil no conjunto.
• Para consultas mistas (igualdade e range): priorize o índice que atende o gargalo principal; hash pode virar índice “especializado” e pouco usado.

5) Cheque armadilhas comuns antes de criar

• Baixa seletividade: igualdade que retorna muita linha reduz o benefício do hash.
• Distribuição desigual: poucos valores dominantes criam buckets grandes e pioram o pior caso.
• Dependência do padrão de consulta: se o sistema evoluir para usar range/ordenação naquela coluna, o hash deixa de ajudar.
• IN muito grande: muitas buscas pontuais podem virar custo alto por acessos aleatórios.

Critérios de escolha (checklist rápido)