sled 0.15.0

a flash-sympathetic persistent lock-free B+ tree
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

use super::*;

#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
pub struct Node {
    pub id: PageID,
    pub data: Data,
    pub next: Option<PageID>,
    pub lo: Bound,
    pub hi: Bound,
}

impl Node {
    pub fn apply(&mut self, frag: &Frag) {
        use self::Frag::*;

        match *frag {
            Set(ref k, ref v) => {
                if Bound::Inc(k.clone()) < self.hi {
                    self.set_leaf(k.clone(), v.clone());
                } else {
                    panic!("tried to consolidate set at key <= hi")
                }
            }
            ChildSplit(ref child_split) => {
                self.child_split(child_split);
            }
            ParentSplit(ref parent_split) => {
                self.parent_split(parent_split);
            }
            Del(ref k) => {
                if Bound::Inc(k.clone()) < self.hi {
                    self.del_leaf(k);
                } else {
                    panic!("tried to consolidate del at key <= hi")
                }
            }
            Base(_, _) => panic!("encountered base page in middle of chain"),
        }
    }

    pub fn set_leaf(&mut self, key: Key, val: Value) {
        if let Data::Leaf(ref mut records) = self.data {
            let search =
                records.binary_search_by(|&(ref k, ref _v)| (**k).cmp(&*key));
            if let Ok(idx) = search {
                records.push((key, val));
                records.swap_remove(idx);
            } else {
                records.push((key, val));
                records.sort();
            }
        } else {
            panic!("tried to Set a value to an index");
        }
    }

    pub fn child_split(&mut self, cs: &ChildSplit) {
        self.data.drop_gte(&cs.at);
        self.hi = Bound::Non(cs.at.inner().unwrap());
        self.next = Some(cs.to);
    }

    pub fn parent_split(&mut self, ps: &ParentSplit) {
        if let Data::Index(ref mut ptrs) = self.data {
            ptrs.push((ps.at.inner().unwrap(), ps.to));
            ptrs.sort_by(|a, b| a.0.cmp(&b.0));
        } else {
            panic!("tried to attach a ParentSplit to a Leaf chain");
        }
    }

    pub fn del_leaf(&mut self, key: KeyRef) {
        if let Data::Leaf(ref mut records) = self.data {
            let search =
                records.binary_search_by(|&(ref k, ref _v)| (**k).cmp(key));
            if let Ok(idx) = search {
                records.remove(idx);
            }
        } else {
            panic!("tried to attach a Del to an Index chain");
        }
    }

    pub fn should_split(&self, fanout: usize) -> bool {
        self.data.len() > fanout
    }

    pub fn split(&self, id: PageID) -> Node {
        let (split, right_data) = self.data.split();
        Node {
            id: id,
            data: right_data,
            next: self.next,
            lo: Bound::Inc(split),
            hi: self.hi.clone(),
        }
    }
}