Hello! Welcome to the final lesson in our module on indexing structures.
So far, we've taken a deep dive into the internals of the two most important index data structures:
- B+ Trees: Ordered, self-balancing trees optimized for disk-based storage, with all data residing in a sorted, linked list of leaf pages.
- Dynamic Hash Indexes: Structures like extendible and linear hashing that map keys to buckets and can grow gracefully without full-table reorganizations.
You now have the foundational knowledge of how they work. The crucial next step, and the focus of today's lesson, is to understand when to use them. We will directly compare the performance of B+ trees and hash indexes for the most common database operations: point queries, range queries, and insertions.
By the end of this 60-minute lesson, you will be able to analyze the performance trade-offs between these two index types and justify why B+ trees are the default, general-purpose index in almost all modern database systems.
1. The Fundamental Difference: Order vs. Hashing
At its core, the performance difference between B+ trees and hash indexes comes down to one thing: B+ trees maintain the sorted order of keys, while hash indexes do not. This single design choice has profound implications for query performance.
Let's start with a high-level overview. This developer blog post clearly summarizes the fundamental characteristics of B-Tree and Hash indexes.
Why Your "Optimized" Queries Might Be Slower Than Before
This blog post provides an excellent, concise summary of the key characteristics of B-Tree (which for our purposes are functionally equivalent to B+ Trees) and Hash indexes.
Read the first two sections, 'How Indexes Are Stored: B-Tree vs Hash', up to (but not including) 'How Indexes Speed Up Queries'. Focus on the key characteristics of each index type. What makes a B-Tree suitable for range queries, and a Hash index unsuitable?
As you read, you saw that B+ trees are structured to support both finding a specific key and scanning through a range of keys. Hash indexes, by contrast, are single-purpose: they use a hash function to find the location of a key as quickly as possible, but the resulting locations have no meaningful order.
Let's break down what this means for different query types.
2. Point Queries: The Speed of Hashing
A point query (or equality query) seeks a single key, like WHERE user_id = 12345.
- Hash Index: The lookup process is, on average, an O(1) operation. The database computes the hash of the key, which directly gives the address of the bucket. Assuming no long overflow chains, this involves just one I/O operation to fetch the bucket page.
- B+ Tree: The lookup is an O(logF N) operation, where F is the fanout and N is the number of leaf pages. This requires traversing the tree from the root to the correct leaf page, typically involving 3-5 I/O operations for even very large tables.
In theory, for pure point queries, hash indexes have a clear performance advantage. Let's see this in a real database system.
F2023 #08 - B+Tree Indexes (CMU Intro to Database Systems)
In this demonstration from the CMU Database Systems course, Professor Pavlo has created both a B+ tree and a hash index on the same column in PostgreSQL. Watch how the query optimizer chooses which index to use for different types of queries.
Watch the segment from 1:17:15 to 1:19:10. Pay attention to the EXPLAIN output when the query uses an IN clause (which is effectively a series of point queries). Notice that PostgreSQL's query optimizer correctly chooses the hash index because it's faster for these equality lookups.
The demo confirms our theoretical understanding: for a series of exact-match lookups, the database prefers the hash index.
3. Range Queries: The Power of Order
A range query seeks all keys that fall within a certain range, like WHERE price BETWEEN 100 AND 500. Here, the story is completely different.
- B+ Tree: B+ trees are built for this. The database performs an
O(log N)search to find the start of the range on a leaf page. It then performs a highly efficient sequential scan by following the sibling pointers that link the leaf pages together until it reaches the end of the range. - Hash Index: Hash indexes are useless for range queries. Since keys are not stored in any order, there is no way to "find the start of the range" or "scan to the end." The only way to satisfy a range query with a hash index is to scan the entire index (or the table itself), which is extremely inefficient.
Let's return to the PostgreSQL demo to see the practical consequence.
F2023 #08 - B+Tree Indexes (CMU Intro to Database Systems)
What happens when we execute a range query or a wildcard search (LIKE 'prefix%')? The answer reveals the B+ tree's greatest strength.
Watch the segment from 1:15:30 to 1:17:15. Observe which index the query optimizer chooses for queries like email LIKE 'zzz%'. Why is the B+ tree the only viable option here?
As the demo shows, the B+ tree is the only choice for queries that rely on the ordering of data. This single advantage is the primary reason why B+ trees are the default index type in virtually all relational databases.
This summary from Duke University's course materials reinforces the point.
These lecture slides provide a concise summary that reinforces what we've just seen in practice.
Read only the 'Summary: Indexes' slide. It neatly encapsulates the core trade-off we're discussing.
Test your understanding!
You are designing the database schema for a simple e-commerce site. You need to support two main lookup patterns for the products table:
- Finding a product by its unique
sku(e.g., "SHIRT-RED-XL"). - Displaying all products with a
pricebetween $20 and $50.
You can create two separate indexes. Which index type (B+ Tree or Hash) would you choose for the sku column and which for the price column? Justify your choices.
Show answer
skucolumn: While a hash index would be excellent for the point query onsku, a B+ tree is the better, more versatile choice. It provides very fast point lookups (nearly as fast as a hash index in practice) and also supports prefix searches (e.g.,sku LIKE 'SHIRT-%') if needed in the future. Given that you can only have one index type, the B+ tree's flexibility is more valuable.pricecolumn: This requires a B+ tree index, without question. The query is a range query, which hash indexes cannot support efficiently. A B+ tree onpricewould allow the database to quickly find the first product priced at $20 and scan the leaf pages until it passes $50.
4. Insertions and the Cost of Maintenance
Indexes accelerate reads, but they impose a penalty on writes (INSERT, UPDATE, DELETE). Every time you modify data, the database must also update any indexes on that data.
Why Your "Optimized" Queries Might Be Slower Than Before
Indexes aren't free. This section of the blog post explains the concept of write overhead.
Read the section 'Problem 2: Index Overhead on Writes'. Understand why every write operation becomes more expensive as you add more indexes.
Let's compare the write overhead for our two index types.
- B+ Tree Insertion: An insertion requires traversing the tree to the correct leaf page (
O(log N)cost) and adding the new entry. If the leaf is full, it must be split. This involves allocating a new page, moving half the entries, and updating the parent node. In the worst case, this split can propagate all the way up to the root, increasing the tree's height. While expensive when they happen, these splits are amortized over many insertions. - Hash Index Insertion: An insertion involves hashing the key to find the correct bucket (
O(1)cost) and adding the entry. If the bucket is full, the system must handle the overflow. In a dynamic scheme like linear hashing, this triggers a split. The cost of a split involves allocating a new page and rehashing the entries of the bucket being split.
It is difficult to declare a universal "winner" for insertion performance.
- Hash index insertions are typically very fast if collisions and overflows are rare.
- B+ tree insertion costs are more predictable (
O(log N)), but a single insertion that triggers a cascade of splits can be slow. - In general, for write-heavy workloads where you are only doing point lookups, an LSM-Tree (which we will cover later in the course) is often preferred over both B+ Trees and hash indexes.
Summary and Conclusion
We can summarize the comparison in a table:
| Operation | B+ Tree Performance | Hash Index Performance | Winner |
|---|---|---|---|
| Point Query | Very Good (O(log N)) |
Excellent (O(1)) |
Hash Index |
| Range Query | Excellent (sorted leaves) | Unusable (unsorted) | B+ Tree (decisively) |
| Insertion | Good (O(log N)), but splits are costly. |
Good (O(1)), but overflow/splits are costly. |
It Depends on workload/data skew. |
Given this, why are B+ trees the default index in almost every system? Because they are consistently good at everything. A hash index is a specialized tool that is faster for one specific task (point queries) but fails completely at another common one (range queries). The versatility and robust all-around performance of the B+ tree make it the most pragmatic choice for a general-purpose database index.
Interestingly, while theory suggests hash indexes are faster for point queries, real-world performance can be complex.
This doesn't invalidate the theory, but it highlights that modern B+ tree implementations are so highly optimized (e.g., cache-conscious layouts) that their practical performance for point queries is often competitive with, and sometimes even better than, hash indexes.
Key Takeaways:
- B+ trees are the versatile, default index type because they efficiently support both point and range queries.
- Hash indexes are a specialized tool for applications that only perform equality lookups on a key and have extremely high-performance requirements for that specific task.
- All indexes impose a write overhead, a critical trade-off to consider when designing a database schema.
Preview of the Next Module:
Congratulations on completing the module on indexing! You now understand the internal machinery of B+ trees and hash indexes. In the next module, "Query Execution," we will move up one layer in the database architecture. We'll see how the system uses these indexes to build query plans and execute operations like selections, sorts, and joins. Our first lesson will focus on implementing an index-based selection operator using the B+ tree structure you now know so well.