Struct VersionChain 

pub struct VersionChain { /* private fields */ }

Multi-version data for a single key with O(log v) read complexity

Optimization: Binary Search with Sorted Commit Ordering

Separates committed versions (sorted descending by commit_ts) from uncommitted version (single optional slot per transaction).

Before: O(v) linear scan + O(v) max computation = O(v) After: O(1) uncommitted check + O(log v) binary search = O(log v)

For v=10 versions: 3.3x speedup For v=100 versions: 7x speedup

Implementations

impl VersionChain

pub fn new() -> Self

Create a new empty version chain

pub fn add_uncommitted(&mut self, value: Option<Vec<u8>>, txn_id: u64)

Add a new uncommitted version If there’s already an uncommitted version from this txn, update it in place

O(1) - just updates the uncommitted slot

pub fn commit(&mut self, txn_id: u64, commit_ts: u64) -> bool

Commit a version - moves from uncommitted slot to sorted committed list

O(log v) - inserts into sorted position using binary search

pub fn abort(&mut self, txn_id: u64)

Abort a version (remove uncommitted version for txn)

O(1) - just clears the uncommitted slot if it matches

pub fn read_at( &self, snapshot_ts: u64, current_txn_id: Option<u64>, ) -> Option<&Version>

Read at a snapshot timestamp, optionally seeing own uncommitted writes Returns the most recent committed version visible at snapshot_ts, or an uncommitted version if it belongs to current_txn_id.

Complexity: O(1) + O(log v) = O(log v)

1. O(1) check for uncommitted version from current transaction
2. O(log v) binary search for most recent visible committed version

Snapshot isolation: we see commits with commit_ts < snapshot_ts (strictly less)

pub fn has_write_conflict(&self, my_txn_id: u64) -> bool

Check if there’s an uncommitted version by another transaction

O(1) - just checks the uncommitted slot

pub fn gc(&mut self, min_active_ts: u64)

Garbage collect old versions

Keeps only versions that might be visible to active transactions, plus one committed version before min_active_ts for new snapshots.

pub fn version_count(&self) -> usize

Get total version count (committed + uncommitted)

Trait Implementations

impl Debug for VersionChain

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

Formats the value using the given formatter.

impl Default for VersionChain

fn default() -> VersionChain

Returns the “default value” for a type.