Overview

Implement a B⁺-tree.

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 value. In that sense, the B⁺-tree will work like a traditional map in a data structures sense; it will store key/value pairs.
2. You do not need to delete anything from the B⁺-tree; you only need to insert.
3. Your tree should not store duplicate keys. If someone tries to store a key that is already in the B⁺-tree, raise an exception.
4. You may assume that all keys are integers, and all values are strings.
5. When a node splits, if the number of keys is uneven, the node on the left after the split should contain one more key than the node on the right.
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. To keep this simple, it should merely print out the keys in each node. Nodes on the same level of the tree should be printed on the same line, but make sure to clearly separate one node from another. For example, the B⁺-tree in Figure 11.9 of your textbook might get printed to your screen as:

             ["Mozart"]
             ["Einstein", "Gold"]  ["Srinivasan"]
             ["Brandt","Califieri","Crick"]  ["Einstein","El Said"]
           

     (The ... indicates that there's more on this line, I'm just leaving it out for brevity.) Note that I chose this example because it was in your textbook; but for your B+-tree, this should contain integers.
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(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.

Parts of assignment

1. Make getValue and printTree work. In order to do this without having insert working yet, you should manually construct a small B⁺-tree "by hand" in a test method. Create a set of nodes and insert values and pointers into them so that you have a ready-made correct B⁺-tree. It should hopefully be a lot easier to do these methods first; then, you will have additional info at your disposal when debugging insert.
2. Make insert work.
3. Optional additional step: add a delete method. We won't be grading this, but this is something you can try if you want to see if you can do it.