B-Tree Bandwidth Optimizer

This interactive simulation demonstrates the core principle from our B-Trees are Bandwidth Optimizers post: B-Trees minimize disk I/O by packing multiple keys per page, dramatically reducing tree height compared to binary trees.

Key Insights to Explore

1. The Height Collapse Effect

Watch how B-Tree height stays remarkably low even as dataset size grows to billions of records. This is the mathematical foundation of bandwidth optimization.

Try this: Set dataset to 1 billion records and compare heights!

2. Page Size Impact

Larger pages = more keys per node = shorter trees. But there's a sweet spot based on your hardware and workload.

Real-world example:

• 4KB pages: Standard for most databases (PostgreSQL, MySQL)
• 8KB pages: MongoDB's WiredTiger storage engine
• 16KB pages: Some analytical systems for better compression

3. Fill Factor Trade-offs

Lower fill factors leave room for insertions without immediate page splits, but reduce key density.

Production tuning:

• 75%: Good balance for mixed workloads
• 90%: Read-heavy workloads
• 60%: Write-heavy with frequent insertions

The Math Behind the Magic

B-Tree Height Formula

Height = ⌈log₍ₖ₊₁₎(N)⌉

Where:

• k = keys per node
• N = total records
• k+1 = fanout (children per node)

Binary Tree Height Formula

Height = ⌈log₂(N)⌉

Why This Matters

Each level = one disk I/O operation. The height difference directly translates to bandwidth savings.

Real-World Performance Impact

Database Index Performance

-- B-Tree index on user_id (1M users)
SELECT * FROM users WHERE user_id = 12345;
-- B-Tree: ~3 disk reads
-- Binary Tree: ~20 disk reads

Storage Engine Optimizations

# MongoDB WiredTiger B-Tree configuration
btree_config = {
    "internal_page_max": "8KB",    # Internal node size
    "leaf_page_max": "8KB",        # Leaf node size
    "split_pct": 75,               # Fill factor
}

Interactive Experiments

Experiment 1: Database Scale

1. Start with 1K records on 4KB pages
2. Gradually increase to 1B records
3. Observe how B-Tree height grows logarithmically while binary tree height explodes

Experiment 2: Hardware Tuning

1. Set 10M records
2. Try different page sizes: 1KB → 4KB → 8KB → 16KB
3. Watch keys-per-node and height changes
4. Find the sweet spot for your simulated workload

Experiment 3: Workload Patterns

1. Set 1M records with 4KB pages
2. Switch between search patterns:
   • Random: Worst case - no cache benefits
   • Sequential: Cache-friendly but not B-Tree's strength
   • Range: B-Tree's killer feature

Experiment 4: Storage Types

1. Use 100M records
2. Compare latencies across storage types:
   • NVMe SSD (0.1ms): I/O difference less critical
   • HDD (10ms): B-Tree advantage massive
   • Network storage (100ms): Every I/O counts

Production Insights

When B-Trees Shine

• Large datasets (>100K records)
• Disk-based storage (not pure in-memory)
• Range queries and sorted access
• Mixed read/write workloads

When to Consider Alternatives

• Small datasets (<1K records): Hash indexes might be better
• Pure memory systems: Other data structures could be faster
• Write-heavy workloads: LSM-trees might be more suitable
• Analytical queries: Columnar storage might win

Configuration Guidelines

PostgreSQL B-Tree Tuning:

-- Page size: 8KB (default)
-- Fill factor for indexes
CREATE INDEX idx_user_email ON users(email) WITH (fillfactor = 90);

MySQL InnoDB Settings:

-- Page size: 16KB (default)
-- Larger pages for better compression in analytical workloads
SET GLOBAL innodb_page_size = 16384;

The Bandwidth Optimization Principle

The core insight: B-Trees optimize for the slowest part of the system - disk I/O. By packing multiple keys per disk page, they minimize the number of expensive disk reads needed for any operation.

This isn't just about speed - it's about system efficiency:

• Lower latency: Fewer I/O operations
• Higher throughput: More queries per second
• Better resource utilization: Each disk read brings maximum useful data
• Improved scalability: Performance degrades gracefully with data growth

Remember: The best data structure is the one optimized for your bottleneck. For most database systems, that bottleneck is disk bandwidth, making B-Trees the perfect choice.