directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1527458 [10/14] - in /directory/mavibot/trunk/mavibot: img/ src/main/java/org/apache/directory/mavibot/btree/ src/main/java/org/apache/directory/mavibot/btree/managed/ src/main/java/org/apache/directory/mavibot/btree/memory/ src/main/java/...
Date Mon, 30 Sep 2013 06:32:28 GMT
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ModifyResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ModifyResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ModifyResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ModifyResult.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,104 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import java.util.List;
+
+
+/**
+ * The result of an insert operation, when the child has not been split. It contains the
+ * reference to the modified page.
+ * 
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier */class ModifyResult<K, V> extends AbstractResult<K, V> implements InsertResult<K, V>
+{
+    /** The modified page reference */
+    protected Page<K, V> modifiedPage;
+
+    /** The modified value if the key was found in the tree*/
+    protected V modifiedValue;
+
+
+    /**
+     * The default constructor for ModifyResult.
+     * 
+     * @param modifiedPage The modified page
+     * @param modifiedvalue The modified value (can be null if the key wasn't present in the tree)
+     */
+    /* No qualifier */ModifyResult( Page<K, V> modifiedPage, V modifiedValue )
+    {
+        super();
+        this.modifiedPage = modifiedPage;
+        this.modifiedValue = modifiedValue;
+    }
+
+
+    /**
+     * A constructor for ModifyResult which takes a list of copied pages.
+     * 
+     * @param copiedPages the list of copied pages
+     * @param modifiedPage The modified page
+     * @param modifiedvalue The modified value (can be null if the key wasn't present in the tree)
+     */
+    /* No qualifier */ModifyResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage, V modifiedValue )
+    {
+        super( copiedPages );
+        this.modifiedPage = modifiedPage;
+        this.modifiedValue = modifiedValue;
+    }
+
+
+    /**
+     * @return the modifiedPage
+     */
+    /* No qualifier */Page<K, V> getModifiedPage()
+    {
+        return modifiedPage;
+    }
+
+
+    /**
+     * @return the modifiedValue
+     */
+    /* No qualifier */V getModifiedValue()
+    {
+        return modifiedValue;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "ModifyResult, old value = " ).append( modifiedValue );
+        sb.append( ", modifiedPage = " ).append( modifiedPage );
+        sb.append( super.toString() );
+
+        return sb.toString();
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MultipleMemoryHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MultipleMemoryHolder.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MultipleMemoryHolder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MultipleMemoryHolder.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,178 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import java.io.IOException;
+import java.lang.ref.SoftReference;
+import java.util.UUID;
+
+
+/**
+ * A holder for values of duplicate keys. The values are either present in memory
+ * or loaded on the fly from disk when needed.
+ * 
+ * @param <K> The type of the BTree key
+ * @param <V> The type of the BTree value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class MultipleMemoryHolder<K, V> implements ElementHolder<V, K, V>
+{
+    /** The BTree */
+    private BTree<K, V> btree;
+
+    /** the offset of the value container btree. This value is set only when the parent BTree is in managed mode */
+    private long valContainerOffset = -1;
+
+    /** The reference to the Value instance, or null if it's not present. This will be null when the parent BTree is in managed mode */
+    private BTree<V, V> valueContainer;
+
+    /** This value is set only when the parent BTree is in managed mode */
+    private SoftReference<BTree<V, V>> reference;
+
+    /** the single value of the key when only one value exists for the key */
+    private V singleValue;
+
+
+    /**
+     * Create a new holder storing an offset and a SoftReference containing the value.
+     * 
+     * @param offset The offset in disk for this value
+     * @param value The value to store into a SoftReference
+     */
+    public MultipleMemoryHolder( BTree<K, V> btree, V value )
+    {
+        this.btree = btree;
+        this.singleValue = value;
+    }
+
+
+    /**
+     * 
+     * Creates a new instance of DuplicateKeyMemoryHolder.
+     * 
+     * Note: the valueContainer should have a valid offset, in other words
+     *       the valueContainer should always be the one that is already
+     *       managed by RecordManager
+     * 
+     * @param btree the parent BTree
+     * @param valueContainer the BTree holding the values of a duplicate key
+     *        present in the parent tree
+     */
+    MultipleMemoryHolder( BTree<K, V> btree, BTree<V, V> valueContainer )
+    {
+        this.btree = btree;
+        this.valueContainer = valueContainer;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public V getValue( BTree<K, V> btree )
+    {
+        if ( valueContainer != null )
+        {
+            // wrong cast to please compiler
+            return ( V ) valueContainer;
+        }
+        else
+        {
+            return singleValue;
+        }
+    }
+
+
+    void switchToSingleValMode()
+    {
+        if ( ( valueContainer == null ) || ( reference == null ) )
+        {
+            return;
+        }
+
+        try
+        {
+            //delete the btree using offset
+            singleValue = valueContainer.rootPage.getLeftMostKey();
+            valueContainer = null;
+        }
+        catch ( IOException e )
+        {
+            throw new RuntimeException( e );
+        }
+    }
+
+
+    BTree<V, V> createAndSwitchToSubTree()
+    {
+        if ( reference != null )
+        {
+            throw new IllegalStateException( "Subtree was already created with offset " + valContainerOffset );
+        }
+
+        try
+        {
+            BTree<V, V> valueContainer = new BTree<V, V>( UUID.randomUUID().toString(), btree.getValueSerializer(),
+                btree.getValueSerializer() );
+
+            this.valueContainer = valueContainer;
+
+            valueContainer.insert( singleValue, null, 0 );
+        }
+        catch ( IOException e )
+        {
+            throw new RuntimeException( e );
+        }
+
+        return valueContainer;
+    }
+
+
+    /**
+     * Tells if there is only one value in this element holder
+     * 
+     * @return true if single value is present, false if multiple values are present
+     */
+    public boolean isSingleValue()
+    {
+        return ( valueContainer == null );
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "'" );
+
+        V value = getValue( btree );
+
+        sb.append( value );
+
+        sb.append( "'" );
+
+        return sb.toString();
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,1318 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import java.io.IOException;
+import java.lang.reflect.Array;
+import java.util.LinkedList;
+import java.util.List;
+
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+
+
+/**
+ * A MVCC Node. It stores the keys and references to its children page. It does not
+ * contain any value.
+ * 
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier */class Node<K, V> extends AbstractPage<K, V>
+{
+    /** Children pages associated with keys. */
+    protected ElementHolder<Page<K, V>, K, V>[] children;
+
+
+    /**
+     * Creates a new Node which will contain only one key, with references to
+     * a left and right page. This is a specific constructor used by the btree
+     * when the root was full when we added a new value.
+     * 
+     * @param btree the parent BTree
+     * @param revision the Node revision
+     * @param nbElems The number of elements in this Node
+     */
+    @SuppressWarnings("unchecked")
+    /* No qualifier */Node( BTree<K, V> btree, long revision, int nbElems )
+    {
+        super( btree, revision, nbElems );
+
+        // Create the children array
+        children = ( ElementHolder<Page<K, V>, K, V>[] ) Array.newInstance( ElementHolder.class, nbElems + 1 );
+    }
+
+
+    /**
+     * Creates a new Node which will contain only one key, with references to
+     * a left and right page. This is a specific constructor used by the btree
+     * when the root was full when we added a new value.
+     * 
+     * @param btree the parent BTree
+     * @param revision the Node revision
+     * @param key The new key
+     * @param leftPage The left page
+     * @param rightPage The right page
+     */
+    @SuppressWarnings("unchecked")
+    /* No qualifier */Node( BTree<K, V> btree, long revision, K key, Page<K, V> leftPage, Page<K, V> rightPage )
+    {
+        super( btree, revision, 1 );
+
+        // Create the children array, and store the left and right children
+        children = ( MemoryHolder[] ) Array.newInstance( MemoryHolder.class,
+            btree.getPageSize() + 1 );
+
+        children[0] = btree.createPageHolder( leftPage );
+        children[1] = btree.createPageHolder( rightPage );
+
+        // Create the keys array and store the pivot into it
+        // We get the type of array to create from the btree
+        // Yes, this is an hack...
+        Class<?> keyType = btree.getKeyType();
+        keys = ( K[] ) Array.newInstance( keyType, btree.getPageSize() );
+
+        keys[0] = key;
+    }
+
+
+    /**
+     * Creates a new Node which will contain only one key, with references to
+     * a left and right page. This is a specific constructor used by the btree
+     * when the root was full when we added a new value.
+     * 
+     * @param btree the parent BTree
+     * @param revision the Node revision
+     * @param key The new key
+     * @param leftPage The left page
+     * @param rightPage The right page
+     */
+    @SuppressWarnings("unchecked")
+    /* No qualifier */Node( BTree<K, V> btree, long revision, K key, ElementHolder<Page<K, V>, K, V> leftPage,
+        ElementHolder<Page<K, V>, K, V> rightPage )
+    {
+        super( btree, revision, 1 );
+
+        // Create the children array, and store the left and right children
+        children = ( ElementHolder<Page<K, V>, K, V>[] ) Array.newInstance( MemoryHolder.class,
+            btree.getPageSize() + 1 );
+
+        children[0] = leftPage;
+        children[1] = rightPage;
+
+        // Create the keys array and store the pivot into it
+        // We get the type of array to create from the btree
+        // Yes, this is an hack...
+        Class<?> keyType = btree.getKeyType();
+        keys = ( K[] ) Array.newInstance( keyType, btree.getPageSize() );
+
+        keys[0] = key;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public InsertResult<K, V> insert( long revision, K key, V value ) throws IOException
+    {
+        // Find the key into this leaf
+        int pos = findPos( key );
+
+        if ( pos < 0 )
+        {
+            // The key has been found in the page. As it's a Node, that means
+            // we must go down in the right child to insert the value
+            pos = -( pos++ );
+        }
+
+        // Get the child page into which we will insert the <K, V> tuple
+        Page<K, V> child = children[pos].getValue( btree );
+
+        // and insert the <K, V> into this child
+        InsertResult<K, V> result = child.insert( revision, key, value );
+
+        // Ok, now, we have injected the <K, V> tuple down the tree. Let's check
+        // the result to see if we have to split the current page
+        if ( result instanceof ModifyResult )
+        {
+            // The child has been modified.
+            return replaceChild( revision, ( ModifyResult<K, V> ) result, pos );
+        }
+        else
+        {
+            // The child has been split. We have to insert the new pivot in the
+            // current page, and to reference the two new pages
+            SplitResult<K, V> splitResult = ( SplitResult<K, V> ) result;
+            K pivot = splitResult.getPivot();
+            Page<K, V> leftPage = splitResult.getLeftPage();
+            Page<K, V> rightPage = splitResult.getRightPage();
+
+            // We have to deal with the two cases :
+            // - the current page is full, we have to split it
+            // - the current page is not full, we insert the new pivot
+            if ( nbElems == btree.getPageSize() )
+            {
+                // The page is full
+                result = addAndSplit( splitResult.getCopiedPages(), revision, pivot, leftPage, rightPage, pos );
+            }
+            else
+            {
+                // The page can contain the new pivot, let's insert it
+                result = insertChild( splitResult.getCopiedPages(), revision, pivot, leftPage, rightPage, pos );
+            }
+
+            return result;
+        }
+    }
+
+
+    /**
+     * Modifies the current node after a remove has been done in one of its children.
+     * The node won't be merged with another node.
+     * 
+     * @param removeResult The result of a remove operation
+     * @param index the position of the key, not transformed
+     * @param pos The position of the key, as a positive value
+     * @param found If the key has been found in the page
+     * @return The new result
+     * @throws IOException If we have an error while trying to access the page
+     */
+    private RemoveResult<K, V> handleRemoveResult( RemoveResult<K, V> removeResult, int index, int pos, boolean found )
+        throws IOException
+    {
+        // Simplest case : the element has been removed from the underlying page,
+        // we just have to copy the current page an modify the reference to link to
+        // the modified page.
+        Node<K, V> newPage = copy( revision );
+
+        Page<K, V> modifiedPage = removeResult.getModifiedPage();
+
+        if ( found )
+        {
+            newPage.children[index + 1] = createHolder( modifiedPage );
+        }
+        else
+        {
+            newPage.children[index] = createHolder( modifiedPage );
+        }
+
+        if ( pos < 0 )
+        {
+            newPage.keys[index] = removeResult.getModifiedPage().getLeftMostKey();
+        }
+
+        // Modify the result and return
+        removeResult.setModifiedPage( newPage );
+        removeResult.addCopiedPage( this );
+
+        return removeResult;
+    }
+
+
+    /**
+     * Handles the removal of an element from the root page, when two of its children
+     * have been merged.
+     * 
+     * @param mergedResult The merge result
+     * @param pos The position in the current root
+     * @param found Tells if the removed key is present in the root page
+     * @return The resulting root page
+     * @throws IOException If we have an error while trying to access the page
+     */
+    private RemoveResult<K, V> handleRootRemove( MergedWithSiblingResult<K, V> mergedResult, int pos, boolean found )
+        throws IOException
+    {
+        RemoveResult<K, V> removeResult = null;
+
+        // If the current node contains only one key, then the merged result will be
+        // the new root. Deal with this case
+        if ( nbElems == 1 )
+        {
+            removeResult = new RemoveResult<K, V>( mergedResult.getCopiedPages(), mergedResult.getModifiedPage(),
+                mergedResult.getRemovedElement() );
+
+            removeResult.addCopiedPage( this );
+        }
+        else
+        {
+            // Remove the element and update the reference to the changed pages
+            removeResult = removeKey( mergedResult, revision, pos );
+        }
+
+        return removeResult;
+    }
+
+
+    /**
+     * Borrows an element from the right sibling, creating a new sibling with one
+     * less element and creating a new page where the element to remove has been
+     * deleted and the borrowed element added on the right.
+     * 
+     * @param revision The new revision for all the pages
+     * @param sibling The right sibling
+     * @param pos The position of the element to remove
+     * @return The resulting pages
+     * @throws IOException If we have an error while trying to access the page
+     */
+    private DeleteResult<K, V> borrowFromRight( long revision, MergedWithSiblingResult<K, V> mergedResult,
+        Node<K, V> sibling, int pos ) throws IOException
+    {
+        // Create the new sibling, with one less element at the beginning
+        Node<K, V> newSibling = new Node<K, V>( btree, revision, sibling.getNbElems() - 1 );
+
+        K siblingKey = sibling.children[0].getValue( btree ).getLeftMostKey();
+
+        // Copy the keys and children of the old sibling in the new sibling
+        System.arraycopy( sibling.keys, 1, newSibling.keys, 0, newSibling.getNbElems() );
+        System.arraycopy( sibling.children, 1, newSibling.children, 0, newSibling.getNbElems() + 1 );
+
+        // Create the new page and add the new element at the end
+        // First copy the current node, with the same size
+        Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems );
+
+        // Copy the keys and the values up to the insertion position
+        int index = Math.abs( pos );
+
+        // Copy the key and children from sibling
+        newNode.keys[nbElems - 1] = siblingKey; // 1
+        newNode.children[nbElems] = sibling.children[0]; // 8
+
+        if ( index < 2 )
+        {
+            // Copy the keys
+            System.arraycopy( keys, 1, newNode.keys, 0, nbElems - 1 );
+
+            // Inject the modified page
+            Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+            newNode.children[0] = createHolder( modifiedPage );
+
+            // Copy the children
+            System.arraycopy( children, 2, newNode.children, 1, nbElems - 1 );
+        }
+        else
+        {
+            if ( index > 2 )
+            {
+                // Copy the keys before the deletion point
+                System.arraycopy( keys, 0, newNode.keys, 0, index - 2 ); // 4
+            }
+
+            // Inject the new modified page key
+            newNode.keys[index - 2] = mergedResult.getModifiedPage().getLeftMostKey(); // 2
+
+            if ( index < nbElems )
+            {
+                // Copy the remaining keys after the deletion point
+                System.arraycopy( keys, index, newNode.keys, index - 1, nbElems - index ); // 3
+
+                // Copy the remaining children after the deletion point
+                System.arraycopy( children, index + 1, newNode.children, index, nbElems - index ); // 7
+            }
+
+            // Copy the children before the deletion point
+            System.arraycopy( children, 0, newNode.children, 0, index - 1 ); // 5
+
+            // Inject the modified page
+            Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+            newNode.children[index - 1] = createHolder( modifiedPage ); // 6
+        }
+
+        // Create the result
+        DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>( mergedResult.getCopiedPages(), newNode,
+            newSibling, mergedResult.getRemovedElement() );
+
+        result.addCopiedPage( this );
+        result.addCopiedPage( sibling );
+
+        return result;
+    }
+
+
+    /**
+     * Borrows an element from the left sibling, creating a new sibling with one
+     * less element and creating a new page where the element to remove has been
+     * deleted and the borrowed element added on the left.
+     * 
+     * @param revision The new revision for all the pages
+     * @param sibling The left sibling
+     * @param pos The position of the element to remove
+     * @return The resulting pages
+     * @throws IOException If we have an error while trying to access the page
+     */
+    private DeleteResult<K, V> borrowFromLeft( long revision, MergedWithSiblingResult<K, V> mergedResult,
+        Node<K, V> sibling, int pos ) throws IOException
+    {
+        // The sibling is on the left, borrow the rightmost element
+        Page<K, V> siblingChild = sibling.children[sibling.nbElems].getValue( btree );
+
+        // Create the new sibling, with one less element at the end
+        Node<K, V> newSibling = new Node<K, V>( btree, revision, sibling.getNbElems() - 1 );
+
+        // Copy the keys and children of the old sibling in the new sibling
+        System.arraycopy( sibling.keys, 0, newSibling.keys, 0, newSibling.getNbElems() );
+        System.arraycopy( sibling.children, 0, newSibling.children, 0, newSibling.getNbElems() + 1 );
+
+        // Create the new page and add the new element at the beginning
+        // First copy the current node, with the same size
+        Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems );
+
+        // Sets the first children
+        newNode.children[0] = createHolder( siblingChild ); //1
+
+        int index = Math.abs( pos );
+
+        if ( index < 2 )
+        {
+            newNode.keys[0] = mergedResult.getModifiedPage().getLeftMostKey();
+            System.arraycopy( keys, 1, newNode.keys, 1, nbElems - 1 );
+
+            Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+            newNode.children[1] = createHolder( modifiedPage );
+            System.arraycopy( children, 2, newNode.children, 2, nbElems - 1 );
+        }
+        else
+        {
+            // Set the first key
+            newNode.keys[0] = children[0].getValue( btree ).getLeftMostKey(); //2
+
+            if ( index > 2 )
+            {
+                // Copy the keys before the deletion point
+                System.arraycopy( keys, 0, newNode.keys, 1, index - 2 ); // 4
+            }
+
+            // Inject the modified key
+            newNode.keys[index - 1] = mergedResult.getModifiedPage().getLeftMostKey(); // 3
+
+            if ( index < nbElems )
+            {
+                // Add copy the remaining keys after the deletion point
+                System.arraycopy( keys, index, newNode.keys, index, nbElems - index ); // 5
+
+                // Copy the remaining children after the insertion point
+                System.arraycopy( children, index + 1, newNode.children, index + 1, nbElems - index ); // 8
+            }
+
+            // Copy the children before the insertion point
+            System.arraycopy( children, 0, newNode.children, 1, index - 1 ); // 6
+
+            // Insert the modified page
+            Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+            newNode.children[index] = createHolder( modifiedPage ); // 7
+        }
+
+        // Create the result
+        DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( mergedResult.getCopiedPages(), newNode,
+            newSibling,
+            mergedResult.getRemovedElement() );
+
+        result.addCopiedPage( this );
+        result.addCopiedPage( sibling );
+
+        return result;
+    }
+
+
+    /**
+     * We have to merge the node with its sibling, both have N/2 elements before the element
+     * removal.
+     * 
+     * @param revision The revision
+     * @param mergedResult The result of the merge
+     * @param sibling The Page we will merge the current page with
+     * @param isLeft Tells if the sibling is on the left
+     * @param pos The position of the key that has been removed
+     * @return The page resulting of the merge
+     * @throws IOException If we have an error while trying to access the page
+     */
+    private DeleteResult<K, V> mergeWithSibling( long revision, MergedWithSiblingResult<K, V> mergedResult,
+        Node<K, V> sibling, boolean isLeft, int pos ) throws IOException
+    {
+        // Create the new node. It will contain N - 1 elements (the maximum number)
+        // as we merge two nodes that contain N/2 elements minus the one we remove
+        Node<K, V> newNode = new Node<K, V>( btree, revision, btree.getPageSize() );
+        Tuple<K, V> removedElement = mergedResult.getRemovedElement();
+        int half = btree.getPageSize() / 2;
+        int index = Math.abs( pos );
+
+        if ( isLeft )
+        {
+            // The sibling is on the left. Copy all of its elements in the new node first
+            System.arraycopy( sibling.keys, 0, newNode.keys, 0, half ); //1
+            System.arraycopy( sibling.children, 0, newNode.children, 0, half + 1 ); //2
+
+            // Then copy all the elements up to the deletion point
+            if ( index < 2 )
+            {
+                newNode.keys[half] = mergedResult.getModifiedPage().getLeftMostKey();
+                System.arraycopy( keys, 1, newNode.keys, half + 1, half - 1 );
+
+                Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+                newNode.children[half + 1] = createHolder( modifiedPage );
+                System.arraycopy( children, 2, newNode.children, half + 2, half - 1 );
+            }
+            else
+            {
+                // Copy the left part of the node keys up to the deletion point
+                // Insert the new key
+                newNode.keys[half] = children[0].getValue( btree ).getLeftMostKey(); // 3
+
+                if ( index > 2 )
+                {
+                    System.arraycopy( keys, 0, newNode.keys, half + 1, index - 2 ); //4
+                }
+
+                // Inject the new merged key
+                newNode.keys[half + index - 1] = mergedResult.getModifiedPage().getLeftMostKey(); //5
+
+                if ( index < half )
+                {
+                    System.arraycopy( keys, index, newNode.keys, half + index, half - index ); //6
+                    System.arraycopy( children, index + 1, newNode.children, half + index + 1, half - index ); //9
+                }
+
+                // Copy the children before the deletion point
+                System.arraycopy( children, 0, newNode.children, half + 1, index - 1 ); // 7
+
+                // Inject the new merged child
+                Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+                newNode.children[half + index] = createHolder( modifiedPage ); //8
+            }
+        }
+        else
+        {
+            // The sibling is on the right.
+            if ( index < 2 )
+            {
+                // Copy the keys
+                System.arraycopy( keys, 1, newNode.keys, 0, half - 1 );
+
+                // Insert the first child
+                Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+                newNode.children[0] = createHolder( modifiedPage );
+
+                // Copy the node children
+                System.arraycopy( children, 2, newNode.children, 1, half - 1 );
+            }
+            else
+            {
+                // Copy the keys and children before the deletion point
+                if ( index > 2 )
+                {
+                    // Copy the first keys
+                    System.arraycopy( keys, 0, newNode.keys, 0, index - 2 ); //1
+                }
+
+                // Copy the first children
+                System.arraycopy( children, 0, newNode.children, 0, index - 1 ); //6
+
+                // Inject the modified key
+                newNode.keys[index - 2] = mergedResult.getModifiedPage().getLeftMostKey(); //2
+
+                // Inject the modified children
+                Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+                newNode.children[index - 1] = createHolder( modifiedPage ); // 7
+
+                // Add the remaining node's key if needed
+                if ( index < half )
+                {
+                    System.arraycopy( keys, index, newNode.keys, index - 1, half - index ); //5
+
+                    // Add the remining children if below half
+                    System.arraycopy( children, index + 1, newNode.children, index, half - index ); // 8
+                }
+            }
+
+            // Inject the new key from sibling
+            newNode.keys[half - 1] = sibling.findLeftMost().getKey(); //3
+
+            // Copy the sibling keys
+            System.arraycopy( sibling.keys, 0, newNode.keys, half, half );
+
+            // Add the sibling children
+            System.arraycopy( sibling.children, 0, newNode.children, half, half + 1 ); // 9
+        }
+
+        // And create the result
+        DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>( mergedResult.getCopiedPages(), newNode,
+            removedElement );
+
+        result.addCopiedPage( this );
+        result.addCopiedPage( sibling );
+
+        return result;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public DeleteResult<K, V> delete( long revision, K key, V value, Page<K, V> parent, int parentPos )
+        throws IOException
+    {
+        // We first try to delete the element from the child it belongs to
+        // Find the key in the page
+        int pos = findPos( key );
+        boolean found = pos < 0;
+        int index = pos;
+        Page<K, V> child = null;
+        DeleteResult<K, V> deleteResult = null;
+
+        if ( found )
+        {
+            index = -( pos + 1 );
+            child = children[-pos].getValue( btree );
+            deleteResult = child.delete( revision, key, value, this, -pos );
+        }
+        else
+        {
+            child = children[pos].getValue( btree );
+            deleteResult = child.delete( revision, key, value, this, pos );
+        }
+
+        // If the key is not present in the tree, we simply return
+        if ( deleteResult instanceof NotPresentResult )
+        {
+            // Nothing to do...
+            return deleteResult;
+        }
+
+        // If we just modified the child, return a modified page
+        if ( deleteResult instanceof RemoveResult )
+        {
+            RemoveResult<K, V> removeResult = handleRemoveResult( ( RemoveResult<K, V> ) deleteResult, index, pos,
+                found );
+
+            return removeResult;
+        }
+
+        // If we had to borrow an element in the child, then have to update
+        // the current page
+        if ( deleteResult instanceof BorrowedFromSiblingResult )
+        {
+            RemoveResult<K, V> removeResult = handleBorrowedResult( ( BorrowedFromSiblingResult<K, V> ) deleteResult,
+                pos );
+
+            return removeResult;
+        }
+
+        // Last, not least, we have merged two child pages. We now have to remove
+        // an element from the local page, and to deal with the result.
+        if ( deleteResult instanceof MergedWithSiblingResult )
+        {
+            MergedWithSiblingResult<K, V> mergedResult = ( MergedWithSiblingResult<K, V> ) deleteResult;
+
+            // If the parent is null, then this page is the root page.
+            if ( parent == null )
+            {
+                RemoveResult<K, V> result = handleRootRemove( mergedResult, pos, found );
+
+                return result;
+            }
+
+            // We have some parent. Check if the current page is not half full
+            int halfSize = btree.getPageSize() / 2;
+
+            if ( nbElems > halfSize )
+            {
+                // The page has more than N/2 elements.
+                // We simply remove the element from the page, and if it was the leftmost,
+                // we return the new pivot (it will replace any instance of the removed
+                // key in its parents)
+                RemoveResult<K, V> result = removeKey( mergedResult, revision, pos );
+
+                return result;
+            }
+            else
+            {
+                // We will remove one element from a page that will have less than N/2 elements,
+                // which will lead to some reorganization : either we can borrow an element from
+                // a sibling, or we will have to merge two pages
+                int siblingPos = selectSibling( ( Node<K, V> ) parent, parentPos );
+
+                Node<K, V> sibling = ( Node<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos].getValue( btree ) );
+
+                if ( sibling.getNbElems() > halfSize )
+                {
+                    // The sibling contains enough elements
+                    // We can borrow the element from the sibling
+                    if ( siblingPos < parentPos )
+                    {
+                        DeleteResult<K, V> result = borrowFromLeft( revision, mergedResult, sibling, pos );
+
+                        return result;
+                    }
+                    else
+                    {
+                        // Borrow from the right
+                        DeleteResult<K, V> result = borrowFromRight( revision, mergedResult, sibling, pos );
+
+                        return result;
+                    }
+                }
+                else
+                {
+                    // We need to merge the sibling with the current page
+                    DeleteResult<K, V> result = mergeWithSibling( revision, mergedResult, sibling,
+                        ( siblingPos < parentPos ), pos );
+
+                    return result;
+                }
+            }
+        }
+
+        // We should never reach this point
+        return null;
+    }
+
+
+    /**
+     * The deletion in a children has moved an element from one of its sibling. The key
+     * is present in the current node.
+     * @param borrowedResult The result of the deletion from the children
+     * @param pos The position the key was found in the current node
+     * @return The result
+     * @throws IOException If we have an error while trying to access the page
+     */
+    private RemoveResult<K, V> handleBorrowedResult( BorrowedFromSiblingResult<K, V> borrowedResult, int pos )
+        throws IOException
+    {
+        Page<K, V> modifiedPage = borrowedResult.getModifiedPage();
+        Page<K, V> modifiedSibling = borrowedResult.getModifiedSibling();
+
+        Node<K, V> newPage = copy( revision );
+
+        if ( pos < 0 )
+        {
+            pos = -( pos + 1 );
+
+            if ( borrowedResult.isFromRight() )
+            {
+                // Update the keys
+                newPage.keys[pos] = modifiedPage.findLeftMost().getKey();
+                newPage.keys[pos + 1] = modifiedSibling.findLeftMost().getKey();
+
+                // Update the children
+                newPage.children[pos + 1] = createHolder( modifiedPage );
+                newPage.children[pos + 2] = createHolder( modifiedSibling );
+            }
+            else
+            {
+                // Update the keys
+                newPage.keys[pos] = modifiedPage.findLeftMost().getKey();
+
+                // Update the children
+                newPage.children[pos] = createHolder( modifiedSibling );
+                newPage.children[pos + 1] = createHolder( modifiedPage );
+            }
+        }
+        else
+        {
+            if ( borrowedResult.isFromRight() )
+            {
+                // Update the keys
+                newPage.keys[pos] = modifiedSibling.findLeftMost().getKey();
+
+                // Update the children
+                newPage.children[pos] = createHolder( modifiedPage );
+                newPage.children[pos + 1] = createHolder( modifiedSibling );
+            }
+            else
+            {
+                // Update the keys
+                newPage.keys[pos - 1] = modifiedPage.findLeftMost().getKey();
+
+                // Update the children
+                newPage.children[pos - 1] = createHolder( modifiedSibling );
+                newPage.children[pos] = createHolder( modifiedPage );
+            }
+        }
+
+        // Modify the result and return
+        RemoveResult<K, V> removeResult = new RemoveResult<K, V>( borrowedResult.getCopiedPages(), newPage,
+            borrowedResult.getRemovedElement() );
+
+        removeResult.addCopiedPage( this );
+
+        return removeResult;
+    }
+
+
+    /**
+     * Remove the key at a given position.
+     * 
+     * @param mergedResult The page we will remove a key from
+     * @param revision The revision of the modified page
+     * @param pos The position into the page of the element to remove
+     * @return The modified page with the <K,V> element added
+     * @throws IOException If we have an error while trying to access the page
+     */
+    private RemoveResult<K, V> removeKey( MergedWithSiblingResult<K, V> mergedResult, long revision, int pos )
+        throws IOException
+    {
+        // First copy the current page, but remove one element in the copied page
+        Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems - 1 );
+
+        int index = Math.abs( pos ) - 2;
+
+        //
+        if ( index < 0 )
+        {
+            // Copy the keys and the children
+            System.arraycopy( keys, 1, newNode.keys, 0, newNode.nbElems );
+            Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+            newNode.children[0] = createHolder( modifiedPage );
+            System.arraycopy( children, 2, newNode.children, 1, nbElems - 1 );
+        }
+        else
+        {
+            // Copy the keys
+            if ( index > 0 )
+            {
+                System.arraycopy( keys, 0, newNode.keys, 0, index );
+            }
+
+            newNode.keys[index] = mergedResult.getModifiedPage().findLeftMost().getKey();
+
+            if ( index < nbElems - 2 )
+            {
+                System.arraycopy( keys, index + 2, newNode.keys, index + 1, nbElems - index - 2 );
+            }
+
+            // Copy the children
+            System.arraycopy( children, 0, newNode.children, 0, index + 1 );
+
+            Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+            newNode.children[index + 1] = createHolder( modifiedPage );
+
+            if ( index < nbElems - 2 )
+            {
+                System.arraycopy( children, index + 3, newNode.children, index + 2, nbElems - index - 2 );
+            }
+        }
+
+        // Create the result
+        RemoveResult<K, V> result = new RemoveResult<K, V>( mergedResult.getCopiedPages(), newNode,
+            mergedResult.getRemovedElement() );
+
+        result.addCopiedPage( this );
+
+        return result;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public V get( K key ) throws IOException, KeyNotFoundException
+    {
+        int pos = findPos( key );
+
+        if ( pos < 0 )
+        {
+            // Here, if we have found the key in the node, then we must go down into
+            // the right child, not the left one
+            return children[-pos].getValue( btree ).get( key );
+        }
+        else
+        {
+            return children[pos].getValue( btree ).get( key );
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
+    {
+        int pos = findPos( key );
+
+        if ( pos < 0 )
+        {
+            // Here, if we have found the key in the node, then we must go down into
+            // the right child, not the left one
+            return children[-pos].getValue( btree ).getValues( key );
+        }
+        else
+        {
+            return children[pos].getValue( btree ).getValues( key );
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public boolean hasKey( K key ) throws IOException
+    {
+        int pos = findPos( key );
+
+        if ( pos < 0 )
+        {
+            // Here, if we have found the key in the node, then we must go down into
+            // the right child, not the left one
+            return children[-pos].getValue( btree ).hasKey( key );
+        }
+        else
+        {
+            Page<K, V> page = children[pos].getValue( btree );
+
+            if ( page == null )
+            {
+                System.out.println( "Page is null for pos = " + pos + ", children = " + children[pos] );
+                System.out.println( "Key = " + key );
+            }
+
+            return page.hasKey( key );
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public boolean contains( K key, V value ) throws IOException
+    {
+        int pos = findPos( key );
+
+        if ( pos < 0 )
+        {
+            // Here, if we have found the key in the node, then we must go down into
+            // the right child, not the left one
+            return children[-pos].getValue( btree ).contains( key, value );
+        }
+        else
+        {
+            return children[pos].getValue( btree ).contains( key, value );
+        }
+    }
+
+
+    /**
+     * Set the value at a give position
+     * 
+     * @param pos The position in the values array
+     * @param value the value to inject
+     */
+    public void setValue( int pos, ElementHolder<Page<K, V>, K, V> value )
+    {
+        children[pos] = value;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public Page<K, V> getReference( int pos ) throws IOException
+    {
+        if ( pos < nbElems + 1 )
+        {
+            return children[pos].getValue( btree );
+        }
+        else
+        {
+            return null;
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public CursorImpl<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+        throws IOException
+    {
+        int pos = findPos( key );
+
+        if ( pos < 0 )
+        {
+            pos = -pos;
+        }
+
+        // We first stack the current page
+        stack.push( new ParentPos<K, V>( this, pos ) );
+
+        return children[pos].getValue( btree ).browse( key, transaction, stack );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public CursorImpl<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+        throws IOException
+    {
+        stack.push( new ParentPos<K, V>( this, 0 ) );
+
+        return children[0].getValue( btree ).browse( transaction, stack );
+    }
+
+
+    /**
+     * This method is used when we have to replace a child in a page when we have
+     * found the key in the tree (the value will be changed, so we have made
+     * copies of the existing pages).
+     * 
+     * @param revision The current revision
+     * @param result The modified page
+     * @param pos The position of the found key
+     * @return A modified page
+     * @throws IOException If we have an error while trying to access the page
+     */
+    private InsertResult<K, V> replaceChild( long revision, ModifyResult<K, V> result, int pos ) throws IOException
+    {
+        // Just copy the current page and update its revision
+        Page<K, V> newPage = copy( revision );
+
+        // Last, we update the children table of the newly created page
+        // to point on the modified child
+        Page<K, V> modifiedPage = result.getModifiedPage();
+
+        ( ( Node<K, V> ) newPage ).children[pos] = createHolder( modifiedPage );
+
+        // We can return the result, where we update the modifiedPage,
+        // to avoid the creation of a new object
+        result.modifiedPage = newPage;
+
+        result.addCopiedPage( this );
+
+        return result;
+    }
+
+
+    /**
+     * Creates a new holder contaning a reference to a Page
+     * 
+     * @param page The page we will refer to
+     * @return A holder contaning a reference to the child page
+     * @throws IOException If we have an error while trying to access the page
+     */
+    private ElementHolder<Page<K, V>, K, V> createHolder( Page<K, V> page ) throws IOException
+    {
+        return btree.createPageHolder( page );
+    }
+
+
+    /**
+     * Adds a new key into a copy of the current page at a given position. We return the
+     * modified page. The new page will have one more key than the current page.
+     * 
+     * @param copiedPages the list of copied pages
+     * @param revision The revision of the modified page
+     * @param key The key to insert
+     * @param leftPage The left child
+     * @param rightPage The right child
+     * @param pos The position into the page
+     * @return The modified page with the <K,V> element added
+     * @throws IOException If we have an error while trying to access the page
+     */
+    private InsertResult<K, V> insertChild( List<Page<K, V>> copiedPages, long revision, K key, Page<K, V> leftPage,
+        Page<K, V> rightPage, int pos )
+        throws IOException
+    {
+        // First copy the current page, but add one element in the copied page
+        Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems + 1 );
+
+        // Copy the keys and the children up to the insertion position
+        if ( nbElems > 0 )
+        {
+            System.arraycopy( keys, 0, newNode.keys, 0, pos );
+            System.arraycopy( children, 0, newNode.children, 0, pos );
+        }
+
+        // Add the new key and children
+        newNode.keys[pos] = key;
+
+        // If the BTree is managed, we now have to write the modified page on disk
+        // and to add this page to the list of modified pages
+        newNode.children[pos] = createHolder( leftPage );
+        newNode.children[pos + 1] = createHolder( rightPage );
+
+        // And copy the remaining keys and children
+        if ( nbElems > 0 )
+        {
+            System.arraycopy( keys, pos, newNode.keys, pos + 1, keys.length - pos );
+            System.arraycopy( children, pos + 1, newNode.children, pos + 2, children.length - pos - 1 );
+        }
+
+        // Create the result
+        InsertResult<K, V> result = new ModifyResult<K, V>( copiedPages, newNode, null );
+        result.addCopiedPage( this );
+
+        return result;
+    }
+
+
+    /**
+     * Splits a full page into two new pages, a left, a right and a pivot element. The new pages will
+     * each contains half of the original elements. <br/>
+     * The pivot will be computed, depending on the place
+     * we will inject the newly added element. <br/>
+     * If the newly added element is in the middle, we will use it
+     * as a pivot. Otherwise, we will use either the last element in the left page if the element is added
+     * on the left, or the first element in the right page if it's added on the right.
+     * 
+     * @param copiedPages the list of copied pages
+     * @param revision The new revision for all the created pages
+     * @param pivot The key that will be move up after the split
+     * @param leftPage The left child
+     * @param rightPage The right child
+     * @param pos The position of the insertion of the new element
+     * @return An OverflowPage containing the pivot, and the new left and right pages
+     * @throws IOException If we have an error while trying to access the page
+     */
+    private InsertResult<K, V> addAndSplit( List<Page<K, V>> copiedPages, long revision, K pivot, Page<K, V> leftPage,
+        Page<K, V> rightPage, int pos ) throws IOException
+    {
+        int middle = btree.getPageSize() >> 1;
+
+        // Create two new pages
+        Node<K, V> newLeftPage = new Node<K, V>( btree, revision, middle );
+        Node<K, V> newRightPage = new Node<K, V>( btree, revision, middle );
+
+        // Determinate where to store the new value
+        // If it's before the middle, insert the value on the left,
+        // the key in the middle will become the new pivot
+        if ( pos < middle )
+        {
+            // Copy the keys and the children up to the insertion position
+            System.arraycopy( keys, 0, newLeftPage.keys, 0, pos );
+            System.arraycopy( children, 0, newLeftPage.children, 0, pos );
+
+            // Add the new element
+            newLeftPage.keys[pos] = pivot;
+            newLeftPage.children[pos] = createHolder( leftPage );
+            newLeftPage.children[pos + 1] = createHolder( rightPage );
+
+            // And copy the remaining elements minus the new pivot
+            System.arraycopy( keys, pos, newLeftPage.keys, pos + 1, middle - pos - 1 );
+            System.arraycopy( children, pos + 1, newLeftPage.children, pos + 2, middle - pos - 1 );
+
+            // Copy the keys and the children in the right page
+            System.arraycopy( keys, middle, newRightPage.keys, 0, middle );
+            System.arraycopy( children, middle, newRightPage.children, 0, middle + 1 );
+
+            // Create the result
+            InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, keys[middle - 1], newLeftPage, newRightPage );
+            result.addCopiedPage( this );
+
+            return result;
+        }
+        else if ( pos == middle )
+        {
+            // A special case : the pivot will be propagated up in the tree
+            // The left and right pages will be spread on the two new pages
+            // Copy the keys and the children up to the insertion position (here, middle)
+            System.arraycopy( keys, 0, newLeftPage.keys, 0, middle );
+            System.arraycopy( children, 0, newLeftPage.children, 0, middle );
+            newLeftPage.children[middle] = createHolder( leftPage );
+
+            // And process the right page now
+            System.arraycopy( keys, middle, newRightPage.keys, 0, middle );
+            System.arraycopy( children, middle + 1, newRightPage.children, 1, middle );
+            newRightPage.children[0] = createHolder( rightPage );
+
+            // Create the result
+            InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, pivot, newLeftPage, newRightPage );
+            result.addCopiedPage( this );
+
+            return result;
+        }
+        else
+        {
+            // Copy the keys and the children up to the middle
+            System.arraycopy( keys, 0, newLeftPage.keys, 0, middle );
+            System.arraycopy( children, 0, newLeftPage.children, 0, middle + 1 );
+
+            // Copy the keys and the children in the right page up to the pos
+            System.arraycopy( keys, middle + 1, newRightPage.keys, 0, pos - middle - 1 );
+            System.arraycopy( children, middle + 1, newRightPage.children, 0, pos - middle - 1 );
+
+            // Add the new element
+            newRightPage.keys[pos - middle - 1] = pivot;
+            newRightPage.children[pos - middle - 1] = createHolder( leftPage );
+            newRightPage.children[pos - middle] = createHolder( rightPage );
+
+            // And copy the remaining elements minus the new pivot
+            System.arraycopy( keys, pos, newRightPage.keys, pos - middle, nbElems - pos );
+            System.arraycopy( children, pos + 1, newRightPage.children, pos + 1 - middle, nbElems - pos );
+
+            // Create the result
+            InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, keys[middle], newLeftPage, newRightPage );
+            result.addCopiedPage( this );
+
+            return result;
+        }
+    }
+
+
+    /**
+     * Copies the current page and all its keys, with a new revision.
+     * 
+     * @param revision The new revision
+     * @return The copied page
+     */
+    protected Node<K, V> copy( long revision )
+    {
+        Node<K, V> newPage = new Node<K, V>( btree, revision, nbElems );
+
+        // Copy the keys
+        System.arraycopy( keys, 0, newPage.keys, 0, nbElems );
+
+        // Copy the children
+        System.arraycopy( children, 0, newPage.children, 0, nbElems + 1 );
+
+        return newPage;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public K getLeftMostKey() throws EndOfFileExceededException, IOException
+    {
+        return children[0].getValue( btree ).getLeftMostKey();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public K getRightMostKey() throws EndOfFileExceededException, IOException
+    {
+        int index = ( nbElems + 1 ) - 1;
+
+        if ( children[index] != null )
+        {
+            return children[index].getValue( btree ).getRightMostKey();
+        }
+
+        return children[nbElems - 1].getValue( btree ).getRightMostKey();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public Tuple<K, V> findLeftMost() throws EndOfFileExceededException, IOException
+    {
+        return children[0].getValue( btree ).findLeftMost();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
+    {
+        return children[nbElems].getValue( btree ).findRightMost();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "Node[" );
+        sb.append( super.toString() );
+        sb.append( "] -> {" );
+
+        try
+        {
+            if ( nbElems > 0 )
+            {
+                // Start with the first child
+                if ( children[0] == null )
+                {
+                    sb.append( "null" );
+                }
+                else
+                {
+                    sb.append( 'r' ).append( children[0].getValue( btree ).getRevision() );
+                }
+
+                for ( int i = 0; i < nbElems; i++ )
+                {
+                    sb.append( "|<" ).append( keys[i] ).append( ">|" );
+
+                    if ( children[i + 1] == null )
+                    {
+                        sb.append( "null" );
+                    }
+                    else
+                    {
+                        sb.append( 'r' ).append( children[i + 1].getValue( btree ).getRevision() );
+                    }
+                }
+            }
+        }
+        catch ( IOException ioe )
+        {
+            // Do nothing
+        }
+
+        sb.append( "}" );
+
+        return sb.toString();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public String dumpPage( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        if ( nbElems > 0 )
+        {
+            try
+            {
+                // Start with the first child
+                sb.append( children[0].getValue( btree ).dumpPage( tabs + "    " ) );
+
+                for ( int i = 0; i < nbElems; i++ )
+                {
+                    sb.append( tabs );
+                    sb.append( "<" );
+                    sb.append( keys[i] ).append( ">\n" );
+                    sb.append( children[i + 1].getValue( btree ).dumpPage( tabs + "    " ) );
+                }
+            }
+            catch ( IOException ioe )
+            {
+                // Do nothing
+            }
+        }
+
+        return sb.toString();
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/NotPresentResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/NotPresentResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/NotPresentResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/NotPresentResult.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,75 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import org.apache.directory.mavibot.btree.Tuple;
+
+
+/**
+ * The result of an delete operation, when the key to delete is not present in the tree.
+ * 
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier */class NotPresentResult<K, V> extends AbstractResult<K, V> implements DeleteResult<K, V>
+{
+    /** The unique instance for this class */
+    @SuppressWarnings("rawtypes")
+    /* No qualifier */static final NotPresentResult NOT_PRESENT = new NotPresentResult();
+
+
+    /**
+     * A private void constructor, as we won't have any other instance.
+     */
+    private NotPresentResult()
+    {
+        // Do nothing
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public Page<K, V> getModifiedPage()
+    {
+        return null;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public Tuple<K, V> getRemovedElement()
+    {
+        return null;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public K getNewLeftMost()
+    {
+        return null;
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Page.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Page.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Page.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Page.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,275 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import java.io.IOException;
+import java.util.LinkedList;
+
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+
+
+/**
+ * A MVCC Page interface. A Page can be either a Leaf (containing keys and values) or a Node
+ * (containing keys and references to child pages).<br/>
+ * A Page can be stored on disk. If so, we store the serialized value of this Page into
+ * one or more {@link PageIO} (they will be linked)
+ * 
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier */interface Page<K, V>
+{
+    /**
+     * @return The number of keys present in this page
+     */
+    int getNbElems();
+
+
+    /**
+     * Inserts the given key and value into this page. We first find the place were to
+     * inject the <K,V> into the tree, by recursively browsing the pages :<br/>
+     * <ul>
+     * <li>If the index is below zero, the key is present in the Page : we modify the
+     * value and return</li>
+     * <li>If the page is a node, we have to go down to the right child page</li>
+     * <li>If the page is a leaf, we insert the new <K,V> element into the page, and if
+     * the Page is full, we split it and propagate the new pivot up into the tree</li>
+     * </ul>
+     * <p>
+     * 
+     * @param revision The new revision for the modified pages
+     * @param key Inserted key
+     * @param value Inserted value
+     * @return Either a modified Page or an Overflow element if the Page was full
+     * @throws IOException If we have an error while trying to access the page
+     */
+    InsertResult<K, V> insert( long revision, K key, V value ) throws IOException;
+
+
+    /**
+     * Deletes the value from an entry associated with the given key in this page. We first find 
+     * the place were to remove the <K,V> into the tree, by recursively browsing the pages.
+     * If the value is present, it will be deleted first, later if there are no other values associated with 
+     * this key(which can happen when duplicates are enabled), we will remove the key from the tree.
+     * 
+     * @param revision The new revision for the modified pages
+     * @param key The key to delete
+     * @param value The value to delete (can be null)
+     * @param parent The parent page
+     * @param parentPos The position of the current page in it's parent
+     * @return Either a modified Page if the key has been removed from the page, or a NotPresentResult.
+     * @throws IOException If we have an error while trying to access the page
+     */
+    DeleteResult<K, V> delete( long revision, K key, V value, Page<K, V> parent, int parentPos ) throws IOException;
+
+
+    /**
+     * Gets the value associated with the given key, if any. If we don't have 
+     * one, this method will throw a KeyNotFoundException.<br/>
+     * Note that we may get back null if a null value has been associated 
+     * with the key.
+     * 
+     * @param key The key we are looking for
+     * @return The associated value, which can be null
+     * @throws KeyNotFoundException If no entry with the given key can be found
+     * @throws IOException If we have an error while trying to access the page
+     */
+    V get( K key ) throws KeyNotFoundException, IOException;
+
+
+    /**
+     * Gets the values associated with the given key, if any. If we don't have 
+     * the key, this method will throw a KeyNotFoundException.<br/>
+     * Note that we may get back null if a null value has been associated 
+     * with the key.
+     * 
+     * @param key The key we are looking for
+     * @return The associated value, which can be null
+     * @throws KeyNotFoundException If no entry with the given key can be found
+     * @throws IOException If we have an error while trying to access the page
+     * @throws IllegalArgumentException If duplicates are not enabled 
+     */
+    DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException;
+
+
+    /**
+     * Checks if the page contains the given key with the given value.
+     * 
+     * @param key The key we are looking for
+     * @param value The value associated with the given key
+     * @return true if the key and value are associated with each other, false otherwise
+     */
+    boolean contains( K key, V value ) throws IOException;
+
+
+    /**
+     * Browses the tree, looking for the given key, and creates a Cursor on top
+     * of the found result.
+     * 
+     * @param key The key we are looking for.
+     * @param transaction The started transaction for this operation
+     * @param stack The stack of parents we go through to get to this page
+     * @return A Cursor to browse the next elements
+     * @throws IOException If we have an error while trying to access the page
+     */
+    CursorImpl<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+        throws IOException;
+
+
+    /**
+     * Browses the whole tree, and creates a Cursor on top of it.
+     * 
+     * @param transaction The started transaction for this operation
+     * @param stack The stack of parents we go through to get to this page
+     * @return A Cursor to browse the next elements
+     * @throws IOException If we have an error while trying to access the page
+     */
+    CursorImpl<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+        throws EndOfFileExceededException, IOException;
+
+
+    /**
+     * @return the revision
+     */
+    long getRevision();
+
+
+    /**
+     * Returns the key at a given position
+     * 
+     * @param pos The position of the key we want to retrieve
+     * @return The key found at the given position
+     */
+    K getKey( int pos );
+
+
+    /**
+     * Finds the leftmost key in this page. If the page is a node, it will go
+     * down in the leftmost children to recursively find the leftmost key.
+     * 
+     * @return The leftmost key in the tree
+     * @throws IOException If we have an error while trying to access the page
+     */
+    K getLeftMostKey() throws IOException;
+
+
+    /**
+     * Finds the rightmost key in this page. If the page is a node, it will go
+     * down in the rightmost children to recursively find the rightmost key.
+     * 
+     * @return The rightmost key in the tree
+     * @throws IOException If we have an error while trying to access the page
+     */
+    K getRightMostKey() throws IOException;
+
+
+    /**
+     * Finds the leftmost element in this page. If the page is a node, it will go
+     * down in the leftmost children to recursively find the leftmost element.
+     * 
+     * @return The leftmost element in the tree
+     * @throws IOException If we have an error while trying to access the page
+     */
+    Tuple<K, V> findLeftMost() throws IOException;
+
+
+    /**
+     * Finds the rightmost element in this page. If the page is a node, it will go
+     * down in the rightmost children to recursively find the rightmost element.
+     * 
+     * @return The rightmost element in the tree
+     * @throws IOException If we have an error while trying to access the page
+     */
+    Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException;
+
+
+    /**
+     * Pretty-prints the tree with tabs
+     * @param tabs The tabs to add in front of each node
+     * @return A pretty-print dump of the tree
+     */
+    String dumpPage( String tabs );
+
+
+    /**
+     * Find the position of the given key in the page. If we have found the key,
+     * we will return its position as a negative value.
+     * <p/>
+     * Assuming that the array is zero-indexed, the returned value will be : <br/>
+     *   position = - ( position + 1)
+     * <br/>
+     * So for the following table of keys : <br/>
+     * <pre>
+     * +---+---+---+---+
+     * | b | d | f | h |
+     * +---+---+---+---+
+     *   0   1   2   3
+     * </pre>
+     * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).<br/>
+     * Computing the real position is just a matter to get -(position++).
+     * <p/>
+     * If we don't find the key in the table, we will return the position of the key
+     * immediately above the key we are looking for. <br/>
+     * For instance, looking for :
+     * <ul>
+     * <li>'a' will return 0</li>
+     * <li>'b' will return -1</li>
+     * <li>'c' will return 1</li>
+     * <li>'d' will return -2</li>
+     * <li>'e' will return 2</li>
+     * <li>'f' will return -3</li>
+     * <li>'g' will return 3</li>
+     * <li>'h' will return -4</li>
+     * <li>'i' will return 4</li>
+     * </ul>
+     * 
+     * 
+     * @param key The key to find
+     * @return The position in the page.
+     */
+    int findPos( K key );
+
+
+    /**
+     * Checks if the given key exists.
+     *  
+     * @param key The key we are looking at
+     * @return true if the key is present, false otherwise
+     * @throws IOException If we have an error while trying to access the page
+     */
+    boolean hasKey( K key ) throws IOException;
+
+
+    /**
+     * @return the offset of the first {@link PageIO} which stores the Page on disk.
+     */
+    long getOffset();
+
+
+    /**
+     * @return the offset of the last {@link PageIO} which stores the Page on disk.
+     */
+    long getLastOffset();
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ParentPos.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ParentPos.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ParentPos.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ParentPos.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,66 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+/**
+ * This class is used to store the parent page and the position in it during
+ * a browse operation. We have as many ParentPos instance than the depth of the tree.
+ * 
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier*/class ParentPos<K, V>
+{
+    /** The page we are browsing */
+    /* No qualifier*/Page<K, V> page;
+
+    /** The current position in the page */
+    /* No qualifier*/int pos;
+
+    /** The current position of the duplicate container in the page */
+    /* No qualifier*/int dupPos;
+
+    /** the container of duplicate key's values. The tuples will be stored as <V,null>*/
+    /* No qualifier*/BTree<V, V> dupsContainer;
+
+
+    /**
+     * Creates a new instance of ParentPos
+     * @param page The current Page
+     * @param pos The current position in the page
+     */
+    /* No qualifier*/ParentPos( Page<K, V> page, int pos )
+    {
+        this.page = page;
+        this.pos = pos;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return "<" + pos + "," + page + ">";
+    }
+}
\ No newline at end of file

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/RemoveResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/RemoveResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/RemoveResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/RemoveResult.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,77 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import java.util.List;
+
+import org.apache.directory.mavibot.btree.Tuple;
+
+
+/**
+ * The result of a delete operation, when the child has not been merged. It contains the
+ * reference to the modified page, and the removed element.
+ * 
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier */class RemoveResult<K, V> extends AbstractDeleteResult<K, V>
+{
+    /**
+     * The default constructor for RemoveResult.
+     * 
+     * @param modifiedPage The modified page
+     * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+     */
+    /* No qualifier */RemoveResult( Page<K, V> modifiedPage, Tuple<K, V> removedElement )
+    {
+        super( modifiedPage, removedElement );
+    }
+
+
+    /**
+     * A constructor for RemoveResult which takes a list of copied pages.
+     * 
+     * @param copiedPages the list of copied pages
+     * @param modifiedPage The modified page
+     * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+     */
+    /* No qualifier */RemoveResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage, Tuple<K, V> removedElement )
+    {
+        super( copiedPages, modifiedPage, removedElement );
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "RemoveResult :" );
+        sb.append( "\n    removed element = " ).append( getRemovedElement() );
+        sb.append( "\n    modifiedPage = " ).append( getModifiedPage() );
+
+        return sb.toString();
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/SplitResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/SplitResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/SplitResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/SplitResult.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,120 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import java.util.List;
+
+
+/**
+ * The result of an insert operation, when the page has been split. It contains
+ * the new pivotal value, plus the reference on the two new pages.
+ * 
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier */class SplitResult<K, V> extends AbstractResult<K, V> implements InsertResult<K, V>
+{
+    /** The left child */
+    protected Page<K, V> leftPage;
+
+    /** The right child */
+    protected Page<K, V> rightPage;
+
+    /** The key pivot */
+    protected K pivot;
+
+
+    /**
+     * The default constructor for SplitResult.
+     * @param pivot The new key to insert into the parent
+     * @param leftPage The new left page
+     * @param rightPage The new right page
+     */
+    /* No qualifier */SplitResult( K pivot, Page<K, V> leftPage, Page<K, V> rightPage )
+    {
+        super();
+        this.pivot = pivot;
+        this.leftPage = leftPage;
+        this.rightPage = rightPage;
+    }
+
+
+    /**
+     * A constructor for SplitResult with copied pages.
+     * 
+     * @param copiedPages the list of copied pages
+     * @param pivot The new key to insert into the parent
+     * @param leftPage The new left page
+     * @param rightPage The new right page
+     */
+    /* No qualifier */SplitResult( List<Page<K, V>> copiedPages, K pivot, Page<K, V> leftPage, Page<K, V> rightPage )
+    {
+        super( copiedPages );
+        this.pivot = pivot;
+        this.leftPage = leftPage;
+        this.rightPage = rightPage;
+    }
+
+
+    /**
+     * @return the leftPage
+     */
+    /* No qualifier */Page<K, V> getLeftPage()
+    {
+        return leftPage;
+    }
+
+
+    /**
+     * @return the rightPage
+     */
+    /* No qualifier */Page<K, V> getRightPage()
+    {
+        return rightPage;
+    }
+
+
+    /**
+     * @return the pivot
+     */
+    /* No qualifier */K getPivot()
+    {
+        return pivot;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "SplitResult, new pivot = " ).append( pivot );
+        sb.append( "\n    leftPage = " ).append( leftPage );
+        sb.append( "\n    rightPage = " ).append( rightPage );
+        sb.append( super.toString() );
+
+        return sb.toString();
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Transaction.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Transaction.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Transaction.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Transaction.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,128 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import java.util.Date;
+
+
+/**
+ * The Transaction is used to protect the BTree against concurrent modifcation,
+ * and insure that a read is always done against one single revision. It's also
+ * used to gather many modifications under one single revision, if needed.
+ * <p/>
+ * A Transaction should be closed when the user is done with it, otherwise the
+ * pages associated with the given revision, and all the referenced pages, will
+ * remain on the storage.
+ * <p/>
+ * A Transaction can be hold for quite a long time, for instance while doing
+ * a browse against a big BTree. At some point, transactions which are pending
+ * for too long will be closed by the transaction manager.
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ */
+public class Transaction<K, V>
+{
+    /** The associated revision */
+    private long revision;
+
+    /** The date of creation */
+    private long creationDate;
+
+    /** The revision on which we are having a transaction */
+    private volatile Page<K, V> root;
+
+    /** A flag used to tell if a transaction is closed ot not */
+    private volatile boolean closed;
+
+
+    /**
+     * Creates a new transaction instance
+     * 
+     * @param root The associated root
+     * @param revision The revision this transaction is using
+     * @param creationDate The creation date for this transaction
+     */
+    public Transaction( Page<K, V> root, long revision, long creationDate )
+    {
+        this.revision = revision;
+        this.creationDate = creationDate;
+        this.root = root;
+        closed = false;
+    }
+
+
+    /**
+     * @return the associated revision
+     */
+    public long getRevision()
+    {
+        return revision;
+    }
+
+
+    /**
+     * @return the associated root
+     */
+    public Page<K, V> getRoot()
+    {
+        return root;
+    }
+
+
+    /**
+     * @return the creationDate
+     */
+    public long getCreationDate()
+    {
+        return creationDate;
+    }
+
+
+    /**
+     * Close the transaction, releasing the revision it was using.
+     */
+    public void close()
+    {
+        root = null;
+        closed = true;
+    }
+
+
+    /**
+     * @return true if this transaction has been closed
+     */
+    public boolean isClosed()
+    {
+        return closed;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return "Transaction[" + revision + ":" + new Date( creationDate ) + ", closed :" + closed + "]";
+    }
+}



Mime
View raw message