Um índice em banco de dados relacional é uma estrutura de acesso aleatório. Ele mapeia chaves lógicas aos identificadores físicos de tuplas (ctid), eliminando varreduras sequenciais completas.
Em tabelas volumosas, substituir uma busca exaustiva O(N) por travessias logarítmicas O(log N) reduz a latência de segundos para milissegundos. Essa diferença viabiliza sistemas de alta escala.
A escolha do tipo de índice determina o consumo de memória e a sobrecarga de escrita. Ela também define quais operadores recebem suporte em cada consulta.
No PostgreSQL, cinco famílias estruturais resolvem problemas distintos de engenharia: B-Tree, Hash, GIN, GiST e BRIN.
O Que É um Índice de Banco de Dados e Como Ele Transforma Consultas?
Um índice de banco de dados é uma estrutura auxiliar independente. Ele organiza ponteiros físicos para os registros armazenados no heap da tabela.
Ele reduz leituras de entrada e saída em disco. O planejador localiza tuplas sem carregar todas as páginas da tabela no buffer pool.
No PostgreSQL, os dados das tabelas residem em blocos físicos de 8 KB chamados heap pages. Cada página contém um cabeçalho fixo de 24 bytes.
Ela também possui ponteiros de linha (Line Pointers de 4 bytes) e o espaço livre para tuplas.
Quando você executa uma consulta sem índice, o motor executa um Seq Scan. Ele lê sequencialmente cada bloco de 8 KB do disco para a memória.
Em uma tabela com 50 milhões de linhas e 40 GB de dados, essa operação consome centenas de milhares de leituras físicas de bloco.
O índice armazena pares com o valor da coluna indexada e o endereço físico da linha (ctid). O ctid é uma coordenada de 6 bytes.
Ele é composto pelo número do bloco (block_number) e a posição do item (item_offset). Com ele, o motor acessa a tupla diretamente.
B-Tree: Como a Árvore Balanceada Domina as Consultas Relacionais?
A B-Tree resolve consultas de igualdade e intervalos ordenados mantendo todas as suas folhas na mesma profundidade. Isso garante complexidade de busca O(log N).
Ela é a estrutura padrão do PostgreSQL. Sustenta restrições primárias, chaves estrangeiras e ordenações explícitas.
A implementação do PostgreSQL adota o algoritmo de concorrência de Lehman e Yao (1981). Essa variante introduz ponteiros laterais (right-links) entre os nós do mesmo nível.
Esses ponteiros permitem que operações de leitura continuem navegando pela árvore sem travamentos exclusivos durante cisões de nós (page splits).
Estrutura Hierárquica de uma B-Tree no PostgreSQL:
[ Meta Page ] -> Ponteiro para a Raiz e Nível da Árvore
|
[ Root Page ]
/ \
[ Internal ] [ Internal ] -> Nós intermediários direcionam chaves
/ \ / \
[Leaf]--[Leaf]--[Leaf]--[Leaf] -> Folhas contêm (chave, ctid) e right-links
As páginas folha guardam a chave indexada e o ctid correspondente. As folhas são encadeadas horizontalmente em lista duplamente ligada.
Filtros com operadores <, <=, =, >= e > executam apenas uma descida na árvore. Em seguida, percorrem as folhas adjacentes até o limite do predicado.
Quando todas as colunas necessárias já estão no índice, o PostgreSQL aciona o Index Only Scan. Ele consulta a Visibility Map (VM) da tabela.
Se a página de heap estiver marcada como totalmente visível para as transações ativas, o motor sequer lê o bloco de dados principal.
Hash: Quando a Busca Direta O(1) Faz Sentido Frente à B-Tree?
O índice Hash oferece buscas por igualdade estrita em complexidade teórica O(1) utilizando funções de espalhamento de 32 bits. Ele não suporta ordenação nem consultas por intervalo.
Historicamente, os índices Hash não eram seguros contra falhas no PostgreSQL. Eles não geravam registros no Write-Ahead Log (WAL).
A partir do PostgreSQL 10, a arquitetura foi reescrita. O método ganhou suporte pleno a WAL, recuperação de travamentos e replicação contínua.
Internamente, a estrutura divide o espaço de busca em baldes (buckets). Cada balde armazena hashes de 32 bits e os respectivos ctids.
Quando ocorrem colisões ou o balde atinge 8 KB, páginas de estouro (overflow pages) são alocadas dinamicamente em lista encadeada.
A B-Tree moderna empata em velocidade na maioria dos tipos escalares inteiros. O índice Hash se destaca quando a chave possui dezenas de caracteres.
Nesse cenário, ele armazena apenas o hash de 4 bytes na página interna. Isso economiza valioso espaço em disco.
GIN: Como o Índice Invertido Acelera JSONB, Arrays e Busca Textual?
O GIN (Generalized Inverted Index) quebra dados compostos em elementos individuais. Ele mapeia cada elemento exclusivo para uma lista de registros físicos.
Ele é a estrutura canônica para acelerar consultas sobre documentos JSONB, vetores de texto completo (tsvector) e arrays.
Em um índice tradicional, cada linha da tabela gera uma entrada na árvore. No GIN, uma linha com dez tags gera dez entradas separadas.
Cada termo indexado aponta para uma posting list compactada com os ctids onde aquele valor aparece.
Mapeamento Invertido do GIN:
Chave / Token Posting List (ctids)
"postgresql" -> (1,4), (1,9), (3,12), (18,2)
"index" -> (1,4), (2,1), (3,12), (99,5)
"btree" -> (2,1), (18,2), (104,7)
Quando a lista de ocorrências de um termo cresce em excesso, o motor converte a lista plana em uma árvore interna denominada posting tree.
Isso previne gargalos de memória durante uniões e interseções de conjuntos em operadores como @>, ? e @@.
Atualizar múltiplas entradas invertidas em cada INSERT impõe alta latência. Por isso, o GIN implementa uma fila temporária chamada pending list.
Novas tuplas entram na lista pendente sem rebalancear o índice principal. O comando VACUUM descarrega essa fila periodicamente para a árvore canônica.
GiST: Como Particionar Espaços Multidimensionais e Tipos Geométricos?
O GiST (Generalized Search Tree) é uma árvore de busca extensível que particiona dados segundo predicados arbitrários de consistência geométrica.
Ele viabiliza consultas espaciais no PostGIS, tipos de intervalo contínuo e buscas por vizinhos mais próximos (k-Nearest Neighbors).
Proposto por Hellerstein, Naughton e Pfeffer (1995), o GiST não exige ordenação unidimensional linear. Ele agrupa registros em polígonos envolventes mínimos (Bounding Boxes).
Cada nó interno do GiST armazena um predicado que descreve todos os elementos da sua subárvore. Em coordenadas geográficas, o predicado delimita um retângulo.
Ao avaliar se dois polígonos se intersectam com o operador &&, o motor descarta galhos inteiros que não tocam na área pesquisada.
O GiST também implementa o operador de distância métrica <->. Essa funcionalidade permite ordenar resultados por proximidade com baixíssimo custo computacional.
Ela evita que o banco de dados calcule a distância euclidiana para todas as linhas da tabela.
BRIN: Como Reduzir o Footprint para Menos de 1% em Tabelas Gigantescas?
O BRIN (Block Range Index) particiona a tabela física em intervalos contíguos de páginas. Ele armazena apenas os valores mínimo e máximo de cada intervalo.
Ele consome frações microscópicas de disco. Torna-se imbatível para séries temporais, logs de telemetria e sequências auto-incrementais.
Por padrão, um intervalo de blocos no BRIN abrange 128 páginas consecutivas de heap, totalizando 1 MB de dados no disco.
O BRIN grava apenas dois valores por intervalo: o menor e o maior valor encontrados naquele bloco de 128 páginas.
Mapeamento de Blocos do Índice BRIN (Intervalos de 128 páginas):
Intervalo Físico Min Timestamp Max Timestamp
Blocos 000 a 127 -> [2026-09-01 00:00:01] [2026-09-01 06:14:22]
Blocos 128 a 255 -> [2026-09-01 06:14:23] [2026-09-01 12:48:10]
Blocos 256 a 383 -> [2026-09-01 12:48:11] [2026-09-01 19:30:05]
Durante a execução da consulta, o otimizador compara a cláusula WHERE contra os resumos de cada intervalo.
Os blocos cujos valores mínimo e máximo não abrangem o filtro são ignorados. Os blocos qualificados sofrem varredura sequencial restrita às suas páginas.
O pré-requisito fundamental do BRIN é a correlação física entre a ordem gravada e a chave de busca. Em tabelas append-only, essa correlação aproxima-se de 1.0.
Uma tabela de 50 GB gera um índice B-Tree de 10 GB. O BRIN equivalente ocupa meros 150 KB.
B-Tree vs Hash vs GIN vs GiST vs BRIN: Qual Escolher?
A tabela a seguir consolida as características operacionais, operadores nativos, consumo de disco e complexidade algorítmica de cada método de acesso do PostgreSQL.
| Tipo de Índice | Complexidade de Busca | Operadores Primários | Overhead em Disco | Custo de Escrita | Cenário de Uso Recomendado |
|---|---|---|---|---|---|
| B-Tree | O(log N) | <, <=, =, >=, >, BETWEEN | Médio (20% a 35% da tabela) | Moderado (balanceamento e splits) | Chaves primárias, chaves estrangeiras, datas e lookups ordenados. |
| Hash | O(1) teórico | = | Médio (similar à B-Tree) | Baixo a moderado | Lookups exatos de strings longas e UUIDs de alta entropia. |
| GIN | Variável / O(log N) | @>, ?, ?&, ?|, @@ | Alto (pode superar o heap) | Alto (mitigado por pending list) | Documentos JSONB, busca textual completa, arrays de tags e vetores. |
| GiST | Variável / O(log N) | &&, <<, &>, <-> | Médio a Alto | Moderado a Alto | Geometria espacial (PostGIS), tipos de intervalo e métricas de vizinhança. |
| BRIN | O(N) com skip | <, <=, =, >=, BETWEEN | Mínimo (< 1% da tabela) | Quase nulo | Séries temporais massivas, logs contínuos e dados ordenados fisicamente. |
A decisão de arquitetura decorre do padrão dominante de carga de trabalho. Para workloads OLTP transacionais, a B-Tree atende a maioria dos casos de uso.
Para cargas analíticas com grandes volumes append-only, o BRIN reduz custos de armazenamento sem penalizar a escrita.
O Custo Oculto da Indexação: Write Amplification, Bloat e Otimização HOT
A adição de índices em excesso degrada a taxa de transferência de escrita do banco de dados. Cada novo índice obriga o motor a atualizar múltiplas estruturas.
O fenômeno da amplificação de escrita (write amplification) ocorre porque qualquer INSERT grava no heap e atualiza todos os índices da tabela.
Em uma tabela com seis índices, uma simples inserção gera sete escritas físicas e múltiplos registros no Write-Ahead Log.
Em operações de UPDATE, o mecanismo MVCC grava uma nova versão da tupla no disco. Ele invalida a versão antiga sem alterar o registro no local.
Se qualquer coluna indexada for alterada, novos ponteiros devem ser inseridos em todas as árvores de índices da tabela.
Para conter esse problema, o PostgreSQL implementa a otimização HOT (Heap-Only Tuples).
Se o UPDATE alterar apenas colunas não indexadas e a tupla couber na mesma página, o motor a encadeia via Line Pointer.
Os índices existentes continuam apontando para a raiz antiga. Isso evita modificações nas páginas dos índices.
Outra técnica crucial de engenharia é o uso de índices cobridores (Covering Indexes) via cláusula INCLUDE. Ela adiciona colunas nas folhas da B-Tree:
-- Índice cobridor habilitando Index Only Scan sem inflar os nós intermediários
CREATE INDEX idx_pedidos_cliente_total
ON pedidos (cliente_id)
INCLUDE (data_pedido, valor_total);
Com a cláusula INCLUDE, o planejador executa um Index Only Scan recuperando campos diretamente da folha do índice.
A árvore intermediária permanece compacta, preservando espaço na memória RAM e reduzindo o consumo de cache.
Como o Runtime do MaxVision Code Aplica Indexação em Alta Escala?
O MaxVision Code opera runtimes locais e distribuídos para agentes de código. O sistema grava fluxos contínuos de telemetria, sessões assíncronas e histórico de alterações em repositórios.
Essa arquitetura combina SQLite para cache local e PostgreSQL para persistência centralizada.
Para manter latência p99 abaixo de 12 milissegundos durante auditorias concorrentes, o motor aplica separação estrita de métodos de acesso.
As sessões ativas e identificadores de agentes utilizam índices B-Tree compostos com a cláusula INCLUDE. Isso permite validar permissões sem leituras de heap.
A telemetria de execução e os rastreios assíncronos de chamadas MCP geram gigabytes semanais de eventos imutáveis.
O MaxVision Code utiliza índices BRIN particionados por timestamp nesses históricos. Essa abordagem reduz o volume de índices de 8,4 GB para menos de 18 MB.
Ela também mantém taxa de inserção contínua superior a 40.000 eventos por segundo sem engarrafar o disco.
Por fim, os metadados de contexto semântico e as assinaturas de código residem em colunas JSONB indexadas por GIN com operador jsonb_path_ops.
Essa combinação viabiliza buscas por operadores de contenção @> em sub-milissegundos. Assim, os agentes localizam dependências de código instantaneamente.
Perguntas Frequentes Sobre Índices de Banco de Dados
O que acontece quando crio índices em excesso em uma tabela?
Criar índices em excesso reduz a velocidade de operações de escrita, pois cada modificação exige sincronizar todas as estruturas associadas. Múltiplos índices disputam espaço no buffer pool da memória RAM, forçando o despejo de páginas úteis de dados para o disco e acelerando a fragmentação física.
Por que o banco de dados opta por Seq Scan mesmo quando o índice existe?
O otimizador escolhe o Seq Scan quando estima que a consulta retornará uma fração significativa da tabela, geralmente acima de 10% das linhas. Leituras sequenciais contínuas de blocos de disco são mais rápidas do que múltiplos acessos aleatórios dispersos alternando entre o índice e o heap.
Qual a diferença prática entre B-Tree e GIN no PostgreSQL?
A B-Tree é uma estrutura balanceada que mapeia uma linha inteira para uma posição ordenada, sendo ideal para chaves primárias, números e datas. O GIN é um índice invertido que divide dados complexos em elementos atômicos, sendo indispensável para consultar arrays, documentos JSONB e campos de busca textual.
Quando o índice BRIN é superior à B-Tree tradicional?
O índice BRIN é superior à B-Tree em tabelas massivas de apenas inserção onde os dados possuem forte correlação física com o disco, como históricos e logs. Nesses cenários, o BRIN ocupa menos de 1% do espaço de uma B-Tree e possui custo de escrita quase nulo, mantendo excelente velocidade de busca.
O que é o índice cobridor e quando devo usar a cláusula INCLUDE?
O índice cobridor armazena colunas adicionais apenas nas páginas folha sem utilizá-las na árvore de ordenação, viabilizando o Index Only Scan sem inflar os nós intermediários. Ele deve ser utilizado quando uma consulta frequente filtra por uma coluna e precisa de outros campos complementares no resultado final.
