O que um índice b-tree realmente é

De um nome a uma estrutura

"SQL: where e operadores" fechou com uma aula nomeando índices B-tree e mostrando a saída de EXPLAIN ANALYZE, o suficiente para distinguir Index Scan de Seq Scan. Este curso parte desse nome e constrói a estrutura por baixo dele. A próxima aula observa um índice mudando o plano de uma query real.

Uma lista telefônica, não uma pilha de papéis

Uma tabela sem índice é uma pilha de papéis na ordem em que foram largados. Achar um papel significa checar página por página até ele aparecer, ou até a pilha acabar. Um índice B-tree (árvore balanceada) se parece mais com uma lista telefônica. As entradas são ordenadas, então você pula para mais ou menos o lugar certo e refina a partir dali, sem checar cada página.

flowchart TB
  M["m..."] --> D["d..."]
  M --> S["s..."]
  D --> AC["a-c<br/>linhas"]
  D --> EL["e-l<br/>linhas"]
  S --> NR["n-r<br/>linhas"]
  S --> TZ["t-z<br/>linhas"]

Estruturalmente, isso é uma árvore: um nó raiz no topo, ramificando em nós filhos, terminando em nós folha que apontam para linhas da tabela. "Balanceada" quer dizer algo específico: toda folha fica na mesma profundidade a partir da raiz. Seja qual for o valor buscado, chegar a uma folha visita o mesmo número de nós. Nenhum valor fica três vezes mais fundo que os outros.

Por que balanceamento vira velocidade

Uma busca começa na raiz. Em cada nó, ela compara o valor procurado, escolhe um ramo e descarta tudo do outro lado sem olhar. Cada passo para baixo elimina uma fração grande das linhas restantes, então o número de passos cresce bem mais devagar que o número de linhas. Ir de 1.000 linhas para 1.000.000, mil vezes mais dado, adiciona só um punhado de passos. A próxima aula mede isso.

Ordem ordenada é o truque inteiro

Toda operação que um B-tree suporta bem remonta a um fato: ele guarda valores em ordem. Igualdade (email = 'x') significa andar direto até onde 'x' estaria. Um intervalo (created_at >= '2025-01-01') significa andar até o começo do intervalo e ler para frente, já que vizinhos ordenados ficam lado a lado nas páginas folha do índice. IS NULL, BETWEEN e IN funcionam do mesmo jeito. LIKE 'prefixo%' também, mas só com um índice criado para correspondência de padrões (text_pattern_ops), como "SQL: where e operadores" mostrou.

O que um B-tree não consegue fazer segue a mesma lógica ao contrário. LOWER(email) = 'x' precisa da posição do valor em minúsculas, mas a árvore está ordenada pelo valor original, então a ordem não ajuda. Essa é a regra de sargabilidade de "SQL: where e operadores": o mesmo fato da ordem, visto do outro lado.

Pontos-chave

• Um índice B-tree é uma árvore ordenada e balanceada, com toda folha na mesma profundidade, então uma busca leva mais ou menos o mesmo número de passos para qualquer valor.
• O balanceamento é o motivo de os passos crescerem bem mais devagar que as linhas: mil vezes mais linhas custam só um punhado de passos a mais.
• Toda operação amigável a B-tree (igualdade, intervalos, prefixos) se reduz a "achar uma posição em ordem, depois ler por perto". Sargabilidade é o mesmo fato visto pelo que o quebra.