Saltar para o conteúdo

professor Índices B-tree Lição 1

Lição 1 · núcleo ~1 hora

A B-tree por dentro

Porque é que três leituras de página chegam para encontrar uma linha entre um milhão — e porque é que a árvore é larga e baixa em vez de alta e estreita.

1. Objetivo

No fim consegues explicar porque é que a altura de uma B-tree cresce tão devagar — e prevê-la: dado o número de linhas e quantas entradas cabem numa página, dizes quantas leituras de página custa localizar um valor. E consegues confirmar essa previsão no EXPLAIN.

2. Recuperar

⭐ Responde de memória antes de ler o resto

Custa, e é suposto custar. O esforço de puxar da memória é o que consolida — porquê.

  1. Qual é a unidade que a base de dados lê do disco, e de que tamanho?
    Resposta

    A página, de 8 kB por omissão em Postgres.

  2. Na moeda do planeador, quantas leituras sequenciais «vale» uma leitura ao calhas, por omissão?
    Resposta

    Quatro — random_page_cost = 4 contra seq_page_cost = 1.

  3. A tabela de treino tem 8348 páginas. Uma query sem índice que devolve 1 linha lê quantas?
    Resposta

    As 8348. É precisamente isto que um índice existe para evitar.

3. O mecanismo

O problema que uma árvore resolve

Se guardarmos as chaves numa lista ordenada, a procura binária encontra qualquer valor em log₂(n) passos — para um milhão, 20 passos. Parece ótimo, até te lembrares da lição 0: cada passo dá um salto para uma posição diferente, e cada salto é uma página. 20 páginas ao calhas custam 80 na moeda do planeador. Melhor do que 8348, mas muito longe do que se consegue.

O problema é o «2» do log₂: uma comparação por leitura é um desperdício absurdo, porque a leitura trouxe 8 kB inteiros e nós usámos uma chave. Usar os 8 kB todos é a ideia inteira da B-tree.

⭐ A ideia numa frase

Uma B-tree é uma árvore de procura em que cada nó ocupa uma página inteira e contém centenas de chaves. Não se divide o problema em 2 a cada leitura — divide-se em centenas. A base do logaritmo deixa de ser 2 e passa a ser o número de chaves que cabem numa página.

Esse número chama-se fanout (grau de ramificação). Com um fanout de cerca de 240:

NíveisChaves alcançáveis (fanout ≈ 240)Leituras de página para localizar uma
1~2401
2~57 6002
3~13 800 0003
4~3 300 000 0004

É por isto que as B-trees são largas e baixas. Uma tabela com três mil milhões de linhas localiza um valor em quatro leituras. Na prática quase todas as tabelas com que trabalhas vivem em árvores de três ou quatro níveis, e passar de um milhão para dez milhões de linhas não acrescenta um nível.

Como está feita, por dentro

Três tipos de página, e a diferença entre elas é o que guardam:

Estrutura de uma B-tree com três níveis No topo, uma página raiz com separadores. No meio, páginas internas com mais separadores. Em baixo, páginas de folha com as chaves ordenadas e ponteiros para as linhas da tabela. As folhas estão ainda ligadas entre si da esquerda para a direita, o que permite percorrer intervalos sem voltar ao topo. raiz · 4 separadores interna interna interna interna folha folha folha as folhas estão ligadas em cadeia → percorrer um intervalo não volta ao topo Caminho de uma procura: raiz → interna → folha = 3 leituras de página
As setas a tracejado entre folhas são o que torna BETWEEN e ORDER BY baratos: encontra-se o início e percorre-se em frente, sem voltar a subir.

A parte que quase toda a gente esquece: as folhas estão ligadas

Cada folha aponta para a folha seguinte. Isto muda o que um índice serve para fazer, porque deixa de ser só «encontrar um valor»:

A documentação do PostgreSQL diz exatamente onde está a fronteira:

«The optimizer can also use a B-tree index for queries involving the pattern matching operators LIKE and ~ if the pattern is a constant and is anchored to the beginning of the string» — PostgreSQL 17, Index Types.

4. Exemplo trabalhado

Vamos abrir uma B-tree a sério e contar-lhe os níveis. Precisas da extensão pageinspect, que vem com o Postgres e serve exatamente para isto:

psql -d treino_indices
CREATE EXTENSION IF NOT EXISTS pageinspect;
CREATE INDEX idx_cliente ON encomendas (cliente_id);

Passo 1 — perguntar a altura antes de contar as páginas

Porquê primeiro isto: a altura é o número que prevê o custo de uma procura. O tamanho do índice é interessante, mas não é o que determina quantas leituras custa encontrar um valor.

SELECT level, root FROM bt_metap('idx_cliente');
 level | root
-------+------
     2 |  290

level = 2 é o nível da raiz, e as folhas são o nível 0. Logo os níveis são 2, 1 e 0 — três. Cuidado com a armadilha de leitura: level=2 não são dois níveis.

Passo 2 — contar as páginas de cada nível

Porquê agora: é isto que transforma «três níveis» de afirmação em coisa verificada, e mostra o fanout real.

SELECT s.btpo_level AS nivel, count(*) AS paginas, sum(s.live_items) AS entradas
FROM generate_series(1, (pg_relation_size('idx_cliente')/8192)::int - 1) AS blk,
     LATERAL bt_page_stats('idx_cliente', blk) AS s
WHERE s.type IN ('r','i','l')
GROUP BY 1 ORDER BY 1 DESC;
 nivel | paginas | entradas
-------+---------+----------
     2 |       1 |        4     <- raiz
     1 |       4 |      947     <- internas (~237 separadores cada)
     0 |     944 |    50943     <- folhas

Lê-se de cima para baixo: uma raiz com 4 separadores aponta para 4 páginas internas; essas contêm 947 separadores ao todo (~237 cada) que apontam para as 944 folhas. Esse ~237 é o fanout — e é ele que explica porque é que três níveis chegam para milhões de linhas.

Passo 3 — a surpresa: 50 943 entradas para 1 000 000 de linhas

As folhas deviam ter uma entrada por linha da tabela. Têm 50 943 — e a tabela tem um milhão. Falta uma peça.

A peça é esta: a coluna cliente_id tem 50 000 valores distintos, cada um repetido ~20 vezes. Desde a versão 13, o Postgres deduplica entradas de índice iguais: em vez de 20 entradas com a mesma chave, guarda uma chave e uma lista com os 20 ponteiros.

Pode confirmar-se desligando a deduplicação e comparando:

CREATE INDEX idx_nodedup ON encomendas (cliente_id) WITH (deduplicate_items = off);
  indice   | tamanho | paginas | nivel_raiz
-----------+---------+---------+------------
 com dedup | 7600 kB |     950 |          2
 sem dedup | 21 MB   |    2749 |          2
✅ 2,8 vezes mais pequeno — e a altura não muda

A deduplicação poupa espaço e I/O de varrimento, não altura. Com fanouts destes, seria preciso um índice quase 240 vezes maior para ganhar mais um nível.

Passo 4 — confirmar as três leituras no EXPLAIN

A previsão é: localizar um valor custa 3 leituras de página no índice. O BUFFERS diz se acertámos.

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM encomendas WHERE cliente_id = 42;
Bitmap Heap Scan on encomendas  (actual time=0.016..0.055 rows=20 loops=1)
  Recheck Cond: (cliente_id = 42)
  Heap Blocks: exact=20
  Buffers: shared hit=20 read=3
  ->  Bitmap Index Scan on idx_cliente  (actual time=0.010..0.010 rows=20 loops=1)
        Index Cond: (cliente_id = 42)
        Buffers: shared read=3            <- três: raiz, interna, folha
Execution Time: 0.075 ms

Três. Exatamente os três níveis. As outras 20 páginas (hit=20) são da tabela, para ir buscar as 20 linhas — e é sobre essa segunda metade que é a lição 2.

Balanço: 23 páginas em vez de 8348, e 0,075 ms em vez de 15. Duas ordens de grandeza, e todas elas previsíveis a partir da estrutura.

5. Exemplo com lacunas

Completa

Passo 1 (dado). Um índice sobre uma tabela de 40 000 000 de linhas, coluna com valores todos distintos. O fanout médio é 240.

Passo 2 (completa). Quantos níveis precisa a árvore? Mostra a conta:

  • 2 níveis alcançam ______ chaves
  • 3 níveis alcançam ______ chaves
  • 4 níveis alcançam ______ chaves
  • Logo, são precisos ______ níveis

Passo 3 (dado). bt_metap devolve level = 3.

Passo 4 (completa). Bate com a tua previsão? E quantas leituras de página custa localizar um valor?

Passo 5 (completa). A tabela cresce para 400 000 000 de linhas — 10×. Quantos níveis passa a ter?

Ver os passos em falta

Passo 2: 240² = 57 600 · 240³ = 13 824 000 · 240⁴ = 3 317 760 000. 40 milhões não cabem em 3 níveis mas cabem folgadamente em 4 → 4 níveis.

Passo 4: level = 3 com folhas no nível 0 significa níveis 3, 2, 1, 0 = 4 níveis. Bate. Custo de localização: 4 leituras.

Passo 5: continuam a ser 4. 400 milhões ainda cabem nos 3,3 mil milhões que 4 níveis alcançam. Multiplicar as linhas por dez não acrescentou leitura nenhuma — é este o significado prático de «logarítmico», e é a razão pela qual um índice não «deixa de servir» quando a tabela cresce.

6. Erros comuns

A ideia erradaComo se reconheceO que é mesmo
«A árvore é binária» Calcular log₂(1 000 000) ≈ 20 e esperar 20 leituras Cada nó é uma página com centenas de chaves. A base do logaritmo é o fanout (~240 aqui), não 2. São 3 leituras, não 20 — e o «B» de B-tree nunca quis dizer binary
«level = 2 são dois níveis» Prever 2 leituras e ver 3 no BUFFERS É o nível da raiz, e as folhas são o nível 0. level = 2 → níveis 2, 1, 0 → três
«Quanto maior a tabela, mais fundo o índice, logo mais lento» Receio de indexar tabelas grandes; «isto não escala» De 1 milhão para 10 milhões a altura não muda. Só multiplicar por ~240 é que acrescenta um nível. O que degrada com o tamanho é a ida à tabela buscar as linhas (lição 2), não a procura no índice
«O índice guarda as linhas» Esperar que qualquer query servida por um índice não toque na tabela A folha guarda a chave e um ponteiro. As outras colunas ficam na tabela, e é preciso lá ir — salvo no index-only scan, lição 2
«LIKE nunca usa índice» Descartar o índice sem olhar para o padrão LIKE 'abc%' é um intervalo e usa. LIKE '%abc' não é, e não usa — a fronteira é a âncora no início, não o operador

7. Praticar

●○○

E1 — quais destas o índice serve?

Índice B-tree sobre encomendas (criada_em). Para cada condição, diz se pode ser servida pelo índice, e porquê em termos da estrutura:

  1. WHERE criada_em = '2025-01-01'
  2. WHERE criada_em BETWEEN '2025-01-01' AND '2025-02-01'
  3. WHERE date_part('year', criada_em) = 2025
  4. ORDER BY criada_em DESC LIMIT 10
  5. WHERE criada_em IS NULL
Solução
  1. Sim. Igualdade: desce-se até à folha.
  2. Sim. Intervalo: desce-se ao início e segue-se a cadeia das folhas.
  3. Não. O índice guarda criada_em, não date_part('year', criada_em). Aplicar uma função à coluna destrói a ordenação de que a árvore depende — não há intervalo contíguo para percorrer. A correção é reescrever como intervalo (>= '2025-01-01' AND < '2026-01-01') ou criar um índice de expressão sobre a própria função (lição 6).
  4. Sim, e é dos casos em que mais se ganha. As chaves já estão ordenadas: percorre-se a cadeia ao contrário e para-se à décima, em vez de ordenar um milhão de linhas para deitar fora 999 990.
  5. Sim. A documentação é explícita: «an IS NULL or IS NOT NULL condition on an index column can be used with a B-tree index». Os nulos têm posição definida na ordenação, portanto formam um intervalo como qualquer outro.
●●○

E2 — código que corre: medir a tua própria árvore

Na base de treino, descobre a altura do índice da chave primária (encomendas_pkey) e compara com a de idx_cliente. Prevê antes se vão ser iguais ou diferentes, e porquê. Depois explica o tamanho.

Solução

Previsão razoável: a PK tem 1 000 000 de valores distintos e cliente_id só 50 000, logo a PK precisa de mais entradas nas folhas. Mas 1 milhão ainda cabe folgadamente em 3 níveis (240³ ≈ 13,8 milhões), portanto a altura deve ser a mesma e só o tamanho deve diferir.

Corrido em Postgres 17.11:

SELECT pg_size_pretty(pg_relation_size('encomendas_pkey')) AS tam,
       pg_relation_size('encomendas_pkey')/8192 AS paginas,
       (SELECT level FROM bt_metap('encomendas_pkey')) AS nivel_raiz;

  tam  | paginas | nivel_raiz
-------+---------+------------
 21 MB |    2745 |          2

Altura igual (3 níveis), tamanho 2,9× maior: 2745 páginas contra 950. E a explicação do tamanho é a mesma da deduplicação — com valores todos distintos não há nada para deduplicar, por isso a PK ocupa praticamente o mesmo que idx_cliente ocupava com a deduplicação desligada (2749 páginas).

●●●

E3 — a pergunta que separa perceber de decorar

Um colega diz: «indexei a coluna estado, que só tem 3 valores possíveis. O índice tem 3 níveis e localiza o valor em 3 leituras, logo a query vai ficar ~2800 vezes mais rápida do que ler as 8348 páginas.»

O raciocínio tem um erro. Onde, exatamente? (Não precisas de saber a lição 2 — precisas de pensar no que está na folha.)

Solução

O erro é confundir localizar a chave com obter as linhas.

As 3 leituras chegam para chegar à folha onde começa estado = 'pendente'. Mas nessa folha está uma lista de ponteiros — e com 3 valores distintos em 1 000 000 de linhas, o valor mais raro ainda tem 10 000 linhas. Cada uma está numa página da tabela que é preciso ir ler. A conta verdadeira é 3 + (páginas da tabela que é preciso visitar), e a segunda parcela domina completamente.

Medido na base de treino, com estado = 'cancelada' (1% das linhas, 10 000 delas):

Index Scan using idx_estado on encomendas (actual rows=10000)
  Buffers: shared hit=8348 read=11

8348 páginas da tabela — exatamente as mesmas que um Seq Scan leria. As 10 000 linhas estão espalhadas por praticamente todas as páginas, por isso o índice localizou-as depressa e não poupou I/O nenhum. Ganhou-se tempo (6 ms contra 15) por outra razão, não por se ler menos.

Esta é a diferença entre seletividade e agrupamento físico, e é o assunto da lição 3. Se percebeste isto agora, essa lição vai parecer óbvia — e é esse o objetivo.

8. Quiz

  1. Porque é que uma B-tree é «larga e baixa» em vez de «alta e estreita»?

  2. bt_metap devolve level = 3. Quantas leituras de página custa localizar uma chave?

  3. Um índice tem 50 943 entradas nas folhas, mas a tabela tem 1 000 000 de linhas e o índice não é parcial. Porquê?

  4. Qual destas não pode ser servida por um índice B-tree sobre nome?

  5. A tabela cresce de 1 para 10 milhões de linhas. O que acontece ao custo de localizar uma chave no índice?

  6. Para que serve a ligação entre folhas vizinhas?

9. Explica por palavras tuas

Entregar

Guardar em topicos/indices-btree-sql/respostas/AAAA-MM-DD.md.

10. Resumo

11. Fontes