将B树节点保留为RandomAccessFile
我的项目正在尝试编写B树。 我无法将树的节点保存到随机访问文件。 我经常遇到EOFexceptions和StreamCorruptionExceptions 。
我目前使用的一些资源是：
在java中将任何对象转换为字节数组
https://inaved-momin.blogspot.com/2012/08/understanding-javaiostreamcorruptedexce.html
当前问题：从节点读取链接位置然后尝试从随机访问文件中读取它会导致StreamCorruptionExceptions 。
目标：能够访问随机访问文件中的所有节点，修改并将其写回随机访问文件。
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 testWords = new ArrayList(); 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{ ArrayListnodeList = new ArrayList(); 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 temp = new ArrayList(); final int MAXKEYS = 3; //31 final int middle = MAXKEYS/2; ArrayList keys = new ArrayList(); ArrayList links = new ArrayList(); 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; i1){ 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 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 getNode(){ return temp; } }//end node
我要尝试的第一件事就是缩小问题所在。 是在序列化还是写入文件。 我的第一个测试是写入一个字节数组，然后从同一个数组中读取。
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(); } ..... }
如果这有效，那么随机访问文件就会出现问题。 要检查的一些事情，写入然后读取字节序列给出完全相同的字节序列。 如果您在文件中间的写入是在您刚刚编写的内容之后的字节。 写作和阅读的偏移量是否相同。
节点大小无关紧要。 各种ArrayLists的序列化和反序列化应该适用于任何大小。 您可以做的是写入一个字节数组，使用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();
感谢EJP的提示。 我在谷歌搜索时遇到了这段代码
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; } }
我对这段代码进行了一些测试，并且能够正确地编写和读取节点。 我不认为序列化整个对象是我应该做的。 所以再次感谢EJP和所有帮助过的人！