Benchmark Results

Last updated: 2026-03-01 | Deno 2.7.1

⚠️ Note: These benchmarks run in GitHub Actions CI (shared runners). Results show relative performance but may have high variability (CV% >20%). For research-grade measurements, run on dedicated hardware.

Performance Comparison

Comparing O(n) linear scan vs O(log n) R-tree across:

• Data sizes: Sparse (n < 100) vs Large (n > 1000)
• Overlap patterns: Sequential, Grid, Overlapping, Large ranges
• Workloads: Write-heavy (pure inserts), Read-heavy (many queries), Mixed (80/20)

Key Question: When does O(log n) beat O(n)?

How to read: Lower time is better. "Relative" compares to RStarTree baseline:

• 1.0x = same speed as RStarTree
• >1.0x = slower than RStarTree (e.g., 2.0x = twice as slow)
• <1.0x = faster than RStarTree (e.g., 0.5x = twice as fast)

Quick Comparison

Speed relative to RStarTree (lower is better):

Key insights:

• Sparse data (n < 100): All implementations competitive, linear scan overhead minimal
• Medium data (n ≈ 1000): R-tree starts to win, but linear scan still reasonable
• Large data (n ≈ 2500): R-tree dramatically faster (20-28x), hierarchical indexing pays off

Write-Heavy Workloads (Pure Inserts)

column-operations (n=20)

diagonal-selection (n=30)

large-grid (n=2500)

large-overlapping (n=1250)

large-ranges (n=500)

large-sequential (n=2500)

merge-like-blocks (n=15)

row-operations (n=20)

single-cell-edits (n=50)

sparse-grid (n=60)

sparse-large-ranges (n=30)

sparse-overlapping (n=40)

sparse-sequential (n=50)

striping-alternating-rows (n=25)

Read-Heavy Workloads (Frequent Queries)

column-operations (n=20) + 100 queries

diagonal-selection (n=30) + 100 queries

large-grid (n=2500) + 100 queries

large-overlapping (n=1250) + 100 queries

large-ranges (n=500) + 100 queries

large-sequential (n=2500) + 100 queries

merge-like-blocks (n=15) + 100 queries

row-operations (n=20) + 100 queries

single-cell-edits (n=50) + 100 queries

sparse-grid (n=60) + 100 queries

sparse-large-ranges (n=30) + 100 queries

sparse-overlapping (n=40) + 100 queries

sparse-sequential (n=50) + 100 queries

striping-alternating-rows (n=25) + 100 queries

Mixed Workloads (80% Write / 20% Read)

large-overlapping (n=500) 80/20

large-sequential (n=1000) 80/20

sparse-overlapping (n=40) 80/20

sparse-sequential (n=50) 80/20

Query-Only Benchmarks (Construction Not Measured)

large (n=5000, 10k queries)

overlapping (n=1000, 10k queries)

sequential (n=1000, 10k queries)

Summary

What do these numbers actually mean?

These benchmarks compare O(n) linear scan vs O(log n) R-tree for different data sizes and workload patterns.

Sparse data (n < 100): Typical for individual spreadsheet properties (backgrounds, borders, etc.) Large data (n > 1000): Consolidated or heavy usage scenarios

RStarTree is the baseline (1.0x) - numbers > 1.0x are slower, < 1.0x are faster.

lazypartitionedindex (2.1KB minified):

• Fastest in 0/35 scenarios, slowest in 29/35 scenarios
• Average 1.00x vs RStarTree (same)

mortonlinearscan (2.4KB minified):

• Fastest in 29/35 scenarios, slowest in 1/35 scenarios
• Average 1.00x vs RStarTree (same)

rstartree (6.1KB minified):

• Fastest in 6/35 scenarios, slowest in 5/35 scenarios
• Average 1.00x vs RStarTree (same)

System: linux x86_64 Run: deno task bench:update to regenerate