Function test_branch_node_split_creates_new_level

rust/tests/bplus_tree.rs:631–714

()

#[test]
fn test_branch_node_split_creates_new_level() {
    let mut tree = BPlusTreeMap::new(4).unwrap();

    // Insert enough items to create a multi-level tree structure
    // This should eventually cause branch node splits
    let mut items_inserted = 0;
    let initial_leaf_count = tree.leaf_count();

    // Insert items until we have a significant tree structure
    // With capacity 4, we need enough items to fill multiple branch nodes
    for i in 1..=25 {
        tree.insert(i, format!("value_{}", i));
        items_inserted += 1;

        // Verify invariants are maintained after each insertion
        assert!(
            tree.check_invariants(),
            "Tree invariants should be maintained after inserting item {}",
            i
        );
    }

    // Verify we have more leaf nodes than we started with
    let final_leaf_count = tree.leaf_count();
    assert!(
        final_leaf_count > initial_leaf_count,
        "Should have more leaf nodes after inserting {} items. Initial: {}, Final: {}",
        items_inserted,
        initial_leaf_count,
        final_leaf_count
    );

    // Verify we have a branch root (not a leaf root)
    assert!(
        !tree.is_leaf_root(),
        "Tree should have a branch root after inserting {} items",
        items_inserted
    );

    // Verify all items are still accessible
    for i in 1..=25 {
        assert_eq!(
            tree.get(&i),
            Some(&format!("value_{}", i)),
            "Item {} should be accessible in multi-level tree",
            i
        );
    }

    // Verify tree structure and size
    assert_eq!(tree.len(), 25, "Tree should have 25 items");

    // Verify range queries work correctly across the complex structure
    let range: Vec<_> = tree.items_range(Some(&1), Some(&26)).collect();
    assert_eq!(range.len(), 25, "Range query should return all 25 items");

    // Verify items are in sorted order
    for i in 0..range.len() - 1 {