Estruturas de busca estática: quando uma boa estrutura deixa a busca binária 40× para trás

Um artigo de 2024, que voltou ao topo do Hacker News hoje, mostra como um layout de memória melhor projetado torna uma estrutura estática 40 vezes mais rápida do que uma busca binária. A verdadeira lição não é o número — é o raciocínio.

Cas concreto: você precisa pesquisar uma chave em um array ordenado com 100 milhões de entradas. Seu primeiro reflexo, aprendido na escola, é a binary search — log₂(n) ≈ 27 comparações. Teoricamente ótimo.

Só que… em 2026, em um CPU moderno, a binary search é catastrófica. Por quê? Porque cada comparação lê uma posição cuja posição depende do resultado anterior. O processador não consegue prever, pré-carregar ou fazer pipelining. A cada passo, ele espera por um cache miss (cerca de 100 ciclos de CPU, ou ~30 ns em DDR5 recente).

O que o artigo faz

O artigo « Static search trees: 40x faster than binary search » (2024, republicado no topo do HN hoje) aprofunda exatamente esse problema. A solução proposta é uma árvore B estática — não uma árvore B dinâmica de manual de banco de dados, mas uma versão otimizada para CPU:

• Layout Eytzinger (nome de um genealogista austríaco do século XVI que inventou um sistema de numeração de árvores) ou árvore B sem ramificações: os filhos de um nó são contíguos na memória.
• Nós calibrados para uma linha de cache (tipicamente 64 bytes, ou 16 chaves de 4 bytes).
• Comparações SIMD (Single Instruction Multiple Data — uma instrução que processa vários dados de uma vez): em um nó, comparar as 16 chaves em uma única instrução AVX2/AVX-512.
• Pré-busca de software (software prefetch): assim que se entra em um nó, dispara o pré-carregamento (__builtin_prefetch) do nó filho provável.

Resultado medido no artigo: em 100 milhões de entradas, a busca cai de ~150 ns para 4 ns. Ou seja, 40× mais rápido.

O que deve ser lembrado

A lição não é “a binary search está morta”. É que a complexidade algorítmica clássica (O log n) ignora a cache de memória. Em um CPU moderno, a estrutura que minimiza cache misses quase sempre vence aquela que minimiza comparações.

Outros exemplos que encontramos em nossos projetos:

• Hash maps “robin hood” (Emmanuel Goossaert, Google Abseil flat_hash_map) vs. std::HashMap clássico.
• PDQ sort (Pattern-Defeating Quicksort, Orson Peters — usado pelo Rust slice::sort_unstable) vs. quicksort escolar.
• Filtros de Bloom antes de buscas exatas para eliminar negativos rapidamente.
• Armazenamento orientado a colunas (Parquet, ClickHouse) que explora cache lines para análise.

Para ler em seguida

• O paper de Paul-Virak Khuong e Pat Morin (2015): Array Layouts for Comparison-Based Searching — a base acadêmica de todo esse campo.
• « What Every Programmer Should Know About Memory » de Ulrich Drepper (2007) — desatualizado em alguns detalhes, mas a base mental permanece sólida.
• O crate Rust static-search-tree ou equivalente para um exemplo produtivo.

Para reter

Quando você otimiza um hot loop, seu primeiro profiler a ser usado não é o cachegrind — é perf stat -e cache-misses,cache-references no Linux (ou Instruments no macOS). É aí que se joga a real performance em 2026. A teoria da complexidade te diz o que é possível; a cache de memória te diz o que é atingível.