Struct InternalNode 

pub struct InternalNode<K, V>
where
    K: Clone + Ord + Debug,
    V: Clone + Debug,
{
    pub id: u64,
    pub keys: Vec<K>,
    pub children: Vec<u64>,
    /* private fields */
}

Internal node (keys + child pointers)

Fields

id: u64

Node ID

keys: Vec<K>

Keys (separator keys)

children: Vec<u64>

Child node IDs (len = keys.len() + 1)

Implementations

impl<K, V> InternalNode<K, V>

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

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

Create new internal node

pub fn with_child(child_id: u64) -> InternalNode<K, V>

Create with initial child

pub fn find_child_index(&self, key: &K) -> usize

Find child index for key

pub fn get_child(&self, key: &K) -> Option<u64>

Get child for key

pub fn insert_at(&mut self, idx: usize, key: K, right_child: u64)

Insert key and child at position

pub fn insert(&mut self, key: K, right_child: u64)

Insert key and child in sorted order

pub fn remove_at(&mut self, idx: usize) -> (K, u64)

Remove key at index

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

Split node at middle

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

Merge with sibling

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

Borrow from left sibling

Invariant

Caller must have verified that left.keys.len() > MIN_KEYS before invoking this function (see rebalance logic in tree.rs). Otherwise borrowing would violate the B-tree invariant on the sibling.

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

Borrow from right sibling

Trait Implementations

impl<K, V> Debug for InternalNode<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 InternalNode<K, V>

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

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

Returns the “default value” for a type.