B+树分裂错误

Question

我想事先说明，我要谈论的是一份作业。我们应该做一个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;
}

- Pinsickle

---

最好在这里粘贴你的节点拆分代码。这样作为同学们自己的作业是不够的，如果他们犯了和你一样的错误 :) 至少他们也可以从你的问题中学习到东西。此外，在考试期间，如果他们被要求编写非平凡的程序，他们将会被发现作弊... - sarnold

@Pinsickle说：“但我会在发布内容时附上源代码。在这个网站上，每个问题都应该对不仅是提问者，而且对其他试图解决类似问题的人有用。如果不包括源代码，就完全背离了这个目的。” - akappa

真的，我同意。通常我会发布源代码，我只是有点担心这门课程。我们的教授今天跟我们谈到了相似程序的惊人数量。我相信我的教授们知道我不是个作弊者，因为我总是能够解释我的逻辑，但我从来不希望别人从我的工作中获利。 - Pinsickle

是的，它肯定需要被拆分。我可能会暂时停止寻找错误，并开始将其拆分为方法。也许当我重新排列代码时，我会偶然发现这个错误。我以前就遇到过这种情况。 - Pinsickle

没有丢失 BookNode 和 SplitBucket 的代码......在我的 Eclipse 中真的很难找到/重现这个 bug！;-) - ggrandes

Answer 1

编写一个测试用例或“main”方法，用于失败的测试。然后您可以断点和调试该情况。

在您的代码中加入日志记录，以输出重要/决定性信息和它正在执行的事情-这样您就可以看到它出了什么问题。

不要记录无趣的东西-记录API调用、正在创建/更新的节点和哪些键范围正在被拆分。记录真正告诉您正在发生什么的内容。

如果您不喜欢日志记录，可以逐步调试。但与使用日志记录进行调试和工程代码相比，效率和生产力都会降低。

- Thomas W