- g++ (used 4.9.2, C++11 support required)
- make (used 4.1)
make
./project2 test.txt
This project consists of a tree
component that is the modified implementation of a B+ tree with the deletion algorithm changed to only remove nodes upon hitting 0 keys. The tree
's degree can be modified with constants at the top of the file.
The studentRecord
class handles the block component and can be modified using the constants at the top of the file.
Upon completion of running the scripts, a file out.txt
will be written into the executable's directory in addition to std::cout
output of any errors, SNAPSHOT
s, or LIST
s that happen to be printed.
###Objective This project will give you an opportunity to familiarize with the most commonly used data organization, B+ trees.
###The Problem
You are given a list of between 400 and 500 student
names containing a significant number of duplicates.
As these names will not be case sensitive Doe, John,
doe, john and DOE, JOHN will represent the same
student. You might therefore want to store your keys in
some canonical form, such as all lower case ore all
upper case. No name will ever occupy more than 32
characters. To each distinct student name, we want to
attach 224 bytes of confidential information that will
initially contain 224 blank characters. Hence we can fit
four student records in a one kilobyte block.
You are to write a program using a B+ tree
organization to manage these data. Given that that each
pointer occupies 64 bits, each B+ tree node will contain
10 keys and 11 pointers. Your program should be able:
- To
INSERT
new student records into a possibly empty table; - To
SEARCH
for the record of a given student and print it out (name and confidential information); - To
LIST
all students names in the appropriate order. - To
UPDATE
a given student record; - To
DELETE
a given student record.
Your INSERT
procedure should be able to detect
duplicate names, reject them and write an error
message. Your SEARCH
and DELETE
procedures should
act in the same way when asked to access or delete
records that do not exist.
To get full credit, your LIST
procedure should be
implemented efficiently using the 11th pointer of the
leave nodes of your B+ tree.
To simplify your life and make the assignment
more interesting, your DELETE
procedure should not
merge B+ tree nodes when one or more records they
point to are deleted. You should wait instead until the
node is empty then delete it.
###The Input Data Your input data will consist of a list of record specifications separated by keywords as in:
*INSERT
Walker, Chris
Toleti, Srinivas
WALKER, CHRIS
Rawlinson, Edward M
Mason, Eric J
Wu, Chang‐Yu
*SNAPSHOT
*SEARCH
rawlinson, edward m
Wong, Qun
*INSERT
Chiang, Mark
*DELETE
Long, Robert
*SNAPSHOT
*UPDATE
WALKER, CHRIS
New project.
Note that the information to be inserted in the confidential information field of a student record only appear in input lines describing updates and will always start on a new line.
All keywords will always start in column 2 and be
preceded by an asterisk in column 1. Every time you
program encounters the keyword SNAPSHOT
, it should
print out a summary of the current structure of the
current index tree. This output should include:
- The number of records in your table;
- The number of blocks occupied by these data, B+ tree nodes excluded;
- The depth of your B+ tree;
- The first and last key of all your B+ tree nodes.
You will soon be provided with a sample data file available from the course page. This handout was updated last on Thursday, April 30, 2015. Please check the course web site for updates.