Índices B-tree e Range Scans: Acelerar Filtros e Ordenações

O que é um índice B-tree (e por que ele serve para igualdade e intervalos)

Índices do tipo B-tree (ou variações como B+tree) são os mais comuns para acelerar buscas por igualdade e por intervalos. A ideia central é manter as chaves do índice em ordem, permitindo localizar rapidamente um ponto (uma chave específica) e, a partir dele, caminhar de forma ordenada por um trecho contínuo do índice.

Essa ordenação é o motivo de a B-tree ser especialmente boa para:

• = (igualdade), por exemplo id = 42
• >, <, BETWEEN (intervalos), por exemplo data BETWEEN '2026-01-01' AND '2026-01-31'
• ORDER BY (ordenar sem precisar ordenar “na mão”)
• prefixos de ordenação/filtragem em índices compostos (por exemplo, usar (cliente_id, data) para filtrar por cliente_id e ordenar por data)

Seek vs Scan no índice: duas formas de “andar” na B-tree

Index seek (busca pontual)

Seek é quando o banco consegue “pular” diretamente para a região do índice onde está a chave desejada (ou o início do intervalo). É o comportamento típico de coluna = valor e também do começo de um range scan (quando há intervalo).

Exemplo conceitual: para id = 42, o mecanismo navega pela árvore até encontrar a entrada correspondente (ou concluir que não existe), lendo poucas páginas do índice.

Index scan (varredura)

Scan é quando o banco percorre uma parte grande do índice (ou até ele inteiro) porque não há um ponto inicial seletivo o suficiente, ou porque o predicado não permite localizar um intervalo contínuo. Scans podem ser aceitáveis em tabelas pequenas, mas em geral crescem com o volume de dados.

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

Importante: existe um meio-termo muito comum e desejável: o range scan, que começa com um seek e depois percorre sequencialmente um trecho ordenado do índice.

Por que a ordenação natural da B-tree permite “range scan”

Como as chaves no índice estão em ordem, ao encontrar o primeiro valor de um intervalo (por exemplo, a primeira data de um mês), o banco pode simplesmente seguir adiante no índice até ultrapassar o fim do intervalo. Isso evita ler registros fora do período e evita ordenar resultados se o ORDER BY for compatível com a ordem do índice.

Em termos práticos, um range scan costuma ter esta forma mental:

• 1) localizar o primeiro item do intervalo (seek)
• 2) ler sequencialmente as próximas entradas do índice (scan ordenado)
• 3) parar quando a chave passar do limite superior

Caso típico 1: busca por id (igualdade)

Quando você filtra por uma chave única (ou altamente seletiva), a B-tree tende a ser extremamente eficiente.

SELECT * FROM usuarios WHERE id = 42;

O que favorece o seek aqui:

• Predicado simples: id = 42
• Sem função aplicada na coluna
• Tipo compatível (evitar comparar número com texto, por exemplo)

Passo a passo prático (como pensar na consulta)

• Passo 1: identifique a coluna de filtro principal (ex.: id).
• Passo 2: garanta que o predicado é direto e sargável (ex.: id = ?).
• Passo 3: se você só precisa de algumas colunas, considere selecionar apenas elas para reduzir leitura (mesmo com índice, buscar muitas colunas pode exigir mais acesso a dados).

Caso típico 2: busca por data em um período (intervalo / BETWEEN)

Filtros por período são o cenário clássico de range scan.

SELECT id, cliente_id, total, data_compra FROM pedidos WHERE data_compra >= '2026-01-01' AND data_compra < '2026-02-01';

Esse formato (>= e <) é frequentemente preferível a BETWEEN quando você quer evitar ambiguidades com horários (por exemplo, registros em 2026-01-31 23:59:59). O ponto principal é: o predicado define um intervalo contínuo na ordem do índice.

Passo a passo prático (montando um range scan eficiente)

• Passo 1: defina limites inferior e superior claros (ex.: início do mês e início do mês seguinte).
• Passo 2: escreva o predicado diretamente na coluna (data_compra >= ... e data_compra < ...).
• Passo 3: se também houver filtro por outra coluna (ex.: cliente_id), avalie índice composto na ordem que favoreça o padrão de consulta (ex.: (cliente_id, data_compra) quando você filtra por cliente e por período).

Caso típico 3: paginação com ORDER BY (evitar ordenar e evitar “pular” caro)

Quando o ORDER BY segue a ordem do índice, o banco pode retornar linhas já ordenadas, reduzindo custo de ordenação. Isso é especialmente útil em paginação.

Paginação com LIMIT/OFFSET (pode degradar)

SELECT id, data_compra, total FROM pedidos ORDER BY data_compra DESC LIMIT 20 OFFSET 2000;

Mesmo com índice em data_compra, offsets altos podem obrigar o banco a “andar” por muitas entradas até chegar na página desejada. Isso é um tipo de scan de um trecho grande.

Paginação por “seek method” (keyset pagination)

Uma alternativa é paginar usando a última chave vista, o que permite um seek direto e um range scan curto.

-- primeira página SELECT id, data_compra, total FROM pedidos ORDER BY data_compra DESC, id DESC LIMIT 20; -- próxima página (usando o último par data_compra/id da página anterior) SELECT id, data_compra, total FROM pedidos WHERE (data_compra < :ultima_data) OR (data_compra = :ultima_data AND id < :ultimo_id) ORDER BY data_compra DESC, id DESC LIMIT 20;

Por que incluir id no ORDER BY: garante desempate estável (ordem determinística) e ajuda a construir um “cursor” consistente. Em muitos cenários, um índice composto como (data_compra DESC, id DESC) (ou equivalente) melhora bastante.

Caso típico 4: funções na coluna e o impacto na sargabilidade

Um predicado é sargável quando o banco consegue transformá-lo em uma busca por intervalo no índice (seek/range scan) sem precisar calcular algo para cada linha. Quando você aplica uma função na coluna indexada, muitas vezes o banco perde a capacidade de localizar um intervalo contínuo e acaba fazendo scan.

Exemplos comuns de predicados não sargáveis

-- função na coluna (pode impedir range scan) WHERE DATE(data_compra) = '2026-01-15' -- transformação na coluna WHERE UPPER(email) = 'ANA@EXEMPLO.COM' -- cálculo na coluna WHERE preco * 1.1 > 100 -- conversão implícita (tipo incompatível) WHERE id = '42'

Reescritas para manter sargabilidade (conceito, sem prender a um SGBD)

1) Data por dia (evitar DATE(coluna))

-- ruim (função na coluna) WHERE DATE(data_compra) = '2026-01-15' -- melhor (intervalo sargável) WHERE data_compra >= '2026-01-15' AND data_compra < '2026-01-16'

2) Texto com case-insensitive (evitar UPPER(coluna) no filtro)

Opções conceituais:

• armazenar uma versão normalizada (ex.: email_normalizado) e indexá-la
• usar collation/configuração que compare sem diferenciar maiúsculas/minúsculas (quando disponível)

-- ruim WHERE UPPER(email) = 'ANA@EXEMPLO.COM' -- melhor (com coluna normalizada) WHERE email_normalizado = 'ana@exemplo.com'

3) Cálculo no lado do parâmetro (em vez da coluna)

-- ruim WHERE preco * 1.1 > 100 -- melhor (isolar a coluna) WHERE preco > 100 / 1.1

4) Tipos compatíveis (evitar conversão implícita)

-- ruim (id numérico comparado com texto) WHERE id = '42' -- melhor WHERE id = 42

ORDER BY, prefixos e índices compostos: quando a B-tree “resolve” filtro e ordenação

Em índices compostos, a ordem das colunas importa. A B-tree fica ordenada primeiro pela primeira coluna, depois pela segunda, e assim por diante. Isso cria um comportamento de “prefixo”: você aproveita melhor o índice quando filtra/ordena seguindo o começo dessa ordem.

Exemplo: índice (cliente_id, data_compra)

Esse índice tende a ser ótimo para:

• WHERE cliente_id = ? AND data_compra BETWEEN ? AND ? (seek em cliente, range scan em data)
• WHERE cliente_id = ? ORDER BY data_compra (já sai ordenado dentro do cliente)

Mas costuma ser menos útil para:

• WHERE data_compra BETWEEN ? AND ? sem filtrar cliente_id (o índice ainda está ordenado por cliente primeiro; pode não ser o melhor caminho)

Checklist: padrões de consulta que favorecem B-tree

• Predicados sargáveis com operadores de comparação direta: =, >=, <=, BETWEEN
• Intervalos bem definidos (principalmente em datas): coluna >= inicio AND coluna < fim
• ORDER BY alinhado com a ordem do índice (incluindo direção quando aplicável)
• Paginação por chave (keyset) em vez de offsets altos
• Índices compostos desenhados para o padrão real: filtrar pela primeira coluna e, se necessário, fazer range/ordenação pelas seguintes
• Comparações com tipos compatíveis (evitar conversões implícitas)
• Evitar funções/cálculos na coluna filtrada/ordenada; preferir reescrever para isolar a coluna

Exemplos rápidos de reescrita de predicados (sargabilidade)