Adding stuff

B-Trees add new entries to their leaves, which then bubble up as nodes grow too large. In order to efficiently find a spot, this is done recursively, removing and replacing ownership as needed. Here is the add() function, which takes care of retrieving ownership of the root node and calling the recursive call with an existing or new node:

type Data = (Option<IoTDevice>, Option<Tree>);

pub fn add(&mut self, device: IoTDevice) {
    let node = if self.root.is_some() {
        mem::replace(&mut self.root, None).unwrap()
    } else {
        Node::new_leaf()
    };

    let (root, _) = self.add_r(node, device, true);
    self.root = Some(root);
}

Except in the case of the root node, the add_r() function (the recursive call) returns two pieces of information: the key it descended into and—in case of a "promotion"—the device and child that are to be added to whichever node it returns to. In principle, this function works as follows:

1. Recursively...