Module optimized_scan 

Optimized Range Scan with O(log n + k) Asymptotics

This module replaces the O(n) full-table scan with proper index utilization:

Optimizations Applied

1. Sparse Index Lookup: O(log n) binary search in level metadata
2. Block-Level Skipping: Only read blocks that overlap [start, end]
3. Version Filtering: Skip blocks with no visible versions
4. Bloom Filter Pre-check: Skip SSTables that definitely don’t contain range
5. K-way Merge with Tournament Tree: O(k log m) merging where m = levels

Complexity Analysis

• Index lookup: O(log n) per level
• Block reads: O(k / block_size) where k = result count
• Merge: O(k log m) where m = number of sources
• Total: O(log n + k log m)

Compare to naive scan: O(n) where n = total entries

Structs

FileRange

File metadata for range-based file selection

LevelFiles

Level metadata for file selection

RangeScanner

Optimized range scanner

ScanConfig

Range scan configuration

ScanStats

Scan statistics

TournamentTree

Tournament tree for efficient k-way merge

VersionedEntry

A key-value pair with version metadata

Traits

EntrySource

Source of entries for merging

Functions

select_files_for_range

Helper to select files for a range scan

Type Aliases

Timestamp

Snapshot timestamp for MVCC visibility