我想要在前面,所以我会说这个我即将谈论的作业.我们假设做一个B +树.我已经完成了大部分工作,但是当我有节点拆分时我遇到了问题.特别是当节点是非叶子(不包括根)并且它分裂时,我失去了我的最右边的指针.
例如,如果树是
|3 5|
|1 2| |4| |5 6|
我失去了指针|5 6|.因此,当我搜索这些值时,我找不到它们,或者当我去添加一个跟随该路径的值时,我得到一个空指针异常.
无论如何,我通常会只贴上我的代码在这里,但不幸的是,我们已经开发与我校作弊,因为该方案即将到期,我相信有很多同学都在网上淘的代码有问题.我想要发生的最后一件事是一些混蛋扯掉我的代码.
如果有人不介意查看代码,我很乐意将它发送给您查看.它再次使用Java并且非常冗长.
提前致谢.
这是代码.在侧节点当我清除偏移和键时,我使用int和long MAX_VALUE,所以当我排序时,我知道那些清除的值将转到节点的末尾.从我之前需要解决的问题来看,Split类只是一个愚蠢的想法.它由节点,偏移量和密钥组成.最初我以为我可能需要返回一个不在拆分节点中的偏移和键.然后我意识到这是愚蠢的,我需要返回的只是新节点本身.
public void add (int key, long offset) throws IOException
{
if (root != null) //start search of where to add the book
{
SplitBucket split = add(root, key, offset); //recursive call
if (split != null) //root has split
{
long newRootOffset;
//make new root and have it point to old root and the split node
BookNode newRoot = new BookNode();
newRoot.changeCurrentChildren(1);
newRoot.setChildKey(0, split.key);
newRoot.setChildOffset(0, root.getMyOffset());
newRoot.setChildOffset(1, split.offset);
newRoot.setChildOffset(2,
root.getChildOffset(Constants.childSize -1));
newRoot.setNode(0, root);
newRoot.setNode(1, split.node);
newRoot.setNode(2, root.getNode(Constants.childSize - 1));
io.setBookNode(root.getMyOffset(), root);
newRootOffset = io.insertNewNode(newRoot);
io.setRoot(newRootOffset);
root = newRoot;
}
}
else //empty tree so create root and add
{
long rootOffset = Long.MAX_VALUE;
root = new BookNode();
root.setChildKey(0, key);
root.setChildOffset(0, offset);
root.changeCurrentChildren(1);
root.switchLeaf(true);
rootOffset = io.insertNewNode(root);
io.setRoot(rootOffset);
root.setMyOffset(rootOffset);
}
}
/**
*
* @param current current BookNode
* @param key Isbn to add
* @param offset offset of Book to add
* @return BookNode if a split occurs
* @throws IOException
*/
private SplitBucket add (BookNode current, int key, long offset)
throws IOException
{
if (current.isLeaf()) // at the bottom level
{
//room to add
if (current.getCurrentChildren() < Constants.childSize - 1)
{
//add the offset and key to the end of the node.
//sort the node and rewrite to file
current.setChildOffset(current.getCurrentChildren(), offset);
current.setChildKey(current.getCurrentChildren(), key);
current.changeCurrentChildren(1);
current.sortKeysAndOffsets();
io.setBookNode(current.getMyOffset(), current);
return null;
}
else //not enough room must split
{ //add offset and key to end of node and sort
current.setChildKey(current.getCurrentChildren(), key);
current.setChildOffset(current.getCurrentChildren(), offset);
current.changeCurrentChildren(1);
current.sortKeysAndOffsets();
int start = current.getCurrentChildren() / 2;
long newNodeOffset =Long.MAX_VALUE;
SplitBucket bucket = new SplitBucket();
BookNode newNode = new BookNode();
newNode.switchLeaf(true);
for(int i = start; i < Constants.childSize; i++)
{
//new node will hold the larger split values
newNode.setChildKey(i - start, current.getChildKey(i));
newNode.setChildOffset(i - start, current.getChildOffset(i));
newNode.setNode(i - start, current.getNode(i));
newNode.changeCurrentChildren(1);
current.setChildKey(i, Integer.MAX_VALUE);
current.setChildOffset(i, Long.MAX_VALUE);
current.setNode(i, null);
current.changeCurrentChildren(-1);
}
//since sorted prior to for loop all data
//needs not to be sorted again
newNode.sortKeysAndOffsets();
current.sortKeysAndOffsets();
//Transferring pre-split nodes 'next' pointer to new node
newNode.setChildOffset(Constants.childSize,
current.getChildOffset(Constants.childSize));
newNode.setNode(Constants.childSize,
current.getNode(Constants.childSize));
newNodeOffset = io.insertNewNode(newNode);
newNode.setMyOffset(newNodeOffset);
current.setChildOffset(Constants.childSize, newNodeOffset);
current.setNode(Constants.childSize, newNode);
io.setBookNode(current.getMyOffset(), current);
bucket.key = newNode.getChildKey(0);
bucket.offset = newNode.getMyOffset();
bucket.node = newNode;
return bucket;
}
}
else //not at a leaf
{
int index = 0;
//find pointer index to follow
while (index < current.getCurrentChildren()
&& key >= current.getChildKey(index))
{
index++;
}
//recursive call
SplitBucket bucket = add(current.getNode(index), key, offset);
if(bucket != null) //split occurred
{
//bucket not full so add here
if(current.getCurrentChildren() < Constants.childSize)
{
current.setChildKey(current.getCurrentChildren(), bucket.key);
current.setChildOffset(current.getCurrentChildren(),
bucket.offset);
current.setNode(current.getCurrentChildren(), bucket.node);
current.changeCurrentChildren(1);
current.sortKeysAndOffsets();
io.setBookNode(current.getMyOffset(), current);
bucket = null;
}
else //bucket is full so split
{
int start = current.getCurrentChildren() / 2;
long newNodeOffset = Long.MAX_VALUE;
BookNode newNode = new BookNode();
for(int i = start; i < Constants.childSize; i++)
{
//larger keys go to the new node
newNode.setChildKey(i - start, current.getChildKey(i));
newNode.setChildOffset(i - start,
current.getChildOffset(i));
newNode.setNode(i - start, current.getNode(i));
newNode.changeCurrentChildren(1);
current.setChildKey(i, Integer.MAX_VALUE);
current.setChildOffset(i, Long.MAX_VALUE);
current.setNode(i, null);
current.changeCurrentChildren(-1);
}
if(bucket.key > newNode.getChildKey(0)) //goes in new bucket
{
newNode.setChildKey(newNode.getCurrentChildren(),
bucket.key);
newNode.setChildOffset(newNode.getCurrentChildren(),
bucket.offset);
newNode.setNode(newNode.getCurrentChildren(),
bucket.node);
newNode.changeCurrentChildren(1);
newNode.sortKeysAndOffsets();
}
else //goes in old bucket
{
current.setChildKey(current.getCurrentChildren(),
bucket.key);
current.setChildOffset(current.getCurrentChildren(),
bucket.offset);
current.setNode(current.getCurrentChildren(),
bucket.node);
current.changeCurrentChildren(1);
current.sortKeysAndOffsets();
}
//may not need this line and next
newNode.setChildOffset(newNode.getCurrentChildren(),
current.getChildOffset(Constants.childSize));
newNode.setNode(newNode.getCurrentChildren(),
current.getNode(Constants.childSize));
newNodeOffset = io.insertNewNode(newNode);
newNode.setMyOffset(newNodeOffset);
io.setBookNode(current.getMyOffset(), current);
bucket = new SplitBucket();
//return middle key value of split node
bucket.key = newNode.getChildKey(
newNode.getCurrentChildren() /2);
bucket.offset = newNode.getMyOffset();
bucket.node = newNode;
return bucket;
}
}
}
return null;
}
为失败的测试编写一个测试用例或“主要”方法。然后你可以断点并调试这种情况。
将日志记录放入您的代码中，以输出重要/决定性的信息及其正在执行的操作 - 这样您就可以看到哪里出了问题。
如果您不喜欢日志记录，则可以单步执行并调试。不过，它不如使用日志记录来调试和设计代码那么高效/高效。
| 归档时间： |
|
| 查看次数： |
1315 次 |
| 最近记录： |