Struct SortedRun 

pub struct SortedRun<K, V> { /* private fields */ }

An immutable sorted segment of key-value pairs

Used by the Balanced policy for LSM-style scan optimization. Each run is sorted by key, enabling efficient k-way merge.

Key Range Metadata

Each run stores min_key and max_key bounds for O(1) overlap checking. This enables prefix scan pruning: runs that don’t overlap the prefix range can be skipped entirely.

Implementations

impl<K: Ord + Clone, V: Clone> SortedRun<K, V>

pub fn from_unsorted(entries: Vec<(K, V)>, level: usize) -> Self

Create a new sorted run from unsorted entries

pub fn from_sorted(entries: Vec<(K, V)>, level: usize) -> Self

Create from already-sorted entries

pub fn len(&self) -> usize

Get number of entries

pub fn is_empty(&self) -> bool

Check if empty

pub fn size_bytes(&self) -> usize

Get size in bytes

pub fn level(&self) -> usize

Get the level

pub fn get(&self, key: &K) -> Option<&V>

Binary search for a key

pub fn range_from<'a>(&'a self, start: &K) -> impl Iterator<Item = &'a (K, V)>

Range scan from start key

pub fn range<'a>( &'a self, start: &K, end: &K, ) -> impl Iterator<Item = &'a (K, V)>

Range scan with bounds

pub fn iter(&self) -> impl Iterator<Item = &(K, V)>

Iterate all entries

pub fn entries(&self) -> &[(K, V)]

Direct access to underlying entries for O(1) indexing

Required for efficient k-way merge. Without this accessor, callers are forced to use iter().nth() which is O(n) per call.

pub fn overlaps_prefix(&self, prefix: &K) -> bool

Check if this run might contain keys with the given prefix.

Uses stored min_key and max_key bounds for O(1) overlap check. Returns true if the run may contain matching keys (conservative). Returns false only if we can prove no keys match.

Prefix Overlap Logic

For a run with [min_key, max_key] to overlap prefix range [prefix, prefix++):

• If max_key < prefix → run is entirely before prefix → no overlap
• If min_key starts with prefix OR min_key < prefix and max_key >= prefix → overlap

We use a conservative check: return true unless max_key < prefix.

pub fn overlaps_range(&self, start: &K, end: &K) -> bool

Check if this run might contain keys in the given range.

Uses stored min_key and max_key bounds for O(1) overlap check. Returns true if the run may contain matching keys (conservative).

pub fn min_key(&self) -> Option<&K>

Get the minimum key in this run, if any

pub fn max_key(&self) -> Option<&K>

Get the maximum key in this run, if any

Trait Implementations

impl<K: Debug, V: Debug> Debug for SortedRun<K, V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.