Índices, otimização de consultas e estruturas de indexação (B-tree e Hash)

Chegamos a um dos módulos que mais separam quem entende banco de dados de quem apenas escreve SQL: a indexação e a otimização de consultas. Eu te garanto que esse tema cai em prova, e cai de formas variadas — desde a pergunta conceitual “para que serve um índice” até a pergunta capciosa sobre por que um índice Hash não serve para uma busca por intervalo. Quero que você termine este módulo enxergando o índice não como uma caixa-preta mágica que “deixa a consulta mais rápida”, mas como uma estrutura de dados concreta, com custo de espaço, custo de manutenção e um comportamento previsível. Vou te conduzir do conceito geral até o detalhe das B-trees e das tabelas hash, e no fim você saberá escolher a estrutura certa para cada cenário. Repare comigo: tudo aqui gira em torno de uma única obsessão — reduzir o número de acessos ao disco.

Por que índices existem

Imagine que você precisa encontrar a palavra “transação” em um livro de oitocentas páginas sem índice remissivo. Você leria página por página. Esse é o método que chamamos de full table scan (varredura completa da tabela): o SGBD percorre cada linha verificando a condição. Agora imagine o mesmo livro com um índice remissivo no fim — você vai direto à entrada certa e salta para a página. O índice de banco de dados é exatamente esse índice remissivo: uma estrutura auxiliar que mapeia valores de uma coluna para a localização física dos registros, evitando a leitura sequencial de tudo.

O propósito central, então, é reduzir acessos a disco. Em uma tabela com dez milhões de linhas, uma varredura completa pode significar dezenas de milhares de leituras de página; uma busca via índice bem construído resolve o mesmo em três ou quatro leituras. Essa diferença é o que separa uma consulta de milissegundos de uma consulta de minutos.

Definição. Um índice é uma estrutura de dados secundária, mantida pelo SGBD em paralelo à tabela, que organiza os valores de uma ou mais colunas (a chave de indexação) de modo a acelerar a localização de registros. Ele não armazena os dados em si necessariamente, mas ponteiros para onde os dados estão.

Tipos de índice e como criá-los

Você cria índices em SQL com o comando CREATE INDEX. Deixa eu te mostrar os tipos mais comuns, porque a prova adora distingui-los. O mais simples é o índice de coluna única, ideal quando você filtra repetidamente por um atributo:

CREATE INDEX idx_estudante_nome ON estudantes (nome);

Quando suas consultas filtram por mais de uma coluna ao mesmo tempo, usa-se o índice composto. Aqui há uma sutileza que vale ouro em prova: a ordem das colunas importa. Um índice em (nome, curso) serve para filtrar só por nome, ou por nome e curso juntos, mas não serve bem para filtrar apenas por curso. É o que chamamos de princípio do prefixo mais à esquerda.

CREATE INDEX idx_estudante_nome_curso ON estudantes (nome, curso);

Há também o índice único, que além de acelerar buscas impõe uma restrição de integridade: nenhum valor duplicado é aceito na coluna. Ele é o mecanismo físico por trás das chaves primárias e das restrições UNIQUE.

CREATE UNIQUE INDEX idx_estudante_email ON estudantes (email);

Além desses, existem índices especializados: o índice de texto completo, otimizado para buscar palavras dentro de campos textuais longos, e o índice espacial, voltado para coordenadas geográficas. Em PostgreSQL você ainda encontra índices bitmap, que representam a presença de valores com cadeias de bits e brilham em colunas de baixa cardinalidade. Por ora, foque nos três primeiros tipos, que são os que mais aparecem.

Atenção — o índice não é de graça. Cada índice ocupa espaço em disco e precisa ser atualizado a cada INSERT, UPDATE ou DELETE na coluna indexada. Em uma tabela com muitas escritas, índices em excesso degradam o desempenho. A regra é: indexe o que você consulta com frequência, não tudo. Índice é acelerador de leitura pago com lentidão de escrita.

Vou organizar visualmente essa decisão de quando criar um índice, porque ela é o coração prático do tema:

flowchart TD
    A[Coluna candidata a indice] --> B{Usada em WHERE, JOIN ou ORDER BY?}
    B -- Nao --> X[Nao indexe]
    B -- Sim --> C{A coluna tem alta cardinalidade?}
    C -- Nao --> D[Considere bitmap ou nao indexe]
    C -- Sim --> E{A tabela tem muitas escritas?}
    E -- Sim --> F[Avalie custo de manutencao]
    E -- Nao --> G[Crie o indice]
    F --> G

Índices clusterizados e não clusterizados

Aqui está uma distinção que você precisa dominar. Um índice clusterizado define a ordem física dos registros no disco — as linhas são gravadas na ordem da chave do índice. Por isso só pode existir um índice clusterizado por tabela: você não pode ordenar fisicamente os mesmos dados de duas maneiras ao mesmo tempo. Em muitos SGBDs, a chave primária cria automaticamente o índice clusterizado.

Já um índice não clusterizado é uma estrutura separada que guarda os valores da chave ordenados e, ao lado de cada valor, um ponteiro para a localização da linha real. Você pode ter vários índices não clusterizados por tabela. A analogia que eu gosto: o índice clusterizado é a própria ordem das páginas do livro; o não clusterizado é o índice remissivo no fim, que aponta para as páginas.

Característica	Clusterizado	Não clusterizado
Quantidade por tabela	Apenas um	Vários
Ordena fisicamente os dados	Sim	Não
Busca por intervalo	Muito eficiente	Eficiente, com saltos
Custo de leitura do registro	Direto	Indireto, via ponteiro
Custo de escrita	Maior (reordena)	Menor

O otimizador de consultas

Agora chegamos a um componente que muita gente nem sabe que existe: o otimizador de consultas. Quando você submete um SELECT, o SGBD não executa a consulta da forma literal como você a escreveu. Ele primeiro decide como executá-la — qual índice usar, em que ordem juntar as tabelas, se vale a pena varrer ou indexar. Esse plano de operações é o plano de execução.

O ponto que sempre surpreende o aluno é que a maioria dos otimizadores modernos é baseada em custo. Isso significa que o otimizador estima, para cada estratégia possível, um custo numérico aproximado (em termos de leituras de disco e processamento) e escolhe a de menor custo. E como ele estima esse custo? Por meio de estatísticas: histogramas e contagens que o SGBD mantém sobre a distribuição dos dados — quantas linhas há, quantos valores distintos uma coluna tem, como esses valores se distribuem.

flowchart LR
    A[Consulta SQL] --> B[Parser]
    B --> C[Reescrita logica]
    C --> D[Otimizador baseado em custo]
    E[(Estatisticas)] --> D
    D --> F[Plano de execucao]
    F --> G[Motor de execucao]
    G --> H[Resultado]

Daqui sai uma lição prática poderosa: se as estatísticas estiverem desatualizadas, o otimizador toma decisões ruins. Ele pode achar que uma coluna tem dez valores distintos quando na verdade tem dez mil, e escolher uma varredura completa onde um índice seria muito melhor. Por isso, manter estatísticas atualizadas é uma das boas práticas mais subestimadas.

-- Atualiza as estatisticas que o otimizador consulta
ANALYZE estudantes;

Lendo planos de execução com EXPLAIN

A ferramenta que te dá raio-X do plano é o EXPLAIN. Ela mostra a estratégia que o otimizador escolheu sem necessariamente executar a consulta. No PostgreSQL, EXPLAIN ANALYZE vai além e executa de fato, retornando os tempos reais.

EXPLAIN SELECT * FROM estudantes WHERE curso = 'Ciencia da Computacao';

O que você procura ali? Principalmente se aparece um Seq Scan (varredura sequencial, lê a tabela inteira) ou um Index Scan (usa o índice). Para uma consulta que retorna poucas linhas de uma tabela grande, ver um Seq Scan é sinal de alerta — provavelmente falta um índice ou as estatísticas estão erradas. Veja a diferença que um índice faz:

Antes do índice	Depois do índice
Seq Scan on estudantes	Index Scan using idx_estudante_curso
custo estimado: 18500	custo estimado: 32
linhas examinadas: 1.000.000	linhas examinadas: 240

Definição. O plano de execução é a sequência ordenada de operações físicas — varreduras, buscas em índice, junções, ordenações — que o SGBD efetivamente realiza para responder a uma consulta. O EXPLAIN revela esse plano; aprender a lê-lo é o que transforma você de quem escreve SQL em quem otimiza SQL.

Boas práticas de otimização

Deixa eu te passar, em prosa, as práticas que realmente movem o ponteiro. A primeira é usar índices de forma apropriada: crie-os nas colunas que aparecem em WHERE, JOIN e ORDER BY, e evite o excesso que penaliza escritas. A segunda é reescrever consultas para não cegar o índice. Um erro clássico é aplicar uma função sobre a coluna indexada na cláusula WHERE — isso geralmente impede o uso do índice, porque o valor calculado não está indexado.

-- Cega o indice: a funcao YEAR e aplicada a cada linha
SELECT * FROM pedidos WHERE EXTRACT(YEAR FROM data_pedido) = 2023;

-- Preserva o indice: a comparacao usa o valor cru da coluna
SELECT * FROM pedidos
WHERE data_pedido BETWEEN '2023-01-01' AND '2023-12-31';

A terceira prática é limitar resultados com LIMIT quando você não precisa de tudo, reduzindo dados transferidos. A quarta é evitar SELECT * e pedir só as colunas necessárias — isso, inclusive, pode permitir que o índice cubra a consulta inteira sem tocar na tabela. Para volumes muito grandes, entram técnicas estruturais como particionamento de tabelas, desnormalização controlada (lembre do nosso módulo de Normalização — às vezes uma redundância calculada compensa em leitura) e visões materializadas, que congelam o resultado de consultas pesadas. Por fim, monitore regularmente, faça revisão periódica dos índices para remover os que ninguém usa, e teste com cargas realistas.

Estruturas de indexação: a B-tree em profundidade

Agora vamos abrir a caixa-preta. Quando você cria um índice comum, o que o SGBD constrói por baixo, em quase todos os casos, é uma B-tree. Ela foi proposta por Rudolf Bayer e Edward McCreight em 1970, projetada deliberadamente para memória externa — ou seja, para minimizar leituras de disco. A ideia central é genial: em vez de uma árvore binária, onde cada nó tem dois filhos e a árvore fica alta, a B-tree é m-ária — cada nó tem até m filhos, onde m é a ordem da árvore. Com nós largos, a árvore fica baixa, e baixa significa poucos acessos a disco.

Uma B-tree de ordem m obedece a regras precisas que você deve memorizar. Cada nó tem no máximo m filhos e no máximo m-1 chaves. Cada nó interno, exceto a raiz, tem ao menos \lceil m/2 \rceil filhos — é a propriedade de ocupação mínima, que garante que a árvore não degenere. A raiz, se não for folha, tem pelo menos dois filhos. Um nó não-folha com k filhos guarda exatamente k-1 chaves, que funcionam como separadores entre as subárvores. E a propriedade decisiva: todas as folhas estão no mesmo nível. É isso que torna a árvore balanceada e garante desempenho previsível.

graph TD
    R["50 | 80"]
    A["10 | 30"]
    B["60 | 70"]
    C["85 | 90 | 95"]
    R --> A
    R --> B
    R --> C

A estrutura interna de um nó intercala ponteiros e chaves nesta forma: [P_1, K_1, P_2, K_2, \dots, K_{n-1}, P_n], onde cada chave K_i separa as subárvores apontadas por P_i e P_{i+1}. Tudo à esquerda de K_1 é menor que K_1; tudo entre K_1 e K_2 está nesse intervalo, e assim por diante.

A busca começa na raiz, compara a chave procurada com as chaves do nó, identifica o intervalo correto e desce pelo ponteiro correspondente, repetindo até achar a chave ou chegar à folha. Como a árvore é balanceada e larga, a complexidade é O(\log_m n) — logarítmica na base m, o que na prática significa altura de duas a quatro para milhões de registros.

A inserção localiza a folha apropriada e insere a chave em ordem. Se a folha estourar o limite de m-1 chaves, ela se divide em duas, e a chave do meio sobe para o pai. Se o pai também estourar, a divisão se propaga para cima; se chegar à raiz, cria-se uma nova raiz e a árvore cresce em altura — sempre pelo topo, jamais pelas folhas, o que preserva o balanceamento.

flowchart TD
    A[Inserir chave] --> B[Localiza folha correta]
    B --> C{Folha tem espaco?}
    C -- Sim --> D[Insere em ordem e termina]
    C -- Nao --> E[Divide a folha em duas]
    E --> F[Promove chave do meio ao pai]
    F --> G{Pai ficou cheio?}
    G -- Nao --> H[Termina]
    G -- Sim --> I[Divide o pai e propaga para cima]
    I --> G

A remoção é a operação mais delicada. Se a chave está numa folha que continua ao menos meio cheia após a remoção, basta tirá-la. Se a folha cai abaixo do mínimo, o SGBD tenta redistribuir chaves com um irmão vizinho; se não der, funde a folha com o irmão. Quando a chave está num nó interno, substitui-se ela pelo predecessor ou sucessor vindo das folhas, e remove-se esse de baixo. Se a fusão se propagar até esvaziar a raiz, ela é removida e a árvore encolhe em altura. As complexidades ficam assim:

Operação	Complexidade	Observação
Busca	O(\log_m n)	Pior caso, altura da árvore
Inserção	O(\log_m n) + divisão	Divisão custa O(m) por nó
Remoção	O(\log_m n) + fusão	Fusão e redistribuição custam O(m)
Busca por intervalo	O(\log_m n + k)	k é o número de chaves no intervalo

A variante mais usada em bancos reais é a B+ tree. Nela, todos os dados reais ficam apenas nas folhas, e os nós internos guardam só cópias de chaves como guias de navegação. Além disso, as folhas são encadeadas entre si por ponteiros laterais. O ganho é enorme para buscas por intervalo: você desce até a primeira folha do intervalo e depois percorre a lista ligada de folhas sequencialmente, sem voltar à raiz. Por isso, quando alguém diz “índice B-tree” num SGBD moderno, quase sempre é uma B+ tree por baixo.

Para fixar a B-tree. Largura grande significa árvore baixa significa poucos acessos a disco. Balanceamento automático mantém todas as folhas no mesmo nível. E o trunfo que nenhuma outra estrutura simples oferece: por manter os dados ordenados, a B-tree resolve com elegância buscas por intervalo, ordenação e comparações como maior que ou menor que.

Estruturas de indexação: hashing em profundidade

A segunda grande família é o hashing, e a filosofia é oposta à da árvore. Em vez de navegar por uma hierarquia, você calcula diretamente onde o dado está. No centro está a função hash: ela recebe a chave e devolve o endereço de um bucket (balde) onde o registro deve estar. Uma boa função hash precisa ser determinística — a mesma chave sempre gera o mesmo endereço —, uniforme — espalha as chaves por igual para evitar concentração — e eficiente de calcular.

A estrutura é um array de buckets, cada bucket com slots para registros. Como a posição é calculada e não navegada, uma busca por igualdade exata custa, em média, O(1) — tempo constante, independente do tamanho da tabela. Esse é o grande atrativo do hashing.

graph LR
    K1["Chave: 'ana'"] --> H{Funcao hash}
    K2["Chave: 'bruno'"] --> H
    K3["Chave: 'carla'"] --> H
    H --> B0["Bucket 0: bruno"]
    H --> B1["Bucket 1: ana, carla"]
    H --> B2["Bucket 2: vazio"]

O problema inevitável é a colisão: duas chaves distintas que a função mapeia para o mesmo bucket. Como sempre haverá mais chaves possíveis do que buckets, colisões são uma certeza, não uma exceção, e tratá-las bem é o que define a qualidade da implementação. Há duas grandes estratégias. No encadeamento (hashing aberto), cada bucket mantém uma lista ligada de registros que colidiram ali. No endereçamento aberto (hashing fechado), procura-se outro slot livre na própria tabela: a sondagem linear tenta o próximo slot sequencialmente, a sondagem quadrática salta em intervalos quadráticos para reduzir aglomerações, e o hashing duplo usa uma segunda função hash para definir o passo da sondagem.

Tratamento de colisão	Como funciona	Risco
Encadeamento	Lista ligada por bucket	Listas longas degradam para O(n)
Sondagem linear	Próximo slot livre	Aglomeração primária
Sondagem quadrática	Saltos quadráticos	Aglomeração secundária
Hashing duplo	Passo por 2ª função	Mais cálculo por inserção

Há ainda a distinção entre hashing estático e dinâmico. No hashing estático, o número de buckets é fixo na criação. O drama aparece quando a tabela enche: o fator de carga (razão entre registros e capacidade) sobe, as colisões explodem e o desempenho desaba. A solução é o rehashing — recriar a tabela maior e recalcular o endereço de todos os registros —, uma operação cara. O hashing dinâmico resolve isso permitindo que a estrutura cresça gradualmente. No hashing extensível, um diretório de ponteiros mapeia para buckets, e cada bucket cheio se divide, podendo dobrar o diretório quando necessário. No hashing linear, a tabela cresce de forma incremental: um ponteiro de divisão percorre os buckets e divide um por vez conforme ocorrem estouros, sem reorganizar tudo de uma vez. As complexidades médias e de pior caso:

Operação	Caso médio	Pior caso
Busca	O(1)	O(n)
Inserção	O(1)	O(n)
Remoção	O(1)	O(n)

O pior caso O(n) acontece quando uma função hash ruim joga quase todas as chaves no mesmo bucket — toda a vantagem evapora. Por isso o hashing é tão sensível à qualidade da função.

B-tree versus Hash: a comparação que cai em prova

Agora a comparação direta, que é onde o examinador adora pegar o aluno desatento. Memorize a regra de ouro: Hash brilha na igualdade exata, B-tree brilha em intervalos e ordenação. O motivo é estrutural. O hash calcula um endereço para um valor específico — perfeito para WHERE id = 42. Mas ele não preserva ordem alguma: valores próximos vão para buckets espalhados, então uma consulta WHERE idade BETWEEN 20 AND 30 obrigaria a varrer a tabela inteira. A B-tree, por manter tudo ordenado, encontra o início do intervalo e percorre as folhas em sequência.

Critério	B-tree	Hash
Busca por igualdade	O(\log n), ótimo	O(1) médio, superior
Busca por intervalo	Excelente	Inviável, requer varredura
Ordenação e ORDER BY	Natural, dados ordenados	Não suporta
Mantém ordem dos dados	Sim	Não
Sensibilidade à distribuição	Baixa	Alta, depende da função
Acesso a disco	Localizado, sequencial	Aleatório
Flexibilidade de tamanho	Cresce naturalmente	Estático exige rehashing
Concorrência	Bloqueios em níveis altos	Granularidade fina por bucket

Em termos de ambiente, o hash tende a vencer em memória principal e quando o conjunto cabe inteiro na RAM, além de se adaptar bem a sistemas distribuídos via particionamento. A B-tree domina em armazenamento secundário, onde sua estrutura hierárquica minimiza acessos a disco, e em qualquer cenário que misture leituras, escritas e necessidade de ordem.

flowchart TD
    A[Que tipo de consulta predomina?] --> B{Igualdade exata apenas?}
    B -- Sim --> C{Dados cabem em memoria?}
    C -- Sim --> D[Use indice Hash]
    C -- Nao --> E[B-tree ainda compete bem]
    B -- Nao --> F{Precisa de intervalo ou ordem?}
    F -- Sim --> G[Use B-tree]
    F -- Nao --> G

Na prática, os SGBDs implementam as duas e deixam você escolher. No PostgreSQL, por exemplo, o índice padrão é B-tree, mas você pode pedir explicitamente um hash quando só fará buscas por igualdade:

-- Indice B-tree, padrao, serve para igualdade e intervalo
CREATE INDEX idx_pedido_data ON pedidos (data_pedido);

-- Indice Hash, apenas para igualdade exata
CREATE INDEX idx_pedido_codigo ON pedidos USING HASH (codigo);

Síntese para a prova. Índice é estrutura auxiliar que troca espaço e custo de escrita por velocidade de leitura — indexe colunas de WHERE, JOIN e ORDER BY, sem excesso. Índice clusterizado ordena fisicamente os dados e há só um por tabela; não clusterizados são vários e usam ponteiros. O otimizador é baseado em custo e depende de estatísticas atualizadas; EXPLAIN revela o plano, e ver Seq Scan numa busca seletiva é sinal de problema. Funções sobre a coluna no WHERE cegam o índice. A B-tree é uma árvore m-ária balanceada, com folhas no mesmo nível, busca em O(\log_m n), mantém dados ordenados e por isso resolve intervalos; a B+ tree põe os dados nas folhas encadeadas. O Hash calcula o endereço pela função hash, busca em O(1) médio mas O(n) no pior caso, trata colisões por encadeamento ou endereçamento aberto, e não preserva ordem. A regra final: Hash para igualdade exata, B-tree para intervalos, ordenação e o uso geral.