btree/
btree.rs

1use crate::error::Error;
2use crate::node::Node;
3use crate::node_type::{Key, KeyValuePair, NodeType, Offset};
4use crate::page::Page;
5use crate::pager::Pager;
6use crate::wal::Wal;
7use std::cmp;
8use std::convert::TryFrom;
9use std::path::Path;
10
11/// B+Tree properties.
12pub const MAX_BRANCHING_FACTOR: usize = 200;
13pub const NODE_KEYS_LIMIT: usize = MAX_BRANCHING_FACTOR - 1;
14
15/// BTree struct represents an on-disk B+tree.
16/// Each node is persisted in the table file, the leaf nodes contain the values.
17pub struct BTree {
18    pager: Pager,
19    b: usize,
20    wal: Wal,
21}
22
23/// BtreeBuilder is a Builder for the BTree struct.
24pub struct BTreeBuilder {
25    /// Path to the tree file.
26    path: &'static Path,
27    /// The BTree parameter, an inner node contains no more than 2*b-1 keys and no less than b-1 keys
28    /// and no more than 2*b children and no less than b children.
29    b: usize,
30}
31
32impl BTreeBuilder {
33    pub fn new() -> BTreeBuilder {
34        BTreeBuilder {
35            path: Path::new(""),
36            b: 0,
37        }
38    }
39
40    pub fn path(mut self, path: &'static Path) -> BTreeBuilder {
41        self.path = path;
42        self
43    }
44
45    pub fn b_parameter(mut self, b: usize) -> BTreeBuilder {
46        self.b = b;
47        self
48    }
49
50    pub fn build(&self) -> Result<BTree, Error> {
51        if self.path.to_string_lossy() == "" {
52            return Err(Error::UnexpectedError);
53        }
54        if self.b == 0 {
55            return Err(Error::UnexpectedError);
56        }
57
58        let mut pager = Pager::new(self.path)?;
59        let root = Node::new(NodeType::Leaf(vec![]), true, None);
60        let root_offset = pager.write_page(Page::try_from(&root)?)?;
61        let parent_directory = self.path.parent().unwrap_or_else(|| Path::new("/tmp"));
62        let mut wal = Wal::new(parent_directory.to_path_buf())?;
63        wal.set_root(root_offset)?;
64
65        Ok(BTree {
66            pager,
67            b: self.b,
68            wal,
69        })
70    }
71}
72
73impl Default for BTreeBuilder {
74    // A default BTreeBuilder provides a builder with:
75    // - b parameter set to 200
76    // - path set to '/tmp/db'.
77    fn default() -> Self {
78        BTreeBuilder::new()
79            .b_parameter(200)
80            .path(Path::new("/tmp/db"))
81    }
82}
83
84impl BTree {
85    fn is_node_full(&self, node: &Node) -> Result<bool, Error> {
86        match &node.node_type {
87            NodeType::Leaf(pairs) => Ok(pairs.len() == (2 * self.b)),
88            NodeType::Internal(_, keys) => Ok(keys.len() == (2 * self.b - 1)),
89            NodeType::Unexpected => Err(Error::UnexpectedError),
90        }
91    }
92
93    fn is_node_underflow(&self, node: &Node) -> Result<bool, Error> {
94        match &node.node_type {
95            // A root cannot really be "underflowing" as it can contain less than b-1 keys / pointers.
96            NodeType::Leaf(pairs) => Ok(pairs.len() < (self.b - 1) && !node.is_root),
97            NodeType::Internal(_, keys) => Ok(keys.len() < (self.b - 1) && !node.is_root),
98            NodeType::Unexpected => Err(Error::UnexpectedError),
99        }
100    }
101
102    /// insert a key value pair possibly splitting nodes along the way.
103    pub fn insert(&mut self, kv: KeyValuePair) -> Result<(), Error> {
104        let root_offset = self.wal.get_root()?;
105        let root_page = self.pager.get_page(&root_offset)?;
106        let new_root_offset: Offset;
107        let mut new_root: Node;
108        let mut root = Node::try_from(root_page)?;
109        if self.is_node_full(&root)? {
110            // split the root creating a new root and child nodes along the way.
111            new_root = Node::new(NodeType::Internal(vec![], vec![]), true, None);
112            // write the new root to disk to aquire an offset for the new root.
113            new_root_offset = self.pager.write_page(Page::try_from(&new_root)?)?;
114            // set the old roots parent to the new root.
115            root.parent_offset = Some(new_root_offset.clone());
116            root.is_root = false;
117            // split the old root.
118            let (median, sibling) = root.split(self.b)?;
119            // write the old root with its new data to disk in a *new* location.
120            let old_root_offset = self.pager.write_page(Page::try_from(&root)?)?;
121            // write the newly created sibling to disk.
122            let sibling_offset = self.pager.write_page(Page::try_from(&sibling)?)?;
123            // update the new root with its children and key.
124            new_root.node_type =
125                NodeType::Internal(vec![old_root_offset, sibling_offset], vec![median]);
126            // write the new_root to disk.
127            self.pager
128                .write_page_at_offset(Page::try_from(&new_root)?, &new_root_offset)?;
129        } else {
130            new_root = root.clone();
131            new_root_offset = self.pager.write_page(Page::try_from(&new_root)?)?;
132        }
133        // continue recursively.
134        self.insert_non_full(&mut new_root, new_root_offset.clone(), kv)?;
135        // finish by setting the root to its new copy.
136        self.wal.set_root(new_root_offset)
137    }
138
139    /// insert_non_full (recursively) finds a node rooted at a given non-full node.
140    /// to insert a given key-value pair. Here we assume the node is
141    /// already a copy of an existing node in a copy-on-write root to node traversal.
142    fn insert_non_full(
143        &mut self,
144        node: &mut Node,
145        node_offset: Offset,
146        kv: KeyValuePair,
147    ) -> Result<(), Error> {
148        match &mut node.node_type {
149            NodeType::Leaf(ref mut pairs) => {
150                let idx = pairs.binary_search(&kv).unwrap_or_else(|x| x);
151                pairs.insert(idx, kv);
152                self.pager
153                    .write_page_at_offset(Page::try_from(&*node)?, &node_offset)
154            }
155            NodeType::Internal(ref mut children, ref mut keys) => {
156                let idx = keys
157                    .binary_search(&Key(kv.key.clone()))
158                    .unwrap_or_else(|x| x);
159                let child_offset = children.get(idx).ok_or(Error::UnexpectedError)?.clone();
160                let child_page = self.pager.get_page(&child_offset)?;
161                let mut child = Node::try_from(child_page)?;
162                // Copy each branching-node on the root-to-leaf walk.
163                // write_page appends the given page to the db file thus creating a new node.
164                let new_child_offset = self.pager.write_page(Page::try_from(&child)?)?;
165                // Assign copied child at the proper place.
166                children[idx] = new_child_offset.to_owned();
167                if self.is_node_full(&child)? {
168                    // split will split the child at b leaving the [0, b-1] keys
169                    // while moving the set of [b, 2b-1] keys to the sibling.
170                    let (median, mut sibling) = child.split(self.b)?;
171                    self.pager
172                        .write_page_at_offset(Page::try_from(&child)?, &new_child_offset)?;
173                    // Write the newly created sibling to disk.
174                    let sibling_offset = self.pager.write_page(Page::try_from(&sibling)?)?;
175                    // Siblings keys are larger than the splitted child thus need to be inserted
176                    // at the next index.
177                    children.insert(idx + 1, sibling_offset.clone());
178                    keys.insert(idx, median.clone());
179
180                    // Write the parent page to disk.
181                    self.pager
182                        .write_page_at_offset(Page::try_from(&*node)?, &node_offset)?;
183                    // Continue recursively.
184                    if kv.key <= median.0 {
185                        self.insert_non_full(&mut child, new_child_offset, kv)
186                    } else {
187                        self.insert_non_full(&mut sibling, sibling_offset, kv)
188                    }
189                } else {
190                    self.pager
191                        .write_page_at_offset(Page::try_from(&*node)?, &node_offset)?;
192                    self.insert_non_full(&mut child, new_child_offset, kv)
193                }
194            }
195            NodeType::Unexpected => Err(Error::UnexpectedError),
196        }
197    }
198
199    /// search searches for a specific key in the BTree.
200    pub fn search(&mut self, key: String) -> Result<KeyValuePair, Error> {
201        let root_offset = self.wal.get_root()?;
202        let root_page = self.pager.get_page(&root_offset)?;
203        let root = Node::try_from(root_page)?;
204        self.search_node(root, &key)
205    }
206
207    /// search_node recursively searches a sub tree rooted at node for a key.
208    fn search_node(&mut self, node: Node, search: &str) -> Result<KeyValuePair, Error> {
209        match node.node_type {
210            NodeType::Internal(children, keys) => {
211                let idx = keys
212                    .binary_search(&Key(search.to_string()))
213                    .unwrap_or_else(|x| x);
214                // Retrieve child page from disk and deserialize.
215                let child_offset = children.get(idx).ok_or(Error::UnexpectedError)?;
216                let page = self.pager.get_page(child_offset)?;
217                let child_node = Node::try_from(page)?;
218                self.search_node(child_node, search)
219            }
220            NodeType::Leaf(pairs) => {
221                if let Ok(idx) =
222                    pairs.binary_search_by_key(&search.to_string(), |pair| pair.key.clone())
223                {
224                    return Ok(pairs[idx].clone());
225                }
226                Err(Error::KeyNotFound)
227            }
228            NodeType::Unexpected => Err(Error::UnexpectedError),
229        }
230    }
231
232    /// delete deletes a given key from the tree.
233    pub fn delete(&mut self, key: Key) -> Result<(), Error> {
234        let root_offset = self.wal.get_root()?;
235        let root_page = self.pager.get_page(&root_offset)?;
236        // Shadow the new root and rewrite it.
237        let mut new_root = Node::try_from(root_page)?;
238        let new_root_page = Page::try_from(&new_root)?;
239        let new_root_offset = self.pager.write_page(new_root_page)?;
240        self.delete_key_from_subtree(key, &mut new_root, &new_root_offset)?;
241        self.wal.set_root(new_root_offset)
242    }
243
244    /// delete key from subtree recursively traverses a tree rooted at a node in certain offset
245    /// until it finds the given key and delete the key-value pair. Here we assume the node is
246    /// already a copy of an existing node in a copy-on-write root to node traversal.
247    fn delete_key_from_subtree(
248        &mut self,
249        key: Key,
250        node: &mut Node,
251        node_offset: &Offset,
252    ) -> Result<(), Error> {
253        match &mut node.node_type {
254            NodeType::Leaf(ref mut pairs) => {
255                let key_idx = pairs
256                    .binary_search_by_key(&key, |kv| Key(kv.key.clone()))
257                    .map_err(|_| Error::KeyNotFound)?;
258                pairs.remove(key_idx);
259                self.pager
260                    .write_page_at_offset(Page::try_from(&*node)?, node_offset)?;
261                // Check for underflow - if it occures,
262                // we need to merge with a sibling.
263                // this can only occur if node is not the root (as it cannot "underflow").
264                // continue recoursively up the tree.
265                self.borrow_if_needed(node.to_owned(), &key)?;
266            }
267            NodeType::Internal(children, keys) => {
268                let node_idx = keys.binary_search(&key).unwrap_or_else(|x| x);
269                // Retrieve child page from disk and deserialize,
270                // copy over the child page and continue recursively.
271                let child_offset = children.get(node_idx).ok_or(Error::UnexpectedError)?;
272                let child_page = self.pager.get_page(child_offset)?;
273                let mut child_node = Node::try_from(child_page)?;
274                // Fix the parent_offset as the child node is a child of a copied parent
275                // in a copy-on-write root to leaf traversal.
276                // This is important for the case of a node underflow which might require a leaf to root traversal.
277                child_node.parent_offset = Some(node_offset.to_owned());
278                let new_child_page = Page::try_from(&child_node)?;
279                let new_child_offset = self.pager.write_page(new_child_page)?;
280                // Assign the new pointer in the parent and continue reccoursively.
281                children[node_idx] = new_child_offset.to_owned();
282                self.pager
283                    .write_page_at_offset(Page::try_from(&*node)?, node_offset)?;
284                return self.delete_key_from_subtree(key, &mut child_node, &new_child_offset);
285            }
286            NodeType::Unexpected => return Err(Error::UnexpectedError),
287        }
288        Ok(())
289    }
290
291    /// borrow_if_needed checks the node for underflow (following a removal of a key),
292    /// if it underflows it is merged with a sibling node, and than called recoursively
293    /// up the tree. Since the downward root-to-leaf traversal was done using the copy-on-write
294    /// technique we are ensured that any merges will only be reflected in the copied parent in the path.
295    fn borrow_if_needed(&mut self, node: Node, key: &Key) -> Result<(), Error> {
296        if self.is_node_underflow(&node)? {
297            // Fetch the sibling from the parent -
298            // TODO: This could be quicker if we implement sibling pointers.
299            let parent_offset = node.parent_offset.clone().ok_or(Error::UnexpectedError)?;
300            let parent_page = self.pager.get_page(&parent_offset)?;
301            let mut parent_node = Node::try_from(parent_page)?;
302            // The parent has to be an "internal" node.
303            match parent_node.node_type {
304                NodeType::Internal(ref mut children, ref mut keys) => {
305                    let idx = keys.binary_search(key).unwrap_or_else(|x| x);
306                    // The sibling is in idx +- 1 as the above index led
307                    // the downward search to node.
308                    let sibling_idx;
309                    match idx > 0 {
310                        false => sibling_idx = idx + 1,
311                        true => sibling_idx = idx - 1,
312                    }
313
314                    let sibling_offset = children.get(sibling_idx).ok_or(Error::UnexpectedError)?;
315                    let sibling_page = self.pager.get_page(sibling_offset)?;
316                    let sibling = Node::try_from(sibling_page)?;
317                    let merged_node = self.merge(node, sibling)?;
318                    let merged_node_offset =
319                        self.pager.write_page(Page::try_from(&merged_node)?)?;
320                    let merged_node_idx = cmp::min(idx, sibling_idx);
321                    // remove the old nodes.
322                    children.remove(merged_node_idx);
323                    // remove shifts nodes to the left.
324                    children.remove(merged_node_idx);
325                    // if the parent is the root, and there is a single child - the merged node -
326                    // we can safely replace the root with the child.
327                    if parent_node.is_root && children.is_empty() {
328                        self.wal.set_root(merged_node_offset)?;
329                        return Ok(());
330                    }
331                    // remove the keys that separated the two nodes from each other:
332                    keys.remove(idx);
333                    // write the new node in place.
334                    children.insert(merged_node_idx, merged_node_offset);
335                    // write the updated parent back to disk and continue up the tree.
336                    self.pager
337                        .write_page_at_offset(Page::try_from(&parent_node)?, &parent_offset)?;
338                    return self.borrow_if_needed(parent_node, key);
339                }
340                _ => return Err(Error::UnexpectedError),
341            }
342        }
343        Ok(())
344    }
345
346    // merges two *sibling* nodes, it assumes the following:
347    // 1. the two nodes are of the same type.
348    // 2. the two nodes do not accumulate to an overflow,
349    // i.e. |first.keys| + |second.keys| <= [2*(b-1) for keys or 2*b for offsets].
350    fn merge(&self, first: Node, second: Node) -> Result<Node, Error> {
351        match first.node_type {
352            NodeType::Leaf(first_pairs) => {
353                if let NodeType::Leaf(second_pairs) = second.node_type {
354                    let merged_pairs: Vec<KeyValuePair> = first_pairs
355                        .into_iter()
356                        .chain(second_pairs.into_iter())
357                        .collect();
358                    let node_type = NodeType::Leaf(merged_pairs);
359                    Ok(Node::new(node_type, first.is_root, first.parent_offset))
360                } else {
361                    Err(Error::UnexpectedError)
362                }
363            }
364            NodeType::Internal(first_offsets, first_keys) => {
365                if let NodeType::Internal(second_offsets, second_keys) = second.node_type {
366                    let merged_keys: Vec<Key> = first_keys
367                        .into_iter()
368                        .chain(second_keys.into_iter())
369                        .collect();
370                    let merged_offsets: Vec<Offset> = first_offsets
371                        .into_iter()
372                        .chain(second_offsets.into_iter())
373                        .collect();
374                    let node_type = NodeType::Internal(merged_offsets, merged_keys);
375                    Ok(Node::new(node_type, first.is_root, first.parent_offset))
376                } else {
377                    Err(Error::UnexpectedError)
378                }
379            }
380            NodeType::Unexpected => Err(Error::UnexpectedError),
381        }
382    }
383
384    /// print_sub_tree is a helper function for recursively printing the nodes rooted at a node given by its offset.
385    fn print_sub_tree(&mut self, prefix: String, offset: Offset) -> Result<(), Error> {
386        println!("{}Node at offset: {}", prefix, offset.0);
387        let curr_prefix = format!("{}|->", prefix);
388        let page = self.pager.get_page(&offset)?;
389        let node = Node::try_from(page)?;
390        match node.node_type {
391            NodeType::Internal(children, keys) => {
392                println!("{}Keys: {:?}", curr_prefix, keys);
393                println!("{}Children: {:?}", curr_prefix, children);
394                let child_prefix = format!("{}   |  ", prefix);
395                for child_offset in children {
396                    self.print_sub_tree(child_prefix.clone(), child_offset)?;
397                }
398                Ok(())
399            }
400            NodeType::Leaf(pairs) => {
401                println!("{}Key value pairs: {:?}", curr_prefix, pairs);
402                Ok(())
403            }
404            NodeType::Unexpected => Err(Error::UnexpectedError),
405        }
406    }
407
408    /// print is a helper for recursively printing the tree.
409    pub fn print(&mut self) -> Result<(), Error> {
410        println!();
411        let root_offset = self.wal.get_root()?;
412        self.print_sub_tree("".to_string(), root_offset)
413    }
414}
415
416#[cfg(test)]
417mod tests {
418    use crate::error::Error;
419
420    #[test]
421    fn search_works() -> Result<(), Error> {
422        use crate::btree::BTreeBuilder;
423        use crate::node_type::KeyValuePair;
424        use std::path::Path;
425
426        let mut btree = BTreeBuilder::new()
427            .path(Path::new("/tmp/db"))
428            .b_parameter(2)
429            .build()?;
430        btree.insert(KeyValuePair::new("a".to_string(), "shalom".to_string()))?;
431        btree.insert(KeyValuePair::new("b".to_string(), "hello".to_string()))?;
432        btree.insert(KeyValuePair::new("c".to_string(), "marhaba".to_string()))?;
433
434        let mut kv = btree.search("b".to_string())?;
435        assert_eq!(kv.key, "b");
436        assert_eq!(kv.value, "hello");
437
438        kv = btree.search("c".to_string())?;
439        assert_eq!(kv.key, "c");
440        assert_eq!(kv.value, "marhaba");
441
442        Ok(())
443    }
444
445    #[test]
446    fn insert_works() -> Result<(), Error> {
447        use crate::btree::BTreeBuilder;
448        use crate::node_type::KeyValuePair;
449        use std::path::Path;
450
451        let mut btree = BTreeBuilder::new()
452            .path(Path::new("/tmp/db"))
453            .b_parameter(2)
454            .build()?;
455        btree.insert(KeyValuePair::new("a".to_string(), "shalom".to_string()))?;
456        btree.insert(KeyValuePair::new("b".to_string(), "hello".to_string()))?;
457        btree.insert(KeyValuePair::new("c".to_string(), "marhaba".to_string()))?;
458        btree.insert(KeyValuePair::new("d".to_string(), "olah".to_string()))?;
459        btree.insert(KeyValuePair::new("e".to_string(), "salam".to_string()))?;
460        btree.insert(KeyValuePair::new("f".to_string(), "hallo".to_string()))?;
461        btree.insert(KeyValuePair::new("g".to_string(), "Konnichiwa".to_string()))?;
462        btree.insert(KeyValuePair::new("h".to_string(), "Ni hao".to_string()))?;
463        btree.insert(KeyValuePair::new("i".to_string(), "Ciao".to_string()))?;
464
465        let mut kv = btree.search("a".to_string())?;
466        assert_eq!(kv.key, "a");
467        assert_eq!(kv.value, "shalom");
468
469        kv = btree.search("b".to_string())?;
470        assert_eq!(kv.key, "b");
471        assert_eq!(kv.value, "hello");
472
473        kv = btree.search("c".to_string())?;
474        assert_eq!(kv.key, "c");
475        assert_eq!(kv.value, "marhaba");
476
477        kv = btree.search("d".to_string())?;
478        assert_eq!(kv.key, "d");
479        assert_eq!(kv.value, "olah");
480
481        kv = btree.search("e".to_string())?;
482        assert_eq!(kv.key, "e");
483        assert_eq!(kv.value, "salam");
484
485        kv = btree.search("f".to_string())?;
486        assert_eq!(kv.key, "f");
487        assert_eq!(kv.value, "hallo");
488
489        kv = btree.search("g".to_string())?;
490        assert_eq!(kv.key, "g");
491        assert_eq!(kv.value, "Konnichiwa");
492
493        kv = btree.search("h".to_string())?;
494        assert_eq!(kv.key, "h");
495        assert_eq!(kv.value, "Ni hao");
496
497        kv = btree.search("i".to_string())?;
498        assert_eq!(kv.key, "i");
499        assert_eq!(kv.value, "Ciao");
500        Ok(())
501    }
502
503    #[test]
504    fn delete_works() -> Result<(), Error> {
505        use crate::btree::BTreeBuilder;
506        use crate::error::Error;
507        use crate::node_type::{Key, KeyValuePair};
508        use std::path::Path;
509
510        let mut btree = BTreeBuilder::new()
511            .path(Path::new("/tmp/db"))
512            .b_parameter(2)
513            .build()?;
514        btree.insert(KeyValuePair::new("d".to_string(), "olah".to_string()))?;
515        btree.insert(KeyValuePair::new("e".to_string(), "salam".to_string()))?;
516        btree.insert(KeyValuePair::new("f".to_string(), "hallo".to_string()))?;
517        btree.insert(KeyValuePair::new("a".to_string(), "shalom".to_string()))?;
518        btree.insert(KeyValuePair::new("b".to_string(), "hello".to_string()))?;
519        btree.insert(KeyValuePair::new("c".to_string(), "marhaba".to_string()))?;
520
521        let mut kv = btree.search("c".to_string())?;
522        assert_eq!(kv.key, "c");
523        assert_eq!(kv.value, "marhaba");
524
525        btree.delete(Key("c".to_string()))?;
526        let mut res = btree.search("c".to_string());
527        assert!(matches!(res, Err(Error::KeyNotFound)));
528
529        kv = btree.search("d".to_string())?;
530        assert_eq!(kv.key, "d");
531        assert_eq!(kv.value, "olah");
532
533        btree.delete(Key("d".to_string()))?;
534        res = btree.search("d".to_string());
535        assert!(matches!(res, Err(Error::KeyNotFound)));
536
537        btree.delete(Key("e".to_string()))?;
538        res = btree.search("e".to_string());
539        assert!(matches!(res, Err(Error::KeyNotFound)));
540
541        btree.delete(Key("f".to_string()))?;
542        res = btree.search("f".to_string());
543        assert!(matches!(res, Err(Error::KeyNotFound)));
544
545        Ok(())
546    }
547
548    #[test]
549    fn delete_with_empty_sub_tree() -> Result<(), Error> {
550        use crate::btree::BTreeBuilder;
551        use crate::node_type::{Key, KeyValuePair};
552        use std::path::Path;
553
554        let mut btree = BTreeBuilder::new()
555            .path(Path::new("/tmp/db"))
556            .b_parameter(2)
557            .build()?;
558        btree.insert(KeyValuePair::new("a".to_string(), "shalom".to_string()))?;
559        btree.insert(KeyValuePair::new("b".to_string(), "hello".to_string()))?;
560        btree.insert(KeyValuePair::new("c".to_string(), "marhaba".to_string()))?;
561        btree.insert(KeyValuePair::new("d".to_string(), "olah".to_string()))?;
562        btree.insert(KeyValuePair::new("e".to_string(), "salam".to_string()))?;
563        btree.insert(KeyValuePair::new("f".to_string(), "hallo".to_string()))?;
564        btree.insert(KeyValuePair::new("g".to_string(), "Konnichiwa".to_string()))?;
565        btree.insert(KeyValuePair::new("h".to_string(), "Ni hao".to_string()))?;
566        btree.insert(KeyValuePair::new("i".to_string(), "Ciao".to_string()))?;
567
568        btree.delete(Key("g".to_string()))?;
569        let mut res = btree.search("g".to_string());
570        assert!(matches!(res, Err(Error::KeyNotFound)));
571
572        btree.delete(Key("h".to_string()))?;
573        res = btree.search("h".to_string());
574        assert!(matches!(res, Err(Error::KeyNotFound)));
575
576        btree.delete(Key("a".to_string()))?;
577        res = btree.search("a".to_string());
578        assert!(matches!(res, Err(Error::KeyNotFound)));
579        
580        btree.delete(Key("b".to_string()))?;
581        res = btree.search("b".to_string());
582        assert!(matches!(res, Err(Error::KeyNotFound)));
583        
584        btree.delete(Key("c".to_string()))?;
585        res = btree.search("c".to_string());
586        assert!(matches!(res, Err(Error::KeyNotFound)));
587
588        btree.delete(Key("d".to_string()))?;
589        res = btree.search("d".to_string());
590        assert!(matches!(res, Err(Error::KeyNotFound)));
591
592        btree.delete(Key("e".to_string()))?;
593        res = btree.search("e".to_string());
594        assert!(matches!(res, Err(Error::KeyNotFound)));
595        Ok(())
596    }
597}
btree/btree.rs

btree/
btree.rs
