Backend interview prep

Start

B-Tree vs Hash Indexes Interview Questions

Master B-Tree and Hash Indexes with interview-focused questions covering internal architecture, search algorithms, equality lookups, range queries, LIKE operations, ORDER BY, GROUP BY, performance comparison, and production best practices.

Introduction

Almost every relational database uses B-Tree indexes as the default indexing structure because they provide excellent performance for a wide variety of queries.

Some databases also support Hash Indexes, which are optimized for extremely fast equality lookups.

Choosing the correct index structure directly affects

  • Query Performance
  • CPU Usage
  • Disk IO
  • Sorting
  • Range Queries
  • Scalability

This guide explains how both indexing structures work internally and when each should be used.

Index Architecture

flowchart LR

SQLQuery --> Optimizer

Optimizer --> BTreeIndex

Optimizer --> HashIndex

BTreeIndex --> TableRows

HashIndex --> TableRows

1. What is a B-Tree Index?

Answer

A B-Tree (Balanced Tree) is a self-balancing tree data structure used by most relational databases.

Characteristics

  • Sorted Data
  • Balanced Tree
  • Fast Search
  • Fast Insert
  • Fast Delete
  • Supports Range Queries

2. Why is it called a Balanced Tree?

Every path from the root node to a leaf node has approximately the same height.

Benefits

  • Predictable Performance
  • Minimal Disk Reads
  • Efficient Navigation

B-Tree Structure

flowchart TD

Root[Root]

Root --> A[20]

Root --> B[60]

A --> A1[5 10]

A --> A2[25 35]

B --> B1[65 70]

B --> B2[80 95]

3. How does a B-Tree search work?

Example

Find

65

Database

↓

Root

↓

Middle Node

↓

Leaf Node

↓

Record

Only a few nodes are visited.

4. What is the search complexity of a B-Tree?

Time Complexity

O(log n)

Very efficient even for billions of rows.

5. What is a B+ Tree?

Most databases actually use

B+ Tree

instead of a traditional B-Tree.

In B+ Trees

  • Internal Nodes store Keys
  • Leaf Nodes store Data Pointers
  • Leaf Nodes are Linked Together

B+ Tree

flowchart TD

Root --> Internal1

Root --> Internal2

Internal1 --> Leaf1

Internal1 --> Leaf2

Internal2 --> Leaf3

Internal2 --> Leaf4

Leaf1 -.-> Leaf2

Leaf2 -.-> Leaf3

Leaf3 -.-> Leaf4

6. Why do databases prefer B+ Trees?

Advantages

  • Better Range Queries
  • Sequential Reads
  • Fewer Disk Accesses
  • Better Caching

7. What is a Hash Index?

Hash Index stores

Hash(Key)

↓

Pointer

Instead of maintaining sorted order.

Hash Index

flowchart LR

CustomerId --> HashFunction --> Bucket --> RowPointer

8. How does a Hash Index work?

Example

CustomerId = 1001

↓

Hash Function

↓

Hash Value

↓

Bucket

↓

Record

9. What is the search complexity of a Hash Index?

Average

O(1)

Very fast equality lookup.

10. Difference between B-Tree and Hash Index?

B-Tree Hash Index
Sorted Unsorted
O(log n) O(1) Average
Supports Range Queries Equality Only
ORDER BY Supported No
GROUP BY Supported No
LIKE Prefix Supported No

11. Which index supports range queries?

B-Tree

Example

WHERE salary BETWEEN 50000 AND 100000

12. Which index supports equality searches?

Both

Example

WHERE EmployeeId=1001

Hash is generally faster.

13. Which index supports ORDER BY?

B-Tree

Example

ORDER BY salary

14. Which index supports GROUP BY?

B-Tree

because data is already sorted.

15. Which index supports LIKE?

B-Tree supports

LIKE 'Ven%'

Does NOT support efficiently

LIKE '%enu'

16. Can Hash Index support range queries?

No.

Example

salary > 50000

Hash cannot locate ordered values.

17. Can Hash Index support sorting?

No.

Hash values are unordered.

18. Which index is used by MySQL?

MySQL InnoDB

↓

B+ Tree

Default.

Hash indexes exist internally in the Adaptive Hash Index but are not general-purpose user indexes.

19. Which index is used by PostgreSQL?

Default

B-Tree

Also supports

  • Hash
  • GIN
  • GiST
  • BRIN
  • SP-GiST

20. Which index is used by Oracle?

Oracle primarily uses

B-Tree

Bitmap indexes are available for specific workloads.

21. Which index is used by SQL Server?

Default

B-Tree

22. Why are B-Trees preferred?

Because one index supports

  • Equality Search
  • Range Search
  • Sorting
  • Grouping
  • Prefix Search

23. What are Hash Collisions?

Different keys may produce the same hash value.

Example

Key A

↓

Hash 200

Key B

↓

Hash 200

Collision handling is required.

24. What are advantages of Hash Indexes?

  • Extremely Fast Equality Search
  • Simple Lookup
  • Low CPU
  • O(1) Average Search

25. What are disadvantages of Hash Indexes?

  • No Sorting
  • No Range Queries
  • No ORDER BY
  • No GROUP BY
  • Hash Collisions

26. What are advantages of B-Tree?

  • Range Queries
  • Sorting
  • Prefix Search
  • GROUP BY
  • ORDER BY
  • Predictable Performance

27. Banking Example

Query

SELECT *

FROM Transactions

WHERE AccountId=1001;

Equality search

↓

Hash or B-Tree

Query

WHERE TransactionDate

BETWEEN

'2026-01-01'

AND

'2026-12-31'

Requires

B-Tree

28. HR Example

Employee Search

WHERE EmployeeId=100

Hash

or

B-Tree

Salary Report

ORDER BY Salary

Requires

B-Tree.

29. E-Commerce Example

Latest Orders

ORDER BY OrderDate DESC

Uses

B-Tree

30. Real Production Scenario

A banking application executed

SELECT *

FROM Transactions

WHERE AccountId=?

millions of times daily.

A B-Tree index was created on

AccountId

Result

  • Query time reduced from seconds to milliseconds.
  • CPU utilization decreased.
  • Database throughput improved significantly.

B-Tree vs Hash Comparison

flowchart LR

Equality --> Hash

Equality --> BTree

Range --> BTree

Sorting --> BTree

Grouping --> BTree

PrefixSearch --> BTree

Enterprise Best Practices

  • Use B-Tree indexes for most OLTP workloads.
  • Use Hash indexes only when the database engine supports them and the workload consists primarily of equality lookups.
  • Use B+ Trees for range searches.
  • Avoid Hash indexes for ORDER BY.
  • Avoid Hash indexes for GROUP BY.
  • Review execution plans regularly.
  • Monitor index usage statistics.
  • Keep statistics updated.
  • Remove unused indexes.
  • Test indexes with production workloads.

Quick Revision

Feature B-Tree Hash
Equality Search ✅ ✅
Range Search ✅ ❌
ORDER BY ✅ ❌
GROUP BY ✅ ❌
Prefix LIKE ✅ ❌
Search Complexity O(log n) O(1) Average
Sorted Yes No
Default Index Yes Rare

Interview Tips

Interviewers frequently ask

  • Difference between B-Tree and Hash Index.
  • Why do databases use B+ Trees?
  • Which index supports range queries?
  • Which index supports ORDER BY?
  • Why can't Hash indexes perform range searches?
  • Explain Hash Collisions.
  • Which databases support Hash indexes?
  • Why are B-Trees the default?
  • Explain B+ Tree architecture.
  • Give a real-world example of choosing between B-Tree and Hash.

Always explain that B-Trees are the default choice for most applications because they support both equality and range-based operations, while Hash indexes are specialized for extremely fast equality lookups but cannot support ordered operations.

Summary

B-Tree and Hash indexes are the two fundamental indexing structures used by relational databases. B-Tree indexes provide balanced performance across equality searches, range queries, sorting, and grouping, making them the default choice in most database systems. Hash indexes excel at equality lookups but are limited to exact-match queries and cannot support ordered operations.

Understanding their internal architecture, performance characteristics, supported query types, and real-world trade-offs is essential for designing efficient databases and succeeding in SQL, backend engineering, database engineering, and solution architect interviews.