In mobile engineering (SQLite / Room / Realm) and backend systems (PostgreSQL / MySQL), database queries run over gigabytes of data stored on non-volatile SSD/disk storage.
Why do database engines use B-Trees and B+ Trees for indexes rather than Binary Search Trees or Hash Tables?
The Hardware Reality: Disk Block I/O
Unlike RAM, which allows byte-level access in nanoseconds, solid-state drives and hard disks read and write data in fixed blocks (typically 4KB to 16KB pages).
Reading from disk is 10,000x to 100,000x slower than reading from CPU cache. Therefore:
The goal of a database index structure is to minimize the total number of DISK I/O READS.
Why Binary Search Trees Fail on Disk
In an AVL or Red-Black tree:
- Every node has only 2 children.
- To store 1,000,000 rows: Height ≈ log_2(1,000,000) ≈ 20.
- Searching for a record requires following 20 pointer references.
- If each node is on a different disk block, that's 20 separate disk read operations!
The Solution: B-Trees and Multi-Way Branching
A B-Tree is a self-balancing search tree where each node can have hundreds of keys and children:
Node size = 4096 bytes (Exact match for a 4KB Disk Page!)
Each node holds 100 keys and 101 child pointers.
[ 50 | 100 | 150 ]
/ | | \
[ <50 ] [51..99] [101..149] [ >150 ]
The Power of Wide Fan-Out:
- Height with fan-out
M = 100:Height = log₁₀₀(1,000,000) = 3
- Finding any row in a database of 1,000,000 items requires at most 3 disk reads!
B-Tree vs B+ Tree
Most production database storage engines (InnoDB in MySQL, SQLite in Android) use a variant called the B+ Tree:
| Feature | Classic B-Tree | B+ Tree (Standard in SQLite) |
|---|---|---|
| Data Storage | Data records stored in all nodes | Data records stored exclusively in Leaf nodes |
| Internal Nodes | Store keys and data pointers | Store keys solely for routing (higher fan-out!) |
| Leaf Node Chaining | Leaves are independent | Leaves are linked via Doubly Linked List |
| Range Queries | Requires in-order tree walk (O(N)) | O(1) sequential scan along linked leaf chain! |
B+ Tree Leaves:
[ Data 1-10 ] <=======> [ Data 11-20 ] <=======> [ Data 21-30 ]
(Range query `WHERE id BETWEEN 5 AND 25` simply traverses this linked list!)
Why Not Hash Indexes for Everything?
While a Hash Index offers O(1) lookup for exact equality (WHERE id = 42), it is useless for:
- Range queries (
WHERE age >= 21 AND age <= 30) - Ordering (
ORDER BY created_at DESC) - Prefix searches (
WHERE name LIKE 'Akshay%')
B+ Trees handle equality, ranges, and sorting seamlessly in logarithmic O(log_B(N)) disk reads.
Summary
- Disk storage reads memory in 4KB/16KB page blocks.
- B+ Trees optimize for disk I/O by maximizing node branching factor (fan-out of 100+), keeping tree height
≤ 3-4. - Leaf nodes in a B+ Tree are chained in a doubly linked list for fast range scanning in SQLite.