Course contentsShow
← Computer Science
Lesson 1687 of 2,87238. Database Transactions and IndexingFree lesson

B-Tree Index Performance Characteristics

Time complexity for search, insert, and delete operations, and how block size affects real-world performance.

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.