Rust implementation of a BTree

I'm studying rust, and I decided to implement a BTree as a way of learning the language.

Can anyone give me suggestions on the code?

As the language has no inheritance, and we must replace it with delegation, I believe I am a little lost in the concepts of an object-oriented language.

My concerns

1. Best Practices

I believe that my code has many changes to be made so that it meets the conditions of good practice in the Rust language.

It's worth mentioning that I started with the book Rust by example.

2. Performance

One thing I noticed was that my implementation is at least 2.1x slower than the official one in std::collections

The code

btree/mod.rs

use std::{borrow::Borrow, cell::RefCell, cmp::Ordering, ops::{Deref, DerefMut}, rc::{Rc, Weak}};

mod non_concurrent;
mod tests;

pub enum TreeOrder {
  InOrder
}

pub struct VisitTree<'a, K: PartialOrd, V> {
  order: TreeOrder,
  cb: Box<dyn Fn(&Item<K, V>) + 'a>
}

impl<'a, K: PartialOrd, V> VisitTree<'a, K, V> {
  fn new(order: TreeOrder, cb: impl Fn(&Item<K, V>) + 'a) -> VisitTree<'a, K, V> {
    VisitTree {
      order,
      cb: Box::new(cb)
    }
  }
}

pub trait Tree<K: PartialOrd, V> {
  fn insert(&mut self, key: K, value: V) -> bool;

  fn get_degree(&self) -> i32;

  fn visit(&self, visit: VisitTree<K, V>);
}

trait TreeCreable<'a, K: PartialOrd, V>: Tree<K, V> {
  fn new(degree: i32) -> impl Tree<K, V> + 'a;

  fn init_internal(&mut self, internal: Weak<RefCell<dyn Tree<K, V>>>);
}

type DefaultTree<K, V> = non_concurrent::Tree<K, V>;

pub struct Item<K, V> {
  key: K,
  value: V
}

impl<K: PartialOrd, V> Ord for Item<K, V> {
  fn cmp(&self, other: &Self) -> Ordering {
    self.key.partial_cmp(&other.key).unwrap()
  }
}

impl<K: PartialOrd, V> PartialOrd for Item<K, V> {
  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    Some(self.cmp(other))
  }
}

impl<K: PartialOrd, V> PartialEq for Item<K, V> {
  fn eq(&self, other: &Self) -> bool {
    self.key == other.key
  }
}

impl<K: PartialOrd, V> Eq for Item<K, V> {}

pub struct BTree<'a, K, V> {
  internal: Rc<RefCell<dyn Tree<K, V> + 'a>>
}

pub enum TreeType {
  Default,
  NonConcurrent
}

impl <'a, K: PartialOrd, V> BTree<'a, K, V> where K: 'a, V: 'a {
  fn intl_create<A: TreeCreable<'a, K, V>>(degree: i32) -> BTree<'a, K, V> {
    let internal = 
      Rc::new(
        RefCell::new(
          A::new(degree)
        )
      );

    let weak = Rc::downgrade(&internal);

    let raw = weak.into_raw() as *const RefCell<dyn Tree<K, V>>;

    let weak = unsafe { Weak::from_raw(raw) };

    let new_raw = raw as *const RefCell<A>;

    let new_weak = unsafe { Weak::from_raw(new_raw) };

    let rc = new_weak
      .borrow()
      .upgrade()
      .unwrap();

    let mut item = rc
      .as_ref()
      .borrow_mut();
    
    item.init_internal(weak);

    BTree {
      internal
    }
  }

  pub fn new(tree_type: TreeType, degree: i32) -> BTree<'a, K, V> {
    use TreeType::*;

    match tree_type {
      Default => {
        BTree::<K, V>::intl_create::<DefaultTree<K, V>>(degree)
      },

      NonConcurrent => {
        BTree::<K, V>::intl_create::<non_concurrent::Tree<K, V>>(degree)
      }
    }
  }
}

impl <'a, K, V>  Deref for BTree<'a, K, V> where 'a: 'static {
  type Target = dyn Tree<K, V>;
  
  fn deref(&self) -> &Self::Target {
    unsafe { &*self.internal.as_ptr() }
  }
}

impl <'a, K, V> DerefMut for BTree<'a, K, V> where 'a: 'static {
  fn deref_mut(&mut self) -> &mut Self::Target {
    unsafe { &mut *self.internal.as_ptr() }
  }
}

btree/non_concurrent.rs

use std::{cell::{Ref, RefCell, RefMut}, rc::{Rc, Weak}};

use super::{Item, TreeCreable, VisitTree};

type TreeItem<K, V> = Weak<RefCell<dyn super::Tree<K, V>>>;

type NodeOption<K, V> = Option<Rc<RefCell<Node<K, V>>>>;

type HasNodeOption<K, V> = Rc<RefCell<Node<K, V>>>;

type NodeOptionVisit<'a, K, V> = Option<&'a Rc<RefCell<Node<K, V>>>>;

type NodeValue<K, V> = Rc<Item<K, V>>;

struct Node<K, V> {
  values: Vec<NodeValue<K, V>>,
  childs: Vec<HasNodeOption<K, V>>,
  parent: NodeOption<K, V>,
  tree: TreeItem<K, V>
}

impl <K: PartialOrd, V> Node<K, V> {
  fn new(tree: TreeItem<K, V>, parent: NodeOption<K, V>) -> Node<K, V> {
    let degree = tree
      .upgrade()
      .unwrap()
      .as_ref()
      .borrow()
      .get_degree();

    let u_degree: usize = degree
      .try_into()
      .unwrap();

    Node::<K, V> {
      values: Vec::with_capacity(u_degree),
      childs: Vec::with_capacity(u_degree),
      parent,
      tree
    }
  }
  
  fn contains_key(&self, key: &K) -> bool {
    self
      .values
      .iter()
      .find(|item| {
        item.key == *key
      })
      .is_some()
  }
}

fn new_node_item<K: PartialOrd, V>(tree: Weak<RefCell<dyn super::Tree<K, V>>>, parent: NodeOption<K, V>) -> NodeOption<K, V> {
  Some(
    Rc::new(
      RefCell::new(
        Node::<K, V>::new(
          tree, 
          parent
        )
      )
    )
  )
}

fn temp_internal<K: PartialOrd, V>() -> Weak<RefCell<dyn super::Tree<K, V>>> {
  let weak = Weak::<RefCell<Tree<K, V>>>::new();

  let raw = weak.into_raw() as *const RefCell<dyn super::Tree<K, V>>;

  unsafe { Weak::from_raw(raw) }
}

pub struct Tree<K, V> {
  head: NodeOption<K, V>,
  degree: i32,
  internal: Weak<RefCell<dyn super::Tree<K, V>>>
}

impl <'a, K: PartialOrd, V> TreeCreable<'a, K, V> for Tree<K, V> where K: 'a, V: 'a {
  fn new(degree: i32) -> impl super::Tree<K, V> + 'a {
    Tree {
      degree,
      head: None,
      internal: temp_internal()
    }
  }
  
  fn init_internal(&mut self, internal: Weak<RefCell<dyn super::Tree<K, V>>>) {
    self.internal = internal;
  }
}

impl <K: PartialOrd, V> Tree<K, V> {
  fn node_option_as_mut(node_item: &NodeOption<K, V>) -> RefMut<Node<K, V>> {
    node_item.as_deref().unwrap().borrow_mut()
  }

  fn node_option_as(node_item: &NodeOption<K, V>) -> Ref<Node<K, V>> {
    node_item.as_deref().unwrap().borrow()
  }

  fn create_lesser_bigger(node: &Node<K, V>) -> (NodeOption<K, V>, NodeOption<K, V>) {
    let binding = node.tree
      .upgrade()
      .unwrap();

    let tree = binding
      .as_ref()
      .borrow();

    let degree = tree.get_degree();

    let u_degree: usize = degree
      .try_into()
      .unwrap();

    let median_key = (u_degree-1) / 2;
      
    let lessers = node
      .values
      .iter()
      .take(median_key);

    let mut lessers_node = Node::<K, V>::new(
      node.tree.clone(),
      node.parent.clone()
    );

    for item in lessers
    {
      lessers_node.values.push(item.clone());
    }

    let lessers_node_opt = Some(Rc::new(RefCell::new(lessers_node)));

    let biggers = node
      .values
      .iter()
      .skip(median_key + 1);

    let mut biggers_node = Node::<K, V>::new(
      node.tree.clone(),
      node.parent.clone()
    );

    for item in biggers
    {
      biggers_node.values.push(item.clone());
    }

    let biggers_node_opt = Some(Rc::new(RefCell::new(biggers_node)));

    (lessers_node_opt, biggers_node_opt)
  }

  fn split(&mut self, node_item: &NodeOption<K, V>){
    let mut node = node_item.as_deref().unwrap().borrow_mut();

    let degree = self.degree;

    let u_degree: usize = degree
      .try_into()
      .unwrap();

    let mut new_head = false;

    if node.parent.is_none() {
      node.parent = new_node_item(node.tree.clone(), None);
      
      new_head = true;
    }
    
    let (lessers_node_opt, biggers_node_opt) = Self::create_lesser_bigger(&*node);

    let median_key = (u_degree-1) / 2;

    let median = node.values[median_key].clone();

    let parent_opt = &node.parent;

    let node_ptr = &*node as *const Node<K, V>;

    let lessers_node_len = Self::node_option_as(&lessers_node_opt).values.len();

    for i in 0..node.childs.len() {
      let mut child = node.childs[i].borrow_mut();

      let mut target_node_opt = if i <= lessers_node_len {
        child.parent = lessers_node_opt.clone();

        Self::node_option_as_mut(&lessers_node_opt)
      } else {
        child.parent = biggers_node_opt.clone();

        Self::node_option_as_mut(&biggers_node_opt)
      };

      target_node_opt.childs.push(node.childs[i].clone())
    }

    let parent_childs_len;

    {
      let mut parent = Self::node_option_as_mut(parent_opt);
      parent.values.push(median);
      parent_childs_len = parent.childs.len();
    }

    let mut new_childs = Vec::<HasNodeOption<K, V>>::with_capacity(parent_childs_len + 2); 

    if !new_head {
      let parent = Self::node_option_as(parent_opt);

      for i in 0..parent.childs.len() {
        let child = &parent.childs[i];

        let child_ptr = child.as_ref().as_ptr() as *const Node<K, V>;

        if child_ptr == node_ptr {
          new_childs.push(lessers_node_opt.unwrap());

          new_childs.push(biggers_node_opt.unwrap());

          for i in i + 1..parent.childs.len() {
            new_childs.push(parent.childs[i].clone());
          }    

          break;
        } else {
          new_childs.push(parent.childs[i].clone());
        }
      }
    } else {
      new_childs.push(lessers_node_opt.unwrap());

      new_childs.push(biggers_node_opt.unwrap());
    }

    {
      let mut parent = Self::node_option_as_mut(parent_opt);
      parent.childs = new_childs;
    }

    if new_head {
      self.head = node.parent.clone();
    }

    let need_parent_split = {
      let parent = Self::node_option_as(parent_opt);

      parent.values.len() >= u_degree
    };

    if need_parent_split {
      self.split(&node.parent);
    }
  }

  fn insert_at_node(&mut self, node_item: &NodeOption<K, V>, key: K, value: V) -> bool {
    if node_item.is_none() {
      return false
    }

    {
      let mut node = node_item.as_deref().unwrap().borrow_mut();

      node.values.push(
        Rc::new(
          Item {
            key,
            value
          }
        )
      );

      node.values.sort();
    }

    let u_degree: usize = self.degree
      .try_into()
      .unwrap();
    
    let need_split = {
      let node = node_item.as_deref().unwrap().borrow();

      node.values.len() >= u_degree
    };

    if need_split {
      self.split(node_item);
    }

    true
  }

  fn get_min_medlst_max(node: &HasNodeOption<K, V>) -> Result<(NodeValue<K, V>, Vec<NodeValue<K, V>>, NodeValue<K, V>), ()> {
    let (min, medlst, max) = {
      let is_empty = node.as_ref().borrow().values.is_empty();

      if is_empty {
        return Err(());
      }

      let intl_node = node.as_ref().borrow();

      let mut medlst = Vec::<NodeValue<K, V>>::new();

      let length = intl_node.values.len();

      let values = &intl_node.values;

      if length > 1 {
        for item in values.iter().skip(1).take(length - 1) {
          medlst.push(item.clone())
        }
      }

      (
        values.first().unwrap().clone(), 
        medlst,
        values.last().unwrap().clone()
      )
    };

    Ok((min, medlst, max))
  }

  fn get_node_to_insert(&self, key: &K) -> NodeOption<K, V> {
    let mut node = self.head.clone().unwrap();
        
    loop {
      let already_exists = {
        let intl_node = node.as_ref().borrow();

        intl_node.contains_key(key)
      };

      if already_exists {
        return None;
      }

      let dont_have_children = {
        let intl_node = node.as_ref().borrow();
  
        intl_node.childs.is_empty()
      };

      if dont_have_children {
        return Some(node)
      }
      
      let result_min_medlst_max = Self::get_min_medlst_max(&node);

      if result_min_medlst_max.is_err() {
        return Some(node);
      }

      let (min, medlst, max) = result_min_medlst_max.unwrap();

      let min_key =  &min.key;

      if *key < *min_key {
        node = {
          let intl_node = node.as_ref().borrow();

          intl_node.childs.first().unwrap().clone()
        };

        continue;
      }

      let max_key =  &max.key;

      if *key > *max_key {
        node = {
          let intl_node = node.as_ref().borrow();

          intl_node.childs.last().unwrap().clone()
        };

        continue;
      }

      for i in 0..medlst.len() {
        let curr = &medlst[i];

        if *key < curr.key {
          node = {
            let intl_node = node.as_ref().borrow();
  
            intl_node.childs[i + 1].clone()
          };
          
          break;
        }
      }
    }
  }

  fn in_order_visit<'a>(node: &NodeOptionVisit<K, V>, cb: &Box<dyn Fn(&Item<K, V>) + 'a>){
    if node.is_none() {
      return;
    }

    let node = node.as_deref().unwrap().borrow();

    for i in 0..node.childs.len() {
      let child = &node.childs[i];
      
      Self::in_order_visit(&Some(child), cb);

      if i < node.values.len() {
        cb(node.values[i].as_ref());
      }
    }

    if node.childs.is_empty() {
      for item in &node.values {
        cb(item.as_ref())
      }
    }
  }
}

impl <K: PartialOrd, V> super::Tree<K, V> for Tree<K, V> {
  fn insert(&mut self, key: K, value: V) -> bool {
    if let None = self.head {
      self.head = new_node_item(
        self.internal.clone(),
        None
      );
    }

    let node_to_insert = self.get_node_to_insert(&key);

    if node_to_insert.is_none() {
      return false;
    }

    self.insert_at_node(&node_to_insert, key, value)
  }
  
  fn get_degree(&self) -> i32 {
    self.degree
  }
  
  fn visit(&self, visit: VisitTree<K, V>) {
    match visit.order {
      super::TreeOrder::InOrder =>
        Self::in_order_visit(&self.head.as_ref(), &visit.cb)
    }
  }
}

btree/tests.rs

use crate::btree::{TreeOrder, VisitTree};

use super::{BTree, TreeType};

#[test]
fn btree_non_concurrent_can_insert(){
  let mut tree: BTree<i32, i32> = BTree::new(TreeType::NonConcurrent, 6);

  for i in 1..101 {
    tree.insert(i, i);
  }

  println!("Key: {}", "Donnne!!");

  tree.visit(
    VisitTree::new(TreeOrder::InOrder, |item|{
      println!("Value: {}", item.value);
    })
  );

  println!("Success??!!");
}

If possible, I would like to ask for special attention in terms of performance.

Why is the implementation of std::collections::BTreeMap much faster than the current one? Does it perhaps use unsafe lines or something like that?