You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2012/01/21 08:44:14 UTC
svn commit: r1234279 - in
/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree:
BTree.java Page.java
Author: elecharny
Date: Sat Jan 21 07:44:14 2012
New Revision: 1234279
URL: http://svn.apache.org/viewvc?rev=1234279&view=rev
Log:
o Removed the inner classes, they are useless : we can propagate a split without having to create intermediary objects. This result to a 50% faster insertion
Modified:
directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java
directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java
Modified: directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java?rev=1234279&r1=1234278&r2=1234279&view=diff
==============================================================================
--- directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java (original)
+++ directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java Sat Jan 21 07:44:14 2012
@@ -25,8 +25,6 @@ import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicLong;
-import org.apache.directory.btree.Page.OverflowResult;
-import org.apache.directory.btree.Page.PageResult;
/**
@@ -154,24 +152,13 @@ public class BTree<K, V>
// starting from the root page
long revision = generateRevision();
- Page.InsertResult<K, V> insert = rootPage.insert( revision, key, value );
-
- if ( insert == null )
- {
- System.out.println( "------------> NULL" );
- }
+ rootPage = rootPage.insert( revision, key, value );
- if ( insert instanceof PageResult )
- {
- rootPage = ( ( PageResult<K, V> ) insert ).page;
- roots.put( revision, rootPage );
- }
- else
+ if ( rootPage.getRecordId() == Page.OVERFLOW )
{
- // We have to create a new rootPage
- rootPage = new Page<K, V>( revision, this, (OverflowResult<K, V>)insert );
- roots.put( revision, rootPage );
+ rootPage.setRecordId();
}
+ roots.put( revision, rootPage );
}
}
finally
Modified: directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java?rev=1234279&r1=1234278&r2=1234279&view=diff
==============================================================================
--- directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java (original)
+++ directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java Sat Jan 21 07:44:14 2012
@@ -62,6 +62,9 @@ public class Page<K, V> implements Clone
/** The number of current values in the Page */
private int nbElems;
+ /** A flag used to know that the Page is the result of a split */
+ /* No qualifier */ static long OVERFLOW = -1L;
+
/**
* No-argument constructor used by serialization.
@@ -73,6 +76,27 @@ public class Page<K, V> implements Clone
/**
+ * Internal constructor used to create Page instance used when a page is being copied or overflow
+ */
+ @SuppressWarnings("unchecked") // Cannot create an array of generic objects
+ private Page( BTree<K, V> btree, long revision, int nbElems, boolean isLeaf )
+ {
+ this.btree = btree;
+ this.revision = revision;
+ this.nbElems = nbElems;
+ this.keys = (K[])new Object[nbElems];
+ this.values = (V[])new Object[nbElems];
+ this.isLeaf = isLeaf;
+ recordId = btree.generateRecordId();
+
+ if ( !isLeaf )
+ {
+ this.children = new Page[nbElems + 1];
+ }
+ }
+
+
+ /**
* Page constructor, for newly created pages.
*
* @param btree The parent B+tree
@@ -105,31 +129,6 @@ public class Page<K, V> implements Clone
/**
- * Creates a new root page, when the root is not anymore a leaf, and has been split.
- *
- * @param revision The new page revision
- * @param btree The associated btree
- * @param result The split Page
- */
- @SuppressWarnings("unchecked")
- /* No qualifier */ Page( long revision, BTree<K, V> btree, OverflowResult<K, V> result )
- {
- this.revision = revision;
- this.btree = btree;
- this.recordId = btree.generateRecordId();
- isLeaf = false;
- nbElems = 1;
- keys = (K[])new Object[nbElems];
- keys[0] = result.pivotKey;
- values = (V[])new Object[nbElems];
- values[0] = result.pivotValue;
- children = new Page[nbElems + 1];
- children[0] = result.leftPage;
- children[1] = result.rightPage;
- }
-
-
- /**
* Find a value in the tree, using its key. If it's not found, this method returns null
*
* @param key The key of the searched value
@@ -178,6 +177,15 @@ public class Page<K, V> implements Clone
/**
+ * Generate a new recordId for this page
+ */
+ /* No qualifier */ void setRecordId()
+ {
+ this.recordId = btree.generateRecordId();
+ }
+
+
+ /**
* @return The page's revision
*/
/* No qualifier */ long getRevision()
@@ -307,7 +315,7 @@ public class Page<K, V> implements Clone
* @param value Inserted value
* @return Either a modified Page or an Overflow element if the Page was full
*/
- /* No qualifier */ InsertResult<K, V> insert( long revision, K key, V value )
+ /* No qualifier */ Page<K, V> insert( long revision, K key, V value )
{
if ( isLeaf )
{
@@ -332,13 +340,13 @@ public class Page<K, V> implements Clone
}
else
{
- InsertResult<K, V> result = children[index].insert( revision, key, value );
+ Page<K, V> result = children[index].insert( revision, key, value );
- if ( result instanceof PageResult )
+ if ( result.recordId != OVERFLOW )
{
// The result is a modified page, we have to replace the associated
// child and to copy the current page with a new revision
- return replaceChild( revision, (PageResult<K, V>)result, index );
+ return replaceChild( revision, result, index );
}
else
{
@@ -348,15 +356,14 @@ public class Page<K, V> implements Clone
{
// The current page has some room : inject the overflow element in
// a copy of the current page and return it
- return insertOverflow( revision, (OverflowResult<K, V>)result, index );
+ return insertOverflow( revision, result, index );
}
else
{
// We don't have enough room in the current page : we split it and
// return the new overflow element we computed.
- OverflowResult<K, V> overflow = (OverflowResult<K, V>)result;
-
- return addAndSplit( revision, index, overflow.pivotKey, overflow.pivotValue, overflow.leftPage, overflow.rightPage );
+ return addAndSplit( revision, result.keys[0], result.values[0],
+ result.children[0], result.children[1], index );
}
}
}
@@ -373,7 +380,7 @@ public class Page<K, V> implements Clone
* @param value The value
* @return The copied Page
*/
- private InsertResult<K, V> insertInLeaf( long revision, K key, V value )
+ private Page<K, V> insertInLeaf( long revision, K key, V value )
{
// Find the key into this leaf
int index = findIndex( key );
@@ -395,7 +402,7 @@ public class Page<K, V> implements Clone
else
{
// The Page is already full : we split it and return the overflow element
- return addAndSplit( revision, index, key, value, null, null );
+ return addAndSplit( revision, key, value, null, null, index );
}
}
@@ -409,12 +416,12 @@ public class Page<K, V> implements Clone
* @param index The position of the modified Page
* @return the copy of this page
*/
- private InsertResult<K, V> replaceChild( long revision, PageResult<K, V> pageResult, int index )
+ private Page<K, V> replaceChild( long revision, Page<K, V> page, int index )
{
Page<K, V> newPage = copy( revision );
- newPage.children[index] = pageResult.page;
+ newPage.children[index] = page;
- return new PageResult<K, V>( newPage );
+ return newPage;
}
@@ -427,36 +434,27 @@ public class Page<K, V> implements Clone
* @param index The position of the overflow element in the current page
* @return The modified page containing the overflow element
*/
- @SuppressWarnings("unchecked")
- private InsertResult<K, V> insertOverflow( long revision, OverflowResult<K, V> result, int index )
+ private Page<K, V> insertOverflow( long revision, Page<K, V> result, int index )
{
- Page<K, V> newPage = new Page<K, V>();
- newPage.btree = btree;
- newPage.revision = revision;
- newPage.isLeaf = false;
- newPage.recordId = btree.generateRecordId();
- newPage.nbElems = nbElems + 1;
+ Page<K, V> newPage = new Page<K, V>( btree, revision, nbElems + 1, false );
- newPage.keys = (K[])new Object[newPage.nbElems];
System.arraycopy( keys, 0, newPage.keys, 0, index );
- newPage.keys[index] = result.pivotKey;
+ newPage.keys[index] = result.keys[0];
System.arraycopy( keys, index, newPage.keys, index + 1, newPage.nbElems - ( index + 1 ) );
- newPage.values = (V[])new Object[newPage.nbElems];
System.arraycopy( values, 0, newPage.values, 0, index );
- newPage.values[index] = result.pivotValue;
+ newPage.values[index] = result.values[0];
System.arraycopy( values, index, newPage.values, index + 1, newPage.nbElems - ( index + 1 ) );
if ( ! isLeaf )
{
- newPage.children = new Page[newPage.nbElems + 1];
System.arraycopy( children, 0, newPage.children, 0, index );
- newPage.children[index] = result.leftPage;
- newPage.children[index + 1] = result.rightPage;
+ newPage.children[index] = result.children[0];
+ newPage.children[index + 1] = result.children[1];
System.arraycopy( children, index + 1, newPage.children, index + 2, newPage.nbElems + 1 - ( index + 2 ) );
}
- return new PageResult<K, V>( newPage );
+ return newPage;
}
@@ -477,9 +475,11 @@ public class Page<K, V> implements Clone
* @param right The right child of the added element
* @return An OverflowPage containing the pivor, and the new left and right pages
*/
- private InsertResult<K, V> addAndSplit( long revision, int index, K key, V value, Page<K, V> left, Page<K, V> right )
+ private Page<K, V> addAndSplit( long revision, K key, V value, Page<K, V> left, Page<K, V> right, int index )
{
- OverflowResult<K, V> result = new OverflowResult<K, V>();
+ Page<K, V> newPage = new Page<K, V>( btree, revision, 1, false );
+ newPage.recordId = OVERFLOW;
+
Page<K, V> child = null;
int pivot = ( nbElems + 1 ) / 2;
@@ -487,45 +487,45 @@ public class Page<K, V> implements Clone
// i == P -> left = a[0..P-1], median = X, right = a[P..N-1]
if ( index == pivot )
{
- result.pivotKey = key;
- result.pivotValue = value;
- result.leftPage = copyHalfPage( revision, 0, pivot - 1, left );
- result.rightPage = copyHalfPage( revision, pivot, nbElems - 1, right );
+ newPage.keys[0] = key;
+ newPage.values[0] = value;
+ newPage.children[0] = copyHalfPage( revision, 0, pivot - 1, left );
+ newPage.children[1] = copyHalfPage( revision, pivot, nbElems - 1, right );
- return result;
+ return newPage;
}
// i < P -> left = a[0..index, X, index+1..P - 2], median = a[P-1], right = a[P..N-1]
if ( index < pivot )
{
- result.pivotKey = keys[pivot - 1];
- result.pivotValue = values[pivot - 1];
- result.leftPage = copyAndInsert( revision, key, value, left, right, index, 0, pivot - 1 );
+ newPage.keys[0] = keys[pivot - 1];
+ newPage.values[0] = values[pivot - 1];
+ newPage.children[0] = copyAndInsert( revision, key, value, left, right, index, 0, pivot - 1 );
if ( !isLeaf )
{
child = children[pivot];
}
- result.rightPage = copyHalfPage( revision, pivot, nbElems - 1, child );
+ newPage.children[1] = copyHalfPage( revision, pivot, nbElems - 1, child );
- return result;
+ return newPage;
}
else
{
// i < P -> left = a[0..P - 1], median = a[P], right = a[P+1..N-1]
- result.pivotKey = keys[pivot];
- result.pivotValue = values[pivot];
+ newPage.keys[0] = keys[pivot];
+ newPage.values[0] = values[pivot];
if ( !isLeaf )
{
child = children[pivot];
}
- result.leftPage = copyHalfPage( revision, 0, pivot - 1, child );
- result.rightPage = copyAndInsert( revision, key, value, left, right, index, pivot + 1, nbElems );
+ newPage.children[0] = copyHalfPage( revision, 0, pivot - 1, child );
+ newPage.children[1] = copyAndInsert( revision, key, value, left, right, index, pivot + 1, nbElems );
- return result;
+ return newPage;
}
}
@@ -538,24 +538,15 @@ public class Page<K, V> implements Clone
* @param end The end in the original page
* @return A page containing all the elements in [start..end] in the original page.
*/
- @SuppressWarnings("unchecked")
private Page<K, V> copyHalfPage( long revision, int start, int end, Page<K, V> child )
{
- Page<K, V> newPage = new Page<K, V>();
- newPage.btree = btree;
- newPage.revision = revision;
- newPage.isLeaf = isLeaf;
- newPage.recordId = btree.generateRecordId();
- newPage.nbElems = end - start + 1;
- newPage.keys = (K[])new Object[newPage.nbElems];
+ Page<K, V> newPage = new Page<K, V>( btree, revision, end - start + 1, isLeaf );
+
System.arraycopy( keys, start, newPage.keys, 0, newPage.nbElems );
- newPage.values = (V[])new Object[newPage.nbElems];
System.arraycopy( values, start, newPage.values, 0, newPage.nbElems );
if ( ! isLeaf )
{
- newPage.children = new Page[newPage.nbElems + 1];
-
if ( start == 0 )
{
// The child has to be copied on the right of the left page
@@ -634,32 +625,23 @@ public class Page<K, V> implements Clone
* @param end The position in the original page to stop the copy
* @return A new page containing half of the split page plus the overflow element
*/
- @SuppressWarnings("unchecked")
private Page<K, V> copyAndInsert( long revision, K pivotKey, V pivotValue, Page<K, V> leftPage,
Page<K, V> rightPage, int index, int start, int end )
{
- Page<K, V> newPage = new Page<K, V>();
- newPage.btree = btree;
- newPage.revision = revision;
- newPage.isLeaf = isLeaf;
- newPage.recordId = btree.generateRecordId();
- newPage.nbElems = end - start + 1;
+ Page<K, V> newPage = new Page<K, V>( btree, revision, end - start + 1, isLeaf );
int middle = index - start;
- newPage.keys = (K[])new Object[newPage.nbElems];
arrayCopy( keys, start, newPage.keys, 0, middle );
newPage.keys[middle] = pivotKey;
System.arraycopy( keys, index, newPage.keys, middle + 1, newPage.nbElems - ( middle + 1 ) );
- newPage.values = (V[])new Object[newPage.nbElems];
System.arraycopy( values, start, newPage.values, 0, middle );
newPage.values[middle] = pivotValue;
System.arraycopy( values, index, newPage.values, middle + 1, newPage.nbElems - ( middle + 1 ) );
if ( ! isLeaf )
{
- newPage.children = new Page[newPage.nbElems + 1];
System.arraycopy( children, start, newPage.children, 0, middle );
newPage.children[middle] = leftPage;
newPage.children[middle + 1] = rightPage;
@@ -678,12 +660,12 @@ public class Page<K, V> implements Clone
* @param value the new value
* @return The copied page
*/
- private InsertResult<K, V> replaceValue( long revision, int index, V value )
+ private Page<K, V> replaceValue( long revision, int index, V value )
{
Page<K, V> newPage = copy( revision );
newPage.values[index] = value;
- return new PageResult<K, V>( newPage );
+ return newPage;
}
@@ -697,21 +679,14 @@ public class Page<K, V> implements Clone
* @param value The value to insert
* @return The modified page with the <K,V> element added
*/
- @SuppressWarnings("unchecked")
- private InsertResult<K, V> addElement( long revision, int index, K key, V value )
+ private Page<K, V> addElement( long revision, int index, K key, V value )
{
- Page<K, V> newPage = new Page<K, V>();
- newPage.btree = btree;
- newPage.revision = revision;
- newPage.isLeaf = isLeaf;
- newPage.recordId = btree.generateRecordId();
- newPage.nbElems = nbElems + 1;
- newPage.keys = (K[])new Object[newPage.nbElems];
+ Page<K, V> newPage = new Page<K, V>( btree, revision, nbElems + 1, true );
+
copyAndAdd( keys, newPage.keys, key, index );
- newPage.values = (V[])new Object[newPage.nbElems];
copyAndAdd( values, newPage.values, value, index );
- return new PageResult<K, V>( newPage );
+ return newPage;
}
@@ -764,23 +739,15 @@ public class Page<K, V> implements Clone
* @param revision The new revision
* @return The copied page
*/
- @SuppressWarnings("unchecked")
private Page<K, V> copy( long revision )
{
- Page<K, V> newPage = new Page<K, V>();
- newPage.btree = btree;
- newPage.revision = revision;
- newPage.isLeaf = isLeaf;
- newPage.recordId = btree.generateRecordId();
- newPage.nbElems = nbElems;
- newPage.keys = (K[])new Object[newPage.nbElems];
+ Page<K, V> newPage = new Page<K, V>( btree, revision, nbElems, isLeaf );
+
System.arraycopy( keys, 0, newPage.keys, 0, newPage.nbElems );
- newPage.values = (V[])new Object[newPage.nbElems];
System.arraycopy( values, 0, newPage.values, 0, newPage.nbElems );
if ( ! newPage.isLeaf )
{
- newPage.children = new Page[newPage.nbElems + 1];
System.arraycopy( children, 0, newPage.children, 0, newPage.nbElems + 1 );
}
@@ -817,73 +784,6 @@ public class Page<K, V> implements Clone
/**
- * Result from insert() method call. If the insertion has created
- * a new page, it will be contained in the overflow field.
- * If the inserted element already exist, then we will store
- * the existing element.
- */
- /* No qualifier */ interface InsertResult<K, V>
- {
- }
-
- /**
- * A inner class used to store a split page. It has a pivot element
- * and a left and right page.
- */
- static class OverflowResult<K, V> implements InsertResult<K, V>
- {
- /** The Left page if it has been split, or the new page containing the new value */
- Page<K, V> leftPage;
-
- /** The right page if it has been split, null otherwise*/
- Page<K, V> rightPage;
-
- /** The Key that must be copied in the parent page if the page was full */
- K pivotKey;
-
- /** The Value that must be copied in the parent page if the page was full */
- V pivotValue;
-
- /**
- * @see Object#toString()
- */
- public String toString()
- {
- // This is a split page
- return "Split Page [" + leftPage.recordId + ", r" + leftPage.revision + "], [" +
- rightPage.recordId + ", r" + rightPage.revision + "], <" + pivotKey + "/" + pivotValue + ">";
- }
- }
-
-
- /**
- * An inner class used to store a modified page.
- */
- static class PageResult<K, V> implements InsertResult<K, V>
- {
- /** The modified page */
- Page<K, V> page;
-
- /**
- * Create the instance of a PageResult
- * @param page The modified page
- */
- private PageResult( Page<K, V> page )
- {
- this.page = page;
- }
-
- /**
- * @see Object#toString()
- */
- public String toString()
- {
- return "Modified Page [" + page.recordId + ", r" + page.revision + "]";
- }
- }
-
-
- /**
* @see Object#toString()
*/
public String toString()