Árboles de búsqueda estática: cuando una buena estructura deja la búsqueda binaria en ridículo

Un artículo de 2024, que volvió a encabezar Hacker News hoy, muestra cómo un diseño de memoria mejor pensado hace que una estructura estática sea 40 veces más rápida que una búsqueda binaria. La verdadera lección no es la cifra: es el razonamiento.

Caso concreto: debe buscar una clave en un array ordenado de 100 millones de entradas. Su primer reflejo, aprendido en la escuela, es la búsqueda binaria — log₂(n) ≈ 27 comparaciones. Teóricamente óptimo.

Excepto que… en 2026, en una CPU moderna, la búsqueda binaria es catastrófica. ¿Por qué? Porque cada comparación lee una casilla cuya dirección depende del resultado anterior. El procesador no puede predecir, precargar ni hacer pipelining. En cada paso, espera un cache miss (unos 100 ciclos de CPU, ~30 ns en DDR5 reciente).

Lo que hace el artículo

El artículo « Static search trees: 40x faster than binary search » (2024, republicado hoy en la portada de HN) profundiza exactamente en este problema. La solución propuesta es un B-tree estático —no un B-tree dinámico de manual de bases de datos, sino una versión optimizada para la CPU:

• Layout Eytzinger (nombre de un genealogista austriaco del siglo XVI que inventó un sistema de numeración de árboles) o B-tree sin ramas: los hijos de un nodo son contiguos en memoria.
• Nodos calibrados en una línea de caché (típicamente 64 bytes, es decir, 16 claves de 4 bytes).
• Comparaciones SIMD (Single Instruction Multiple Data —una instrucción que procesa varios datos a la vez): en un nodo, comparar las 16 claves en una sola instrucción AVX2/AVX-512.
• Prefetch software: al entrar en un nodo, se lanza la precarga (__builtin_prefetch) del nodo hijo probable.

Resultado medido en el artículo: en 100 millones de entradas, la búsqueda pasa de unos 150 ns a 4 ns. Es decir, 40× más rápido.

Lo que hay que recordar

La lección no es «la búsqueda binaria está muerta». Es que la complejidad algorítmica clásica (O log n) ignora la caché de memoria. En una CPU moderna, la estructura que minimiza los cache misses casi siempre supera a la que minimiza las comparaciones.

Otros ejemplos que encontramos en nuestros proyectos:

• Hash maps «robin hood» (Emmanuel Goossaert, Google Abseil flat_hash_map) vs. std::HashMap clásico.
• PDQ sort (Pattern-Defeating Quicksort, Orson Peters —usado por Rust slice::sort_unstable) vs. quicksort escolar.
• Filtros de Bloom antes de búsquedas exactas para eliminar negativos rápidamente.
• Almacenamiento orientado a columnas (Parquet, ClickHouse) que aprovecha las líneas de caché para análisis.

Para leer después

• El artículo de Paul-Virak Khuong y Pat Morin (2015): Array Layouts for Comparison-Based Searching —la base académica de todo este campo.
• «What Every Programmer Should Know About Memory» de Ulrich Drepper (2007) —desactualizado en algunos detalles, pero la base mental sigue siendo sólida.
• El crate de Rust static-search-tree o equivalente para un ejemplo productivo.

Para recordar

Cuando optimice un hot loop, su primer profiler no debe ser cachegrind —es perf stat -e cache-misses,cache-references en Linux (o Instruments en macOS). Ahí es donde se juega el rendimiento real en 2026. La teoría de la complejidad le dice lo que es posible; la caché de memoria le dice lo que es alcanzable.