Database Indexing Demystified – B-Tree vs Hash vs Bitmap
This blog breaks down the different types of database indexes—B-tree, hash, and bitmap—and explains when to use each based on your query patterns. It simplifies indexing concepts with real-world use cases, helping developers choose the right index for performance and scalability.
Picture a library with millions of books but no catalog – finding one title would be agonizing.
Now imagine a database with millions of records and no indexes; any search means scanning every record one by one.
A database index is like the library’s catalog: it’s a shortcut that tells the system where to find each piece of data.
In other words, if you're unsure what indexing in databases means, think of it as creating a special lookup table that points to data locations for faster retrieval.
By giving the database this roadmap, indexes drastically speed up queries – a well-tuned index can find a single record in 8 TB of data with only about 4 disk reads (no, that’s not a typo!).
That’s essentially how database indexes improve query performance.
Of course, indexes aren’t magic – they add some storage and slow down writes slightly (since the index must be updated on data changes).
This makes it important to choose the right type of index for the job.
Let’s explore the three most common types of indexes (B-tree, hash, and bitmap) and when to use each.
B-Tree Indexes: The All-Purpose Workhorse
B-tree indexes are the default index type in most relational databases, and for good reason.
A B-tree (typically a B+ tree under the hood) keeps data sorted and balanced, so looking up a value is highly efficient even as the dataset grows large.
You can use B-tree indexes for all kinds of queries – exact matches, range queries, prefix lookups, sorting – and get great performance in each case.
In fact, a B-tree index supports queries using equality and inequality operators (<, <=, =, >=, BETWEEN, etc.) thanks to its sorted structure. This means it’s just as handy for finding a single ID as it is for scanning a range (e.g. “all orders from January”).
If you’re not sure which index type to use, a B-tree is usually the safe bet because of its flexibility.
It handles high-cardinality data (columns with many distinct values) well and even copes with frequent inserts/updates by rebalancing the tree automatically.
Use case: Almost every application relies on B-tree indexes.
For example, an e-commerce app might index the orders table by order_date to quickly retrieve orders in a date range, and index the customers table by last_name to find all the “Smiths” without scanning the whole table.
Whenever you need broad versatility and fast range or sorted lookups, B-tree indexes are your go-to workhorse.
Hash Indexes: Lightning-Fast for Exact Lookups
A hash index uses a completely different strategy: it’s like a dictionary that maps each key through a hash function to a specific “bucket” or location.
The benefit?
O(1) (constant-time) lookups on exact matches, which is blazing fast.
If you query WHERE username = 'alice', a hash index can immediately jump to the location of “alice” without traversing a tree. However, this speed comes with strict limitations.
Hash indexes only help with exact lookups – they do nothing for range queries or sorting, because hashing scrambles the natural order of the data.
As the MySQL documentation notes, hash indexes are used only for equality comparisons and cannot assist with < or > range searches. You also can’t use them to speed up an ORDER BY clause because there’s no sorted order to leverage.
In short, asking a hash index for “the next item” makes no sense, since it doesn’t maintain any sequence.
Use case: Use hash indexes sparingly, and only when you know you’ll always query by exact value.
For example, a cache table or a configuration lookup table that’s always accessed by a unique key might benefit from a hash index.
Some NoSQL and in-memory databases use hash tables behind the scenes for fast key-value retrieval.
In traditional SQL databases, though, B-tree indexes are usually preferred for general use because they’re nearly as fast for equality lookups and far more flexible.
Choose a hash index only for a very targeted performance boost on equality queries – and if there’s any chance you’ll need range queries or ordering on that data, stick with B-tree.
Bitmap Indexes: Turbocharging Analytics Queries
Bitmap indexes shine in analytics and data warehousing scenarios.
Instead of a tree or hash, a bitmap index uses bit arrays to represent the data.
Imagine a table has a column status with three possible values: “Active”, “Inactive”, “Banned”.
A bitmap index on status would create three bitmaps (arrays of bits), each one indicating the rows where a given value is present (1 for present, 0 for absent).
For example, the “Active” bitmap might look like 101100... where each bit corresponds to a row in the table. The true power of this approach appears with complex queries on multiple columns.
Suppose you want all records where status = 'Active' AND gender = 'Female' AND region = 'North'.
If each of those columns has a bitmap index, the database can simply take the three bitmaps and do a fast bitwise AND operation to get a new bitmap of the result – no heavy scanning required.
These bit operations are extremely efficient, so bitmap indexes excel at answering ad-hoc queries on low-cardinality columns (columns with few distinct values). They are super space-efficient for such data and can be combined like building blocks to satisfy query filters quickly.
However, bitmap indexes are not suited for every situation. They struggle with high-cardinality data – if a column has thousands of distinct values (e.g. a user ID), a bitmap index would need thousands of bit arrays, which is impractical and memory-hungry.
They also incur overhead for frequent updates: changing a single row’s value means flipping a bit in a large bitmap, which can be slow and may cause locking contentions in a high-concurrency environment.
For this reason, you typically see bitmap indexes in read-mostly environments like data warehouses, where data is loaded in bulk and then queried many times but updated infrequently.
Use case: Consider a large analytics database for a retail company. A sales fact table with 100 million rows might have columns like region, product_category, and year – each with a limited set of possible values.
By creating bitmap indexes on these columns, analysts can instantly query things like “total sales for Electronics in the North region in 2023” by combining the relevant bitmaps, instead of slogging through every row.
Bitmap indexes are a perfect fit here, delivering lightning-fast aggregations and filters in OLAP (analytical) workloads.
Check out SQL vs NoSQL for more details.
Conclusion
Database indexing isn’t a dark art – it’s a fundamental tool for boosting data retrieval speed. The key is to use the right type of index for your needs.
If you’re unsure, a B-tree index is usually the best starting point due to its versatility.
If you have a very specific use-case, like a purely equality-based access pattern or an analytics scenario with low-cardinality data, then consider hash or bitmap indexes, respectively.
Remember that indexes are a double-edged sword: too few, and reads are slow; too many (or the wrong kind), and writes can slow down. It’s all about finding the balance based on your application’s query patterns.
Finally, whether you’re using a classic SQL database or a modern NoSQL store, indexing remains crucial for performance.
By demystifying database indexing and understanding B-tree, hash, and bitmap indexes, you’re well on your way to designing faster, more efficient data systems that keep your users (and your servers) happy.
What our users say
MO JAFRI
The courses which have "grokking" before them, are exceptionally well put together! These courses magically condense 3 years of CS in short bite-size courses and lectures (I have tried System Design, OODI, and Coding patterns). The Grokking courses are godsent, to be honest.
Brandon Lyons
The famous "grokking the system design interview course" on http://designgurus.io is amazing. I used this for my MSFT interviews and I was told I nailed it.
Roger Cruz
The world gets better inch by inch when you help someone else. If you haven't tried Grokking The Coding Interview, check it out, it's a great resource!
