B-Tree Index Performance Characteristics
What you'll learn: How B-tree indexes achieve their time complexity guarantees and why physical block size matters in real-world database performance.
Time Complexity Analysis
B-tree indexes provide logarithmic time complexity for all three fundamental operations:
- Search: O(log n)
- Insert: O(log n)
- Delete: O(log n)
The logarithm base depends on the branching factor (number of children per node), which is typically quite large in database systems—often hundreds of keys per node. This means even massive tables require very few disk reads.
Why So Fast?
Unlike binary search trees with a branching factor of 2, B-trees maximize each node's capacity. A B-tree storing 1 billion records with 200 keys per node requires only about log₂₀₀(1,000,000,000) ≈ 4 levels. That's just 4 disk I/O operations to find any record!
Block Size and Real-World Performance
The block size (page size) of your storage system directly impacts B-tree efficiency:
- Each B-tree node is stored in one disk block (typically 4KB–16KB)
- Larger blocks mean more keys per node → higher branching factor → shorter tree height
- Fewer levels = fewer disk reads = faster queries
However, larger blocks also mean more data transferred per read. The sweet spot balances these trade-offs based on your workload—smaller blocks for random access patterns, larger for sequential scans.
Clustered vs Non-Clustered Impact
As you learned previously, clustered indexes store actual data rows sorted by the index key, making range queries extremely efficient (sequential disk reads). Non-clustered indexes store pointers, requiring random access to fetch actual rows—potentially one disk seek per row.
Key Takeaway: B-tree indexes deliver O(log n) performance for all operations, with real-world speed heavily influenced by block size, tree height, and whether the index is clustered or non-clustered.