将B树节点持久化到RandomAccessFile [英] Persisting B-Tree nodes to RandomAccessFile
本文介绍了将B树节点持久化到RandomAccessFile的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我的项目正在尝试编写B树.我在将树的节点持久保存到随机访问文件时遇到麻烦.我经常遇到EOFexceptions和StreamCorruptionExceptions.
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:
https://inaved-momin.blogspot.com/2012/08/understanding-javaiostreamcorruptedexce.html
当前问题:从节点读取链接位置，然后尝试从随机访问文件中读取链接位置会导致StreamCorruptionExceptions.
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
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
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
推荐答案
感谢EJP的提示.我在谷歌搜索时碰到了这段代码
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;
}
}
我对此代码进行了一些测试，并且能够正确地读写节点.我不认为序列化整个对象是我应该做的.因此，再次感谢EJP和所有提供帮助的人！！！
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!!!
这篇关于将B树节点持久化到RandomAccessFile的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
