Program 3
Topic: B-Trees
B-Trees are the basis for many disk-based data storage systems supporting rapid search and update operations. When a B-Tree is used as the underlying implementation for a Dictionary ADT, the Dictionary data persists across invocations of the program. Main memory is also utilized efficiently as only data currently being used is actually taking up space in RAM.
Your task is to implement a Dictionary ADT using a B-Tree implementation. This will be a template implementation to allow flexibility of application. Only objects that meet certain requirements can be handled by the B-Tree implementation. The basic requirement is that the object must be correctly copied using the default assignment operator. This means the entire state of the object is contained within the memory occupied by the object itself. This will allow the objects to be stored in a binary format in the file.
Our goal is not so much towards efficiency but towards a proof of concept. A 'real' implementation would buffer disk blocks and streamline node sizes to fit physical blocks on the disk. We will ignore these issues.
The B-Tree class will be a template, allowing the object type and BTree order to be specified. The constructor for our class will require a file name. The nodes will be constructed to hold at most n (n is the order) data items. Nodes other than the root node will always have at least floor(n/2) values.
The file will be opened by the constructor and closed in the destructor. The file will contain B-Tree structure information at the start of the file - a 4 byte integer representing the location of the root node, a 4-byte integer representing the location of the first free node, a 4-byte integer representing the size of the nodes (in bytes), and a 4-byte integer representing the order of the tree. These values are inserted in every new file and updated as necessary when the B-Tree is closed. If an existing file is opened and the B-Tree parameters do not match what is in the file, then the B-Tree object should close the file and report an error. No methods should do anything if the file is not open.
A sample application will create a couple of BTree objects and perform some data manipulation to exercise your class. This will be provided later. Get the template for the project (revised 3/20 at 1 PM) and begin work now.
Your finished project must be zipped and submitted via email by the due date. Mail the project to me margush@uakron.edu and use the subject line: DSAII Program 3 Submission. All project files must be in one folder named your_name_3. Delete or empty the Debug folder before zipping. Zip the entire project folder and contents so when I unzip it, everything is in a single folder named with your name and the project number. Please submit a printed copy of the program.