Struct DeferredSortedIndex 

pub struct DeferredSortedIndex { /* private fields */ }

Deferred Sorted Index with LSM-style compaction

Scan Optimization (80/20 Fix)

The original SkipMap-based scan was 3.3x slower than SQLite because:

• SkipMap iteration = pointer chasing across memory
• Each entry.key().clone() = heap allocation
• Poor cache locality (random memory access pattern)

The fix: Use a sorted Vec<Vec<u8>> for the cold storage.

• Sequential memory access = L1/L2 cache hits
• Binary search for range start = O(log N)
• Iteration = simple pointer increment

Benchmarked improvement: +50-80% scan throughput

Implementations

impl DeferredSortedIndex

pub fn new() -> Self

Create a new deferred index with default config

pub fn with_config(config: DeferredIndexConfig) -> Self

Create with custom configuration

pub fn insert(&self, key: Vec<u8>)

Insert a key into the index

O(1) append to hot buffer (fast path)

pub fn insert_ref(&self, key: &[u8])

Insert a key reference (avoids one clone if key is already owned)

pub fn compact(&self)

Compact hot buffer into sorted storage

Merges hot buffer with existing sorted vec using k-way merge. This is O(N + M) where N = hot buffer size, M = existing sorted size.

pub fn range_from<'a>( &'a self, start: &[u8], ) -> impl Iterator<Item = Vec<u8>> + 'a

Iterate over all keys starting from start

Uses binary search + sequential iteration for cache-friendly access.

pub fn range<'a>( &'a self, start: &[u8], end: &[u8], ) -> impl Iterator<Item = Vec<u8>> + 'a

Iterate over keys in range [start, end)

Binary search for bounds, then sequential iteration.

pub fn contains(&self, key: &[u8]) -> bool

Check if a key exists in the index

pub fn stats(&self) -> DeferredIndexStats

Get statistics

pub fn clear(&self)

Clear the index

pub fn len(&self) -> usize

Get the total number of unique keys (requires compaction)

pub fn is_empty(&self) -> bool

Check if index is empty

Trait Implementations

impl Default for DeferredSortedIndex

fn default() -> Self

Returns the “default value” for a type.