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

Rec 11: Consolidated

Delegates binary-search logic to BinarySearchChain<Version> from sochdb-core, eliminating duplication with mvcc_concurrent::VersionChain.

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

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

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

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.

impl MvccVersionChain for VersionChain

type Value = Option<Vec<u8>>

The value type stored in versions

fn get_visible(&self, ctx: &VisibilityContext) -> Option<&Self::Value>

Get the visible version for the given context

fn get_latest(&self) -> Option<&Self::Value>

Get the latest version (regardless of visibility)

fn version_count(&self) -> usize

Number of versions in the chain

fn is_empty(&self) -> bool

Check if the chain is empty

impl MvccVersionChainMut for VersionChain

fn add_uncommitted(&mut self, value: Self::Value, txn_id: TxnId)

Add a new uncommitted version

fn commit_version(&mut self, txn_id: TxnId, commit_ts: Timestamp) -> bool

Commit a version

fn delete_version(&mut self, txn_id: TxnId, _delete_ts: Timestamp) -> bool

Mark the latest visible version as deleted

fn gc(&mut self, min_visible_ts: Timestamp) -> (usize, usize)

Garbage collect versions older than the given timestamp Returns (versions_removed, bytes_freed)

impl WriteConflictDetection for VersionChain

fn has_write_conflict(&self, txn_id: TxnId) -> bool

Check if there’s a write-write conflict with another transaction