What Is a Roaring Bitmap?

A roaring bitmap is a compressed data structure for representing sets of integers, designed to be both space-efficient and fast to query — closing the gap between plain bitmaps, which are fast but can waste enormous amounts of memory on sparse data, and general-purpose compression schemes, which save space but are slow to query directly.

The problem with plain bitmaps

A standard bitmap represents a set of integers as a sequence of bits, where bit n is set if n is in the set. Checking membership, computing unions, and computing intersections are all extremely fast — just bitwise operations. The catch is memory: a bitmap covering integers up to 4 billion needs 4 billion bits, about 500 megabytes, regardless of whether the set actually contains ten values or ten million. For sparse sets, that’s an enormous amount of wasted space just to represent “mostly zeros.”

Traditional compressed bitmap formats, like run-length encoding schemes, fix the space problem for sparse or clustered data but often lose the speed advantage — decompressing a run-length-encoded bitmap to check whether a single value is present, or to compute an intersection, can be considerably slower than working with an ordinary bitmap directly.

How roaring bitmaps split the difference

Roaring bitmaps solve this by dividing the full range of possible integers into fixed-size chunks — typically 65,536 values each, based on splitting a 32-bit integer into a 16-bit “chunk key” and a 16-bit value within that chunk — and choosing a different internal representation for each chunk depending on how dense it is:

• Sparse chunks (few values present) are stored as a simple sorted array of the actual values — compact, and fast to scan for small counts.
• Dense chunks (most values present) are stored as a plain bitmap — since with high density, the bitmap’s fixed-size cost is worth paying for its speed, and there’s little room left for compression to help anyway.

Each chunk independently picks whichever representation is smaller, and operations like union, intersection, and membership testing are implemented per chunk, using whichever representation each chunk happens to have. The result keeps most of a plain bitmap’s speed while avoiding its worst-case memory blowup on sparse data.

Why this matters for real workloads

Sets of integers show up constantly in systems that need to track membership at scale: which document IDs match a search filter, which user IDs belong to a segment, which row IDs satisfy a query predicate. These sets are frequently very sparse in some regions (a rare tag matching a handful of documents) and very dense in others (a common tag matching almost everything) — exactly the mixed pattern roaring bitmaps are built to handle well, since each chunk adapts independently rather than committing the whole structure to one strategy.

This makes roaring bitmaps a natural fit inside systems that need fast set operations over large ID spaces: search engines use them to represent posting lists (which documents contain a given term), analytics and time-series systems use them for indexing, and some databases use them as an alternative index representation for columns with a manageable number of distinct values — a role adjacent to the bitmap indexing approach used in analytical databases, but with roaring’s per-chunk compression applied on top.

Roaring bitmaps vs other set structures

	Plain bitmap	Roaring bitmap	Hash set
Memory on sparse data	Poor — fixed cost regardless of density	Good — sparse chunks stay compact	Good
Memory on dense data	Good — fixed, low per-bit cost	Good — dense chunks use a plain bitmap	Poor — per-entry overhead
Set operations (union, intersection)	Very fast, bitwise	Fast, per-chunk	Slower — no native bitwise ops
Ordered iteration	Trivial	Trivial	Requires sorting

A hash table is a reasonable choice for simple membership testing on its own, but it doesn’t support fast bitwise union and intersection the way bitmap-based structures do, and it uses meaningfully more memory per stored integer once overhead is accounted for. A Bloom filter solves a different problem entirely — approximate membership testing with a tunable false-positive rate and no way to enumerate members — whereas a roaring bitmap stores the exact set and supports exact set operations, at a real but bounded memory cost.

For scenarios where even approximate distinct counting is enough and exact membership doesn’t matter, structures built for cardinality estimation are a lighter-weight option than any exact set representation, roaring bitmaps included — see what is a Trie and other structures in the same family for related tradeoffs between exactness, memory, and query speed across different key types.

The takeaway

A roaring bitmap represents a set of integers by chunking the value range and letting each chunk independently choose between a compact array and a plain bitmap, based on how dense that chunk actually is. That per-chunk adaptivity gives it much of a plain bitmap’s speed on set operations while avoiding the memory blowup a plain bitmap suffers on sparse data — which is why it shows up wherever systems need fast, memory-efficient set operations over large ID spaces, from search engine posting lists to analytical database indexes.