Struct InternalNode 

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

Internal node (keys + child pointers)

Fields

id: NodeId

Node ID

keys: Vec<K>

Keys (separator keys)

children: Vec<NodeId>

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() -> Self

Create new internal node

pub fn with_child(child_id: NodeId) -> Self

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<NodeId>

Get child for key

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

Insert key and child at position

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

Insert key and child in sorted order

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

Remove key at index

pub fn split(&mut self) -> (K, Self)

Split node at middle

pub fn merge(&mut self, separator: K, right: &mut Self)

Merge with sibling

pub fn borrow_from_left(&mut self, left: &mut Self, 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 Self, parent_key: &K) -> K

Borrow from right sibling

Trait Implementations

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

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

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

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() -> Self

Returns the “default value” for a type.