public <V> Object[] update(Object[] btree, Comparator<V> comparator, Iterable<V> source, UpdateFunction<V> updateF)
    {
        assert updateF != null;

        NodeBuilder current = rootBuilder;
        current.reset(btree, POSITIVE_INFINITY, updateF, comparator);

        for (V key : source)
        {
            while (true)
            {
                if (updateF.abortEarly())
                {
                    rootBuilder.clear();
                    return null;
                }
                NodeBuilder next = current.update(key);
                if (next == null)
                    break;
                // we were in a subtree from a previous key that didn't contain this new key;
                // retry against the correct subtree
                current = next;
            }
        }

        // finish copying any remaining keys from the original btree
        while (true)
        {
            NodeBuilder next = current.finish();
            if (next == null)
                break;
            current = next;
        }

        // updating with POSITIVE_INFINITY means that current should be back to the root
        assert current.isRoot();

        Object[] r = current.toNode();
        current.clear();
        return r;
    }
public < V > Object [ ] update ( Object [ ] btree , Comparator < V > comparator , Iterable < V > source , UpdateFunction < V > updateF ) { assert updateF != null ; NodeBuilder current = rootBuilder ; current . reset ( btree , POSITIVE_INFINITY , updateF , comparator ) ; for ( V key : source ) { while ( true ) { if ( updateF . abortEarly ( ) ) { rootBuilder . clear ( ) ; return null ; } NodeBuilder next = current . update ( key ) ; if ( next == null ) break ; current = next ; } } while ( true ) { NodeBuilder next = current . finish ( ) ; if ( next == null ) break ; current = next ; } assert current . isRoot ( ) ; Object [ ] r = current . toNode ( ) ; current . clear ( ) ; return r ; }
At the highest level, we adhere to the classic b-tree insertion algorithm:

1. Add to the appropriate leaf
2. Split the leaf if necessary, add the median to the parent
3. Split the parent if necessary, etc.

There is one important difference: we don't actually modify the original tree, but copy each node that we
modify.  Note that every node on the path to the key being inserted or updated will be modified; this
implies that at a minimum, the root node will be modified for every update, so every root is a "snapshot"
of a tree that can be iterated or sliced without fear of concurrent modifications.

The NodeBuilder class handles the details of buffering the copied contents of the original tree and
adding in our changes.  Since NodeBuilder maintains parent/child references, it also handles parent-splitting
(easy enough, since any node affected by the split will already be copied into a NodeBuilder).

One other difference from the simple algorithm is that we perform modifications in bulk;
we assume @param source has been sorted, e.g. by BTree.update, so the update of each key resumes where
the previous left off.