CS Fundamentals Trainer · Guias

Como funcionam os índices de banco de dados

B-trees, ordem de índices compostos, índices de cobertura, como ler o EXPLAIN e por que o banco ignora o seu índice.

21 min de leitura

Um índice é uma segunda cópia de algumas colunas de uma tabela, mantida em uma ordem que torna a busca rápida. Sem ele, o banco lê todas as linhas para responder "quais pedidos pertencem ao cliente 4242?". Com ele, vai direto ao lugar certo. Quase todo problema de desempenho em um banco relacional termina em uma de duas frases: "não existe índice para esta consulta" ou "existe um índice, e a consulta não consegue usá-lo". Este guia explica como os índices funcionam o suficiente para você saber em qual dos casos está.

1. O problema que um índice resolve

Uma tabela é armazenada como um monte de páginas (blocos de alguns kilobytes, 8 KB no PostgreSQL). Para achar as linhas que atendem a uma condição sem índice, o banco faz uma varredura sequencial (sequential scan): lê todas as páginas e confere todas as linhas. O custo cresce com a tabela. Um milhão de linhas é tranquilo; cem milhões levam um minuto.

Um índice faz o custo crescer com o logaritmo da tabela. Buscar em uma lista ordenada, dividindo-a ao meio repetidamente, é a mesma ideia da busca binária, só que organizada para discos, onde o caro é o número de páginas lidas, não o número de comparações.

Pense no índice remissivo no fim de um livro. Você não lê o livro inteiro para achar "mutex"; procura em ordem alfabética e vai às páginas indicadas.

2. Como funciona uma B-tree

O índice padrão em praticamente todo banco relacional é a B-tree (a rigor, uma B+tree na maioria dos sistemas) [1]. É uma árvore de páginas:

Diagram: A tiny B-tree: find 57 by following one page per level

Para achar 57: na raiz, 57 está entre 40 e 80, então vá ao filho do meio; ali, ele fica entre 50 e 60, então vá a essa folha; varra-a e encontre 57. Três páginas, por maior que seja a tabela.

Por que a árvore é tão rasa

Uma página guarda centenas de entradas, então cada nível multiplica o alcance por centenas. Com cerca de 300 entradas por página:

NíveisLinhas alcançáveis
2300 × 300 = 90 000
3300^3 = 27 milhões
4300^4 = 8,1 bilhões

Uma tabela com dezenas de milhões de linhas exige uma busca de cerca de 3 ou 4 leituras de página. Os níveis do topo ficam na memória porque toda consulta passa por eles, então na prática o custo é uma ou duas leituras do disco. É por isso que uma busca por índice leva quase o mesmo tempo em uma tabela pequena e em uma enorme.

Escritas: mantendo a ordem

Inserir um valor significa achar sua folha e adicioná-lo ali. Se a folha está cheia, ela é dividida (split) em duas, e um novo separador sobe para o pai (que pode se dividir também). Apagar e atualizar valores indexados também mexe no índice. Esse é o preço de um índice: todo insert, todo update de uma coluna indexada e todo delete faz trabalho extra em cada índice da tabela.

Onde mora a linha em si

Até aqui, uma entrada de índice "aponta para a linha". Como isso acontece depende do banco.

Isso muda alguns conselhos. No InnoDB, uma chave primária larga (uma string UUID de 36 caracteres) é copiada em todo índice secundário e deixa todos maiores, e uma chave primária aleatória espalha as inserções pela própria tabela, não só por um índice. A ideia do "índice de cobertura" funciona especialmente bem ali, porque pula a segunda caminhada.

3. O que um índice pode fazer por uma consulta

Uma B-tree mantém os valores ordenados, então ajuda em mais do que "igual a":

Ele não ajuda em WHERE name LIKE '%ada%' (o casamento pode começar em qualquer lugar, então a ordem não serve de nada), nem na maioria dos cálculos feitos sobre a coluna (mais na seção 7).

4. Vendo na prática: EXPLAIN

Nunca adivinhe; peça o plano ao banco. No PostgreSQL isso é o EXPLAIN, e o EXPLAIN ANALYZE também executa a consulta e mostra contagens de linhas e tempos reais [3].

Cuidado: o EXPLAIN ANALYZE realmente executa o comando. Em um UPDATE, INSERT ou DELETE, a mudança acontece. Envolva-o: BEGIN; EXPLAIN ANALYZE UPDATE ...; ROLLBACK;. No meu teste, o update mudou 5 linhas dentro da transação e nenhuma depois do ROLLBACK.

Um experimento no PostgreSQL

Copie isto para o psql. Ele cria 200 000 pedidos para 20 000 clientes e pede os dez últimos pedidos pagos de um cliente:

CREATE TABLE orders (
  id bigserial PRIMARY KEY, customer_id int, status text, created_at date, total numeric(8,2));

INSERT INTO orders (customer_id, status, created_at, total)
SELECT 1 + floor(random() * 20000)::int,
       (ARRAY['new', 'paid', 'shipped'])[1 + floor(random() * 3)::int],
       date '2026-01-01' + floor(random() * 300)::int,
       round((random() * 100)::numeric, 2)
FROM generate_series(1, 200000);
ANALYZE orders;

EXPLAIN (ANALYZE, COSTS OFF)
SELECT id, total FROM orders
WHERE customer_id = 4242 AND status = 'paid'
ORDER BY created_at DESC LIMIT 10;

Isto foi o que obtive no PostgreSQL 16 (os seus números serão diferentes). Sem índice:

 Limit (actual rows=2 loops=1)
   ->  Gather Merge (actual rows=2 loops=1)
         ->  Sort (actual rows=1 loops=2)
               Sort Key: created_at DESC
               ->  Parallel Seq Scan on orders (actual rows=1 loops=2)
                     Filter: ((customer_id = 4242) AND (status = 'paid'::text))
                     Rows Removed by Filter: 99999
 Execution Time: 14.205 ms

Depois de CREATE INDEX orders_cust_status_created ON orders (customer_id, status, created_at); ANALYZE orders;:

 Limit (actual rows=2 loops=1)
   ->  Sort (actual rows=2 loops=1)
         Sort Key: created_at DESC
         ->  Bitmap Heap Scan on orders (actual rows=2 loops=1)
               Recheck Cond: ((customer_id = 4242) AND (status = 'paid'::text))
               ->  Bitmap Index Scan on orders_cust_status_created (actual rows=2 loops=1)
                     Index Cond: ((customer_id = 4242) AND (status = 'paid'::text))
 Execution Time: 0.081 ms

De 14,2 ms para 0,08 ms: o primeiro plano olha todas as 200 000 linhas (cada uma é lida e rejeitada, "Rows Removed by Filter"), o segundo olha as 2 que casam. Como apenas duas linhas casam, o PostgreSQL as ordena sem problema; para um cliente com milhares de pedidos pagos, ele percorreria o índice de trás para frente e pararia após dez entradas, sem nenhuma ordenação. Mais dois planos da mesma tabela:

O mesmo experimento no SQLite

Se você só tem Python, o SQLite [4] não exige nada instalado. Ele cria a mesma tabela:

import sqlite3, random

db = sqlite3.connect(":memory:")
db.execute("""CREATE TABLE orders (
  id INTEGER PRIMARY KEY, customer_id INTEGER, status TEXT, created_at TEXT, total REAL)""")
random.seed(1)
db.executemany(
    "INSERT INTO orders (customer_id, status, created_at, total) VALUES (?, ?, ?, ?)",
    [(random.randint(1, 20000), random.choice(["new", "paid", "shipped"]),
      f"2026-{random.randint(1, 10):02d}-{random.randint(1, 28):02d}", random.random() * 100)
     for _ in range(200000)])

query = """SELECT id, total FROM orders
           WHERE customer_id = 4242 AND status = 'paid'
           ORDER BY created_at DESC LIMIT 10"""

def plan():
    for row in db.execute("EXPLAIN QUERY PLAN " + query):
        print("  ", row[3])

print("no index");              plan()
db.execute("CREATE INDEX orders_customer ON orders (customer_id)")
print("index on customer_id");  plan()
db.execute("DROP INDEX orders_customer")
db.execute("CREATE INDEX orders_cust_status_created ON orders (customer_id, status, created_at)")
print("composite index");       plan()

Esta é a saída que obtive (SQLite 3.45):

no index
   SCAN orders
   USE TEMP B-TREE FOR ORDER BY
index on customer_id
   SEARCH orders USING INDEX orders_customer (customer_id=?)
   USE TEMP B-TREE FOR ORDER BY
composite index
   SEARCH orders USING INDEX orders_cust_status_created (customer_id=? AND status=?)

Três histórias diferentes:

  1. SCAN orders: a tabela inteira e, depois, uma ordenação do que casou.
  2. SEARCH ... (customer_id=?): salta para as linhas deste cliente (cerca de 10 das 200 000), mas ainda precisa filtrar por status e ordenar.
  3. SEARCH ... (customer_id=? AND status=?) sem etapa de ordenação: o índice acha as linhas certas e as entrega na ordem de created_at, então o LIMIT 10 pode parar depois de dez entradas. (O PostgreSQL preferiu ordenar duas linhas por conta própria; ambos servem para tão poucas linhas.)

Na minha máquina, a consulta levou cerca de 6,5 ms sem índice e 0,09 ms com o composto. A diferença cresce com a tabela: a varredura é proporcional às linhas, a busca à profundidade da árvore.

As palavras que vale conhecer para ler planos do PostgreSQL:

5. Índices compostos: a ordem das colunas é tudo

Um índice em (customer_id, status, created_at) é ordenado por cliente, depois, dentro de um cliente, por status, depois, dentro de um status, por data. Como uma lista telefônica ordenada por sobrenome e depois por nome, é excelente para "todos os Silva" e para "João Silva", e inútil para "todo mundo chamado João" [5].

ConsultaUsa bem o índice?
WHERE customer_id = 4242Sim: a coluna líder
WHERE customer_id = 4242 AND status = 'paid'Sim: as duas primeiras colunas
WHERE customer_id = 4242 AND status = 'paid' ORDER BY created_atSim, e sem precisar ordenar
WHERE customer_id = 4242 AND created_at > '2026-06-01'Em parte: acha o cliente, mas precisa filtrar as datas dentro dele
WHERE status = 'paid'Mal: falta a coluna líder, então não consegue buscar
WHERE status = 'paid' AND created_at > '2026-06-01'Mal, pelo mesmo motivo

(Versões recentes do PostgreSQL às vezes conseguem "pular" uma coluna líder ausente quando ela tem poucos valores distintos. Ajuda em alguns casos, mas não projete em cima disso.)

Uma regra prática para a ordem

  1. Colunas de igualdade primeiro (=). A ordem entre elas quase não muda o custo de uma busca; o que ela muda é quais outras consultas podem reaproveitar o índice, porque precisam usar um prefixo à esquerda. Coloque primeiro a coluna que a maioria das suas consultas filtra.
  2. Depois a coluna usada para um intervalo ou para ordenar (>, BETWEEN, ORDER BY).
  3. Colunas depois de uma coluna de intervalo só são usadas para filtrar dentro do intervalo, não para buscar.

Projete índices a partir das suas consultas reais, não da tabela. Liste as dez consultas que mais importam; um índice que atende três delas vale mais do que três índices estreitos. Um índice composto em (a, b) também atende consultas só em a, então um índice separado em a é redundante e custa a cada escrita.

6. Índices de cobertura e index-only scans

Normalmente o índice acha a linha e o banco visita a tabela para ler as outras colunas. Se o próprio índice contém todas as colunas de que a consulta precisa, a visita é desnecessária: um index-only scan. No meu teste com SQLite, incluir total no índice mudou o plano para USING COVERING INDEX.

O PostgreSQL permite adicionar colunas a um índice sem fazê-las parte da sua ordenação, com INCLUDE:

CREATE INDEX orders_customer_covering
  ON orders (customer_id, created_at)
  INCLUDE (total);

Um índice de cobertura é mais rápido para consultas quentes, mas é maior e custa mais a cada escrita, então use-o só para algumas consultas importantes. No PostgreSQL, um index-only scan também precisa que o visibility map da tabela esteja atualizado, o que o VACUUM mantém; em uma tabela que muda o tempo todo, a economia pode diminuir [6].

7. Por que o banco ignora o seu índice

Você criou o índice, e o plano ainda mostra uma varredura sequencial. Os motivos usuais:

Quando suspeitar de um problema, não confie só no plano: o EXPLAIN ANALYZE mostra o número estimado e o real de linhas em cada etapa. Uma grande diferença entre eles é a pista.

8. Tipos especiais de índices

TipoBom paraExemplo
B-treeIgualdade, intervalos, ordenação. O padrãoQuase tudo
HashSó igualdadeRaramente vale mais que uma B-tree
GINValores que contêm muitos itensBusca de texto completo, jsonb, arrays
GiST / SP-GiSTGeometria, vizinho mais próximo, intervalosMapas, "achar num raio de 5 km"
BRINTabelas enormes cujos valores seguem a ordem físicaLogs de séries temporais, índice minúsculo

9. O que os índices custam

Índices não são de graça, e uma tabela com quinze deles é um mau sinal.

Ache os que ninguém usa. No PostgreSQL, pg_stat_user_indexes.idx_scan conta quantas vezes cada índice foi usado desde a última zeragem das estatísticas. Um índice com zero varreduras ao longo de semanas (e que não impõe uma restrição única) é candidato à remoção. Crie índices em tabelas grandes e ativas com CREATE INDEX CONCURRENTLY, para que as escritas não fiquem bloqueadas enquanto ele é construído.

Indexe suas chaves estrangeiras

Uma chave estrangeira (orders.customer_id REFERENCES customers(id)) faz o banco verificar, sempre que um cliente é apagado ou sua chave muda, que nenhum pedido ainda aponta para ele. O PostgreSQL indexa a coluna referenciada (a chave primária), mas não cria um índice na coluna que referencia; o InnoDB do MySQL cria. Sem um, cada verificação varre a tabela filha inteira. No meu teste (200 000 pedidos, nenhum índice começando com customer_id), apagar um cliente sem pedidos ainda levou 7,6 ms, porque a verificação varreu a tabela orders inteira, e 0,4 ms depois de CREATE INDEX ON orders (customer_id); o custo cresce com a tabela, e a mesma varredura deixa lento todo join nessa coluna. Como hábito, indexe as colunas de chave estrangeira, sozinhas ou como coluna líder de um índice composto.

10. Paginação: onde os índices encontram o design do produto

Mostrar a página 5 000 de uma lista com OFFSET é lento, mesmo com índice, porque o banco precisa passar por todas as linhas puladas:

-- slow for deep pages: reads and throws away 100 000 rows
SELECT * FROM orders WHERE customer_id = 4242 ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 100000;

-- fast at any depth: seek to where the previous page ended
SELECT * FROM orders
WHERE customer_id = 4242 AND (created_at, id) < ('2026-06-01 10:00', 9812)
ORDER BY created_at DESC, id DESC
LIMIT 20;

A segunda forma é a paginação por keyset: o cliente devolve o último (created_at, id) que viu, e a consulta busca até ele usando o índice em (customer_id, created_at, id). O id desempata, então nenhuma linha é pulada ou repetida. O preço é que você não pode saltar para a "página 5 000", o que ninguém precisa em feeds e rolagem infinita [5].

11. Perguntas que entrevistadores gostam de acrescentar

"Devo indexar todas as colunas?"

Não. Indexe o que você filtra, junta e ordena, na ordem que suas consultas usam, e meça. Todo índice deixa as escritas mais lentas e ocupa espaço.

"Como você descobre qual índice adicionar?"

Comece pelo log de consultas lentas ou pelo pg_stat_statements, para as consultas que consomem mais tempo total. Rode EXPLAIN ANALYZE. Adicione o índice. Rode EXPLAIN ANALYZE de novo e compare os números, não só o plano.

"Chave primária: UUID ou inteiro?"

Um UUID aleatório é inserido em lugares aleatórios da árvore, o que causa muitas divisões de página e deixa o índice maior e mais lento de manter do que inteiros sequenciais ou ids ordenados por tempo (como o UUID versão 7). Ids aleatórios também espalham o conjunto de trabalho por todas as páginas, em vez de só as recentes. No InnoDB é pior, porque a chave primária é a própria ordem da tabela e é copiada em todo índice secundário (veja "Onde mora a linha em si"); guarde UUIDs como 16 bytes (BINARY(16)), não como 36 caracteres. Escolha conforme as necessidades (unicidade global, esconder contagens) e conheça o custo.

"Por que minha consulta fica lenta só às vezes?"

O plano pode mudar com os parâmetros (um cliente com 3 pedidos e um com 3 milhões precisam de planos diferentes), com estatísticas desatualizadas, ou quando o índice deixa de caber na memória.

12. Coisas a mencionar em uma entrevista

Resumo rápido

  1. Sem um índice, uma consulta lê a tabela inteira. Uma B-tree a reduz a cerca de 3 ou 4 leituras de página, mesmo com bilhões de linhas.
  2. A árvore é ordenada, então atende igualdade, intervalos, ordenação, mínimo e máximo.
  3. Em um índice composto, a ordem das colunas decide quais consultas ele atende: colunas líderes primeiro, igualdade antes de intervalo.
  4. Um índice de cobertura (INCLUDE) pode responder a uma consulta sem visitar a tabela.
  5. Funções sobre a coluna, curingas no início, tipos incompatíveis e baixa seletividade fazem o planejador pular o índice.
  6. Cada índice custa escritas, espaço e manutenção. Meça e pode.
  7. Use EXPLAIN ANALYZE antes e depois de cada mudança.

Fontes

  1. Bayer e McCreight, Organization and maintenance of large ordered indexes, Acta Informatica, 1972. O artigo original da B-tree.
  2. Documentação do MySQL, Clustered and Secondary Indexes. Como o InnoDB armazena linhas e o que seus índices secundários contêm.
  3. Documentação do PostgreSQL, Using EXPLAIN.
  4. Documentação do SQLite, EXPLAIN QUERY PLAN. A ferramenta usada no experimento acima.
  5. Markus Winand, Use The Index, Luke. Um livro gratuito sobre indexação SQL para desenvolvedores; cobre a ordem de índices compostos e a paginação por keyset ("no offset").
  6. Documentação do PostgreSQL, Index-Only Scans and Covering Indexes.
  7. Documentação do PostgreSQL, Partial Indexes e Multicolumn Indexes.

Pratique este tema: Databases

Mais guias