B-Tree vs Hash vs R-Tree: The Only Indexing Guide You Need
This blog discusses three key database indexing strategies—B-Tree, Hash Table, and R-Tree. You'll learn how each data structure works, where they shine, and how choosing the right index can make your database queries blazingly fast.
Imagine trying to find a specific file in a messy room with no labels—painfully slow, right?
Databases face a similar challenge when searching data.
Indexing is the technique that makes retrieval lightning-quick by avoiding full table scans.
In this post, we'll dive into three popular index structures: B-Trees, Hash Tables, and R-Trees.
(If you're preparing for system design interviews or want to strengthen your fundamentals, check out DesignGurus.io courses like Grokking System Design Fundamentals, Grokking the System Design Interview, and Grokking the Advanced System Design Interview. These courses cover these topics in depth.)
B-Tree Indexes: The Versatile Workhorse
A B-Tree is a self-balancing tree structure that keeps data sorted.
It's like an ordered phonebook where you can flip straight to the "M" section without checking every page.
How It Works
B-Trees keep keys sorted in a hierarchy and automatically balance as they grow.
To find a value, the database starts at the root and traverses down through child nodes by comparing keys. This yields a search time of about O(log n), which stays efficient even as the dataset gets huge.
B-Trees excel at range queries and ordered retrieval.
For example, a B-Tree index can fetch all entries from "Alice" to "Allison" directly without scanning everything in between.
Thanks to this versatility, most relational databases use B-Tree indexes by default, since they work well for most queries and scale gracefully.
Trade-offs
B-Tree indexes use extra storage to maintain tree nodes and pointers. Also, in write-heavy scenarios, there’s some overhead for rebalancing when inserting or deleting data. Even so, if you're unsure which index to choose, a B-Tree is usually a safe bet.
Hash Table Indexes: The Speed Demon for Exact Lookups
A hash index uses a hash table.
Think of it like a dictionary that maps each key via a hash function to a specific bucket. The big appeal is constant-time lookups on average — about O(1).
How It Works
The database hashes each index key (e.g. a user ID) to determine which bucket the record belongs in.
To retrieve data, it hashes the key and jumps straight to the corresponding bucket. There’s no need to traverse a tree or search through sorted values.
Hash indexes are blazing fast for exact-match queries.
If your query is WHERE user_id = 12345, a hash index can fetch that record faster than a B-Tree, since it goes straight to the data.
Hash indexes also have minimal storage overhead per entry (they don't maintain any sort order).
Trade-offs
Hash indexes only speed up equality comparisons (key = value). They won't help with range queries or sorting, because the index isn’t ordered.
You also must provide the full key for lookups (no "starts with" partial matches).
Even with a good hash function, different keys can still land in the same bucket, causing a collision that the database must handle (adding some overhead).
In summary, use hash indexes when you need ultra-fast lookups on specific keys and you're not doing range or order-based queries on that field.
R-Tree Indexes: Indexing the Multi-Dimensional World
An R-Tree index is built for spatial data — multi-dimensional information like geographic coordinates or geometric shapes.
It's the go-to index for queries such as "find all coffee shops within 5 miles of this location" or "retrieve all objects that overlap this area".
How It Works
R-Trees group nearby items into bounding boxes and organize these hierarchically in a tree.
Each node covers a region of space, with child nodes covering sub-regions.
To answer a spatial query, the R-Tree prunes away entire branches that don't intersect the search area, quickly zooming in on the relevant region.
This avoids scanning every point in the dataset and makes multi-dimensional searches much more efficient.
R-Trees shine for spatial queries.
They handle range searches in two or more dimensions very efficiently.
For example, a mapping application can use an R-Tree to find all points of interest within a given area.
If your app deals with coordinates or geography (say, a "nearby stores" feature), R-Tree indexing will drastically speed up those queries.
Trade-offs
R-Trees are a specialized tool.
Not every database supports them unless spatial features are enabled. They also involve more complex balancing logic (since they're indexing areas, not single values).
And for non-spatial data (like plain text or numbers), an R-Tree offers no benefit — it would just add overhead.
In short, R-Trees are fantastic for maps and spatial data, but not useful for standard indexing needs.
Choosing the Right Index for the Job
Choosing the right index comes down to your access pattern:
-
Range or sorted queries: Use a B-Tree index. It's great for BETWEEN queries and any scenario that benefits from ordered data.
-
Exact match queries: Use a Hash index. For purely exact lookups (like querying by a unique ID), a hash index can be the fastest option.
-
Spatial or multi-dimensional data: Use an R-Tree (or another spatial index). For coordinates and "find within area" queries, R-Trees are ideal.
B-Trees remain the workhorse in databases, but knowing when to use a hash or R-Tree index can give you an edge.
The next time you're optimizing a query—or tackling a system design interview question—you'll know which index to choose to make your data fly!
Conclusion
Choosing the right indexing strategy isn't just a database optimization trick—it's a fundamental skill every developer, especially those prepping for system design interviews, should master.
Whether you're dealing with billions of rows, speeding up a slow query, or explaining trade-offs in an interview, understanding B-Trees, Hash Tables, and R-Trees will give you a clear edge.
Each index serves a unique purpose:
-
B-Trees handle range and sorted queries with elegance.
-
Hash Tables are your best bet for lightning-fast exact lookups.
-
R-Trees dominate when working with spatial or multi-dimensional data.
No single structure is universally perfect. But the ability to pick the right one—based on your access pattern and use case—is what separates solid developers from great system thinkers.
What our users say
AHMET HANIF
Whoever put this together, you folks are life savers. Thank you :)
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!
Arijeet
Just completed the “Grokking the system design interview”. It's amazing and super informative. Have come across very few courses that are as good as this!
