B-tree vs. Hash Indexes: When to Use Which

Introducing the Hash Index

If a B-tree is analogous to a balanced binary search tree adapted for disk, a hash index is its counterpart to the hash map (or dictionary, in Python terms) that you're very familiar with from programming. Its design is ruthlessly simple and optimized for a single purpose: extremely fast equality lookups.

Here's how it works:

1. When you create a hash index on a column, the database builds a data structure that contains a set of "buckets".
2. To find a row, the database takes the value you're searching for (e.g., a specific username) and passes it through a hash function.
3. The output of this function is a hash value that directly maps to one of the buckets.
4. The database then looks inside that bucket, which contains pointers to the actual data rows on disk that have that value.

The ideal performance is constant time, or $O(1)$, because the hash function tells you exactly where to look, regardless of how many rows are in the table.

This seems incredibly efficient—so why don't we use hash indexes for everything? The answer lies in what the hash function does to the data.

The Core Trade-Off: Order vs. Direct Access

The fundamental difference between B-tree and hash indexes comes down to one thing: order.

• B-Tree Indexes Preserve Order: As you learned, B-trees maintain their keys in sorted order. This is their superpower. It's what allows them to efficiently handle not just equality checks (=), but also range queries (WHERE value > 100), sorting (ORDER BY), and prefix matching (LIKE 'search%'). The database can simply walk the sorted leaf nodes.

• Hash Indexes Destroy Order: A hash function, by its very nature, scrambles its input to produce a bucket location. The key 'user_A' might hash to bucket 5, while the very next key, 'user_B', might hash to bucket 97. There is no relationship between the proximity of keys and the proximity of their storage locations.

This single fact makes hash indexes completely useless for any operation that relies on order. You cannot use a hash index to satisfy a range query or to avoid a sort operation. If you try, the database will ignore the index and fall back to a slow, full table scan.

A Tale of Two Indexes: Practical Scenarios

The best way to understand this trade-off is to see it in action. Let's look at when you would choose one over the other.

The following article gives excellent, practical examples. We'll focus on its comparison of B-Tree and Hash indexes, which includes clear SQL examples and a real-world scenario.

The session management example from the article is a perfect illustration of the core principle: use the right tool for the job.

• For the session_token column, which is only ever queried with an exact match (WHERE session_token = '...'), a hash index is a strong candidate.
• For the expires_at column, which is queried with a range (WHERE expires_at < NOW()), a B-tree is the only viable choice.

This shows that you can, and often should, have multiple indexes of different types on the same table to optimize different query patterns.

Synthesizing the Concepts

Let's consolidate this with a video that summarizes the key decision points when choosing an index.

The flowchart at the end of the video is a great mental model to carry with you. For most general-purpose database workloads (OLTP systems), the B-tree is the default and correct answer. Hash indexes are reserved for more niche, performance-critical scenarios.

Database Support and In-Memory Systems

It's also important to know that support and usage for hash indexes vary across database systems.

• PostgreSQL: Supports user-created hash indexes, but its documentation notes that B-tree performance for equality checks is often comparable, making B-trees a safer, more flexible default.
• MySQL (InnoDB): Does not allow you to explicitly create a hash index. However, InnoDB uses an internal mechanism called the Adaptive Hash Index. It monitors B-tree lookups and automatically builds a hash index in memory for frequently accessed B-tree pages, effectively giving you the speed of a hash lookup for hot data without sacrificing the B-tree's flexibility.
• In-Memory Databases (e.g., Redis): Hash indexes are very common in in-memory systems. Since the entire dataset is in RAM, the complexities of disk I/O that B-trees are designed to solve are less relevant. Here, the raw speed and simplicity of a hash table make it an excellent choice.

Conclusion

You now have a clear understanding of the strengths and weaknesses of B-tree and hash indexes. This knowledge moves you from simply knowing that "indexes make things fast" to being able to reason about why a particular index is suited for a particular job.

Key Takeaways:

• B-Tree Index (The Generalist):

  • Structure: A balanced tree, sorted by key.
  • Best for: The vast majority of use cases. It excels at equality checks, range queries (>, <, BETWEEN), sorting (ORDER BY), and prefix LIKE searches.
  • Performance: Excellent and consistent $O(\log N)$ lookups.

• Hash Index (The Specialist):

  • Structure: A hash table mapping keys to data pointers.
  • Best for: Niche scenarios requiring the absolute fastest exact equality lookups (=).
  • Performance: Theoretically $O(1)$, but can degrade with many hash collisions.
  • Major Limitation: Cannot be used for range queries or sorting, as the hash function destroys ordering.

When in doubt, use a B-tree. It is the most versatile and reliable choice. Only consider a hash index when you have a high-volume query pattern that only uses equality lookups and you've identified it as a performance bottleneck.

Preview of the Next Lesson:
So far, our focus has been on optimizing individual queries for speed. However, real-world applications rarely execute queries in isolation. They group related operations (e.g., debiting one account and crediting another) into a single logical unit of work called a transaction. In our next lesson, we will explore the four critical properties that ensure data integrity during these transactions: ACID (Atomicity, Consistency, Isolation, and Durability).