Arquitetura dos Dados

Se você já estudou bancos de dados, provavelmente encontrou alguma frase parecida com esta: “o PostgreSQL usa índices B-tree”.

Ela aparece em livros, cursos, documentações e entrevistas técnicas. O curioso é que quase nunca vem acompanhada de uma explicação importante: na prática, os grandes bancos relacionais utilizam uma variação chamada B+ Tree. Parece um detalhe de nomenclatura, mas não é.

Na verdade, entender essa diferença ajuda a responder uma pergunta bem mais interessante: por que uma estrutura criada há mais de cinquenta anos continua sendo a escolha padrão para indexar bilhões de registros?

O problema nunca foi encontrar um dado

Ou melhor: não apenas encontrar um dado. O verdadeiro desafio sempre foi encontrá-lo sem precisar ler o banco inteiro.

Vamos pegar como exemplo uma tabela com um bilhão de linhas. Sem um índice, o banco não tem muitas opções. Ele começa a ler os registros até encontrar aquele que você pediu. Em algum momento ele chega lá, mas talvez precise percorrer uma parte enorme da tabela.

Agora vamos supor que esses registros estejam organizados como uma árvore. Em vez de verificar um registro por vez, cada comparação elimina uma quantidade gigantesca de possibilidades. Em poucos passos, o banco sabe exatamente para qual parte da estrutura deve seguir.

É daí que vem a eficiência das árvores B. Não porque elas “procuram rápido”, mas porque evitam trabalho desnecessário. Essa diferença parece sutil, mas muda completamente a forma como pensamos sobre índices.

O gargalo sempre esteve no armazenamento

Durante muito tempo, acessar um disco rígido era absurdamente mais caro do que fazer qualquer cálculo na CPU. Mesmo hoje, com SSDs extremamente rápidos, essa diferença continua existindo. Por isso, quando um banco de dados foi projetado, os engenheiros não estavam tentando economizar operações matemáticas. Eles estavam tentando economizar leituras de disco.

É exatamente para isso que as B-trees foram criadas. Quanto menos páginas o banco precisar acessar para responder uma consulta, melhor será o desempenho.

Essa ideia continua tão atual hoje quanto era na década de 1970.

Mas afinal, B-tree e B+ Tree são a mesma coisa?

A resposta é… não.

A B-tree original permite que os dados sejam armazenados tanto nos nós internos quanto nas folhas da árvore. Já a B+ Tree faz uma escolha diferente: os nós internos servem apenas para orientar a busca. Os registros ficam armazenados exclusivamente nas folhas.

À primeira vista, parece uma mudança pequena, mas na prática, ela traz duas consequências enormes. A primeira é que os nós internos ficam menores. Como armazenam apenas chaves e ponteiros, cada página consegue comportar muito mais informações. Isso reduz a altura da árvore e, consequentemente, o número de páginas que precisam ser lidas durante uma busca. A segunda consequência é ainda mais interessante.

O segredo está nas folhas

Na B+ Tree, todas as folhas são ligadas entre si. Pode parecer um detalhe de implementação, mas é justamente ele que faz a estrutura funcionar tão bem para bancos relacionais.

Vamos pegar uma consulta como esta:

SELECT *
FROM pedidos
WHERE data BETWEEN '2026-01-01' AND '2026-12-31';

O banco localiza o primeiro registro do intervalo. Depois disso, ele simplesmente percorre as folhas em sequência. Não precisa voltar para a raiz da árvore a cada novo registro encontrado.

O mesmo raciocínio vale para operações como ORDER BY, MIN(), MAX(), consultas por intervalo e até buscas por prefixo, como LIKE 'Art%'.

Essas consultas aparecem o tempo todo em aplicações reais. Não é coincidência que a estrutura tenha sido desenhada exatamente para lidar bem com elas.

E por que outras estruturas não substituíram a B+ Tree?

Porque elas resolvem problemas diferentes.

Índices hash são excelentes quando a consulta procura exatamente uma chave.

LSM Trees revolucionaram bancos orientados à escrita e hoje aparecem em sistemas como RocksDB e Cassandra.

Também existem estruturas especializadas para buscas geográficas, documentos JSON, texto completo e diversos outros cenários.

O ponto é que um banco relacional precisa fazer um pouco de tudo. Ele precisa responder rapidamente a uma busca por chave primária, ordenar milhares de registros, percorrer intervalos de datas, calcular mínimos e máximos, realizar junções e continuar aceitando inserções e atualizações ao longo do tempo.

É difícil encontrar outra estrutura que consiga equilibrar todas essas necessidades tão bem quanto a B+ Tree. Talvez ela não seja a campeã absoluta em cada cenário específico. Mas é excelente em quase todos. E, em engenharia, esse tipo de equilíbrio costuma valer mais do que vencer uma única prova.

Uma tecnologia que atravessou gerações

Na computação, muita coisa envelhece rapidamente. Linguagens entram e saem de moda. Frameworks aparecem todos os anos. Ferramentas que pareciam revolucionárias desaparecem em poucos ciclos de tecnologia. Os índices baseados em B+ Trees seguiram um caminho diferente. Eles sobreviveram a discos rígidos, SSDs, computação em nuvem e ao surgimento de bancos NoSQL.

Não porque sejam antigos, mas porque continuam resolvendo muito bem o problema para o qual foram criados. Talvez esse seja o aspecto mais interessante dessa história.

Quando criamos um índice em PostgreSQL, MySQL, SQL Server ou Oracle, estamos usando uma ideia concebida há mais de meio século. Ela recebeu otimizações, adaptações e melhorias ao longo do tempo. Mas o princípio continua praticamente o mesmo. E isso diz muito sobre a qualidade da solução original.

Algumas tecnologias são lembradas porque mudaram a computação. Outras continuam sendo usadas porque, décadas depois, ainda ninguém encontrou uma forma melhor de resolver o mesmo problema.

As B+ Trees pertencem ao segundo grupo.