Hash Index vs B+ Tree Index - Range Queries & Equality Lookups

🎯

Hash Index vs B+ Tree Index - Range Queries & Equality Lookups

mediumDBMSGoogleAmazonFlipkart

Imagine searching for a book in a massive library: do you look up a single exact title or browse all books published between 2000 and 2010? Different indexing methods optimize these searches differently.

💡 Beginners often confuse hash indexes and B+ trees as interchangeable for all queries, not realizing their strengths differ significantly between exact matches and range scans.

📋

Interview Question

Explain the differences between hash indexes and B+ tree indexes, particularly focusing on their suitability for range queries and equality lookups.

Index data structures and their organizationHow hash indexes handle equality lookupsHow B+ tree indexes support range queries and ordered traversal

💡

Scenario & Trace

ScenarioA user queries a database for all employees with salary exactly $50,000.

Using a hash index on the salary column, the database hashes the value 50,000 to find the exact bucket quickly and retrieves matching records efficiently.

ScenarioA user queries for all employees with salary between $40,000 and $60,000.

Using a B+ tree index on the salary column, the database locates the starting leaf node for $40,000 and traverses leaf nodes sequentially up to $60,000, retrieving all matching records in order.

ScenarioA query requests employees with salary greater than $70,000.

B+ tree index supports this by starting at the leaf node for $70,000 and scanning forward through the linked leaf nodes, while a hash index cannot efficiently support this range scan.

• Range query on a hash index → what happens?
• Equality lookup on a B+ tree index → performance implications?
• Highly skewed data distribution → impact on hash index bucket sizes and B+ tree balance

⚠️

Common Mistakes

Assuming hash indexes support efficient range queries

Interviewer doubts your understanding of index data structures

✅ Clarify that hash indexes do not maintain order and require full scans for range queries

Believing B+ trees are always slower than hash indexes for equality lookups

Interviewer questions your grasp of balanced tree search complexity

✅ Explain that B+ trees have O(log n) lookup, which is efficient and often acceptable

Ignoring the impact of data distribution on hash index performance

Interviewer suspects lack of practical knowledge about collisions and bucket overflow

✅ Mention how skewed data causes uneven bucket sizes and degrades hash index performance

Confusing B+ tree leaf node linkage with hash bucket chaining

Interviewer detects confusion between ordered traversal and collision resolution

✅ Clarify that B+ tree leaf nodes are linked for ordered scans, while hash chaining resolves collisions

🧠

Basic Definition - What It Is

💡 This level covers the fundamental difference in how hash and B+ tree indexes organize data and their typical use cases.

Intuition

Hash indexes are like a direct lookup table for exact matches; B+ trees are like sorted phone books enabling ordered searches.

Explanation

Hash indexes use a hash function to map keys to buckets, enabling very fast equality lookups but no inherent order. B+ tree indexes organize keys in a balanced tree structure with linked leaf nodes, supporting both equality and range queries efficiently. Hash indexes excel when queries ask for a specific value, while B+ trees are preferred when queries involve ranges or ordering.

Memory Hook

💡 Think of hash indexes as a dictionary where you look up a word directly, and B+ trees as a phone book where you can flip through pages in order.

Interview Questions

❓ What type of queries is a hash index best suited for?

• Equality lookups
• Exact key matches
• Not suitable for range queries

❓ Can a B+ tree index support range queries?

• Yes, because leaf nodes are linked
• Supports ordered traversal
• Efficient for range scans

⏱

Depth Level

Interview Time30 seconds

Depthbasic

Covers core definitions and typical use cases; sufficient for quick screening questions.

Interview Target: Minimum floor - never go below this

Knowing only this will help you pass initial screening but not detailed technical rounds.

🧠

Mechanism Depth - How It Works

💡 This level explains internal data organization, query processing, and trade-offs expected in product company interviews.

Intuition

Hash indexes use a hash function to jump directly to a bucket, while B+ trees maintain a balanced multi-level tree with sorted keys and linked leaves for sequential access.

Explanation

Hash indexes compute a hash of the search key to find the exact bucket containing matching records, providing O(1) average lookup time for equality queries. However, they do not maintain any order, so range queries require scanning all buckets, which is inefficient. B+ trees store keys in a balanced tree structure where internal nodes guide the search to leaf nodes containing sorted keys. Leaf nodes are linked, enabling efficient range scans by traversing sequentially. B+ trees have O(log n) lookup time for equality and range queries. Additionally, B+ trees handle insertions and deletions by splitting or merging nodes to maintain balance, while hash indexes may suffer from collisions and require overflow handling.

Memory Hook

💡 Imagine hash indexes as a set of mailboxes keyed by a hash, and B+ trees as a multi-level filing cabinet with sorted folders linked for easy browsing.

Interview Questions

❓ What happens when you perform a range query on a hash index?

• No ordering in hash buckets
• Must scan all buckets
• Inefficient for range queries

❓ How does a B+ tree support both equality and range queries efficiently?

• Balanced tree structure
• Sorted keys in leaf nodes
• Linked leaf nodes for sequential access

❓ What are the trade-offs between hash and B+ tree indexes?

• Hash is faster for equality
• B+ tree supports range queries
• B+ tree has overhead for maintaining balance

⏱

Depth Level

Interview Time2-3 minutes

Depthintermediate

Demonstrates understanding of internal workings and trade-offs; suitable for FAANG on-site interviews.

Interview Target: Target level for FAANG on-sites

Mastering this level distinguishes you from most candidates.

📊

Explanation Depth Levels

💡 Choose your explanation depth based on interview stage and company expectations.

Level	Interview Time	Suitable For	Risk
Basic Definition	30s	Screening call or quick conceptual questions	Too shallow for detailed technical rounds
Mechanism Depth	2-3 minutes	On-site interviews at FAANG and top tech companies	Requires solid understanding; missing details may lose points

💼

Interview Strategy

💡 Use this guide to structure your explanation clearly and confidently before every mock or real interview.

How to Present

Start with a clear definition of hash and B+ tree indexes.Give a relatable example or analogy to illustrate their differences.Explain the internal mechanisms that enable their query performance.Discuss edge cases and trade-offs to show depth of understanding.

Time Allocation

Definition: 30s → Example: 1min → Mechanism: 2min → Edge cases: 30s. Total ~4min

What the Interviewer Tests

Interviewer checks if you know when to use each index type, how they work internally, and their limitations.

Common Follow-ups

• What happens if the data distribution is skewed in a hash index? → Leads to uneven bucket sizes and performance degradation.
• Can you combine hash and B+ tree indexes for complex queries? → Composite or multi-level indexing strategies.

💡 These follow-ups test your ability to handle real-world complexities beyond textbook definitions.

🔍

Pattern Recognition

When to Use

Asked when discussing database indexing strategies, query optimization, or data structure trade-offs.

Signature Phrases

'Explain the difference between...''Compare hash index and B+ tree index for...''What happens when you run a range query on...'

NOT This Pattern When

Similar Problems

Practice

1. Trace the sequence of events when a transaction commits in a database that guarantees Durability. What happens immediately after the commit command?

easy

A. The transaction's changes are written to volatile memory and then acknowledged

B. The transaction's changes are visible to other transactions before being saved

C. The transaction's changes are flushed to stable storage before acknowledgment

D. The transaction's changes are rolled back if a system failure occurs immediately after commit

Solution

1. Step 1: Recall Durability definition

   Durability means once a transaction commits, its changes survive system failures.

2. Step 2: What ensures durability?

   Changes must be flushed to stable storage (disk) before acknowledging commit.

3. Step 3: Analyze options

   A is incorrect because volatile memory is not durable. B is about visibility, not durability. D contradicts durability.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Durability requires stable storage flush before commit acknowledgment.

Hint: Durability = flush to disk before commit confirmation

Common Mistakes:

• Assuming volatile memory is enough for durability
• Confusing visibility with durability

2. When a clustered index is created on a table, what sequence of internal operations occurs during an insert of a new row with a key value that falls between existing keys?

easy

A. The database finds the correct leaf page, inserts the row physically there, and shifts subsequent rows to maintain order.

B. The database appends the row at the end of the table and updates the clustered index pointers accordingly.

C. The database inserts the row into a non-clustered index first, then updates the clustered index asynchronously.

D. The database inserts the row into the appropriate leaf page and may split the page if full, updating parent nodes as needed.

Solution

1. Step 1: Locate insertion point in clustered index B-tree

   The clustered index is a B-tree; the database finds the leaf node where the key fits.

2. Step 2: Insert row physically in sorted order

   The row is inserted in sorted order within the leaf page.

3. Step 3: Handle leaf page fullness

   If the leaf page is full, it splits, and parent nodes are updated to maintain B-tree properties.

4. Step 4: Update parent nodes

   Parent nodes reflect new keys and pointers after split.

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   Clustered index insertion -> B-tree leaf insert + possible split [OK]

Hint: Clustered index insertion = B-tree leaf insert + split if needed [OK]

Common Mistakes:

• Thinking rows are shifted physically like an array (Option A)
• Assuming append-only insertion (Option B)
• Confusing clustered and non-clustered index insertion order (Option C)

3. Which of the following statements about the Atomicity property of ACID is INCORRECT?

medium

A. Atomicity guarantees that either all operations of a transaction are applied or none are.

B. Atomicity ensures that once a transaction starts, it cannot be interrupted by other transactions.

C. Atomicity helps prevent partial updates that could leave the database in an inconsistent state.

D. Atomicity is typically implemented using mechanisms like write-ahead logging and rollback.

Solution

1. Step 1: Recall Atomicity meaning

   Atomicity means all-or-nothing execution of a transaction.

2. Step 2: Analyze each option

   A is correct; C is correct as partial updates violate atomicity; D is correct as logging and rollback implement atomicity.
3. B is incorrect because Atomicity does not prevent interruption by other transactions; that is Isolation's role.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Atomicity is about completeness, not concurrency control.

Hint: Atomicity = all-or-nothing, not about concurrency

Common Mistakes:

• Confusing Atomicity with Isolation
• Assuming Atomicity controls transaction scheduling

4. Which of the following statements about MVCC is INCORRECT?

medium

A. MVCC allows readers to never block writers and vice versa

B. MVCC guarantees that all transactions see the most recent committed data at all times

C. MVCC uses transaction timestamps or IDs to determine version visibility

D. MVCC requires periodic cleanup of obsolete row versions to reclaim storage

Solution

1. Step 1: Analyze read-write blocking

   MVCC is designed to avoid read-write blocking, so this is correct.

2. Step 2: Analyze visibility of most recent data

   Incorrect because MVCC provides snapshot isolation; transactions see a consistent snapshot as of their start time, not necessarily the most recent committed data.

3. Step 3: Analyze version visibility determination

   MVCC uses transaction IDs or timestamps to determine visibility, so this is correct.

4. Step 4: Analyze cleanup requirements

   Periodic vacuuming or cleanup is required to remove obsolete versions, so this is correct.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   MVCC snapshots are fixed at transaction start, not always the latest data [OK]

Hint: MVCC snapshots fix visibility at transaction start, not real-time latest data

Common Mistakes:

• Assuming MVCC always shows the latest committed data
• Believing MVCC causes read-write blocking
• Ignoring the need for version cleanup

5. Identify the bug in the following SQL query that attempts to rank products within categories after filtering categories with total sales > 200:

SELECT category, product_id, total_sales,
       RANK() OVER (ORDER BY total_sales DESC) AS rank
FROM (
    SELECT category, product_id, SUM(sales_amount) AS total_sales
    FROM sales
    GROUP BY category, product_id
    HAVING SUM(sales_amount) > 200
) sub
ORDER BY category, rank

medium

A. Missing PARTITION BY category in the window function causes ranking over entire dataset instead of per category.

B. HAVING clause is incorrectly used instead of WHERE to filter sales_amount.

C. GROUP BY clause is missing product_id, causing aggregation errors.

D. ORDER BY clause at the end should order by total_sales, not rank.

Solution

1. Step 1: Examine window function usage

   The RANK() function lacks PARTITION BY category, so ranking is global, not per category.

2. Step 2: Understand impact on results

   Without partitioning, ranks mix products from all categories, breaking per-category ranking requirement.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding PARTITION BY category fixes ranking scope [OK]

Hint: Window functions need PARTITION BY for per-group ranking [OK]

Common Mistakes:

• Confusing HAVING and WHERE
• Forgetting partition in window functions