Method insert_into_leaf

rust/src/insert_operations.rs:31–120

Insert into a leaf node by ID.

(&mut self, leaf_id: NodeId, key: K, value: V)

    /// Insert into a leaf node by ID.
    fn insert_into_leaf(&mut self, leaf_id: NodeId, key: K, value: V) -> InsertResult<K, V> {
        let leaf = match self.get_leaf_mut(leaf_id) {
            Some(leaf) => leaf,
            None => return InsertResult::Updated(None),
        };

        // Do binary search once and use the result throughout
        match leaf.binary_search_keys(&key) {
            Ok(index) => {
                // Key already exists, update the value
                if let Some(old_val) = leaf.get_value_mut(index) {
                    let old_value = std::mem::replace(old_val, value);
                    InsertResult::Updated(Some(old_value))
                } else {
                    InsertResult::Updated(None)
                }
            }
            Err(index) => {
                // Key doesn't exist, need to insert
                // Check if split is needed BEFORE inserting
                if !leaf.is_full() {
                    // Room to insert without splitting
                    leaf.insert_at_index(index, key, value);
                    // Simple insertion - no split needed
                    return InsertResult::Updated(None);
                }

                // Node is full, need to split
                // Don't insert first. That causes the Vecs to overflow.

                // Calculate split point for better balance while ensuring both sides have at least min_keys
                let min_keys = leaf.capacity / 2; // min_keys() inlined
                let total_keys = leaf.keys.len();

                // Use a more balanced split: aim for roughly equal distribution
                let mid = total_keys.div_ceil(2); // Round up for odd numbers

                // Ensure the split point respects minimum requirements
                let mid = mid.max(min_keys).min(total_keys - min_keys);

                // Split the keys and values
                let right_keys = leaf.keys.split_off(mid);
                let right_values = leaf.values.split_off(mid);

                // Store values we need before releasing the leaf borrow
                let leaf_capacity = leaf.capacity;
                let leaf_next = leaf.next;
                let leaf_keys_len = leaf.keys.len();

                // End the leaf borrow scope here

                // Create the new right node - allocate directly in arena to reuse deallocated nodes
                let new_right_id = self.allocate_leaf_with_data(
                    leaf_capacity,
                    right_keys,
                    right_values,
                    leaf_next, // Right node takes over the next pointer
                );