Struct LeafNode 

pub struct LeafNode<K, V>
where
    K: Clone + Ord + Debug,
    V: Clone + Debug,
{
    pub id: u64,
    pub keys: Vec<K>,
    pub entries: Vec<LeafEntry<K, V>>,
    pub next: Option<u64>,
    pub prev: Option<u64>,
}

Leaf node (keys + versioned values)

Fields

id: u64

Node ID

keys: Vec<K>

Keys

entries: Vec<LeafEntry<K, V>>

Versioned values (parallel to keys)

next: Option<u64>

Next leaf (for range scans)

prev: Option<u64>

Previous leaf (for reverse scans)

Implementations

impl<K, V> LeafNode<K, V>

where K: Clone + Ord + Debug, V: Clone + Debug,

pub fn new() -> LeafNode<K, V>

Create new leaf node

pub fn find_index(&self, key: &K) -> Result<usize, usize>

Find index for key

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

Get value for key

pub fn contains(&self, key: &K, snapshot: &Snapshot) -> bool

Check if key exists

pub fn insert( &mut self, key: K, value: V, txn_id: TxnId, timestamp: Timestamp, ) -> bool

Insert key-value pair

pub fn delete(&mut self, key: &K, txn_id: TxnId, timestamp: Timestamp) -> bool

Delete key

pub fn split(&mut self) -> (K, LeafNode<K, V>)

Split node at middle

pub fn merge(&mut self, right: &mut LeafNode<K, V>)

Merge with right sibling

pub fn borrow_from_left(&mut self, left: &mut LeafNode<K, V>) -> K

Borrow from left sibling

Invariant

Caller must have verified that left.keys.len() > MIN_KEYS before invoking this function. In leaf nodes keys.len() == entries.len() always, so one invariant check covers both pops.

pub fn borrow_from_right(&mut self, right: &mut LeafNode<K, V>) -> K

Borrow from right sibling

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

Get all keys in range

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

Garbage collect old versions

Trait Implementations

impl<K, V> Debug for LeafNode<K, V>

where K: Debug + Clone + Ord, V: Debug + Clone,

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

Formats the value using the given formatter.

impl<K, V> Default for LeafNode<K, V>

where K: Clone + Ord + Debug, V: Clone + Debug,

fn default() -> LeafNode<K, V>

Returns the “default value” for a type.