Overview

Implement a simulation of a B⁺-tree in Python.

This is an individual assignment.

Here are some details.

1. In a real B⁺-tree, the leaves contain keys and pointers to the corresponding records in pages. To keep this assignment focused on just the B⁺-tree, we will instead have the pointer in a leaf point to a specific Python value. In that sense, the B⁺-tree will work like a traditional map in a data structures sense; it will store key/value pairs. That value can even be a Python tuple, so it can simulate a B+-tree that way. Think of this as a secondary index.
2. Your tree should not store duplicate keys. If someone tries to store a key that is already in the B⁺-tree, raise an exception.
3. You may assume that all keys are integers. Values can be any type.
4. When a node splits, if the number of keys is uneven, the node on the right after the split should contain one more key than the node on the left. (Typo here was fixed on 10/30, 6am
5. You do not need to implement the linked list of pointers that one typically finds in a B⁺-tree at the leaf level.
6. Create a module called bptree, inside of which is a class called Bptree. The constructor (i.e., the __init__ method) should take a parameter indicating how many keys can be stored in each node. Assume that the number of keys in leaves and internal nodes are the same. There are only three methods that your Bptree class must have (though you will undoubtedly need others):
   • insert(self,key,value): Inserts a key-value pair into the tree.
   • getValue(self,key): Returns the value associated with a particular key. Returns None if the key is not in the tree.
   • printTree(self): Prints out a text version of the tree to the screen. The easiest way I found to do this was to rotate the tree vertically, showing the root on the left hand side of the terminal window, expanding to the right, and indenting further for deeper levels. Doing a recursive depth-first traversal of the tree made this pretty easy.
7. When your code is working, I should be able to execute the following code from a file in the same directory:

       import bptree
       b = bptree.Bptree(4)  # Each node contains 4 keys, which means 5 pointers
       b.insert(12,"hello")
       b.insert(24,"bye")
       print b.getValue(24)
       b.printTree()
     

   Note that this is not a sufficient test for your code. We will be running it with more complicated data than this.
8. You do not need to delete anything from the B⁺-tree; you only need to insert.

Optional extra part

Optional additional step: add a delete method.

Though this work is optional, I'll offer a tiny incentive to work on it: we will add 1 point back to a past assignment of your choice (not an exam) if you successfully make delete work. Indicate in program comments that you have done so, so that we know to test it.