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

Answer 1

为失败的测试编写一个测试用例或“主要”方法。然后你可以断点&调试这种情况。

将日志记录放入您的代码中，以输出重要/决定性的信息和信息。它正在做的事情——这样你就可以看到哪里出了问题。

不要记录无趣的内容——记录 API 调用、正在创建/更新的节点以及正在创建的节点。正在分割哪些关键范围。记录真正告诉您正在发生的事情。

如果您不喜欢日志记录，可以单步执行并查看日志。调试。它不如使用日志记录来调试和生产那么高效/高效。不过，设计你的代码。