Skip to content

RECOMMENDATIONS.md

Latest commit

 

History

History
194 lines (159 loc) · 5.66 KB

RECOMMENDATIONS.md

File metadata and controls

194 lines (159 loc) · 5.66 KB

Data Structure Selection Guide: BTreeMap vs BPlusTreeMap

This guide provides objective, data-driven recommendations for choosing between Rust's standard library BTreeMap and our custom BPlusTreeMap implementation.

📊 Performance Summary

Based on comprehensive benchmarking across multiple scenarios:

BTreeMap Strengths

  • Memory Efficiency: 7.3x smaller stack footprint (24B vs 176B)
  • Small Dataset Performance: Superior for datasets < 1,000 items
  • Iteration Speed: 1.8x faster iteration on small datasets
  • Standard Library Optimization: Decades of compiler optimizations

BPlusTreeMap Strengths

  • Large Dataset Performance: Better scalability for > 10,000 items
  • Bulk Operations: Optimized for batch insertions/deletions
  • Specialized Features: B+ tree specific operations
  • Custom Iteration: Multiple iteration strategies available

🎯 Decision Matrix

Criteria BTreeMap BPlusTreeMap Recommendation
Dataset Size < 100 ✅ Excellent ⚠️ Adequate Use BTreeMap
Dataset Size 100-1K ✅ Good ✅ Good Use BTreeMap (memory)
Dataset Size 1K-10K ✅ Good ✅ Good Either (test both)
Dataset Size > 10K ⚠️ Adequate ✅ Excellent Use BPlusTreeMap
Memory Constrained ✅ Excellent ❌ Poor Use BTreeMap
Iteration Heavy ✅ Excellent ⚠️ Adequate Use BTreeMap
Bulk Operations ⚠️ Adequate ✅ Excellent Use BPlusTreeMap
Standard Ecosystem ✅ Perfect ❌ Custom Use BTreeMap

🔍 Specific Use Cases

Choose BTreeMap For:

1. Small Collections (< 1,000 items)

// Configuration maps, small caches, lookup tables
let mut config = BTreeMap::new();
config.insert("timeout", 30);
config.insert("retries", 3);

2. Memory-Critical Applications

// Embedded systems, resource-constrained environments
struct EmbeddedCache {
    data: BTreeMap<u16, u32>, // Only 24 bytes overhead
}

3. Iteration-Heavy Workloads

// Processing all key-value pairs frequently
for (key, value) in btree_map.iter() {
    process(key, value); // 1.8x faster than BPlusTreeMap
}

4. Standard Rust Patterns

// When using with other std collections
use std::collections::BTreeMap;
let map: BTreeMap<String, Vec<i32>> = BTreeMap::new();

Choose BPlusTreeMap For:

1. Large Datasets (> 10,000 items)

// Database-like operations, large indices
let mut large_index = BPlusTreeMap::new(128)?;
for i in 0..100_000 {
    large_index.insert(i, format!("record_{}", i));
}

2. Bulk Operations

// Batch processing, data loading
let mut tree = BPlusTreeMap::new(64)?;
// Bulk insert is more efficient
tree.bulk_insert(large_dataset)?;

3. Custom Iteration Needs

// When you need different iteration strategies
for item in tree.items_fast() { /* fastest */ }
for item in tree.items() { /* safe */ }

4. B+ Tree Specific Features

// When you need B+ tree semantics specifically
let tree = BPlusTreeMap::new(order)?;
// Guaranteed leaf-level linking, etc.

📈 Performance Benchmarks

Creation Performance

Dataset Size: 100 items
- BTreeMap: 0.04ms
- BPlusTreeMap: 0.03ms
Winner: BPlusTreeMap (marginal)

Dataset Size: 10,000 items  
- BTreeMap: 6.68ms
- BPlusTreeMap: 5.23ms
Winner: BPlusTreeMap (22% faster)

Memory Usage

Stack Overhead:
- BTreeMap: 24 bytes
- BPlusTreeMap: 176 bytes
Winner: BTreeMap (7.3x smaller)

Iteration Performance

10,000 items iteration:
- BTreeMap: 0.47ms
- BPlusTreeMap (safe): 0.86ms
- BPlusTreeMap (fast): 0.44ms
Winner: BTreeMap standard, BPlusTreeMap fast mode

⚖️ Trade-off Analysis

BTreeMap Trade-offs

Pros:

  • Minimal memory overhead
  • Excellent small dataset performance
  • Standard library reliability
  • Optimized iteration

Cons:

  • Less scalable for very large datasets
  • No specialized B+ tree features
  • Standard API limitations

BPlusTreeMap Trade-offs

Pros:

  • Better large dataset scalability
  • Specialized B+ tree operations
  • Multiple iteration strategies
  • Custom implementation flexibility

Cons:

  • Higher memory overhead
  • Slower iteration (safe mode)
  • Custom implementation risks
  • Less ecosystem integration

🚀 Final Recommendations

Default Choice: BTreeMap

For most Rust applications, BTreeMap is the recommended default choice because:

  • It's part of the standard library
  • Excellent performance for typical dataset sizes
  • Minimal memory overhead
  • Proven reliability and optimization

When to Consider BPlusTreeMap:

Only choose BPlusTreeMap when you have specific requirements:

  • Working with very large datasets (> 10,000 items)
  • Need B+ tree specific features
  • Bulk operations are critical
  • Memory overhead is not a concern

Migration Strategy:

  1. Start with BTreeMap for new projects
  2. Profile your application to identify bottlenecks
  3. Benchmark both if you hit performance issues
  4. Switch to BPlusTreeMap only if data shows clear benefits

📋 Quick Decision Checklist

Ask yourself:

  • Is my dataset typically < 1,000 items? → BTreeMap
  • Is memory usage critical? → BTreeMap
  • Do I iterate frequently? → BTreeMap
  • Am I using standard Rust patterns? → BTreeMap
  • Do I have > 10,000 items regularly? → Consider BPlusTreeMap
  • Do I need bulk operations? → Consider BPlusTreeMap
  • Do I need B+ tree specific features? → BPlusTreeMap

When in doubt, choose BTreeMap. It's the safer, more optimized choice for the majority of use cases.