Help understanding borrowing rules in B+ Tree Implementation

[tcaputi]

Hello,
I'm trying to give learning Rust another shot (after failing to wrap my head around it the first time). I am currently very comfortable with C, but I think Rust might be a good fit for an upcoming project I want to work on. I would like to start with learning to implement a B+ Tree since it is a data structure I am fairly familiar with and it seems like implementing it will force me to learn a variety of Rust concepts.

Conceptually I think I understand what I want from the borrow checker, but for the life of me I can't get the compiler to accept it. I am trying to build the implementation incrementally, but I can't even get an insert into an empty tree to work. This is what I have so far:

use std::rc::Rc;
use std::rc::Weak;

/************************* B+ TREE IMPLEMENTATION *************************/

/*
 * I want the keys to implement Ord so that I can just use <,=,> to decide
 * where to place them. I also want the keys to implement Copy because I
 * B+ trees need t be able to keep copies of keys at different levels of
 * the tree. The values can be any type, but for simplicity I want it to be
 * copyable because I don't know how to move the value into the tree. I want
 * each node to have a pointer to its parent. The root won't have a parent
 * so this needs to be an Option. I'm using Weak references here so that I
 * can break the resulting reference cycles.
 */
struct BPlusLeaf<K: Ord + Copy, V: Copy> {
    parent: Option<Weak<BPlusInterior<K, V>>>,
    keys: Vec<K>,
    values: Vec<V>,
}

/*
 * Same idea here with the parent pointer and keys value. The children
 * may be either leaves or more interior nodes. I am not 100% sure
 * what the difference between an Rc and a Box is in this instance. I
 * want these nodes allocated on the heap, but I am only using Rc
 * because I am using Rc::Weak for the parent pointer.
 */
struct BPlusInterior<K: Ord + Copy, V: Copy> {
    parent: Option<Weak<BPlusInterior<K, V>>>,
    keys: Vec<K>,
    children: Vec<Rc<BPlusNode<K, V>>>
}

/*
 * I am using this enum so that BPlusInterior.children can be either
 * interior nodes or leaves.
 */
enum BPlusNode<K: Ord + Copy, V: Copy> {
    Leaf(BPlusLeaf<K, V>),
    Interior(BPlusInterior<K, V>)
}

/*
 * This is meant to be the externally-facing struct that eternal code
 * would call methods on. I will probably want to add fields in the
 * future, but for the moment I am already sufficiently confused. :P
 */
struct BPlusTree<K: Ord + Copy, V: Copy> {
    root: Option<Rc<BPlusNode<K, V>>>
}

impl<K: Ord + Copy, V: Copy> BPlusTree<K, V> {
    /* Simple constructor */
    fn new() -> Self {
        return BPlusTree { root: None }
    }
    
    fn insert(&mut self, key: &K, value: &V) {
        /* If the root doesn't exist yet allocate an empty leaf */
        if self.root.is_none() {
            self.root = Some(Rc::new(BPlusNode::Leaf(BPlusLeaf {
                parent: None,
                keys: Vec::new(),
                values: Vec::new(),
            })));
        }
        
        /* Insert the key / value into the leaf */
        match self.root { /* unwrap the option */
            None => panic!("This can't happen"),
            Some(ref mut node_rc) => {
            
                /* this line produces a compiler error */
                let mut node = *Rc::get_mut(node_rc).unwrap();
                
                match node { /* unwrap the BPlusNode enum */
                    BPlusNode::Interior(ref mut interior) => {
                        //TODO: implement interior nodes
                        panic!("This also can't happen yet") 
                    },
                    BPlusNode::Leaf(ref mut leaf) => {
                        leaf.keys.push(*key);
                        leaf.values.push(*value);
                        //TODO: implement node splitting + tree growth
                    }
                }
            }
        }
    }
}

/************************* TESTING PROGRAM *************************/

/* Dummy value type for testing */
#[derive(Debug, Copy, Clone)]
struct TestData {
    data: [u64;  4],
}

fn main() {
    let tree: BPlusTree<u64, TestData> = BPlusTree::new();
}

My big questions are:

1. How can I resolve the compiler error in the insert() method?
2. Are my structures even remotely correct?
3. Is there anyway to do this without so much nesting? The simple version of the insert function ends up 6 levels deep just trying to unwrap the Vectors I want to work with.
4. I'm having a very hard time finding documentation on how to unwrap values. As far as I can tell I need a match to unwrap the Option, and BPlusNode enums and I don't think I'm using the right thing to unwrap the Rc based on the compiler error. In particular, I can't figure out the correct way to modify the Vecs in the leaves and interior nodes. What is the right way to do this?

Sorry for the wall of text. I've been staring at this for a few days now and can't get anything to work. Thanks for any help.

[TomP]

Have you already read Rust Collections Case Study: BTreeMap? See also rust/src/liballoc/collections/btree/ and, for insight into the underlying issues, Learn Rust With Entirely Too Many Linked Lists.

[DevinR528]

To fix this if you remove the * from get_mut().unwrap(). get_mut() gives you a mutable ref inside the option which is what you want, one way to fix it would be

// no deref "*" before Rc
let mut node = Rc::get_mut(node_rc).unwrap();
// everything else the same

try it out i did add a bunch of debug bounds to the K and V but other wise the same playground

[tcaputi]

Wow haha. Alright. I guess that fixes the compilation issue. Can't believe I stared at that so long without trying that.... Thanks.

[tcaputi]

I haven't seen the first 2. I'll take a look at that. Thanks.

[DevinR528]

I do the same thing it's all good!! Its like it gets harder to see the "obvious" stuff the longer you look.