B+ Tree split bug

Question

I want to be up front so I will say this homework that I am about to talk about. We are suppose to do a B+ tree. I've got it most of the way there but I am having a problem when I have a node split. Specifically when the node is a non-leaf (excluding the root) and it splits I am losing my far right pointer.

For example if the tree was

                          |3 5|

           |1 2|           |4|           |5 6|

I lose the pointer to |5 6|. So when I search for those values I cannot find them or when I go to add a value that would follow that path I get a null pointer exception.

Anyway I normally would just paste my code here but, unfortunately, we have developed a problem with cheating in my school and since the program is due soon, I am sure a lot of my classmates are scouring the internet for the code. The last thing I want to happen is some jerk rip off my code.

If anyone wouldn't mind looking at the code I will gladly send it to you to check out. Once again it is in Java and is pretty lengthy.

Thanks in advance.

Here is the code. On a side node When I clear offsets and keys I use int and long MAX_VALUE so when I sort I know those cleared values will go to the end of the node. The Split class is just a dumb idea from earlier I need to fix. It consists of a node, offset, and key. Originally I was thinking that I may need to return an offset and key that wasn't in the split node. I then realized that was dumb and all I would ever need to return was the new node itself.

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

Write a test case, or a 'main' method, for the test that fails. Then you can breakpoint & debug just that situation.

Put logging in your code, to output the important/ decisive information & things it's doing -- so you can see where it's going wrong.

Don't log uninteresting stuff -- log the API calls, which nodes are being created/ updated & which key ranges are being split. Log what really tells you what's going on.

If you don't like logging, you step thru & debug. It's not as efficient/ productive as using logging to debug & engineer your code, though.