Skip to content
Snippets Groups Projects
Select Git revision
  • main default protected
1 result
Blame Permalink
Code owners
Assign users and groups as approvers for specific file changes. Learn more.
assign5.md 3.16 KiB

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. 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.