fsqlite-btree 0.1.10

B-tree storage engine
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

use std::collections::BTreeSet;

use crate::{BtCursor, BtreeCursorOps, MemPageStore};
use fsqlite_types::PageNumber;
use fsqlite_types::cx::Cx;

fn key_for(i: u32) -> Vec<u8> {
    let mut key = vec![0u8; 100];
    key[0..4].copy_from_slice(&i.to_be_bytes());
    key
}

fn key_prefix_u32(key: &[u8]) -> u32 {
    let mut buf = [0u8; 4];
    buf.copy_from_slice(&key[0..4]);
    u32::from_be_bytes(buf)
}

#[test]
fn test_index_delete_interior() {
    let cx = Cx::new();
    let root = PageNumber::new(2).unwrap();
    // 512 byte pages so it splits quickly
    let store = MemPageStore::with_empty_index(root, 512);
    let mut cursor = BtCursor::new(store, root, 512, false);

    let mut expected = BTreeSet::new();

    // Insert 100 elements to force interior nodes
    for i in 0..100_u32 {
        let key = key_for(i);
        cursor.index_insert(&cx, &key).unwrap();
        expected.insert(i);
    }

    // Delete in ascending order and assert cursor positioning + remaining set.
    for i in 0..100_u32 {
        let key = key_for(i);
        let seek = cursor.index_move_to(&cx, &key).unwrap();
        assert!(seek.is_found());
        cursor.delete(&cx).unwrap();
        assert!(
            expected.remove(&i),
            "deleted key must exist in expected set"
        );

        if let Some(next_expected) = expected.iter().next().copied() {
            assert!(
                !cursor.eof(),
                "cursor should be positioned at successor after delete"
            );
            let next_key = cursor.payload(&cx).unwrap();
            assert_eq!(
                key_prefix_u32(&next_key),
                next_expected,
                "cursor should point at immediate successor",
            );
        } else {
            assert!(cursor.eof(), "cursor should be EOF after final delete");
        }
    }

    // Final full scan: tree must be empty.
    assert!(
        !cursor.first(&cx).unwrap(),
        "first() on empty tree should be false"
    );
    assert!(cursor.eof(), "cursor must remain at EOF for empty tree");
}

#[test]
fn test_index_delete_interior_needs_rebalance() {
    let cx = Cx::new();
    let root = PageNumber::new(2).unwrap();
    // 512 byte pages so it splits quickly
    let store = MemPageStore::with_empty_index(root, 512);
    let mut cursor = BtCursor::new(store, root, 512, false);

    // Let's explicitly construct the case.
    // Insert 10 (size 10), 20 (size 10), 30 (size 10)
    // 40 (size 10), 50 (size 10), 60 (size 10).
    // Let's just insert 0..100 with alternating sizes!
    // If i == 20, size = 10 (interior maybe?)
    // If i == 21, size = 200 (successor)
    for i in 0..100_u32 {
        let mut key = vec![0u8; if i % 2 == 0 { 10 } else { 200 }];
        key[0..4].copy_from_slice(&i.to_be_bytes());
        cursor.index_insert(&cx, &key).unwrap();
    }

    // Now delete everything!
    for i in 0..100_u32 {
        let mut key = vec![0u8; if i % 2 == 0 { 10 } else { 200 }];
        key[0..4].copy_from_slice(&i.to_be_bytes());
        if cursor.index_move_to(&cx, &key).unwrap().is_found() {
            cursor.delete(&cx).unwrap();
        }
    }
}