Índices e B-trees

O índice remissivo de um livro

Para achar todas as menções a "recursão" num livro de 800 páginas, há duas opções: ler as 800 páginas, ou ir ao índice remissivo no fim, achar "recursão" (que está em ordem alfabética) e ler a lista de páginas. O índice remissivo é uma estrutura separada, ordenada e menor que aponta de volta para o conteúdo.

Um índice de banco é exatamente isso. E carrega os mesmos custos: ocupa páginas extras no fim do livro, e se você reescrever um capítulo, precisa refazer o índice. É por isso que um banco com muitos índices lê rápido e escreve devagar — cada INSERT precisa atualizar cada um deles.

A árvore, e o ponto em que ela deixa de valer a pena

Na primeira aba, busque uma chave e conte as páginas lidas com e sem índice; troque para o modo intervalo para ver por que as folhas são encadeadas. Na segunda, mexa na seletividade e encontre o ponto em que o otimizador passa a preferir varrer a tabela inteira.

Por que B+tree

-- Um índice é uma estrutura ORDENADA e separada, mantida pelo banco,
-- que mapeia valor → localização física da linha.

CREATE INDEX idx_email ON usuarios(email);

-- Por que B+tree e não uma árvore binária balanceada?
-- Porque o gargalo aqui não é comparação de CPU, é LEITURA DE DISCO.
-- Ler 1 byte custa quase o mesmo que ler uma página de 8 KB.
--
--   Árvore binária, 1 bilhão de chaves:
--     altura ≈ log₂(10⁹) = 30 → até 30 leituras de disco
--
--   B+tree com 256 chaves por nó (uma página cada):
--     altura ≈ log₂₅₆(10⁹) = 4 → 4 leituras de disco
--
-- Mesmo O(log n). Base do logaritmo diferente. Sete vezes menos I/O.

-- Duas escolhas de projeto da B+tree, e o porquê de cada uma:
--   1. os VALORES ficam só nas folhas; os nós internos guardam
--      apenas separadores → cabem mais chaves por página → menor altura
--   2. as folhas são LIGADAS entre si → ler um intervalo é descer
--      uma vez e seguir a lista, sem voltar à raiz a cada valor

Quando o índice é usado — e quando não é

-- O índice serve para:                    Mas NÃO serve para:
WHERE email = '[email protected]'          -- ✓  igualdade
WHERE idade BETWEEN 20 AND 30     -- ✓  intervalo (por ser ordenado)
ORDER BY criado_em DESC          -- ✓  ordenação de graça
WHERE nome LIKE 'Ana%'           -- ✓  prefixo fixo

WHERE nome LIKE '%Ana'           -- ✗  sufixo: a ordem não ajuda
WHERE LOWER(email) = '[email protected]'  -- ✗  função sobre a coluna
WHERE idade + 1 > 30            -- ✗  expressão sobre a coluna
WHERE ativo = true              -- ✗  seletividade péssima (50%)

-- A regra: o índice guarda o VALOR DA COLUNA. Se você aplica uma
-- função nela, o banco não tem o resultado dessa função guardado
-- em lugar nenhum e precisa calcular linha a linha.

-- Solução: índice sobre a EXPRESSÃO
CREATE INDEX idx_email_lower ON usuarios(LOWER(email));
-- agora WHERE LOWER(email) = ... usa índice

-- Índice PARCIAL: só indexa o que interessa. Menor e mais rápido.
CREATE INDEX idx_pendentes ON pedidos(criado_em)
    WHERE status = 'pendente';

Índices compostos e a regra do prefixo

-- ÍNDICE COMPOSTO: a ordem das colunas muda tudo.
CREATE INDEX idx ON pedidos(cliente_id, criado_em);

-- Pense numa lista telefônica ordenada por (sobrenome, nome).
-- Você consegue achar "todos os Silva" e "Silva, Ana".
-- Mas achar "todas as Anas", de qualquer sobrenome? Impossível
-- sem ler tudo — porque as Anas estão espalhadas.

-- Este índice serve para:
WHERE cliente_id = 7                          -- ✓ prefixo
WHERE cliente_id = 7 AND criado_em > '2024-01-01' -- ✓ completo
WHERE cliente_id = 7 ORDER BY criado_em         -- ✓ ordena de graça

-- E NÃO serve para:
WHERE criado_em > '2024-01-01'                  -- ✗ pula a 1ª coluna

-- Isso se chama regra do PREFIXO MAIS À ESQUERDA.
-- Corolário prático: um índice em (a, b) torna desnecessário um
-- índice só em (a) — mas não substitui um índice só em (b).

-- ÍNDICE COBRINDO (covering index): se todas as colunas da consulta
-- estão no índice, o banco responde SEM TOCAR na tabela.
CREATE INDEX idx ON pedidos(cliente_id) INCLUDE (valor);
SELECT valor FROM pedidos WHERE cliente_id = 7;
--   → "Index Only Scan" no EXPLAIN. O caminho mais rápido possível.

O custo dos índices

-- Índice não é grátis. O que ele custa:
--
--  1. ESPAÇO — um índice pode ocupar 10-30% do tamanho da tabela.
--     Cinco índices podem ocupar mais que os dados.
--
--  2. ESCRITA — todo INSERT/UPDATE/DELETE precisa atualizar TODOS
--     os índices da tabela, cada um com sua própria descida na
--     B+tree e eventual divisão de página.
--     Uma tabela com 8 índices pode ter escrita 5x mais lenta.
--
--  3. PLANOS PIORES — mais opções para o otimizador significa mais
--     chance de ele escolher errado com estatísticas ruins.

-- Como decidir: MEÇA, não adivinhe.
EXPLAIN ANALYZE SELECT ... ;   -- o plano real, com tempos

-- No PostgreSQL, índices que ninguém usa aparecem aqui:
SELECT relname, indexrelname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0;              -- nunca usados: candidatos a DROP

-- E como criar sem travar a tabela em produção:
CREATE INDEX CONCURRENTLY idx ON tabela(coluna);
-- (mais lento, mas não bloqueia escritas — em tabela grande,
--  a diferença entre uma manutenção invisível e uma queda)

Medindo de verdade

Mini projeto: crie uma tabela com 1 milhão de linhas geradas (em PostgreSQL, generate_series faz isso numa linha). Rode EXPLAIN ANALYZE numa consulta por igualdade, crie o índice, rode de novo e compare os tempos e os planos. Depois teste LIKE 'abc%' e LIKE '%abc' e confirme que só o primeiro usa o índice.

Projeto principal: encontre o ponto de virada da seletividade no seu próprio banco. Com uma coluna que tenha valores repetidos em proporções variadas, rode a mesma consulta filtrando valores que retornam 0,1%, 1%, 5% e 20% da tabela, sempre com EXPLAIN ANALYZE. Anote em que ponto o plano muda de Index Scan para Seq Scan. Você acabou de medir na prática a curva do widget acima — e o número vai depender do seu hardware, porque em SSD o custo do acesso aleatório é bem menor que em disco rígido.

Desafio extra: meça o custo de escrita. Crie duas tabelas idênticas, uma sem índices e outra com seis, e cronometre a inserção de 100 mil linhas em cada. Depois compare o tamanho em disco (pg_total_relation_size). O resultado costuma surpreender quem só pensou em índices do ponto de vista da leitura — e é o argumento que falta em toda discussão sobre "vamos indexar tudo por precaução".

Teste sua intuição

Onde você encontra isso