Test Assignment for Students Applying for a Position at the Chair for Database Systems
Prologue
As our research requires complex C++ programs, students applying for positions at our chair need sufficient C++ and software engineering knowledge. Therefore, we require each applicant to implement the following assignment.
Before taking the assignment, make sure that you are familiar with the following C++ concepts as the assignment and the work at our chair will require them:
- Pointers and references: Be sure you know what these two are and when to use them
- Copy constructors, copy assignments: When does the compiler implicitly call these methods and what are they good for?
- Templates: We use a lot of C++ templates. You must be able to work with class and function templates effectively!
- Memory management: What are malloc and free, and memcpy good for?
Taking the Assignment
Solve the following assignment with C++. You may use the latest standard C++11. Make sure that your program compiles under gcc version 4.7 or later. If you currently do not use gcc for compiling your C++ code, download and install it! Make sure to compile the code with the -std=c++11 option, as we use c++11 constructs and the code will not compile otherwise!
This exercise should take you no longer than 8 hours if you know how a B+ Tree works (otherwise, add the time for looking it up). If you need a lot more time than that, you should reconsider applying as your programming skills might not suffice for this position. This is neither good for us (as you will produce more work for us than you do for us) nor for you (as you will be frustrated, because the tasks we will give to you will be a lot harder than this excercise).
Do not try to cheat by using an implementation from the web or letting somebody else implement the assignment for you. We will find that out quickly once you fail to implement the tasks we give to you.
Once you are finished, send your implementation to your adivsor.
Assignment
Implement a B+ Tree. Use the skeleton implementation that is provided here. Make sure you adhere to all restrictions and directions given in the comments contained in the file! The class itself is already provided; you "only" have to implement the following three things:
- two constructors (parameterless constructor, copy constructor)
- four missing methods (insert, hasKey, find, split)
- Test code in the yourTests function. Make sure to test your implementation thoroughly!
The following call should be able to compile your code, assuming that the skeleton file is in the current working directory:
g++ -std=c++11 bplustree.cpp
Note that the skeleton file should compile without any modifications!
Please write all additional code you need into the same file, do not use more than one file. Do not use liberaries despite of the standard library! Note that you do not have to implement a method for removing keys from a tree which greatly simplifies the implementation.
Make sure your implementation meets the following criteria:
- Performance: Your implementation should be reasonably fast! All operations should have a worst case runtime complexity of at most O(log n).
- Readability: Your code should be readable and comprehensible.
- Make sure your methods are not too long
- Make sure you follow common naming conventions and coding standards
- Make sure code is document as much as necessary, but not too much
- Test coverage: Make sure that your tests are reasonable and test your implementation thoroughly! Especially, test corner cases, e.g., when a node is split after an insert.
About the B+ Tree
The B+ Tree in this assignment is an implementation of an ordered map, mapping keys K to values V. The mapping is unique, so no key K may be present more than once in the tree.
A B+ Tree is a B Tree variant in which the inner nodes only store routing keys and no values. Only the leaf nodes store key value pairs. The explanation at wikipedia should suffice for understanding the B+ tree. Use it to guide your implementation. The split operation is not explained there. Thus, it is your duty to think of a sane and efficient implementation (which is quite easy if you think a bit).