Building a basic database Table in Java

Part1.md

Part 1: A Simple Database Table

Create a Table class with three methods:

NOTE: for this exercise you only need to handle storing Strings in the Table; Modifying your finished Table class to handle columns with different data types is a good stretch assignment.

insert()

• Takes 1 parameter: a record ( String->String key-value pairs; keys represent column names in the table and values are String values stored in each column)
• Stores the records in a data structure in the Table class
• Returns the unique ID number of the newly inserted database row (IDs start at 1)

findById()

• Takes 1 parameter: an ID number
• Returns the record corresponding to that id number
• Example: findById(4)

findBy()

• Takes 2 parameters: column name and a value
• Returns a list of all record IDs that contain that value.
• Example: findBy("age", "42")

Part2.md

Part 2: Optimizing Table.findBy()

Calling the findBy method is at this point is rather inefficient. In a small table it's not very noticeable, but in a table with thousands of rows it will take a long time to search through every row for all the records with the desired value. This can be optimized by keeping an index of the values stored in each column.

Speed up the process of accessing the table by adding automatically generated indexes for each column. For Part II indexes should be a simple associative data structure mapping values seen in each column to a list of records with that value (i.e.: [column value]->[list of record IDs with that value]). Modify the appropriate methods in the Table class so that indexes are automatically kept up to date when inserting new records, and calls to findBy() use the index to find the appropriate records instead of iterating through the entire table.

Part3.md

Part 3: Optimizing Indexes with B-Trees

The indexes created in Part 2 are a good optimization for the findBy method, but we can do better. In this exercise we will replace them with B-Trees.

Remember that B-Trees are a data structure with nodes, each of which contains multiple values (Nodes in a B-Tree of degree 2, which we will be implementing, have 2*2-1=3 keys and values, and 2*2=4 children.

Step 1

Implement a B-Tree class, composed of Nodes (an inner class). Nodes should have public search(), insert(), and split() methods. B-Tree instances should contain the root Node of the tree, and provide methods for inserting and retrieving (get-ing) objects stored in the tree.

Step 2

Once the B-Tree implementation is complete, refactor your Table class to use B-Trees for its indexes. To help with fully understanding the operation of B-Trees, try playing around with this B-tree simulator Optional: Implement B-Tree to support generic data types to be stored.

Table.java

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.HashMap;

/**
 * A sample solution to Part I coded together in class.
 */
public class Table {

    //ArrayList<HashMap<String, String>> records = new ArrayList<>();
    HashMap<Integer, HashMap<String, String>> records = new HashMap<>();

    int id = 0;

    public int insert(HashMap<String, String> row) {

        records.put(++id, row);

        System.out.println("Id during insert " + id);
        return id;


    }

    public HashMap<String, String> findById(int findId) {

        HashMap<String, String> targetRow;
        targetRow = records.get(findId);
        return targetRow;


        //return records.get(findId);
    }

    public ArrayList<HashMap<String, String>> findBy(String colName, String value) {

        ArrayList<HashMap<String, String>> result = new ArrayList<>();

        for(HashMap<String, String> row : records.values()){
            if(row.containsKey(colName) && 0 == value.compareTo(row.get(colName))){
                result.add(row);

            }
        }

        return result;
    }

    public static void main(String[] args) {

        HashMap<String, String> person = new HashMap<>();
        person.put("name", "Joe");
        person.put("age", "43");

        Table people = new Table();

        System.out.println(people.insert(person));

        person = new HashMap<>();
        person.put("name", "May");
        person.put("age", "34");
        person.put("height", "43");
        System.out.println(people.insert(person));

        person = new HashMap<>();
        person.put("name", "Sue");
        person.put("age", "43");
        people.insert(person);

        System.out.println(people.findById(2));

        System.out.println(people.findBy("name", "Sue"));
        System.out.println(people.findBy("age", "43"));
        System.out.println(people.findBy("height", "43"));

    }
}