Roaring Bitmaps: cómo Lucene comprime IDs sin descomprimir todo

Lo esencial

Roaring Bitmaps divide cada entero de 32 bits en una clave de 16 bits (bloque) y un valor de 16 bits dentro del bloque.
Cada bloque cubre 65.536 valores posibles y elige uno de tres contenedores: array, bitmap o run.
El array container se usa hasta 4.096 elementos; el bitmap container ocupa 8.192 bytes fijos por bloque.
Apache Lucene usa Roaring Bitmaps desde la versión 5.0 para representar conjuntos de IDs de documentos.
Elasticsearch, Apache Druid e InfluxDB lo usan en sus índices de segmentos y filtros booleanos.
Las operaciones AND, OR y XOR se ejecutan contenedor por contenedor, sin expandir el bitmap completo en memoria.
La librería de referencia en Java es RoaringBitmap, con puertos activos en Go, C, Python y Rust.

¿Qué es un bitmap y por qué pesa tanto?

Filtrar mil millones de documentos con un bit por cada uno pesa 125 megabytes en memoria, sin importar cuántos de esos bits estén en 1. Un bitmap es un array de bits donde la posición N vale 1 si el elemento N pertenece al conjunto: buscar si el elemento 4 está adentro es instantáneo, solo hay que mirar un bit. El problema es el costo fijo: cuanto más disperso el conjunto, peor la relación entre información útil y espacio ocupado.

La idea de Roaring: dividir en bloques de 16 bits

Roaring Bitmaps, publicado por Daniel Lemire y sus coautores, resuelve esto dividiendo cada entero de 32 bits en dos mitades de 16 bits. Los 16 bits altos son la clave del bloque; los 16 bits bajos son el valor dentro de ese bloque. Cada bloque cubre como máximo 65.536 valores consecutivos y se comprime por separado según su densidad. La implementación de referencia en Java está en el repositorio oficial, con puertos activos en Go, C, Python y Rust.

Los tres contenedores: array, bitmap y run

Cada bloque elige uno de tres formatos según cuántos elementos tiene. El array container guarda una lista ordenada de shorts de 16 bits y se usa mientras el bloque tenga 4.096 elementos o menos, es decir hasta 8.192 bytes. El bitmap container se activa a partir de ahí: reserva un bloque fijo de 65.536 bits, 8.192 bytes exactos, uno por cada valor posible. El run container guarda tramos de valores consecutivos como pares (inicio, longitud) y es el más eficiente cuando el conjunto tiene rangos largos sin huecos, como IDs consecutivos de una tabla.

Operaciones de conjuntos sin descomprimir

La ventaja frente a un bitset plano no es solo el tamaño: las operaciones AND, OR, XOR y NOT se ejecutan contenedor por contenedor, sin expandir todo el conjunto en memoria. Intersectar dos array containers es un merge de dos listas ordenadas. Intersectar dos bitmap containers es un AND de palabras de 64 bits. La librería convierte automáticamente de array a bitmap, o al revés, cuando el resultado cruza el umbral de 4.096 elementos.

Ejemplo práctico en Java

Con la librería RoaringBitmap, crear e intersectar dos conjuntos es directo:

import org.roaringbitmap.RoaringBitmap;

RoaringBitmap usuariosActivos = RoaringBitmap.bitmapOf(3, 4, 1000, 1_000_000);
RoaringBitmap usuariosPremium = RoaringBitmap.bitmapOf(4, 1000, 2_000_000);

RoaringBitmap activosPremium = RoaringBitmap.and(usuariosActivos, usuariosPremium);
System.out.println(activosPremium); // {4, 1000}
System.out.println(activosPremium.getSizeInBytes()); // tamano serializado real

El resultado activosPremium contiene solo los IDs presentes en ambos conjuntos. Llamar a getSizeInBytes() después de cada operación es la forma correcta de medir cuánto pesa realmente tu bitmap en un caso concreto, en vez de asumir un número de memoria.

Dónde se usa en producción

Apache Lucene usa Roaring Bitmaps desde la versión 5.0 para representar conjuntos de IDs de documentos que coinciden con una consulta o un filtro. Elasticsearch, construido sobre Lucene, hereda ese mecanismo para cachear filtros booleanos. Apache Druid e InfluxDB lo usan en sus índices de segmentos para acotar qué filas leer sin escanear todo el bloque. Pilosa, renombrado luego FeatureBase, construyó su motor de analítica completo alrededor de bitmaps Roaring como estructura de indexación primaria.

Cuándo no conviene

Roaring Bitmaps no gana en todos los casos. Si el conjunto es denso y sin patrón, por ejemplo la mitad de los bits en 1 distribuidos al azar dentro de un bloque, el contenedor cae en modo bitmap y ocupa exactamente lo mismo que un bitset plano: 8.192 bytes por cada 65.536 valores. Ahí no hay compresión, solo evitás decodificar de más cuando la consulta toca una parte del rango. Para conjuntos pequeños y estáticos que caben enteros en una sola palabra de 64 bits, un bitset simple es más rápido y más fácil de razonar.

Conclusión

Roaring Bitmaps convirtió una estructura de los años 90 en la base de motores de búsqueda y bases analíticas en 2026. La idea central, particionar y elegir el contenedor más barato para cada partición, se puede aplicar a cualquier problema donde la densidad de los datos varía dentro del propio conjunto. Antes de reinventar una estructura de bits a medida, vale la pena revisar si Roaring ya resuelve el caso.