CS 334: B+-trees

Overview

Implement a B⁺-tree.

Here are some details.

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.
You do not need to delete anything from the B⁺-tree; you only need to insert.
Your tree should not store duplicate keys. If someone tries to store a key that is already in the B⁺-tree, raise an exception.
You may assume that all keys are integers, and all values are strings.
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.
Create a module called bptree, inside of which is a class called Bptree. 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. You don't have to print out the values associated with each key. 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 12.12 of your textbook might get printed to your screen as:
```
        ["Perryridge"]
        ["Downtown", "Mianus"]  ["Redwood"]
        ["Brighton", "Clearview"]  ["Downtown"]  ["Mianus"] ...
      
```
  (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.
The number of key values in each node should be obtained from a parameter to the constructor. See the sample code below.

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(5)  #<-- each node has 5 keys, and thus 6 pointers
    b.insert(12,"hello")
    b.insert(24,"bye")
    print b.getValue(24)
    b.printTree()

Parts of assignment

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.
Make insert work.