Bitmap Index

You have an orders table with 100 million rows. One column is status with five possible values: pending, processing, shipped, delivered, returned. You need to answer queries like:

SELECT COUNT(*) FROM orders WHERE status = 'shipped' AND region = 'us-east';

A B-tree index on status seems logical. But B-trees are designed for high-cardinality columns, columns with many distinct values (like user IDs or email addresses). When a column has only 5 distinct values, a B-tree index points to roughly 20 million rows per value. The database ends up reading huge portions of the index and the table, barely faster than a full scan.

Bitmap indexes take a completely different approach. Instead of building a tree structure, they represent each distinct value as a bit array, one bit per row. For 100 million rows, the shipped bitmap is 100 million bits (about 12 MB). Each bit is 1 if that row's status is "shipped" and 0 otherwise.

The magic: combining conditions is just a bitwise AND. "shipped AND us-east" means AND-ing two bit arrays, an operation CPUs execute in nanoseconds on 64 bits at a time. No tree traversal, no row lookups, no joins. Just bit manipulation.

Given this simplified table:

Bitmap for status:

pending: 0 1 0 0 1 0
shipped: 1 0 1 0 0 1
delivered: 0 0 0 1 0 0

Bitmap for region:

us-east: 1 0 1 0 1 0
us-west: 0 1 0 0 0 0
eu-west: 0 0 0 1 0 1

Query: WHERE status = 'shipped' AND region = 'us-east'

shipped: 1 0 1 0 0 1
us-east: 1 0 1 0 1 0
AND result: 1 0 1 0 0 0 → Rows 0 and 2 match

Two bitwise AND operations. Done. No matter how many rows you have, the operation scales linearly with the number of bits, and modern CPUs process 64 bits per instruction.

Compression makes it even better. Real-world bitmaps are sparse, most bits are 0. Compression algorithms like Roaring Bitmaps and WAH (Word-Aligned Hybrid) compress these sparse arrays dramatically while still allowing bitwise operations directly on the compressed form.

Roaring Bitmaps, used by Apache Lucene, Apache Druid, and Apache Spark, can compress a bitmap of 100 million rows down to a few hundred kilobytes if the 1-bits are clustered together.