What makes a bitmap index different from a B-tree, and when is it better?
A bitmap index stores one bit per row per distinct value — a row's bit is 1 if it has that value, 0 otherwise. This is extremely space-efficient and fast to combine with AND/OR operations across multiple bitmap indexes, but only when the column has few distinct values (like a status flag or a boolean). On a high-cardinality column like a user ID, a bitmap index would need one bitmap per unique value, which stops making sense.
Answered in
What Actually Happens Inside a Database Index: The Data StructuresAn index trades disk I/O for lookup speed. Here's how B-trees, hash tables, and bitmap indexes each make that trade differently.
Read the full analysisOther questions this article answers
More system design questions
- Why does a database need an index at all — why can't it just scan the table?
- When is a hash index better than a B-tree index?
- What is a composite index and why does column order matter?
- What's a covering index and why is it faster than a normal index?
- What's the real cost of adding an index, beyond disk space?
- What does ACID actually stand for, and why do all four properties matter together?
- What's the practical difference between pessimistic and optimistic concurrency control?
- What is a race condition in a database transaction, and how does isolation prevent it?
Every answer on Crashtech is written by the editor of the article it comes from — never auto-summarised. Browse all answers or the System Design beat.