I am unclear how to implement the DBTable class from the following BTree class: The DBTable class implements the basic parts of a database table. The DBTable must also use the B+Tree to find rows in the table. Every DBTable method will use Btree.

//BTree class

import java.io.BufferedReader;

import java.io.File;

import java.io.FileNotFoundException;

import java.io.FileReader;

import java.io.IOException;

import java.io.RandomAccessFile;

import java.lang.reflect.Array;

import java.util.Arrays;

import java.util.Collections;

import java.util.LinkedList;

import java.util.Stack;

public class BTree {

private RandomAccessFile f;

private int order;

private int blockSize;

private long root;

private long free;

private class BTreeNode {

private int count;

private int keys[];

private long children[];

private long address; // the address of the node in the file

public BTreeNode() {

this.keys = new int[order - 1];

this.children = new long[order];

this.count = 0;

this.address = 0;

}

public BTreeNode(long addr) throws IOException {

f.seek(addr);

for (int i = 0; i < keys.length; i++) {

this.keys[order-1] = f.readInt();

}

for (int i = 0; i < order; i++) {

this.children[order] = f.readLong();

}

this.count = f.readInt();

this.address = addr;

}

public void writeNode(long addr) throws IOException {

f.seek(addr);

f.writeLong(address);

f.writeInt(blockSize);

f.writeInt(keys[order-1]);

f.writeLong(children[order]);

}

public boolean isLeaf() {

if(children.length == 0) {

return true;

}

return false;

}

}

public BTree(String filename, int bsize) throws FileNotFoundException {

//bsize is the block size. This value is used to calculate the order

//of the B+Tree

//all B+Tree nodes will use bsize bytes

//makes a new B+tree

try {

this.f = new RandomAccessFile(filename, "rw");

this.blockSize = bsize;

}catch(FileNotFoundException e) {

e.printStackTrace();

}

}

public BTree(String filename) throws FileNotFoundException {

//open an existing B+Tree

this.f = new RandomAccessFile(filename, "rw");

}

public boolean insert(int key, long addr) throws IOException {

/*

If key is not a duplicate add, key to the B+tree

addr (in DBTable) is the address of the row that contains the key

return true if the key is added

return false if the key is a duplicate

*/

return Insert(key, root);

}

public void nonFullInsert(long r, int key) throws IOException {

BTreeNode x;

BTreeNode child;

x = new BTreeNode(r); //make a new node at address r

int i = x.count; //i is the number of keys in node x

if(x.isLeaf()) {

//find a spot to put the key

while(i >= 1 && key < x.keys[i-1]) {

x.keys[i] = x.keys[i-1];

i--;

}

x.keys[i] = key; //assign value to node

x.count++; //increment count of keys in node

}

else {

int j = 0;

//find a spot to recurse on correct child

while(j < x.count && key > x.keys[j]) {

j++;

}

//i++;

child = new BTreeNode(x.children[j]);

if(child.count == order * 2 - 1) {

//call split on node x's ith child

split(x, j, child);

if(key > x.keys[j]) {

j++;

}

}

nonFullInsert(x.children[j], key); //recurse

}

}

public boolean Insert(int key, long r) throws IOException {

//this method finds the node to be inserted

//as it goes through this starting at root node

BTreeNode currNode;

currNode = new BTreeNode(r);

int i = currNode.count;

//check if node is full

if(currNode.count == order * 2 - 1) {

BTreeNode newNode;

newNode = new BTreeNode();

currNode = newNode;

boolean n = newNode.isLeaf();

newNode.count = 0;

n = false;

newNode.children[0] = r;

int j = newNode.count;

//split root

split(newNode, 0, currNode);

//call insert method

nonFullInsert(newNode.children[j], key);

return false;

}

else {

//node not full, insert key

nonFullInsert(currNode.children[i], key);

return true;

}

}

public long remove(int key) throws IOException {

/*

If the key is in the Btree, remove the key and return the address of the

row return 0 if the key is not found in the B+tree

*/

return remove(root, key);

}

private long remove(long r, int key) throws IOException {

BTreeNode x;

x = new BTreeNode(r);

int val = x.count;

//temp BTreeNode

BTreeNode temp = new BTreeNode();

//call search method on tree for key

r = search(x.children[val], key);

if(temp.isLeaf() && temp.count > order - 1) {

int i = 0;

//while(key > temp.getValue(i)) {

//i++;

//}

for(int j = 0; j < order * 2 - 2; j++) {

temp.keys[j] = temp.keys[j+1];

}

temp.count--;

}

else {

System.out.println("This node is either not a leaf or has less than order - 1 keys.");

}

return r;

}

public long search(int key) throws IOException {

/*

This is an equality search

If the key is found return the address of the row with the key

otherwise return 0

*/

return search(root, key);

}

private long search(long r, int k) throws IOException {

BTreeNode currNode;

int i = 0;

if(r == 0) {

return 0;

}

currNode = new BTreeNode(r); //make a new node at address r

if(currNode.count > 0) {

i = 0;

while (i < currNode.count && k > currNode.keys[i]) {

i++;

}

if (i <= currNode.count && k == currNode.keys[i]) {

return r;

}

if(currNode.isLeaf()) {

return 0;

}

else {

return search(currNode.children[i], k);

}

}

return search(currNode.children[i], k);

}

public LinkedList rangeSearch(int low, int high) {

//PRE: low <= high

/*

return a list of row addresses for all keys in the range low to high inclusive

return an empty list when no keys are in the range

*/

LinkedList list = new LinkedList<>();

BTreeNode x;

x = new BTreeNode();

return list;

}

private void split(BTreeNode x, int i, BTreeNode y) throws IOException {

BTreeNode z = new BTreeNode(); //extra node, will use to split

BTreeNode child; //BTreeNode at address children[i+1]

child = new BTreeNode(x.children[i+1]);

boolean xleaf = x.isLeaf();

boolean yleaf = y.isLeaf();

boolean zleaf = z.isLeaf();

zleaf = yleaf; //set boolean to same as y

z.count = order - 1; //update size of z

for(int j = 0; j < order -1; j++) {

z.keys[j] = y.keys[j+order]; //copy end of y into front of z

}

//if not leaf we have to reassign child nodes

if(!yleaf) {

for(int k = 0; k < order; k++) {

//reassign child of y

z.children[k] = y.children[k+order];

}

}

y.count = order - 1; //new size of y

//if we push key into x, must rearrange child nodes

for(int j = x.count; j > i; j--) {

x.children[j+1] = x.children[j]; //shift children of x

}

child = z; //reassign i+1 child of x

for(int j = x.count; j > i; j--) {

x.keys[j+1] = x.keys[j]; //shift keys

}

x.keys[i] = y.keys[order-1]; //push value into root

y.keys[order-1] = 0; //erase value where we pushed from

for(int j = 0; j < order - 1; j++) {

y.keys[j+order] = 0; //'delete' old values

}

x.count++; //increment count of keys in x node

}

public void print() {

//print the B+Tree to standard output

//print one node per line

//This method can be helpful for debugging

}

public void close() throws IOException {

//close the B+tree. The tree should not be accessed after close is called

f.seek(0);

f.writeLong(free);

f.writeLong(root);

f.close();

}

public static void main(String[] args) throws IOException {

BTree tree = new BTree(args[0]);

tree.insert(16, 15);

System.out.println(tree.search(16));

}

}

-------------------------------------------------------------------------------------------------- //CLASS TO BE IMPLEMENTED //DBTable class

import java.io.File;

import java.io.FileNotFoundException;

import java.io.IOException;

import java.io.RandomAccessFile;

import java.util.LinkedList;

public class DBTable {

private RandomAccessFile rows; //the file that stores the rows in the table

private long free; //head of the free list space for rows

private int numOtherFields;

private int otherFieldLengths[];

private int blockSize;

//add other instance variables as needed

private class Row {

private int keyField;

private char otherFields[][];

/*

Each row consists of unique key and one or more character array fields.

Each character array field is a fixed length field (for example 10

characters).

Each field can have a different length.

Fields are padded with null characters so a field with a length of

of x characters always uses space for x characters.

*/

//Constructors and other Row methods

}

public DBTable(String filename, int fL[], int bsize ) throws FileNotFoundException {

/*

Use this constructor to create a new DBTable.

filename is the name of the file used to store the table

fL is the lengths of the otherFields

fL.length indicates how many other fields are part of the row

bsize is the block size. It is used to calculate the order of the B+Tree

A B+Tree must be created for the key field in the table

If a file with name filename exists, the file should be deleted before the

new file is created.

*/

File path = new File(filename);

if(path.exists()) {

path.delete();

this.rows = new RandomAccessFile(path, "rw");

}

this.otherFieldLengths = fL;

this.numOtherFields = fL.length;

this.blockSize = bsize;

}

public DBTable(String filename) throws FileNotFoundException {

//Use this constructor to open an existing DBTable

this.rows = new RandomAccessFile(filename, "rw");

}

public boolean insert(int key, char fields[][]) throws IOException {

//PRE: the length of each row is fields matches the expected length

/*

If a row with the key is not in the table, the row is added and the method

returns true otherwise the row is not added and the method returns false.

The method must use the B+tree to determine if a row with the key exists.

If the row is added the key is also added into the B+tree.

*/

return false;

}

public boolean remove(int key) throws IOException{

/*

If a row with the key is in the table it is removed and true is returned

otherwise false is returned.

The method must use the B+Tree to determine if a row with the key exists.

If the row is deleted the key must be deleted from the B+Tree

*/

return false;

}

public LinkedList search(int key) throws IOException{

/*

If a row with the key is found in the table return a list of the other fields in

the row.

The string values in the list should not include the null characters.

If a row with the key is not found return an empty list

The method must use the equality search in B+Tree

*/

LinkedList list = new LinkedList<>();

return list;

}

public LinkedList> rangeSearch(int low, int high) throws IOException{

//PRE: low <= high

/*

For each row with a key that is in the range low to high inclusive a list

of the fields (including the key) in the row is added to the list

returned by the call.

If there are no rows with a key in the range return an empty list

The method must use the range search in B+Tree

*/

LinkedList> list = new LinkedList<>();

return list;

}

public void print() {

//Print the rows to standard output in ascending order (based on the keys)

//One row per line

}

public void close() throws IOException {

//close the DBTable. The table should not be used after it is closed

rows.seek(0);

rows.writeLong(free);

rows.close();

}

}