Overview
Implement a simulation of a B+-tree in Python.
This is an individual assignment.
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 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.
- 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. Values can be any type.
- 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.
- You do not need to implement the linked list of pointers that
one typically finds in a B+-tree at the leaf level.
- 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.
- 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.
- 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.