CS44 Weekly Lab: week 11

C++, C++ Tools, B+Tree Lab

Checkpoint 2 Submision:

cd into your cs44/labs/ subdirectory and copy over this directory and its contents:
cp -r /home/newhall/public/cs44/lab05/checkpt2 .
cd into the checkpt2 directory, open the README file and follow the directions.
cd checkpt2
The directions assume that your Lab repo is in ~yourhomedir/cs44/labs/Lab5-youandpartner/. If it is in a different subdirectory, then adjust the cp command examples in the README accordingly.

(you are going to copy your btree.[cpp,h] files into this directory, run make, run the test script redirecting its output to a file, cp the file to your repo, and add, commit and push the output file).

I will demo these steps in lab on Monday, but you can do them before then, and must run and add, commit, and push the ouput file to your repo anytime before 4:30 on Monday. I will pull everyone's repo at that time to get your checkpoint 2 output.

Here is a samle of what your chkpt2_out file might look like: chkpt2_out example

Final Part of Lab 5

The last functionality to implement is:
  1. File scans. These are the support for range queries (and exact match queries) on the index. The state of a scan is kept in the BTreeIndex data members. You need to implement methods to start and end a scan and to get the next rid in an initialized scan.

  2. Splitting internal nodes. This may be the most difficult part of the lab. I suggest that you start by drawing different examples and cases and stepping through them on paper, and then planning out your algorithm before jummping in and coding. Remember that all split nodes must be at least 50% full. Test with DEBUG defined so you can trigger a lot of splitting, and use a printTree method to help you see the effects of splits.

    You sould also do some testing without DEBUG defined to see that it works on larger capacity nodes. File scan functionality is useful for large index testing; you can do some scans over the resulting index to see if ranges of K* entries are in correct order after splits.

  3. Further testing and test code development to stress test your solution: inserts, scans, correctness and error handling. Make sure you test some large size indexes. File scans are useful for large index testing.


As you work on C++ labs, remember all these resources: