Method split_data

rust/src/node.rs:548–579

Split this branch node, returning the new right node and promoted key.

(&mut self)

    /// Split this branch node, returning the new right node and promoted key.
    pub fn split_data(&mut self) -> (BranchNode<K, V>, K) {
        // For branch nodes, we need to ensure both resulting nodes have at least min_keys
        // The middle key gets promoted, so we need at least min_keys on each side
        let min_keys = self.min_keys();
        let _total_keys = self.keys.len();

        // For branch splits, we promote the middle key, so we need:
        // - Left side: min_keys keys
        // - Middle: 1 key (promoted)
        // - Right side: min_keys keys
        // Total needed: min_keys + 1 + min_keys
        let mid = min_keys;

        // Extract the promoted key
        let promoted_key = self.keys[mid].clone();

        // Split keys and children
        let right_keys = self.keys.split_off(mid + 1); // Skip the promoted key
        let right_children = self.children.split_off(mid + 1);

        // Remove the promoted key from left side
        self.keys.pop(); // Remove the key that was promoted

        // Create the new right branch
        let new_right = BranchNode {
            capacity: self.capacity,
            keys: right_keys,
            children: right_children,
        };

        (new_right, promoted_key)
    }

    // ============================================================================
    // STATUS CHECKS