java - 将 B 树节点持久保存到 RandomAccessFile

Question

我的项目正在尝试编写 B 树。我在将树的节点持久保存到随机访问文件时遇到问题。我经常遇到 EOFExceptions 和 StreamCorruptionExceptions。

我当前使用的一些资源是:

Converting any object to a byte array in java

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

当前问题:从节点读取链接位置，然后尝试从随机访问文件中读取它会导致 StreamCorruptionExceptions。

目标:能够访问随机访问文件中的所有节点，修改并写回到随机访问文件中。

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

我首先要尝试的是缩小问题的范围。是在序列化还是在写文件。我的第一个测试是写入字节数组，然后从同一数组中读取。

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(); 
    }
    .....
}

如果有效，那么它是您的随机访问文件的问题。有些事情需要检查，写入然后读取字节序列是否会给出完全相同的字节序列。如果您写入文件的中间，则在您刚刚写入的内容之后会有字节。写入和读取的偏移量是否相同。

节点大小应该不重要。无论大小如何，各种 ArrayList 的序列化和反序列化都应该有效。您可以做的是写入字节数组并使用 count 字段找出长度。然后，当您写入文件时，首先写入字节数，然后写入字节数组。要读取，首先读取字节数，然后读取那么多字节。

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);

阅读

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();