Method insert_child_and_split_if_needed

rust/src/node.rs:522–545

Insert a separator key and new child into this branch node. Returns None if no split needed, or Some((new_branch_data, promoted_key)) if split occurred. The caller should handle arena allocation for the split data.

(
        &mut self,
        child_index: usize,
        separator_key: K,
        new_child: NodeRef<K, V>,
    )

    /// Returns None if no split needed, or Some((new_branch_data, promoted_key)) if split occurred.
    /// The caller should handle arena allocation for the split data.
    pub fn insert_child_and_split_if_needed(
        &mut self,
        child_index: usize,
        separator_key: K,
        new_child: NodeRef<K, V>,
    ) -> Option<(BranchNode<K, V>, K)> {
        // Check if split is needed BEFORE inserting
        if self.is_full() {
            // Branch is at capacity, need to handle split
            // For branches, we MUST insert first because split promotes a key
            // With capacity=4: 4 keys → split needs 5 keys (2 left + 1 promoted + 2 right)
            self.keys.insert(child_index, separator_key);
            self.children.insert(child_index + 1, new_child);

            // Now split the overfull branch
            let (new_right, promoted_key) = self.split_data();
            Some((new_right, promoted_key))
        } else {
            // Room to insert without splitting
            self.keys.insert(child_index, separator_key);
            self.children.insert(child_index + 1, new_child);
            None
        }
    }

    /// Split this branch node, returning the new right node and promoted key.
    pub fn split_data(&mut self) -> (BranchNode<K, V>, K) {