You have now completed the necessary steps to represent a BTree in Python and can now move on to implementing the fundamental operations needed to leverage BTrees. We start first with an insert method. Insert has multiple steps in the general implementation, but we will first start with inserting values into nodes. First, we fill a BTree. We will only need to fill in the keys of the root element until it’s full. More specifically:
- When we insert a new value, we first check if the root has space.
- If so, and the root is a leaf, we can insert the value into the root.
- To insert a value into a node, we need to make sure the keys stay in order, and thus we insert in order (don’t append and then sort).
For testing, we will set a high branching factor in this exercise, so all values are inserted into the root node. Here and in the coming exercises, we will split our implementation between the
BTree classes, so be aware of what is going where when implementing.
Start by implementing the
add_key() method in
BTreeNode, which takes in a
value argument. Here, we need to make sure that when adding keys, they stay in ascending order.
To do this, our code will be as follows:
- Iterate over the length of
- Check if
valueis less than the element in
self.keyswe are at.
valueis less than the element, insert
valueat the index of the element.
- If this condition isn’t hit during the iteration, append
valueat the end of
Next, implement the initial
insert() method in
BTree. This function will be added too later, but for now, take in a value and add it to the root node using the root node’s
Click the hint if you feel stuck.