## Project 5: B+-trees
### Due Oct 27, 2023, 11:59PM

*The assignment is to be done by yourself.*

### Setup

Download files for Assignment 5 [here](https://ceres.cs.umd.edu/424/assign/assignment5Dist.tgz?1").
*We do not provide a new Vagrant file as you can use your existing VM's with this project, or just natively on your computer.*

### Overview

In this project, you will modify a very simple database system that we have written to illustrate some of the B+-Tree algorithms. 
The database system is written in Python3 and attempts to simulate how a database system would work, including what blocks it would read from disk, etc.

* `disk_relations.py`: This module contains the classes Block, RelationBlock, Relation, and a few others helper classes like Pointer. A Block is a base class, 
that is subclassed by RelationBlock and BTreeBlock (in `btree.py` file). A RelationBlock contains a set of tuples, and a Relation contains a list of RelationBlocks. 
* `btree.py`: Code that implements some of the BTree functionality including search, insert, and delete (partially). The main class here is the BTreeBlock class, that captures the information stored in a BTree node.

There are a set of parameters that control how many tuples can be stored in each RelationBlock, how many key/ptrs can be stored in each BTreeBlock, etc. You can't set those directly, but you can set the "blockSize" and also the size of a key, etc. Those parameters are in the class `Globals`, and can be modified to constructs trees of different fanouts.

**Important Note: The B+-Tree code isn't fully debugged and there may be corner cases where it fails. Let us know if you see unexpected behavior.**

### How to Use the Files
The directory also contains two other files:
* `create_sample_databases.py`: Creates a sample database with 2 relations and 2 indexes.
* `testing-btree.py`: Shows the execution of some simple btree tasks using the sample data. 

The simplest way you can run this is by just doing: `python3 testing-btree.py`
That will run all the code in the `testing-btree.py` file.

A better option is to do: `python3 -i testing-btree.py`. This will execute all the code in `testing-btree.py` file and then it will open a Python3 shell. In that shell, you can start doing more operations (e.g., you can play with the index to add/delete tuples, etc.)

### Your Task

Your task is to finish one unfinished piece in the `btree.py` file.

* Function `redistributeWithBlock(self, otherBlock)` in `btree.py`: The delete code does not handle the case where an underfull node borrows entries from one of its siblings.

You are to implement this function. **Note that `redistributeWithBlock` is called on the right child for this project.** Refer to Figure 14.21 from the textbook (7th edition) in the textbook for guidance. You will need to cover 4 cases:
* When the right (self) child is underfull and (1) it's a leaf node and (2) it's not a leaf node
* When the left (other) child is underfull and (3) it's a leaf node and (4) it's not a leaf node

Note that you only need to return the value that will update kprime.

### Submission
Submit the modified `btree.py` file [here](https://www.gradescope.com/courses/535193/assignments/2852230).