B树

B-Trees are version of 2-3 trees, which are self-balancing. They are used to improve Disk reads and have a complexity of O(log(n)), for every tree operations.The number of Childrens/Keys a particular node has, is determined by the Branching Factor/Degree of that tree. B-Trees will always have sorted keys.

  • Branching Factor(B) / Degree (D): If B = n, n <= Children per Node < 2(n), n-1 <= Keys per Node < 2(n) - 1

Properties

  • Worst/Average case performance for all operations O(log n)
  • Space complexity O(n)
  1. use std::convert::TryFrom;
  2. use std::fmt::Debug;
  3. use std::mem;
  5. struct Node<T> {
  6.     keys: Vec<T>,
  7.     children: Vec<Node<T>>,
  8. }
  10. pub struct BTree<T> {
  11.     root: Node<T>,
  12.     props: BTreeProps,
  13. }
  15. // Why to need a different Struct for props...
  16. // Check - http://smallcultfollowing.com/babysteps/blog/2018/11/01/after-nll-interprocedural-conflicts/#fnref:improvement
  17. struct BTreeProps {
  18.     degree: usize,
  19.     max_keys: usize,
  20.     mid_key_index: usize,
  21. }
  23. impl<T> Node<T>
  24. where
  25.     T: Ord,
  26. {
  27.     fn new(degree: usize, _keys: Option<Vec<T>>, _children: Option<Vec<Node<T>>>) -> Self {
  28.         Node {
  29.             keys: match _keys {
  30.                 Some(_keys) => _keys,
  31.                 None => Vec::with_capacity(degree - 1),
  32.             },
  33.             children: match _children {
  34.                 Some(_children) => _children,
  35.                 None => Vec::with_capacity(degree),
  36.             },
  37.         }
  38.     }
  40.     fn is_leaf(&self) -> bool {
  41.         self.children.is_empty()
  42.     }
  43. }
  45. impl BTreeProps {
  46.     fn new(degree: usize) -> Self {
  47.         BTreeProps {
  48.             degree,
  49.             max_keys: degree - 1,
  50.             mid_key_index: (degree - 1) / 2,
  51.         }
  52.     }
  54.     fn is_maxed_out<T: Ord + Copy>(&self, node: &Node<T>) -> bool {
  55.         node.keys.len() == self.max_keys
  56.     }
  58.     // Split Child expects the Child Node to be full
  59.     /// Move the middle_key to parent node and split the child_node's
  60.     /// keys/chilren_nodes into half
  61.     fn split_child<T: Ord + Copy + Default>(&self, parent: &mut Node<T>, child_index: usize) {
  62.         let child = &mut parent.children[child_index];
  63.         let middle_key = child.keys[self.mid_key_index];
  64.         let right_keys = match child.keys.split_off(self.mid_key_index).split_first() {
  65.             Some((_first, _others)) => {
  66.                 // We don't need _first, as it will move to parent node.
  67.                 _others.to_vec()
  68.             }
  69.             None => Vec::with_capacity(self.max_keys),
  70.         };
  71.         let right_children = if !child.is_leaf() {
  72.             Some(child.children.split_off(self.mid_key_index + 1))
  73.         } else {
  74.             None
  75.         };
  76.         let new_child_node: Node<T> = Node::new(self.degree, Some(right_keys), right_children);
  78.         parent.keys.insert(child_index, middle_key);
  79.         parent.children.insert(child_index + 1, new_child_node);
  80.     }
  82.     fn insert_non_full<T: Ord + Copy + Default>(&mut self, node: &mut Node<T>, key: T) {
  83.         let mut index: isize = isize::try_from(node.keys.len()).ok().unwrap() - 1;
  84.         while index >= 0 && node.keys[index as usize] >= key {
  85.             index -= 1;
  86.         }
  88.         let mut u_index: usize = usize::try_from(index + 1).ok().unwrap();
  89.         if node.is_leaf() {
  90.             // Just insert it, as we know this method will be called only when node is not full
  91.             node.keys.insert(u_index, key);
  92.         } else {
  93.             if self.is_maxed_out(&node.children[u_index]) {
  94.                 self.split_child(node, u_index);
  95.                 if node.keys[u_index] < key {
  96.                     u_index += 1;
  97.                 }
  98.             }
  100.             self.insert_non_full(&mut node.children[u_index], key);
  101.         }
  102.     }
  104.     fn traverse_node<T: Ord + Debug>(&self, node: &Node<T>, depth: usize) {
  105.         if node.is_leaf() {
  106.             print!(" {0:{<1$}{2:?}{0:}<1$} ", "", depth, node.keys);
  107.         } else {
  108.             let _depth = depth + 1;
  109.             for (index, key) in node.keys.iter().enumerate() {
  110.                 self.traverse_node(&node.children[index], _depth);
  111.                 // Check https://doc.rust-lang.org/std/fmt/index.html
  112.                 // And https://stackoverflow.com/a/35280799/2849127
  113.                 print!("{0:{<1$}{2:?}{0:}<1$}", "", depth, key);
  114.             }
  115.             self.traverse_node(node.children.last().unwrap(), _depth);
  116.         }
  117.     }
  118. }
  120. impl<T> BTree<T>
  121. where
  122.     T: Ord + Copy + Debug + Default,
  123. {
  124.     pub fn new(branch_factor: usize) -> Self {
  125.         let degree = 2 * branch_factor;
  126.         BTree {
  127.             root: Node::new(degree, None, None),
  128.             props: BTreeProps::new(degree),
  129.         }
  130.     }
  132.     pub fn insert(&mut self, key: T) {
  133.         if self.props.is_maxed_out(&self.root) {
  134.             // Create an empty root and split the old root...
  135.             let mut new_root = Node::new(self.props.degree, None, None);
  136.             mem::swap(&mut new_root, &mut self.root);
  137.             self.root.children.insert(0, new_root);
  138.             self.props.split_child(&mut self.root, 0);
  139.         }
  140.         self.props.insert_non_full(&mut self.root, key);
  141.     }
  143.     pub fn traverse(&self) {
  144.         self.props.traverse_node(&self.root, 0);
  145.         println!();
  146.     }
  148.     pub fn search(&self, key: T) -> bool {
  149.         let mut current_node = &self.root;
  150.         let mut index: isize;
  151.         loop {
  152.             index = isize::try_from(current_node.keys.len()).ok().unwrap() - 1;
  153.             while index >= 0 && current_node.keys[index as usize] > key {
  154.                 index -= 1;
  155.             }
  157.             let u_index: usize = usize::try_from(index + 1).ok().unwrap();
  158.             if index >= 0 && current_node.keys[u_index - 1] == key {
  159.                 break true;
  160.             } else if current_node.is_leaf() {
  161.                 break false;
  162.             } else {
  163.                 current_node = &current_node.children[u_index];
  164.             }
  165.         }
  166.     }
  167. }
  169. #[cfg(test)]
  170. mod test {
  171.     use super::BTree;
  173.     #[test]
  174.     fn test_search() {
  175.         let mut tree = BTree::new(2);
  176.         tree.insert(10);
  177.         tree.insert(20);
  178.         tree.insert(30);
  179.         tree.insert(5);
  180.         tree.insert(6);
  181.         tree.insert(7);
  182.         tree.insert(11);
  183.         tree.insert(12);
  184.         tree.insert(15);
  185.         assert!(tree.search(15));
  186.         assert_eq!(tree.search(16), false);
  187.     }
  188. }