Introduction

In this assignment, you will answer several questions about B+ trees, in particular, their current implementation in Minibase. You will write small programs using an object library we provide that has an implementation of B+ trees. Your programs will output ``trace'' files that you will then use as input to our B+ tree visualization tool.

You will carry out this assignment in teams of two with the same partner as for the first assignment.

This assignment involves no programming beyond modifying the (given) template program for inserting/deleting entries in a B+ tree. Try and use the visualization tool to help you think through the problems!

Available Documentation

You should begin by reading the chapter on Tree Structured Indexes, in particular the sections on B+ tree insertion and deletion. The visualization tool provides on-line help.

The Exercises

1. Start with the template program we provide, which initializes a B+ tree of order 2. Make your program insert the following strings, in this order:

   "02", "16", "07", "20", "29", "33", "39", "38", "03", "05", "14", "19", "22", "24", "27", "34"

   When you run this program, it will print a trace to stdout. To save the trace to a file, redirect output to the file. Use this file as the input to the B+ tree visualization tool. Work with the tool to see what the tree's structure is. Draw a picture of the tree similar to Figure 5.10 in the text.

2. How does the structure of this tree differ from the one depicted in Figure 5.10? (Ignore the fact that the text uses integer keys, and your program uses string keys.) Actually, Both B+ trees are index on the same set of data records. What lead to the two different B+ trees that we get?
3. Modify your program from exercise 1. to insert the string "23" as the last operation on the tree. What happens? How many page writes and reads are required in this insertion? What can you deduce about the insertion algorithm implemented in the library, compared to the one in the text?
4. Modify your program from exercise 1. to delete "29", "33", and "34" at the very end. How many page writes and reads are required in this series of deletion? What can you deduce about the library's deletion algorithm by comparing the one in the text?

5. Given what you have deduced about the library's insertion and deletion algorithm, modify your program in exercise 1. so the internal structure of the tree exactly matches Figure 5.14. What do you have to do?

6. Using insertions of unique keys only, construct a tree of order 2 and height 4 that has as few records as possible.

7. Using insertions only, construct a tree of order 2 and height 3 that has as many records as possible.

Compiling Your Code and Running the Tests

The code and documentation for this assignment is in ~cs564-1/assigns95/assign2/. You have to copy the Makefile and btree-template.C to your directories. The file you have to modify for this assignment is: btree-template.C You can change it to insert and delete different keys from the tree, and then compile it with the following command:

        make NAME=<your-file-name>

The visualization tool can be run by typing

        /p/course/cs564-raghu/assigns95/assign2/bin/btview

What to Turn In, and When

You should turn in:

1. Your solutions in the form of modified versions of the template programs.
2. Brief answers to the questions in a separate file. Use any word processing software that you want, but please make the file easily readable. (Plain text is preferable.)

The assignment is due at 5PM on October 4th. The solution will be made public then, and solutions turned in after that time will not receive any credit. So be sure to turn in whatever you have, even if it is not working fully, at that time.