Persisting B-Tree nodes to RandomAccessFile

Question

My project is trying to write a B-Tree. I am having trouble persisting nodes of the tree to a random access file. I am constantly encountering EOFexceptions and StreamCorruptionExceptions.

some resources that I am currently using are:

Converting any object to a byte array in java

https://inaved-momin.blogspot.com/2012/08/understanding-javaiostreamcorruptedexce.html

current Problem: reading a link position from a node and then trying to read it from the random access file is causing a StreamCorruptionExceptions.

Goal: to be able to access all node in the random access file,modify and write them back to the random access file.

Test.java

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.RandomAccessFile;
import java.util.ArrayList;

public class Test {

    public static void main(String[] args) throws IOException, ClassNotFoundException {
        //JsoupTestStringManipulating();
        //testAdd();
        //testFindPredecessor();
        //testDelete();
        //testPrefexFind();
        //testSave();
        testSave2();

    }

    public static void JsoupTestStringManipulating(){
        JsoupParser pars = new JsoupParser();
        String word = "Spike Spegal"; 
        String URL = "http://en.wikipedia.org/wiki/Zombie";

         for(String s: pars.urlTrimming(URL)){
             System.out.println("words: "+s);
         }

        System.out.println(pars.getPadding(word.length()));
    }

    public static void testAdd() throws IOException, ClassNotFoundException{
        BTree tree = new BTree();   
        String padding,fixedString;
        ArrayList<String> testWords = new ArrayList<String>();
        testWords.add("apple");
        testWords.add("sand");
        testWords.add("math");
        testWords.add("tree");
        testWords.add("north");
        testWords.add("onion");
        testWords.add("pan");
        testWords.add("pink");
        testWords.add("pool");
        testWords.add("net");
        testWords.add("never");

        for(String k : testWords){
            padding = getPadding(k.length());
            fixedString = k + padding;
            tree.insert(fixedString);
        }

        Node temp1,temp2,temp3,temp4,temp5,temp6,temp7,temp8,root;
        root = tree.per.read(0);
        temp1 = tree.per.read(root.links.get(0));
        temp2 = tree.per.read(root.links.get(1));
        temp3 = tree.per.read(temp1.links.get(0));
        temp4 = tree.per.read(temp1.links.get(1));
        temp5 = tree.per.read(temp1.links.get(2));
        temp6 = tree.per.read(temp2.links.get(0));
        temp7 = tree.per.read(temp2.links.get(1));
        temp8 = tree.per.read(temp2.links.get(2));

    /*
        System.out.println("root: "+root.keys);
        System.out.println("left: "+temp1.keys);
        System.out.println("right: "+temp2.keys);
        System.out.println("left 0: "+temp3.keys);
        System.out.println(" left 1: "+temp4.keys);
        System.out.println(" left 2: "+temp5.keys);
        System.out.println(" right 0: "+temp6.keys);
        System.out.println(" right 1: "+temp7.keys);
        System.out.println(" right 2: "+temp8.keys);
        System.out.println("node count: "+tree.getNodeCount());
    */

        System.out.println("root: "+root.getStartIndex());
        System.out.println("left: "+temp1.getStartIndex());
        System.out.println("right: "+temp2.getStartIndex());
        System.out.println("left 0: "+temp3.getStartIndex());
        System.out.println(" left 1: "+temp4.getStartIndex());
        System.out.println(" left 2: "+temp5.getStartIndex());
        System.out.println(" right 0: "+temp6.getStartIndex());
        System.out.println(" right 1: "+temp7.getStartIndex());
        System.out.println(" right 2: "+temp8.getStartIndex());
        System.out.println("node count: "+tree.getNodeCount());

    }
    public static void testFindPredecessor() throws IOException, ClassNotFoundException{
        BTree tree = new BTree();
        tree.insert("apple"); 
        tree.insert("sand");
        tree.insert("math");
        tree.insert("tree");
        tree.insert("north");
        tree.insert("onion");
        tree.insert("pan");
        tree.insert("pink");
        tree.insert("pool"); 
        System.out.println("get predicessor: "+tree.getRoot().predacessor(0));
    }   
    public static void testDelete() throws IOException, ClassNotFoundException{
        BTree tree = new BTree();
        tree.insert("apple"); 
        tree.insert("sand");
        tree.insert("math");
        tree.insert("tree");
        tree.insert("north");
        tree.insert("onion");
        tree.insert("pan");
        tree.insert("pink");
        tree.insert("pool"); 
        tree.insert("net");
        tree.insert("never");
        tree.delete("apple");
    /*  
        System.out.println("root: "+tree.getRoot().keys);
        System.out.println("left: "+tree.getRoot().links.get(0).keys);
        System.out.println("right: "+tree.getRoot().links.get(1).keys);
        System.out.println(" left 0: "+tree.getRoot().links.get(0).links.get(0).keys);
        System.out.println(" left 1: "+tree.getRoot().links.get(0).links.get(1).keys);
        //System.out.println(" left 2: "+tree.getRoot().links.get(0).links.get(2).keys);
        System.out.println(" right 0: "+tree.getRoot().links.get(1).links.get(0).keys);
        System.out.println(" right 1: "+tree.getRoot().links.get(1).links.get(1).keys);
        System.out.println(" right 2: "+tree.getRoot().links.get(1).links.get(2).keys);
    */
    }

    public static void testPrefexFind() throws IOException, ClassNotFoundException{
        BTree tree = new BTree();   
        tree.insert("apple"); 
        tree.insert("sand");
        tree.insert("math");
        tree.insert("tree");
        tree.insert("north");
        tree.insert("onion");
        tree.insert("pan");
        tree.insert("pink");
        tree.insert("pool"); 
        tree.insert("net");
        tree.insert("never");

        System.out.println(tree.findPrefix("s"));
    }//end prefex test
    private static String getPadding(int wordLength){
        int diffrence;
        String pad =" ";
        String padding = "";
        diffrence = 34 - wordLength;
        for(int i =0; i < diffrence;i++){
            padding = padding + pad;
        }// end for
        return padding;
    }

    public static void testSave() throws IOException,ClassNotFoundException{
        Node node = new Node(); 
        node.keys.add("apple");
        node.keys.add("math"); 
        node.keys.add("sand");

        ByteArrayOutputStream b2 = new ByteArrayOutputStream();
        ObjectOutputStream OOS = new ObjectOutputStream(b2);
        OOS.writeObject(node);
        byte[] array = b2.toByteArray();
        ByteArrayInputStream in2 = new ByteArrayInputStream(array); 
        ObjectInputStream OIS = new ObjectInputStream(in2);
        Node temp = (Node) OIS.readObject();
        OIS.close();

        for(String s : temp.keys){
            System.out.println(s);
        }
    }

    public static void testSave2() throws IOException,ClassNotFoundException{
        ArrayList<Node>nodeList = new ArrayList<Node>();
        RandomAccessFile raf = new RandomAccessFile("Test.dat","rw");
        byte[] recivingAry;
        Node node = new Node(); 
        Node node2 = new Node();
        node.setStartIndex(0);
        node2.setStartIndex(560);
        node.keys.add("apple");
        node.keys.add("math"); 
        node.keys.add("sand");
        node2.keys.add("candle");
        node2.keys.add("final"); 
        node2.keys.add("better");
        node.links.add((long) 560);
        nodeList.add(node);
        nodeList.add(node2);


        ByteArrayOutputStream b2 = new ByteArrayOutputStream();
        ObjectOutputStream OOS = new ObjectOutputStream(b2);
        for(Node n : nodeList){
            OOS.writeObject(n);
            byte[] array = b2.toByteArray();
            raf.write(array);
        }
    //  byte[] array = b2.toByteArray();
    //  raf.write(array);
        recivingAry = new byte[560];
        raf.seek(0);
        raf.read(recivingAry);
        ByteArrayInputStream in2 = new ByteArrayInputStream(recivingAry); 
        ObjectInputStream OIS = new ObjectInputStream(in2);
        Node temp = (Node) OIS.readObject();
        if(temp.links.size()!= 0){
            recivingAry = new byte[560];
            //System.out.raf.length();
            raf.seek(temp.links.get(0));
            raf.read(recivingAry);
            ByteArrayInputStream in1 = new ByteArrayInputStream(recivingAry); 
            ObjectInputStream OIS1 = new ObjectInputStream(in2);
            Node temp1 = (Node) OIS.readObject();   

            for(String s1:temp1.keys){
                System.out.println(s1);

            }
        }
        OIS.close();

        for(String s : temp.keys){
            System.out.println(s);
        }
    }
}//end class 

Node.java

import java.io.IOException;
import java.io.Serializable;
import java.util.ArrayList;
// this needs to use the trees persist instead of its own. 
public class Node implements Serializable{
    private static final long serialVersionUID = 1L;
    ArrayList<Node> temp = new ArrayList<Node>();
    final int MAXKEYS = 3; //31
    final int middle = MAXKEYS/2;
    ArrayList<String> keys = new ArrayList<String>(); 
    ArrayList<Long> links = new ArrayList<Long>();
    int incrementSize =2048;//2364 - for 31 keys 32 links/ 394 - for 3 keys 4 links
    long startIndex;
    BTree tree;
    public Node(){

    }
    public boolean isLeaf(){
        if(links.size() == 0)
        {
            return true;
        }
        else
            return false;
    }// end is leaf 

    public boolean isFull(){
        if(keys.size() == MAXKEYS)
        {
            return true;
        }
        else{
            return false;
        }
    }//end isFull

    public void split(Node link, int nodeCount) throws IOException{
        Node right = new Node();
        right.setStartIndex(nodeCount * incrementSize);
        String middleVal;
        int count = 0;
        //get right
        while(link.keys.size()> middle+1){
            right.keys.add(link.keys.remove(middle+1)); 
        }
        //get the middle value
        middleVal= link.keys.remove(link.keys.size()-1);

        //compare the keys to the middle guy
        for(String value: keys){
            if(middleVal.compareTo(value)>0){
                count++;
            }
        }
        //add keys and links in proper spot
        keys.add(count,middleVal); 
        links.add(count+1,(long) (nodeCount * incrementSize));
        // i will need to send per the incrament size
        tree.per.write(right);
    }//end split

    //look over how i write to splits
    public void rootSplit(int nodeCount) throws IOException{
        int leftCount = nodeCount -1;
        long offLeft = (leftCount * incrementSize);
        long offRight = (nodeCount * incrementSize);
        Node myLeft = makeNewLeft();
        Node myRight = makeNewRight();
        if(!links.isEmpty()){
            addLeftLinks(myLeft); 
            addRightLinks(myRight);
        }
        hookLinks(offLeft,offRight);

        //send in the new incrament size
        temp.add(myLeft);
        temp.add(myRight);
        //tree.per.write(myLeft);
        //tree.per.write(myRight);
    }//end split root

    private Node makeNewLeft(){
        int mid = middle;
        Node left = new Node(); 
        //get all the left keys
        for(int i =0; i < mid;i++){
            left.keys.add(keys.remove(i));
        }//end for
        return left;
    }// end makeNewLeft

    private void addLeftLinks(Node left){
        int mid = middle+1; 
        for(int i =0; i<mid;i++){
            left.links.add(links.remove(0));
        }//end for
    }//end add left links

    private Node makeNewRight(){
        Node right = new Node();
        //get all the keys from the right
        while(keys.size() >1){
            right.keys.add(keys.remove(1));
        }
        return right;
    }// end makeNewRight

    private void addRightLinks(Node right){
            right.links.addAll(links);
            links.clear();
    }//end add right links

    // this needs to take in the incrament size
    private void hookLinks(long offleft,long offright){
        links.add(offleft);
        links.add(offright);
    }

    public void internalRepair(int count) throws ClassNotFoundException, IOException{
        Node temp,temp2;
         long nodeLocA = links.get(count);
        temp =  tree.per.read(nodeLocA);
        goRightRepair(temp,count+1);
        for(int i = 0; i < links.size();i++){
            long nodeLocB = links.get(i);
            temp2 = tree.per.read(nodeLocB);
            if(temp2.minSize()){
                repair(i);
                i = 0;
                tree.per.write(temp2);
            }
        }
    }// end internalRepair

    //will repair upto the internal node
    public void goRightRepair(Node myNode,int count) throws ClassNotFoundException, IOException{
        if(myNode.isLeaf()){
            return;
        }//end if
        else{
            goRightRepair(tree.per.read(myNode.links.get(count)),count);
            Node temp;
            for(int i = 0; i < links.size();i++){
                long nodeLocA = links.get(i);
                temp = tree.per.read(nodeLocA);
                if(temp.minSize()){
                    repair(i);
                    i = 0;
                    tree.per.write(temp);

                }
            }
        }
    }

    public void repair(int count) throws ClassNotFoundException, IOException{
        //write node back to file
        Node temp = new Node(); 
        Node temp2 = new Node();
        long nodeLocA = links.get(count -1);
        long nodeLocB = links.get(count +1);
        temp = tree.per.read(nodeLocA);
        temp2 = tree.per.read(nodeLocB);
        if(count != 0 && temp.keys.size() > middle ){
            rotateLeft(count);
            tree.per.write(temp);
        }
        else if(temp2.keys.size() > middle){
            rotateRight(count);
            tree.per.write(temp2);
        }
        else{
            merge(count);
        }
    }// end steal
    // need to get the link before i remove the key---error
    private void rotateLeft(int count) throws ClassNotFoundException, IOException{
        String parentKey;
        String replaceKey;
        Node temp;
        Node temp2;
        long nodeLocA = links.get(count -1);
        long nodeLocB = links.get(count);
        int apple =tree.per.read(nodeLocA).keys.size()-1;

        //get the link to the deficient right node
        temp2 = tree.per.read(nodeLocA);
        temp = tree.per.read(nodeLocB);

        // the parent key
        parentKey = keys.remove(count -1 );
        // parent key is placed in deficient right node brining it to minimum
        temp.keys.add(0,parentKey);
        // get the key from the over full left node
        replaceKey = temp2.keys.remove(apple);

        //put the new key in the proper spot.
        keys.add(count -1,replaceKey);

        //write node back to file
        tree.per.write(temp);
        tree.per.write(temp2);
    }

    private void rotateRight(int count) throws ClassNotFoundException, IOException{
        String parentKey;
        String replaceKey;
        long nodeLocA = links.get(count); 
        long nodeLocB = links.get(count+1);
        Node temp = tree.per.read(nodeLocA);
        Node temp2 = tree.per.read(nodeLocB);
        //the parent key
        parentKey = keys.remove(count);
        //parent key is placed in deficient left node brining it to minimum
        temp.keys.add(parentKey);
        //get the key from the over full right node
        replaceKey = temp2.keys.remove(0);
        //put the new key in the proper spot 
        keys.add(count,replaceKey);

        //write node back to file
        tree.per.write(temp);
        tree.per.write(temp2);
    }

    private void merge(int count) throws ClassNotFoundException, IOException{
        String parentKey;
        Node temp,temp2;
        long nodeLocA = links.get(count+1);
        long nodeLocB = links.get(count);

        temp = tree.per.read(nodeLocA);
        temp2 = tree.per.read(nodeLocB);
        //get the parentKey
        parentKey = keys.remove(count);

        //put parentKey into right link 
        temp.keys.add(0,parentKey);
            // put left values into right values
        for(String s: temp2.keys) {
            temp.keys.add(0,s);
        }// end for
            //left links go into rights links
        for(long Link: temp2.links){
                temp.links.add(0,Link);
        }// end for

        links.remove(count);

        tree.per.write(temp);
    }// end merge

    public String predacessor(int count) throws ClassNotFoundException, IOException{
        long nodeLocA = links.get(count);
        Node temp = tree.per.read(nodeLocA);
        return goRight(temp,count+1);
    }

    public String goRight(Node myNode,int count) throws ClassNotFoundException, IOException{
        String toReturn;
        if(myNode.isLeaf()){
        toReturn = myNode.keys.remove(myNode.keys.size()-1);
        }//end if
        else{
            toReturn = goRight(tree.per.read(myNode.links.get(count)),count);
        }
        return toReturn;
    }
    public boolean minSize(){
        boolean result; 
        if(keys.size() < MAXKEYS/2){
            result = true;
        }
        else{ 
            result = false;
        }
        return result;
    }// end minSize
    public void setStartIndex(long startIndex){
        this.startIndex = startIndex;
    }
    public long getStartIndex(){
        return startIndex;
    }
    public ArrayList<Node> getNode(){
        return temp;
    }
}//end node

Answer 1

Thanks EJP for the tips. I came across this bit of code while googling

import java.io.RandomAccessFile;
import java.io.IOException;
import java.io.Serializable;

/**
 * John 
 * Fall 2012
 */ 

public class FLRAF extends RandomAccessFile implements Serializable {
    private int blockSize;

    public FLRAF(int blockSize, String file) throws IOException {
        super(file, "rw");
        this.blockSize = blockSize;
    }

    public byte[] read(int blockNumber) throws IOException {
        seek(blockNumber*blockSize);
        byte[] b = new byte[blockSize];
        read(b);
        return b;
    }

    public void write(byte[] b, int blockNumber) throws IOException {
        seek(blockNumber*blockSize);
        write(b);
        return;
    }
} 

I ran some tests on this code and was able to write and read a node properly. I don't think that serializing entire objects is what I was supposed to do. So thanks Again EJP and everyone that helped!!!

Answer 2

First thing I would try is to narrow down where the problem is. Is it in the serialization or writing the file. My first test is to write to a byte array and then read from the same array.

public class Persistance implements Serializable {
    .....
    public void test(Node node) throws IOException{
        ByteArrayOutputStream b2= new ByteArrayOutputStream();
        ObjectOutput out2 = new ObjectOutputStream(b2);
        out2.writeObject(node);
        out2.close();
        byte[] array2 = b.toByteArray();
        ByteArrayInputStream in2 = new ByteArrayInputStream(array2);
        ObjectInputStream OIS2 = new ObjectInputStream(in2);
        Node temp = (Node) OIS2.readObject();
        OIS2.close(); 
    }
    .....
}

If that works then its a problem with your random access files. Some things to check, does writing and then reading a sequence of bytes give exactly the same sequence of bytes. If your writing to the middle of a file are there bytes following what you have just written. Are the offsets for writing and reading the same.

It should not matter about the node size. The serialisation and deserialisation of the of various ArrayLists should work what ever the size. What you could do is write to a byte array find out the length using the count field. Then when you write to the file first write the number of bytes then the array of bytes. To read first read the number of bytes, then read that many bytes.

ByteArrayOutputStream b2= new ByteArrayOutputStream();
ObjectOutput out2 = new ObjectOutputStream(b2);
out2.writeObject(node);
out2.close();
byte[] array2 = b2.toByteArray();
int length = array2.length;

raf.writeInt(length);
raf.write(array2);

To read

int length = raf.readInt();
byte inArray[] = new byte[length];
raf.read(inArray,0,length);

ByteArrayInputStream in2 = new ByteArrayInputStream(inArray);
ObjectInputStream OIS2 = new ObjectInputStream(in2);
Node temp = (Node) OIS2.readObject();
OIS2.close();