diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/CheckTuple.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/CheckTuple.java
deleted file mode 100644
index d7a24a6..0000000
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/CheckTuple.java
+++ /dev/null
@@ -1,73 +0,0 @@
-/*
- * Copyright 2009-2010 by The Regents of the University of California
- * Licensed 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 from
- * 
- *     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 edu.uci.ics.hyracks.storage.am.btree.tests;
-
-@SuppressWarnings({"rawtypes", "unchecked"})
-public class CheckTuple<T extends Comparable<T>> implements Comparable<T> {
-    private final int numKeys;    
-    private final Comparable[] tuple;
-    private int pos;
-
-    public CheckTuple(int numFields, int numKeys) {
-        this.numKeys = numKeys;
-        this.tuple = new Comparable[numFields];
-        pos = 0;
-    }
-
-    public void add(T e) {
-        tuple[pos++] = e;
-    }
-
-    @Override
-    public int compareTo(T o) {
-        CheckTuple<T> other = (CheckTuple<T>)o;
-        for (int i = 0; i < numKeys; i++) {            
-            int cmp = tuple[i].compareTo(other.get(i));
-            if (cmp != 0) {
-                return cmp;
-            }
-        }
-        return 0;
-    }
-
-    public T get(int idx) {
-        return (T)tuple[idx];
-    }
-    
-    public void set(int idx, T e) {
-        tuple[idx] = e;
-    }
-    
-    public int size() {
-        return tuple.length;
-    }
-    
-    public int getNumKeys() {
-        return numKeys;
-    }
-    
-    @Override
-    public String toString() {
-        StringBuilder strBuilder = new StringBuilder();
-        for (int i = 0; i < tuple.length; i++) {
-            strBuilder.append(tuple[i].toString());
-            if (i != tuple.length-1) {
-                strBuilder.append(" ");
-            }
-        }
-        return strBuilder.toString();
-    }
-}
\ No newline at end of file
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/IOrderedIndexTestContext.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/IOrderedIndexTestContext.java
deleted file mode 100644
index 0102180..0000000
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/IOrderedIndexTestContext.java
+++ /dev/null
@@ -1,52 +0,0 @@
-/*
- * Copyright 2009-2010 by The Regents of the University of California
- * Licensed 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 from
- * 
- *     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 edu.uci.ics.hyracks.storage.am.btree.tests;
-
-import java.util.TreeSet;
-
-import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
-import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
-import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
-import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
-
-@SuppressWarnings("rawtypes")
-public interface IOrderedIndexTestContext {
-    public int getFieldCount();
-    
-    public int getKeyFieldCount();
-        
-	public ISerializerDeserializer[] getFieldSerdes();
-	
-	public IBinaryComparatorFactory[] getComparatorFactories();
-    
-    public ITreeIndexAccessor getIndexAccessor();
-    
-    public ITreeIndex getIndex();
-
-    public ArrayTupleReference getTuple();
-    
-    public ArrayTupleBuilder getTupleBuilder();
-
-    public CheckTuple createIntCheckTuple(int[] fieldValues);
-    
-    public CheckTuple createStringCheckTuple(String[] fieldValues);
-    
-    public void insertCheckTuple(CheckTuple checkTuple, TreeSet<CheckTuple> checkTuples);
-    
-    public TreeSet<CheckTuple> getCheckTuples();
-}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexBulkLoadTest.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexBulkLoadTest.java
index 5d64f2d..4325d6c 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexBulkLoadTest.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexBulkLoadTest.java
@@ -24,34 +24,38 @@
 @SuppressWarnings("rawtypes")
 public abstract class OrderedIndexBulkLoadTest extends OrderedIndexTestDriver {
 
+    private final OrderedIndexTestUtils orderedIndexTestUtils;
     private final int bulkLoadRounds;
-    
+
     public OrderedIndexBulkLoadTest(BTreeLeafFrameType[] leafFrameTypesToTest, int bulkLoadRounds) {
         super(leafFrameTypesToTest);
         this.bulkLoadRounds = bulkLoadRounds;
+        this.orderedIndexTestUtils = new OrderedIndexTestUtils();
     }
 
     @Override
     protected void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType,
             ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey)
             throws Exception {
-        IOrderedIndexTestContext ctx = createTestContext(fieldSerdes, numKeys, leafType);
+        OrderedIndexTestContext ctx = createTestContext(fieldSerdes, numKeys, leafType);
         for (int i = 0; i < bulkLoadRounds; i++) {
-            // We assume all fieldSerdes are of the same type. Check the first one
+            // We assume all fieldSerdes are of the same type. Check the first
+            // one
             // to determine which field types to generate.
             if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
-                OrderedIndexTestUtils.bulkLoadIntTuples(ctx, numTuplesToInsert, getRandom());
+                orderedIndexTestUtils.bulkLoadIntTuples(ctx, numTuplesToInsert, getRandom());
             } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
-                OrderedIndexTestUtils.bulkLoadStringTuples(ctx, numTuplesToInsert, getRandom());
+                orderedIndexTestUtils.bulkLoadStringTuples(ctx, numTuplesToInsert, getRandom());
             }
-            OrderedIndexTestUtils.checkPointSearches(ctx);
-            OrderedIndexTestUtils.checkOrderedScan(ctx);
-            OrderedIndexTestUtils.checkDiskOrderScan(ctx);
-            OrderedIndexTestUtils.checkRangeSearch(ctx, lowKey, highKey, true, true);
+            orderedIndexTestUtils.checkPointSearches(ctx);
+            orderedIndexTestUtils.checkScan(ctx);
+            orderedIndexTestUtils.checkDiskOrderScan(ctx);
+            orderedIndexTestUtils.checkRangeSearch(ctx, lowKey, highKey, true, true);
             if (prefixLowKey != null && prefixHighKey != null) {
-                OrderedIndexTestUtils.checkRangeSearch(ctx, prefixLowKey, prefixHighKey, true, true);
+                orderedIndexTestUtils.checkRangeSearch(ctx, prefixLowKey, prefixHighKey, true, true);
             }
         }
+        ctx.getIndex().close();
     }
 
     @Override
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexDeleteTest.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexDeleteTest.java
index a472934..4d9a235 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexDeleteTest.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexDeleteTest.java
@@ -24,8 +24,11 @@
 @SuppressWarnings("rawtypes")
 public abstract class OrderedIndexDeleteTest extends OrderedIndexTestDriver {
 
+    private final OrderedIndexTestUtils orderedIndexTestUtils;
+
     public OrderedIndexDeleteTest(BTreeLeafFrameType[] leafFrameTypesToTest) {
         super(leafFrameTypesToTest);
+        this.orderedIndexTestUtils = new OrderedIndexTestUtils();
     }
 
     private static final int numInsertRounds = 3;
@@ -35,27 +38,29 @@
     protected void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType,
             ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey)
             throws Exception {
-        IOrderedIndexTestContext ctx = createTestContext(fieldSerdes, numKeys, leafType);
+        OrderedIndexTestContext ctx = createTestContext(fieldSerdes, numKeys, leafType);
         for (int i = 0; i < numInsertRounds; i++) {
             // We assume all fieldSerdes are of the same type. Check the first
             // one to determine which field types to generate.
             if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
-                OrderedIndexTestUtils.insertIntTuples(ctx, numTuplesToInsert, getRandom());
+                orderedIndexTestUtils.insertIntTuples(ctx, numTuplesToInsert, getRandom());
             } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
-                OrderedIndexTestUtils.insertStringTuples(ctx, numTuplesToInsert, getRandom());
+                orderedIndexTestUtils.insertStringTuples(ctx, numTuplesToInsert, getRandom());
             }
-            int numTuplesPerDeleteRound = (int) Math.ceil((float) ctx.getCheckTuples().size() / (float) numDeleteRounds);
+            int numTuplesPerDeleteRound = (int) Math
+                    .ceil((float) ctx.getCheckTuples().size() / (float) numDeleteRounds);
             for (int j = 0; j < numDeleteRounds; j++) {
-                OrderedIndexTestUtils.deleteTuples(ctx, numTuplesPerDeleteRound, getRandom());
-                OrderedIndexTestUtils.checkPointSearches(ctx);
-                OrderedIndexTestUtils.checkOrderedScan(ctx);
-                OrderedIndexTestUtils.checkDiskOrderScan(ctx);
-                OrderedIndexTestUtils.checkRangeSearch(ctx, lowKey, highKey, true, true);
+                orderedIndexTestUtils.deleteTuples(ctx, numTuplesPerDeleteRound, getRandom());
+                orderedIndexTestUtils.checkPointSearches(ctx);
+                orderedIndexTestUtils.checkScan(ctx);
+                orderedIndexTestUtils.checkDiskOrderScan(ctx);
+                orderedIndexTestUtils.checkRangeSearch(ctx, lowKey, highKey, true, true);
                 if (prefixLowKey != null && prefixHighKey != null) {
-                    OrderedIndexTestUtils.checkRangeSearch(ctx, prefixLowKey, prefixHighKey, true, true);
+                    orderedIndexTestUtils.checkRangeSearch(ctx, prefixLowKey, prefixHighKey, true, true);
                 }
             }
         }
+        ctx.getIndex().close();
     }
 
     @Override
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexInsertTest.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexInsertTest.java
index 65bfc81..8561bcb 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexInsertTest.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexInsertTest.java
@@ -33,31 +33,34 @@
  */
 @SuppressWarnings("rawtypes")
 public abstract class OrderedIndexInsertTest extends OrderedIndexTestDriver {
-    
+
+    private final OrderedIndexTestUtils orderedIndexTestUtils;
+
     public OrderedIndexInsertTest(BTreeLeafFrameType[] leafFrameTypesToTest) {
         super(leafFrameTypesToTest);
+        this.orderedIndexTestUtils = new OrderedIndexTestUtils();
     }
 
     @Override
     protected void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType,
             ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey)
             throws Exception {
-        IOrderedIndexTestContext ctx = createTestContext(fieldSerdes, numKeys, leafType);
+        OrderedIndexTestContext ctx = createTestContext(fieldSerdes, numKeys, leafType);
         // We assume all fieldSerdes are of the same type. Check the first one
         // to determine which field types to generate.
         if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
-            OrderedIndexTestUtils.insertIntTuples(ctx, numTuplesToInsert, getRandom());
+            orderedIndexTestUtils.insertIntTuples(ctx, numTuplesToInsert, getRandom());
         } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
-            OrderedIndexTestUtils.insertStringTuples(ctx, numTuplesToInsert, getRandom());
+            orderedIndexTestUtils.insertStringTuples(ctx, numTuplesToInsert, getRandom());
         }
 
-        OrderedIndexTestUtils.checkPointSearches(ctx);
-        OrderedIndexTestUtils.checkOrderedScan(ctx);
-        OrderedIndexTestUtils.checkDiskOrderScan(ctx);
+        orderedIndexTestUtils.checkPointSearches(ctx);
+        orderedIndexTestUtils.checkScan(ctx);
+        orderedIndexTestUtils.checkDiskOrderScan(ctx);
 
-        OrderedIndexTestUtils.checkRangeSearch(ctx, lowKey, highKey, true, true);
+        orderedIndexTestUtils.checkRangeSearch(ctx, lowKey, highKey, true, true);
         if (prefixLowKey != null && prefixHighKey != null) {
-            OrderedIndexTestUtils.checkRangeSearch(ctx, prefixLowKey, prefixHighKey, true, true);
+            orderedIndexTestUtils.checkRangeSearch(ctx, prefixLowKey, prefixHighKey, true, true);
         }
         ctx.getIndex().close();
     }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexTestContext.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexTestContext.java
index 888a5a9..caf51bb 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexTestContext.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexTestContext.java
@@ -18,73 +18,17 @@
 import java.util.TreeSet;
 
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
-import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
-import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.common.test.CheckTuple;
+import edu.uci.ics.hyracks.storage.am.common.test.TreeIndexTestContext;
 
 @SuppressWarnings("rawtypes")
-public abstract class OrderedIndexTestContext implements IOrderedIndexTestContext {
-    protected final ISerializerDeserializer[] fieldSerdes;
-    protected final ITreeIndex treeIndex;
-    protected final ArrayTupleBuilder tupleBuilder;
-    protected final ArrayTupleReference tuple = new ArrayTupleReference();
+public abstract class OrderedIndexTestContext extends TreeIndexTestContext<CheckTuple> {
+
     protected final TreeSet<CheckTuple> checkTuples = new TreeSet<CheckTuple>();
-    protected final ITreeIndexAccessor indexAccessor;
 
     public OrderedIndexTestContext(ISerializerDeserializer[] fieldSerdes, ITreeIndex treeIndex) {
-        this.fieldSerdes = fieldSerdes;
-        this.treeIndex = treeIndex;
-        this.indexAccessor = treeIndex.createAccessor();
-        this.tupleBuilder = new ArrayTupleBuilder(fieldSerdes.length);
-    }
-
-    @Override
-    public int getFieldCount() {
-        return fieldSerdes.length;
-    }
-
-    @Override
-    public ITreeIndexAccessor getIndexAccessor() {
-        return indexAccessor;
-    }
-
-    @Override
-    public ArrayTupleReference getTuple() {
-        return tuple;
-    }
-
-    @Override
-    public ArrayTupleBuilder getTupleBuilder() {
-        return tupleBuilder;
-    }
-
-    @Override
-    public CheckTuple createIntCheckTuple(int[] fieldValues) {        
-        CheckTuple<Integer> checkTuple = new CheckTuple<Integer>(getFieldCount(), getKeyFieldCount());
-        for(int v : fieldValues) {
-            checkTuple.add(v);
-        }
-        return checkTuple;
-    }
-
-    @Override
-    public CheckTuple createStringCheckTuple(String[] fieldValues) {
-        CheckTuple<String> checkTuple = new CheckTuple<String>(getFieldCount(), getKeyFieldCount());
-        for(String s : fieldValues) {
-            checkTuple.add((String)s);
-        }
-        return checkTuple;
-    }
-    
-    @Override
-    public void insertCheckTuple(CheckTuple checkTuple, TreeSet<CheckTuple> checkTuples) {        
-        checkTuples.add(checkTuple);
-    }
-
-    @Override
-    public ISerializerDeserializer[] getFieldSerdes() {
-        return fieldSerdes;
+        super(fieldSerdes, treeIndex);
     }
 
     @Override
@@ -92,8 +36,4 @@
         return checkTuples;
     }
 
-    @Override
-    public ITreeIndex getIndex() {
-        return treeIndex;
-    }
 }
\ No newline at end of file
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexTestDriver.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexTestDriver.java
index e89c38f..0a99809 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexTestDriver.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexTestDriver.java
@@ -31,132 +31,146 @@
 @SuppressWarnings("rawtypes")
 public abstract class OrderedIndexTestDriver {
     protected final Logger LOGGER = Logger.getLogger(OrderedIndexTestDriver.class.getName());
-    
+
     protected static final int numTuplesToInsert = 10000;
-    
-    protected abstract IOrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType) throws Exception;
+
+    protected abstract OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+            BTreeLeafFrameType leafType) throws Exception;
+
     protected abstract Random getRandom();
-    protected abstract void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType, ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey) throws Exception;
+
+    protected abstract void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType,
+            ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey)
+            throws Exception;
+
     protected abstract String getTestOpName();
-    
+
     protected final BTreeLeafFrameType[] leafFrameTypesToTest;
-    
+
     public OrderedIndexTestDriver(BTreeLeafFrameType[] leafFrameTypesToTest) {
         this.leafFrameTypesToTest = leafFrameTypesToTest;
     }
-    
+
     @Test
-    public void oneIntKeyAndValue() throws Exception {        
+    public void oneIntKeyAndValue() throws Exception {
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info("BTree " + getTestOpName() + " Test With One Int Key And Value.");
         }
-                
-        ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+
+        ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE,
+                IntegerSerializerDeserializer.INSTANCE };
         // Range search in [-1000, 1000]
         ITupleReference lowKey = TupleUtils.createIntegerTuple(-1000);
         ITupleReference highKey = TupleUtils.createIntegerTuple(1000);
-        
+
         for (BTreeLeafFrameType leafFrameType : leafFrameTypesToTest) {
             runTest(fieldSerdes, 1, leafFrameType, lowKey, highKey, null, null);
         }
     }
-    
+
     @Test
-    public void twoIntKeys() throws Exception {    
+    public void twoIntKeys() throws Exception {
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info("BTree " + getTestOpName() + " Test With Two Int Keys.");
         }
-        
-        ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
-        
+
+        ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE,
+                IntegerSerializerDeserializer.INSTANCE };
+
         // Range search in [50 0, 50 500]
         ITupleReference lowKey = TupleUtils.createIntegerTuple(50, 0);
         ITupleReference highKey = TupleUtils.createIntegerTuple(50, 500);
-        
+
         // Prefix range search in [50, 50]
         ITupleReference prefixLowKey = TupleUtils.createIntegerTuple(50);
         ITupleReference prefixHighKey = TupleUtils.createIntegerTuple(50);
-        
+
         for (BTreeLeafFrameType leafFrameType : leafFrameTypesToTest) {
             runTest(fieldSerdes, 2, leafFrameType, lowKey, highKey, prefixLowKey, prefixHighKey);
         }
     }
-    
+
     @Test
-    public void twoIntKeysAndValues() throws Exception {  
+    public void twoIntKeysAndValues() throws Exception {
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info("BTree " + getTestOpName() + " Test With Two Int Keys And Values.");
         }
-        
-        ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
-        
+
+        ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE,
+                IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE,
+                IntegerSerializerDeserializer.INSTANCE };
+
         // Range search in [50 100, 100 100]
         ITupleReference lowKey = TupleUtils.createIntegerTuple(-100, -100);
         ITupleReference highKey = TupleUtils.createIntegerTuple(100, 100);
-        
+
         // Prefix range search in [50, 50]
         ITupleReference prefixLowKey = TupleUtils.createIntegerTuple(50);
         ITupleReference prefixHighKey = TupleUtils.createIntegerTuple(50);
-        
+
         for (BTreeLeafFrameType leafFrameType : leafFrameTypesToTest) {
             runTest(fieldSerdes, 2, leafFrameType, lowKey, highKey, prefixLowKey, prefixHighKey);
         }
-    }        
-    
+    }
+
     @Test
-    public void oneStringKeyAndValue() throws Exception {        
+    public void oneStringKeyAndValue() throws Exception {
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info("BTree " + getTestOpName() + " Test With One String Key And Value.");
         }
-        
-        ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
-        
+
+        ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE,
+                UTF8StringSerializerDeserializer.INSTANCE };
+
         // Range search in ["cbf", cc7"]
         ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
         ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7");
-        
+
         for (BTreeLeafFrameType leafFrameType : leafFrameTypesToTest) {
             runTest(fieldSerdes, 1, leafFrameType, lowKey, highKey, null, null);
         }
     }
-    
+
     @Test
     public void twoStringKeys() throws Exception {
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info("BTree " + getTestOpName() + " Test With Two String Keys.");
         }
-        
-        ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
-        
+
+        ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE,
+                UTF8StringSerializerDeserializer.INSTANCE };
+
         // Range search in ["cbf", "ddd", cc7", "eee"]
         ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf", "ddd");
         ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7", "eee");
-        
+
         // Prefix range search in ["cbf", cc7"]
         ITupleReference prefixLowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
         ITupleReference prefixHighKey = TupleUtils.createTuple(fieldSerdes, "cc7");
-        
+
         for (BTreeLeafFrameType leafFrameType : leafFrameTypesToTest) {
             runTest(fieldSerdes, 2, leafFrameType, lowKey, highKey, prefixLowKey, prefixHighKey);
         }
     }
-    
+
     @Test
-    public void twoStringKeysAndValues() throws Exception {      
+    public void twoStringKeysAndValues() throws Exception {
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info("BTree " + getTestOpName() + " Test With Two String Keys And Values.");
         }
-        
-        ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
-        
+
+        ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE,
+                UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE,
+                UTF8StringSerializerDeserializer.INSTANCE };
+
         // Range search in ["cbf", "ddd", cc7", "eee"]
         ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf", "ddd");
         ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7", "eee");
-        
+
         // Prefix range search in ["cbf", cc7"]
         ITupleReference prefixLowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
         ITupleReference prefixHighKey = TupleUtils.createTuple(fieldSerdes, "cc7");
-        
+
         for (BTreeLeafFrameType leafFrameType : leafFrameTypesToTest) {
             runTest(fieldSerdes, 2, leafFrameType, lowKey, highKey, prefixLowKey, prefixHighKey);
         }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexTestUtils.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexTestUtils.java
index 7843082..04c1f99 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexTestUtils.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexTestUtils.java
@@ -5,7 +5,7 @@
 import java.io.ByteArrayInputStream;
 import java.io.DataInput;
 import java.io.DataInputStream;
-import java.io.DataOutput;
+import java.util.Collection;
 import java.util.Iterator;
 import java.util.NavigableSet;
 import java.util.Random;
@@ -24,62 +24,41 @@
 import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeDuplicateKeyException;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
 import edu.uci.ics.hyracks.storage.am.btree.util.BTreeUtils;
-import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
-import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.test.CheckTuple;
+import edu.uci.ics.hyracks.storage.am.common.test.ITreeIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.common.test.TreeIndexTestUtils;
 
 @SuppressWarnings("rawtypes")
-public class OrderedIndexTestUtils {
-	private static final Logger LOGGER = Logger.getLogger(OrderedIndexTestUtils.class.getName());
-	
-	private static void compareActualAndExpected(ITupleReference actual, CheckTuple expected, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {
+public class OrderedIndexTestUtils extends TreeIndexTestUtils {
+    private static final Logger LOGGER = Logger.getLogger(OrderedIndexTestUtils.class.getName());
+
+    private static void compareActualAndExpected(ITupleReference actual, CheckTuple expected,
+            ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {
         for (int i = 0; i < fieldSerdes.length; i++) {
-            ByteArrayInputStream inStream = new ByteArrayInputStream(
-                    actual.getFieldData(i), actual.getFieldStart(i),
+            ByteArrayInputStream inStream = new ByteArrayInputStream(actual.getFieldData(i), actual.getFieldStart(i),
                     actual.getFieldLength(i));
             DataInput dataIn = new DataInputStream(inStream);
-            Object actualObj = fieldSerdes[i].deserialize(dataIn);            
+            Object actualObj = fieldSerdes[i].deserialize(dataIn);
             if (!actualObj.equals(expected.get(i))) {
-                fail("Actual and expected fields do not match on field " + i + ".\nExpected: " + expected.get(i) + "\nActual  : " + actualObj);
+                fail("Actual and expected fields do not match on field " + i + ".\nExpected: " + expected.get(i)
+                        + "\nActual  : " + actualObj);
             }
         }
     }
-	
-	@SuppressWarnings("unchecked")
-    private static void createTupleFromCheckTuple(CheckTuple checkTuple, ArrayTupleBuilder tupleBuilder, ArrayTupleReference tuple, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {
-        int fieldCount = tupleBuilder.getFieldEndOffsets().length; 
-        DataOutput dos = tupleBuilder.getDataOutput();
-        tupleBuilder.reset();
-        for (int i = 0; i < fieldCount; i++) {
-            fieldSerdes[i].serialize(checkTuple.get(i), dos);
-            tupleBuilder.addFieldEndOffset();
-        }
-        tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
-    }
-	
-	@SuppressWarnings("unchecked")
-    private static CheckTuple createCheckTupleFromTuple(ITupleReference tuple, ISerializerDeserializer[] fieldSerdes, int numKeys) throws HyracksDataException {
-        CheckTuple checkTuple = new CheckTuple(fieldSerdes.length, numKeys);
-        int fieldCount = Math.min(fieldSerdes.length, tuple.getFieldCount());
-        for (int i = 0; i < fieldCount; i++) {
-            ByteArrayInputStream inStream = new ByteArrayInputStream(
-                    tuple.getFieldData(i), tuple.getFieldStart(i),
-                    tuple.getFieldLength(i));
-            DataInput dataIn = new DataInputStream(inStream);
-            Comparable fieldObj = (Comparable)fieldSerdes[i].deserialize(dataIn);
-            checkTuple.add(fieldObj);
-        }
-        return checkTuple;
-    }
-	
-	@SuppressWarnings("unchecked")
-    // Create a new TreeSet containing the elements satisfying the prefix search.
-    // Implementing prefix search by changing compareTo() in CheckTuple does not work.
-    public static TreeSet<CheckTuple> getPrefixExpectedSubset(TreeSet<CheckTuple> checkTuples, CheckTuple lowKey, CheckTuple highKey) {
+
+    @SuppressWarnings("unchecked")
+    // Create a new TreeSet containing the elements satisfying the prefix
+    // search.
+    // Implementing prefix search by changing compareTo() in CheckTuple does not
+    // work.
+    public static TreeSet<CheckTuple> getPrefixExpectedSubset(TreeSet<CheckTuple> checkTuples, CheckTuple lowKey,
+            CheckTuple highKey) {
         TreeSet<CheckTuple> expectedSubset = new TreeSet<CheckTuple>();
         Iterator<CheckTuple> iter = checkTuples.iterator();
-        while(iter.hasNext()) {
+        while (iter.hasNext()) {
             CheckTuple t = iter.next();
             boolean geLowKey = true;
             boolean leHighKey = true;
@@ -101,93 +80,34 @@
         }
         return expectedSubset;
     }
-	
-	public static void checkOrderedScan(IOrderedIndexTestContext ctx) throws Exception {
-        if (LOGGER.isLoggable(Level.INFO)) {
-            LOGGER.info("Testing Ordered Scan.");
-        }
-        ITreeIndexCursor scanCursor = ctx.getIndexAccessor().createSearchCursor();
-        RangePredicate nullPred = new RangePredicate(null, null, true, true, null, null);
-        ctx.getIndexAccessor().search(scanCursor, nullPred);
-        Iterator<CheckTuple> checkIter = ctx.getCheckTuples().iterator();
-        int actualCount = 0;
-        try {
-            while (scanCursor.hasNext()) {
-                if (!checkIter.hasNext()) {
-                    fail("Ordered scan returned more answers than expected.\nExpected: " + ctx.getCheckTuples().size());
-                }
-                scanCursor.next();
-                CheckTuple expectedTuple = checkIter.next();
-                ITupleReference tuple = scanCursor.getTuple();
-                compareActualAndExpected(tuple, expectedTuple, ctx.getFieldSerdes());
-                actualCount++;
-            }
-            if (actualCount < ctx.getCheckTuples().size()) {
-                fail("Ordered scan returned fewer answers than expected.\nExpected: " + ctx.getCheckTuples().size() + "\nActual  : " + actualCount);
-            }
-        } finally {
-            scanCursor.close();
-        }
-    }
-	
-    public static void checkDiskOrderScan(IOrderedIndexTestContext ctx) throws Exception {
-        try {
-            if (LOGGER.isLoggable(Level.INFO)) {
-                LOGGER.info("Testing Disk-Order Scan.");
-            }
-            ITreeIndexCursor diskOrderCursor = ctx.getIndexAccessor().createDiskOrderScanCursor();
-            ctx.getIndexAccessor().diskOrderScan(diskOrderCursor);
-            int actualCount = 0;
-            try {
-                while (diskOrderCursor.hasNext()) {
-                    diskOrderCursor.next();
-                    ITupleReference tuple = diskOrderCursor.getTuple();
-                    CheckTuple checkTuple = createCheckTupleFromTuple(tuple, ctx.getFieldSerdes(), ctx.getKeyFieldCount());
-                    if (!ctx.getCheckTuples().contains(checkTuple)) {
-                        fail("Disk-order scan returned unexpected answer: " + checkTuple.toString());
-                    }
-                    actualCount++;
-                }
-                if (actualCount < ctx.getCheckTuples().size()) {
-                    fail("Disk-order scan returned fewer answers than expected.\nExpected: "
-                            + ctx.getCheckTuples().size() + "\nActual  : " + actualCount);
-                }
-                if (actualCount > ctx.getCheckTuples().size()) {
-                    fail("Disk-order scan returned more answers than expected.\nExpected: "
-                            + ctx.getCheckTuples().size() + "\nActual  : " + actualCount);
-                }
-            } finally {
-                diskOrderCursor.close();
-            }
-        } catch (UnsupportedOperationException e) {
-            // Ignore exception because some indexes, e.g. the LSMBTree, don't
-            // support disk-order scan.
-            if (LOGGER.isLoggable(Level.INFO)) {
-                LOGGER.info("Ignoring disk-order scan since it's not supported.");
-            }
-        }
-    }
-    
-    public static void checkRangeSearch(IOrderedIndexTestContext ctx, ITupleReference lowKey, ITupleReference highKey, boolean lowKeyInclusive, boolean highKeyInclusive) throws Exception {
+
+    @SuppressWarnings("unchecked")
+    public void checkRangeSearch(ITreeIndexTestContext ctx, ITupleReference lowKey, ITupleReference highKey,
+            boolean lowKeyInclusive, boolean highKeyInclusive) throws Exception {
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info("Testing Range Search.");
         }
         MultiComparator lowKeyCmp = BTreeUtils.getSearchMultiComparator(ctx.getComparatorFactories(), lowKey);
         MultiComparator highKeyCmp = BTreeUtils.getSearchMultiComparator(ctx.getComparatorFactories(), highKey);
         ITreeIndexCursor searchCursor = ctx.getIndexAccessor().createSearchCursor();
-        RangePredicate rangePred = new RangePredicate(lowKey, highKey, lowKeyInclusive, highKeyInclusive, lowKeyCmp, highKeyCmp);
+        RangePredicate rangePred = new RangePredicate(lowKey, highKey, lowKeyInclusive, highKeyInclusive, lowKeyCmp,
+                highKeyCmp);
         ctx.getIndexAccessor().search(searchCursor, rangePred);
-        // Get the subset of elements from the expected set within given key range.
+        // Get the subset of elements from the expected set within given key
+        // range.
         CheckTuple lowKeyCheck = createCheckTupleFromTuple(lowKey, ctx.getFieldSerdes(), lowKeyCmp.getKeyFieldCount());
-        CheckTuple highKeyCheck = createCheckTupleFromTuple(highKey, ctx.getFieldSerdes(), highKeyCmp.getKeyFieldCount());
+        CheckTuple highKeyCheck = createCheckTupleFromTuple(highKey, ctx.getFieldSerdes(),
+                highKeyCmp.getKeyFieldCount());
         NavigableSet<CheckTuple> expectedSubset = null;
-        if (lowKeyCmp.getKeyFieldCount() < ctx.getKeyFieldCount() || 
-                highKeyCmp.getKeyFieldCount() < ctx.getKeyFieldCount()) {
+        if (lowKeyCmp.getKeyFieldCount() < ctx.getKeyFieldCount()
+                || highKeyCmp.getKeyFieldCount() < ctx.getKeyFieldCount()) {
             // Searching on a key prefix (low key or high key or both).
-            expectedSubset = getPrefixExpectedSubset(ctx.getCheckTuples(), lowKeyCheck, highKeyCheck);
+            expectedSubset = getPrefixExpectedSubset((TreeSet<CheckTuple>) ctx.getCheckTuples(), lowKeyCheck,
+                    highKeyCheck);
         } else {
             // Searching on all key fields.
-            expectedSubset = ctx.getCheckTuples().subSet(lowKeyCheck, lowKeyInclusive, highKeyCheck, highKeyInclusive);
+            expectedSubset = ((TreeSet<CheckTuple>) ctx.getCheckTuples()).subSet(lowKeyCheck, lowKeyInclusive,
+                    highKeyCheck, highKeyInclusive);
         }
         Iterator<CheckTuple> checkIter = expectedSubset.iterator();
         int actualCount = 0;
@@ -203,40 +123,42 @@
                 actualCount++;
             }
             if (actualCount < expectedSubset.size()) {
-                fail("Range search returned fewer answers than expected.\nExpected: " + expectedSubset.size() + "\nActual  : " + actualCount);
+                fail("Range search returned fewer answers than expected.\nExpected: " + expectedSubset.size()
+                        + "\nActual  : " + actualCount);
             }
         } finally {
             searchCursor.close();
         }
     }
-	
-    public static void checkPointSearches(IOrderedIndexTestContext ctx) throws Exception {
+
+    public void checkPointSearches(ITreeIndexTestContext ictx) throws Exception {
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info("Testing Point Searches On All Expected Keys.");
-        }        
-        
+        }
+        OrderedIndexTestContext ctx = (OrderedIndexTestContext) ictx;
         ITreeIndexCursor searchCursor = ctx.getIndexAccessor().createSearchCursor();
-        
+
         ArrayTupleBuilder lowKeyBuilder = new ArrayTupleBuilder(ctx.getKeyFieldCount());
         ArrayTupleReference lowKey = new ArrayTupleReference();
         ArrayTupleBuilder highKeyBuilder = new ArrayTupleBuilder(ctx.getKeyFieldCount());
         ArrayTupleReference highKey = new ArrayTupleReference();
         RangePredicate rangePred = new RangePredicate(lowKey, highKey, true, true, null, null);
 
-        // Iterate through expected tuples, and perform a point search in the BTree to verify the tuple can be reached.
+        // Iterate through expected tuples, and perform a point search in the
+        // BTree to verify the tuple can be reached.
         for (CheckTuple checkTuple : ctx.getCheckTuples()) {
             createTupleFromCheckTuple(checkTuple, lowKeyBuilder, lowKey, ctx.getFieldSerdes());
             createTupleFromCheckTuple(checkTuple, highKeyBuilder, highKey, ctx.getFieldSerdes());
             MultiComparator lowKeyCmp = BTreeUtils.getSearchMultiComparator(ctx.getComparatorFactories(), lowKey);
             MultiComparator highKeyCmp = BTreeUtils.getSearchMultiComparator(ctx.getComparatorFactories(), highKey);
-                        
+
             rangePred.setLowKey(lowKey, true);
             rangePred.setHighKey(highKey, true);
             rangePred.setLowKeyComparator(lowKeyCmp);
             rangePred.setHighKeyComparator(highKeyCmp);
-            
+
             ctx.getIndexAccessor().search(searchCursor, rangePred);
-            
+
             try {
                 // We expect exactly one answer.
                 if (searchCursor.hasNext()) {
@@ -252,40 +174,9 @@
             }
         }
     }
-    
-	public static void insertIntTuples(IOrderedIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
-        int fieldCount = ctx.getFieldCount();
-        int numKeyFields = ctx.getKeyFieldCount();
-        int[] fieldValues = new int[ctx.getFieldCount()];
-        // Scale range of values according to number of keys. 
-        // For example, for 2 keys we want the square root of numTuples, for 3 keys the cube root of numTuples, etc.        
-        int maxValue = (int)Math.ceil(Math.pow(numTuples, 1.0/(double)numKeyFields));
-        for (int i = 0; i < numTuples; i++) {
-            // Set keys.
-            for (int j = 0; j < numKeyFields; j++) {
-                fieldValues[j] = rnd.nextInt() % maxValue;
-            }
-            // Set values.
-            for (int j = numKeyFields; j < fieldCount; j++) {
-                fieldValues[j] = j;
-            }
-            TupleUtils.createIntegerTuple(ctx.getTupleBuilder(), ctx.getTuple(), fieldValues);
-            if (LOGGER.isLoggable(Level.INFO)) {
-                if ((i + 1) % (numTuples / Math.min(10, numTuples)) == 0) {
-                    LOGGER.info("Inserting Tuple " + (i + 1) + "/" + numTuples);
-                }
-            }
-            try {
-            	ctx.getIndexAccessor().insert(ctx.getTuple());
-                // Set expected values. Do this only after insertion succeeds because we ignore duplicate keys.
-                ctx.insertCheckTuple(ctx.createIntCheckTuple(fieldValues), ctx.getCheckTuples());
-            } catch (BTreeDuplicateKeyException e) {
-                // Ignore duplicate key insertions.
-            }                        
-        }
-    }
-	
-	public static void insertStringTuples(IOrderedIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
+
+    @SuppressWarnings("unchecked")
+    public void insertStringTuples(ITreeIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
         int fieldCount = ctx.getFieldCount();
         int numKeyFields = ctx.getKeyFieldCount();
         String[] fieldValues = new String[fieldCount];
@@ -304,45 +195,20 @@
             for (int j = numKeyFields; j < fieldCount; j++) {
                 fieldValues[j] = getRandomString(5, rnd);
             }
-            TupleUtils.createTuple(ctx.getTupleBuilder(), ctx.getTuple(), ctx.getFieldSerdes(), (Object[])fieldValues);
+            TupleUtils.createTuple(ctx.getTupleBuilder(), ctx.getTuple(), ctx.getFieldSerdes(), (Object[]) fieldValues);
             try {
                 ctx.getIndexAccessor().insert(ctx.getTuple());
-                // Set expected values. Do this only after insertion succeeds because we ignore duplicate keys.
-                ctx.insertCheckTuple(ctx.createStringCheckTuple(fieldValues), ctx.getCheckTuples());
+                // Set expected values. Do this only after insertion succeeds
+                // because we ignore duplicate keys.
+                ctx.insertCheckTuple(createStringCheckTuple(fieldValues, ctx.getKeyFieldCount()), ctx.getCheckTuples());
             } catch (BTreeDuplicateKeyException e) {
                 // Ignore duplicate key insertions.
             }
         }
     }
-	
-	public static void bulkLoadIntTuples(IOrderedIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
-        int fieldCount = ctx.getFieldCount();
-        int numKeyFields = ctx.getKeyFieldCount();
-        int[] fieldValues = new int[ctx.getFieldCount()];
-        int maxValue = (int)Math.ceil(Math.pow(numTuples, 1.0/(double)numKeyFields));
-        TreeSet<CheckTuple> tmpCheckTuples = new TreeSet<CheckTuple>();
-        for (int i = 0; i < numTuples; i++) {
-            // Set keys.
-            for (int j = 0; j < numKeyFields; j++) {
-                fieldValues[j] = rnd.nextInt() % maxValue;
-            }
-            // Set values.
-            for (int j = numKeyFields; j < fieldCount; j++) {
-                fieldValues[j] = j;
-            }
-            
-            // Set expected values. We also use these as the pre-sorted stream for bulk loading.
-            ctx.insertCheckTuple(ctx.createIntCheckTuple(fieldValues), tmpCheckTuples);
-        }
-        bulkLoadCheckTuples(ctx, tmpCheckTuples);
-        
-        // Add tmpCheckTuples to ctx check tuples for comparing searches.
-        for (CheckTuple checkTuple : tmpCheckTuples) {
-            ctx.insertCheckTuple(checkTuple, ctx.getCheckTuples());
-        }
-    }
-    
-    public static void bulkLoadStringTuples(IOrderedIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
+
+    @SuppressWarnings("unchecked")
+    public void bulkLoadStringTuples(ITreeIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
         int fieldCount = ctx.getFieldCount();
         int numKeyFields = ctx.getKeyFieldCount();
         String[] fieldValues = new String[fieldCount];
@@ -357,72 +223,21 @@
             for (int j = numKeyFields; j < fieldCount; j++) {
                 fieldValues[j] = getRandomString(5, rnd);
             }
-            // Set expected values. We also use these as the pre-sorted stream for bulk loading.
-            ctx.insertCheckTuple(ctx.createStringCheckTuple(fieldValues), tmpCheckTuples);
+            // Set expected values. We also use these as the pre-sorted stream
+            // for bulk loading.
+            ctx.insertCheckTuple(createStringCheckTuple(fieldValues, ctx.getKeyFieldCount()), tmpCheckTuples);
         }
         bulkLoadCheckTuples(ctx, tmpCheckTuples);
-        
+
         // Add tmpCheckTuples to ctx check tuples for comparing searches.
         for (CheckTuple checkTuple : tmpCheckTuples) {
             ctx.insertCheckTuple(checkTuple, ctx.getCheckTuples());
         }
     }
-    
-    private static void bulkLoadCheckTuples(IOrderedIndexTestContext ctx, TreeSet<CheckTuple> checkTuples) throws HyracksDataException, TreeIndexException {
-        int fieldCount = ctx.getFieldCount();
-        int numTuples = checkTuples.size();
-        ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
-        ArrayTupleReference tuple = new ArrayTupleReference();
-        // Perform bulk load.
-        IIndexBulkLoadContext bulkLoadCtx = ctx.getIndex().beginBulkLoad(0.7f);
-        int c = 1;
-        for (CheckTuple checkTuple : checkTuples) {
-            if (LOGGER.isLoggable(Level.INFO)) {
-                if (c % (numTuples / 10) == 0) {
-                    LOGGER.info("Bulk Loading Tuple " + c + "/" + numTuples);
-                }
-            }
-            createTupleFromCheckTuple(checkTuple, tupleBuilder, tuple, ctx.getFieldSerdes());
-            ctx.getIndex().bulkLoadAddTuple(tuple, bulkLoadCtx);
-            c++;
-        }
-        ctx.getIndex().endBulkLoad(bulkLoadCtx);
-    }
-    
-    public static void deleteTuples(IOrderedIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
-        ArrayTupleBuilder deleteTupleBuilder = new ArrayTupleBuilder(ctx.getKeyFieldCount());
-        ArrayTupleReference deleteTuple = new ArrayTupleReference();
-        int numCheckTuples = ctx.getCheckTuples().size();        
-        // Copy CheckTuple references into array, so we can randomly pick from there.
-        CheckTuple[] checkTuples = new CheckTuple[numCheckTuples];
-        int idx = 0;
-        for (CheckTuple checkTuple : ctx.getCheckTuples()) {
-            checkTuples[idx++] = checkTuple;
-        }
-        for (int i = 0; i < numTuples && numCheckTuples > 0; i++) {
-            if (LOGGER.isLoggable(Level.INFO)) {
-                if ((i + 1) % (numTuples / Math.min(10, numTuples)) == 0) {
-                    LOGGER.info("Deleting Tuple " + (i + 1) + "/" + numTuples);
-                }
-            }
-            int checkTupleIdx = Math.abs(rnd.nextInt() % numCheckTuples);
-            CheckTuple checkTuple = checkTuples[checkTupleIdx];            
-            createTupleFromCheckTuple(checkTuple, deleteTupleBuilder, deleteTuple, ctx.getFieldSerdes());
-            ctx.getIndexAccessor().delete(deleteTuple);
-            
-            // Remove check tuple from expected results.
-            ctx.getCheckTuples().remove(checkTuple);
-            
-            // Swap with last "valid" CheckTuple.
-            CheckTuple tmp = checkTuples[numCheckTuples - 1];
-            checkTuples[numCheckTuples - 1] = checkTuple;
-            checkTuples[checkTupleIdx] = tmp;
-            numCheckTuples--;                        
-        }
-    }
-    
+
     @SuppressWarnings("unchecked")
-    public static void updateTuples(IOrderedIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
+    public void updateTuples(ITreeIndexTestContext ictx, int numTuples, Random rnd) throws Exception {
+        OrderedIndexTestContext ctx = (OrderedIndexTestContext) ictx;
         int fieldCount = ctx.getFieldCount();
         int keyFieldCount = ctx.getKeyFieldCount();
         // This is a noop because we can only update non-key fields.
@@ -432,7 +247,8 @@
         ArrayTupleBuilder updateTupleBuilder = new ArrayTupleBuilder(fieldCount);
         ArrayTupleReference updateTuple = new ArrayTupleReference();
         int numCheckTuples = ctx.getCheckTuples().size();
-        // Copy CheckTuple references into array, so we can randomly pick from there.
+        // Copy CheckTuple references into array, so we can randomly pick from
+        // there.
         CheckTuple[] checkTuples = new CheckTuple[numCheckTuples];
         int idx = 0;
         for (CheckTuple checkTuple : ctx.getCheckTuples()) {
@@ -451,10 +267,10 @@
                 Comparable newValue = getRandomUpdateValue(ctx.getFieldSerdes()[j], rnd);
                 checkTuple.set(j, newValue);
             }
-            
-            createTupleFromCheckTuple(checkTuple, updateTupleBuilder, updateTuple, ctx.getFieldSerdes());            
+
+            createTupleFromCheckTuple(checkTuple, updateTupleBuilder, updateTuple, ctx.getFieldSerdes());
             ctx.getIndexAccessor().update(updateTuple);
-            
+
             // Swap with last "valid" CheckTuple.
             CheckTuple tmp = checkTuples[numCheckTuples - 1];
             checkTuples[numCheckTuples - 1] = checkTuple;
@@ -462,7 +278,15 @@
             numCheckTuples--;
         }
     }
-    
+
+    public CheckTuple createStringCheckTuple(String[] fieldValues, int numKeyFields) {
+        CheckTuple<String> checkTuple = new CheckTuple<String>(fieldValues.length, numKeyFields);
+        for (String s : fieldValues) {
+            checkTuple.add((String) s);
+        }
+        return checkTuple;
+    }
+
     private static Comparable getRandomUpdateValue(ISerializerDeserializer serde, Random rnd) {
         if (serde instanceof IntegerSerializerDeserializer) {
             return Integer.valueOf(rnd.nextInt());
@@ -471,8 +295,8 @@
         }
         return null;
     }
-	
-	public static String getRandomString(int length, Random rnd) {
+
+    public static String getRandomString(int length, Random rnd) {
         String s = Long.toHexString(Double.doubleToLongBits(rnd.nextDouble()));
         StringBuilder strBuilder = new StringBuilder();
         for (int i = 0; i < s.length() && i < length; i++) {
@@ -480,4 +304,72 @@
         }
         return strBuilder.toString();
     }
+
+    @Override
+    protected CheckTuple createCheckTuple(int numFields, int numKeyFields) {
+        return new CheckTuple(numFields, numKeyFields);
+    }
+
+    @Override
+    protected ISearchPredicate createNullSearchPredicate() {
+        return new RangePredicate(null, null, true, true, null, null);
+    }
+
+    @Override
+    public void checkExpectedResults(ITreeIndexCursor cursor, Collection checkTuples,
+            ISerializerDeserializer[] fieldSerdes, int keyFieldCount, Iterator<CheckTuple> checkIter) throws Exception {
+        int actualCount = 0;
+        try {
+            while (cursor.hasNext()) {
+                if (!checkIter.hasNext()) {
+                    fail("Ordered scan returned more answers than expected.\nExpected: " + checkTuples.size());
+                }
+                cursor.next();
+                CheckTuple expectedTuple = checkIter.next();
+                ITupleReference tuple = cursor.getTuple();
+                compareActualAndExpected(tuple, expectedTuple, fieldSerdes);
+                actualCount++;
+            }
+            if (actualCount < checkTuples.size()) {
+                fail("Ordered scan returned fewer answers than expected.\nExpected: " + checkTuples.size()
+                        + "\nActual  : " + actualCount);
+            }
+        } finally {
+            cursor.close();
+        }
+
+    }
+
+    @Override
+    protected CheckTuple createIntCheckTuple(int[] fieldValues, int numKeyFields) {
+        CheckTuple<Integer> checkTuple = new CheckTuple<Integer>(fieldValues.length, numKeyFields);
+        for (int v : fieldValues) {
+            checkTuple.add(v);
+        }
+        return checkTuple;
+    }
+
+    @Override
+    protected void setIntKeyFields(int[] fieldValues, int numKeyFields, int maxValue, Random rnd) {
+        for (int j = 0; j < numKeyFields; j++) {
+            fieldValues[j] = rnd.nextInt() % maxValue;
+        }
+    }
+
+    @Override
+    protected boolean insertTuple(ITreeIndexTestContext ctx) throws Exception {
+        try {
+            ctx.getIndexAccessor().insert(ctx.getTuple());
+        } catch (BTreeDuplicateKeyException e) {
+            // We set expected values only after insertion succeeds because we
+            // ignore duplicate keys.
+            return false;
+        }
+        return true;
+    }
+
+    @Override
+    protected Collection createCheckTuplesCollection() {
+        return new TreeSet<CheckTuple>();
+    }
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexUpdateTest.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexUpdateTest.java
index 6022058..56df7d3 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexUpdateTest.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tests/OrderedIndexUpdateTest.java
@@ -24,12 +24,15 @@
 @SuppressWarnings("rawtypes")
 public abstract class OrderedIndexUpdateTest extends OrderedIndexTestDriver {
 
+    private final OrderedIndexTestUtils orderedIndexTestUtils;
+
     public OrderedIndexUpdateTest(BTreeLeafFrameType[] leafFrameTypesToTest) {
         super(leafFrameTypesToTest);
+        this.orderedIndexTestUtils = new OrderedIndexTestUtils();
     }
 
     private static final int numUpdateRounds = 3;
-    
+
     @Override
     protected void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType,
             ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey)
@@ -38,23 +41,23 @@
         if (fieldSerdes.length == numKeys) {
             return;
         }
-        IOrderedIndexTestContext ctx = createTestContext(fieldSerdes, numKeys, leafType);
+        OrderedIndexTestContext ctx = createTestContext(fieldSerdes, numKeys, leafType);
         // We assume all fieldSerdes are of the same type. Check the first one
         // to determine which field types to generate.
         if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
-            OrderedIndexTestUtils.insertIntTuples(ctx, numTuplesToInsert, getRandom());
+            orderedIndexTestUtils.insertIntTuples(ctx, numTuplesToInsert, getRandom());
         } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
-            OrderedIndexTestUtils.insertStringTuples(ctx, numTuplesToInsert, getRandom());
+            orderedIndexTestUtils.insertStringTuples(ctx, numTuplesToInsert, getRandom());
         }
         int numTuplesPerDeleteRound = (int) Math.ceil((float) ctx.getCheckTuples().size() / (float) numUpdateRounds);
         for (int j = 0; j < numUpdateRounds; j++) {
-            OrderedIndexTestUtils.updateTuples(ctx, numTuplesPerDeleteRound, getRandom());
-            OrderedIndexTestUtils.checkPointSearches(ctx);
-            OrderedIndexTestUtils.checkOrderedScan(ctx);
-            OrderedIndexTestUtils.checkDiskOrderScan(ctx);
-            OrderedIndexTestUtils.checkRangeSearch(ctx, lowKey, highKey, true, true);
+            orderedIndexTestUtils.updateTuples(ctx, numTuplesPerDeleteRound, getRandom());
+            orderedIndexTestUtils.checkPointSearches(ctx);
+            orderedIndexTestUtils.checkScan(ctx);
+            orderedIndexTestUtils.checkDiskOrderScan(ctx);
+            orderedIndexTestUtils.checkRangeSearch(ctx, lowKey, highKey, true, true);
             if (prefixLowKey != null && prefixHighKey != null) {
-                OrderedIndexTestUtils.checkRangeSearch(ctx, prefixLowKey, prefixHighKey, true, true);
+                orderedIndexTestUtils.checkRangeSearch(ctx, prefixLowKey, prefixHighKey, true, true);
             }
         }
     }
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestContext.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestContext.java
index 4b0129c..7e6e932 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestContext.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestContext.java
@@ -15,6 +15,8 @@
 
 package edu.uci.ics.hyracks.storage.am.common.test;
 
+import java.util.Collection;
+
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
 import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
@@ -65,4 +67,9 @@
     public ITreeIndex getIndex() {
         return treeIndex;
     }
+
+    @Override
+    public void insertCheckTuple(T checkTuple, Collection<T> checkTuples) {
+        checkTuples.add(checkTuple);
+    }
 }
\ No newline at end of file
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestUtils.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestUtils.java
index 5b21485..8bf4ae5 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestUtils.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestUtils.java
@@ -27,12 +27,12 @@
 public abstract class TreeIndexTestUtils {
     private static final Logger LOGGER = Logger.getLogger(TreeIndexTestUtils.class.getName());
 
-    protected abstract CheckTuple createCheckTuple(int numfields, int numKeyFields);
+    protected abstract CheckTuple createCheckTuple(int numFields, int numKeyFields);
 
     protected abstract ISearchPredicate createNullSearchPredicate();
 
     public abstract void checkExpectedResults(ITreeIndexCursor cursor, Collection checkTuples,
-            ISerializerDeserializer[] fieldSerdes, int keyFieldCount) throws Exception;
+            ISerializerDeserializer[] fieldSerdes, int keyFieldCount, Iterator<CheckTuple> checkIter) throws Exception;
 
     protected abstract CheckTuple createIntCheckTuple(int[] fieldValues, int numKeyFields);
 
@@ -43,7 +43,7 @@
     protected abstract Collection createCheckTuplesCollection();
 
     @SuppressWarnings("unchecked")
-    private static void createTupleFromCheckTuple(CheckTuple checkTuple, ArrayTupleBuilder tupleBuilder,
+    public static void createTupleFromCheckTuple(CheckTuple checkTuple, ArrayTupleBuilder tupleBuilder,
             ArrayTupleReference tuple, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {
         int fieldCount = tupleBuilder.getFieldEndOffsets().length;
         DataOutput dos = tupleBuilder.getDataOutput();
@@ -70,6 +70,7 @@
         return checkTuple;
     }
 
+    @SuppressWarnings("unchecked")
     public void checkScan(ITreeIndexTestContext ctx) throws Exception {
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info("Testing Scan.");
@@ -77,7 +78,8 @@
         ITreeIndexCursor scanCursor = ctx.getIndexAccessor().createSearchCursor();
         ISearchPredicate nullPred = createNullSearchPredicate();
         ctx.getIndexAccessor().search(scanCursor, nullPred);
-        checkExpectedResults(scanCursor, ctx.getCheckTuples(), ctx.getFieldSerdes(), ctx.getKeyFieldCount());
+        Iterator<CheckTuple> checkIter = ctx.getCheckTuples().iterator();
+        checkExpectedResults(scanCursor, ctx.getCheckTuples(), ctx.getFieldSerdes(), ctx.getKeyFieldCount(), checkIter);
     }
 
     public void checkDiskOrderScan(ITreeIndexTestContext ctx) throws Exception {
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
index 5b48b8d..bda4292 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
@@ -51,11 +51,10 @@
 
 public class RTree implements ITreeIndex {
 
-    private boolean loaded = false;
-    private final int rootPage = 1; // the root page never changes
+    private final int rootPage = 1;
 
-    private final AtomicLong globalNsn; // Global node sequence number
-    private int numOfPages = 1;
+    // Global node sequence number used for the concurrency control protocol
+    private final AtomicLong globalNsn;
     private final ReadWriteLock treeLatch;
 
     private final IFreePageManager freePageManager;
@@ -67,17 +66,6 @@
     private final int fieldCount;
     private final IBinaryComparatorFactory[] cmpFactories;
 
-    public int rootSplits = 0;
-    public int[] splitsByLevel = new int[500];
-    public AtomicLong readLatchesAcquired = new AtomicLong();
-    public AtomicLong readLatchesReleased = new AtomicLong();
-    public AtomicLong writeLatchesAcquired = new AtomicLong();
-    public AtomicLong writeLatchesReleased = new AtomicLong();
-    public AtomicLong pins = new AtomicLong();
-    public AtomicLong unpins = new AtomicLong();
-    public byte currentLevel = 0;
-
-    // TODO: is MultiComparator needed at all?
     public RTree(IBufferCache bufferCache, int fieldCount, IBinaryComparatorFactory[] cmpFactories,
             IFreePageManager freePageManager, ITreeIndexFrameFactory interiorFrameFactory,
             ITreeIndexFrameFactory leafFrameFactory) {
@@ -99,49 +87,6 @@
         return globalNsn.get();
     }
 
-    public void incrementReadLatchesAcquired() {
-        readLatchesAcquired.incrementAndGet();
-    }
-
-    public void incrementReadLatchesReleased() {
-        readLatchesReleased.incrementAndGet();
-    }
-
-    public void incrementWriteLatchesAcquired() {
-        writeLatchesAcquired.incrementAndGet();
-    }
-
-    public void incrementWriteLatchesReleased() {
-        writeLatchesReleased.incrementAndGet();
-    }
-
-    public void incrementPins() {
-        pins.incrementAndGet();
-    }
-
-    public void incrementUnpins() {
-        unpins.incrementAndGet();
-    }
-
-    public String printStats() {
-        StringBuilder strBuilder = new StringBuilder();
-        strBuilder.append("\n");
-        strBuilder.append("ROOTSPLITS: " + rootSplits + "\n");
-        strBuilder.append("SPLITS BY LEVEL\n");
-        for (int i = 0; i < currentLevel; i++) {
-            strBuilder.append(String.format("%3d ", i) + String.format("%8d ", splitsByLevel[i]) + "\n");
-        }
-        strBuilder.append(String.format("READ LATCHES:  %10d %10d\n", readLatchesAcquired.get(),
-                readLatchesReleased.get()));
-        strBuilder.append(String.format("WRITE LATCHES: %10d %10d\n", writeLatchesAcquired.get(),
-                writeLatchesReleased.get()));
-        strBuilder.append(String.format("PINS:          %10d %10d\n", pins.get(), unpins.get()));
-
-        strBuilder.append(String.format("Num of Pages:          %10d\n", numOfPages));
-
-        return strBuilder.toString();
-    }
-
     public byte getTreeHeight(IRTreeLeafFrame leafFrame) throws HyracksDataException {
         ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), false);
         rootNode.acquireReadLatch();
@@ -219,20 +164,15 @@
 
             // initialize root page
             ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), true);
-            incrementPins();
 
             rootNode.acquireWriteLatch();
-            incrementWriteLatchesAcquired();
             try {
                 leafFrame.setPage(rootNode);
                 leafFrame.initBuffer((byte) 0);
             } finally {
                 rootNode.releaseWriteLatch();
-                incrementWriteLatchesReleased();
                 bufferCache.unpin(rootNode);
-                incrementUnpins();
             }
-            currentLevel = 0;
         } finally {
             treeLatch.writeLock().unlock();
         }
@@ -292,9 +232,7 @@
         }
 
         leafNode.releaseWriteLatch();
-        incrementWriteLatchesReleased();
         bufferCache.unpin(leafNode);
-        incrementUnpins();
     }
 
     private ICachedPage findLeaf(RTreeOpContext ctx) throws HyracksDataException {
@@ -311,20 +249,16 @@
             while (true) {
                 if (!writeLatched) {
                     node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
-                    incrementPins();
                     ctx.interiorFrame.setPage(node);
                     isLeaf = ctx.interiorFrame.isLeaf();
                     if (isLeaf) {
                         node.acquireWriteLatch();
                         writeLatched = true;
-                        incrementWriteLatchesAcquired();
 
                         if (!ctx.interiorFrame.isLeaf()) {
                             node.releaseWriteLatch();
                             writeLatched = false;
-                            incrementWriteLatchesReleased();
                             bufferCache.unpin(node);
-                            incrementUnpins();
                             continue;
                         }
                     } else {
@@ -334,7 +268,6 @@
                         // tuple.
                         node.acquireReadLatch();
                         readLatched = true;
-                        incrementReadLatchesAcquired();
                     }
                 }
 
@@ -345,15 +278,11 @@
                     if (writeLatched) {
                         node.releaseWriteLatch();
                         writeLatched = false;
-                        incrementWriteLatchesReleased();
                         bufferCache.unpin(node);
-                        incrementUnpins();
                     } else {
                         node.releaseReadLatch();
                         readLatched = false;
-                        incrementReadLatchesReleased();
                         bufferCache.unpin(node);
-                        incrementUnpins();
                     }
 
                     pageId = ctx.pathList.getLastPageId();
@@ -378,16 +307,12 @@
                         if (!writeLatched) {
                             node.releaseReadLatch();
                             readLatched = false;
-                            incrementReadLatchesReleased();
                             // TODO: do we need to un-pin and pin again?
                             bufferCache.unpin(node);
-                            incrementUnpins();
 
                             node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
-                            incrementPins();
                             node.acquireWriteLatch();
                             writeLatched = true;
-                            incrementWriteLatchesAcquired();
                             ctx.interiorFrame.setPage(node);
 
                             if (ctx.interiorFrame.getPageLsn() != pageLsn) {
@@ -405,22 +330,16 @@
 
                         node.releaseWriteLatch();
                         writeLatched = false;
-                        incrementWriteLatchesReleased();
                         bufferCache.unpin(node);
-                        incrementUnpins();
                     } else {
                         if (readLatched) {
                             node.releaseReadLatch();
                             readLatched = false;
-                            incrementReadLatchesReleased();
                             bufferCache.unpin(node);
-                            incrementUnpins();
                         } else if (writeLatched) {
                             node.releaseWriteLatch();
                             writeLatched = false;
-                            incrementWriteLatchesReleased();
                             bufferCache.unpin(node);
-                            incrementUnpins();
                         }
                     }
 
@@ -437,15 +356,11 @@
                 if (readLatched) {
                     node.releaseReadLatch();
                     readLatched = false;
-                    incrementReadLatchesReleased();
                     bufferCache.unpin(node);
-                    incrementUnpins();
                 } else if (writeLatched) {
                     node.releaseWriteLatch();
                     writeLatched = false;
-                    incrementWriteLatchesReleased();
                     bufferCache.unpin(node);
-                    incrementUnpins();
                 }
             }
         }
@@ -494,15 +409,11 @@
             case INSUFFICIENT_SPACE: {
                 int rightPageId = freePageManager.getFreePage(ctx.metaFrame);
                 ICachedPage rightNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rightPageId), true);
-                incrementPins();
                 rightNode.acquireWriteLatch();
-                incrementWriteLatchesAcquired();
 
                 try {
                     IRTreeFrame rightFrame;
-                    numOfPages++; // debug
                     if (!isLeaf) {
-                        splitsByLevel[ctx.interiorFrame.getLevel()]++; // debug
                         rightFrame = (IRTreeFrame) interiorFrameFactory.createFrame();
                         rightFrame.setPage(rightNode);
                         rightFrame.initBuffer((byte) ctx.interiorFrame.getLevel());
@@ -515,7 +426,6 @@
                         ctx.interiorFrame.setPageNsn(newNsn);
                         ctx.interiorFrame.setPageLsn(newNsn);
                     } else {
-                        splitsByLevel[0]++; // debug
                         rightFrame = (IRTreeFrame) leafFrameFactory.createFrame();
                         rightFrame.setPage(rightNode);
                         rightFrame.initBuffer((byte) 0);
@@ -530,16 +440,10 @@
                     }
                     ctx.splitKey.setPages(pageId, rightPageId);
                     if (pageId == rootPage) {
-                        rootSplits++; // debug
-                        splitsByLevel[currentLevel]++;
-                        currentLevel++;
-
                         int newLeftId = freePageManager.getFreePage(ctx.metaFrame);
                         ICachedPage newLeftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, newLeftId),
                                 true);
-                        incrementPins();
                         newLeftNode.acquireWriteLatch();
-                        incrementWriteLatchesAcquired();
                         try {
                             // copy left child to new left child
                             System.arraycopy(node.getBuffer().array(), 0, newLeftNode.getBuffer().array(), 0,
@@ -560,18 +464,14 @@
                             ctx.interiorFrame.setPageNsn(newNsn);
                         } finally {
                             newLeftNode.releaseWriteLatch();
-                            incrementWriteLatchesReleased();
                             bufferCache.unpin(newLeftNode);
-                            incrementUnpins();
                         }
 
                         ctx.splitKey.reset();
                     }
                 } finally {
                     rightNode.releaseWriteLatch();
-                    incrementWriteLatchesReleased();
                     bufferCache.unpin(rightNode);
-                    incrementUnpins();
                 }
                 break;
             }
@@ -582,10 +482,8 @@
         boolean writeLatched = false;
         int parentId = ctx.pathList.getLastPageId();
         ICachedPage parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
-        incrementPins();
         parentNode.acquireWriteLatch();
         writeLatched = true;
-        incrementWriteLatchesAcquired();
         ctx.interiorFrame.setPage(parentNode);
         boolean foundParent = true;
 
@@ -602,9 +500,7 @@
                     int rightPage = ctx.interiorFrame.getRightPage();
                     parentNode.releaseWriteLatch();
                     writeLatched = false;
-                    incrementWriteLatchesReleased();
                     bufferCache.unpin(parentNode);
-                    incrementUnpins();
 
                     if (rightPage == -1) {
                         break;
@@ -612,10 +508,8 @@
 
                     parentId = rightPage;
                     parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
-                    incrementPins();
                     parentNode.acquireWriteLatch();
                     writeLatched = true;
-                    incrementWriteLatchesAcquired();
                     ctx.interiorFrame.setPage(parentNode);
                 }
             }
@@ -626,9 +520,7 @@
 
                 parentNode.releaseWriteLatch();
                 writeLatched = false;
-                incrementWriteLatchesReleased();
                 bufferCache.unpin(parentNode);
-                incrementUnpins();
                 return;
             }
 
@@ -636,9 +528,7 @@
             if (writeLatched) {
                 parentNode.releaseWriteLatch();
                 writeLatched = false;
-                incrementWriteLatchesReleased();
                 bufferCache.unpin(parentNode);
-                incrementUnpins();
             }
         }
         // very rare situation when the there is a root split, do an
@@ -666,10 +556,8 @@
                 parentIndex = ctx.traverseList.getFirstPageIndex();
 
                 node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
-                incrementPins();
                 node.acquireReadLatch();
                 readLatched = true;
-                incrementReadLatchesAcquired();
                 ctx.interiorFrame.setPage(node);
                 pageLsn = ctx.interiorFrame.getPageLsn();
                 pageIndex = ctx.traverseList.first();
@@ -692,17 +580,13 @@
                 }
                 node.releaseReadLatch();
                 readLatched = false;
-                incrementReadLatchesReleased();
                 bufferCache.unpin(node);
-                incrementUnpins();
             }
         } finally {
             if (readLatched) {
                 node.releaseReadLatch();
                 readLatched = false;
-                incrementReadLatchesReleased();
                 bufferCache.unpin(node);
-                incrementUnpins();
             }
         }
     }
@@ -736,9 +620,7 @@
             }
 
             ctx.leafFrame.getPage().releaseWriteLatch();
-            incrementWriteLatchesReleased();
             bufferCache.unpin(ctx.leafFrame.getPage());
-            incrementUnpins();
         }
     }
 
@@ -746,10 +628,8 @@
         boolean writeLatched = false;
         int parentId = ctx.pathList.getLastPageId();
         ICachedPage parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
-        incrementPins();
         parentNode.acquireWriteLatch();
         writeLatched = true;
-        incrementWriteLatchesAcquired();
         ctx.interiorFrame.setPage(parentNode);
         boolean foundParent = true;
         int tupleIndex = -1;
@@ -767,9 +647,7 @@
                     int rightPage = ctx.interiorFrame.getRightPage();
                     parentNode.releaseWriteLatch();
                     writeLatched = false;
-                    incrementWriteLatchesReleased();
                     bufferCache.unpin(parentNode);
-                    incrementUnpins();
 
                     if (rightPage == -1) {
                         break;
@@ -777,10 +655,8 @@
 
                     parentId = rightPage;
                     parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
-                    incrementPins();
                     parentNode.acquireWriteLatch();
                     writeLatched = true;
-                    incrementWriteLatchesAcquired();
                     ctx.interiorFrame.setPage(parentNode);
                 }
             }
@@ -809,18 +685,14 @@
 
                 parentNode.releaseWriteLatch();
                 writeLatched = false;
-                incrementWriteLatchesReleased();
                 bufferCache.unpin(parentNode);
-                incrementUnpins();
                 return;
             }
         } finally {
             if (writeLatched) {
                 parentNode.releaseWriteLatch();
                 writeLatched = false;
-                incrementWriteLatchesReleased();
                 bufferCache.unpin(parentNode);
-                incrementUnpins();
             }
         }
 
@@ -848,10 +720,8 @@
                 int pageIndex = ctx.pathList.getLastPageIndex();
                 ctx.pathList.moveLast();
                 node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
-                incrementPins();
                 node.acquireReadLatch();
                 readLatched = true;
-                incrementReadLatchesAcquired();
                 ctx.interiorFrame.setPage(node);
                 boolean isLeaf = ctx.interiorFrame.isLeaf();
                 long pageLsn = ctx.interiorFrame.getPageLsn();
@@ -883,15 +753,11 @@
 
                         node.releaseReadLatch();
                         readLatched = false;
-                        incrementReadLatchesReleased();
                         bufferCache.unpin(node);
-                        incrementUnpins();
 
                         node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
-                        incrementPins();
                         node.acquireWriteLatch();
                         writeLatched = true;
-                        incrementWriteLatchesAcquired();
                         ctx.leafFrame.setPage(node);
 
                         if (ctx.leafFrame.getPageLsn() != pageLsn) {
@@ -904,9 +770,7 @@
 
                                 node.releaseWriteLatch();
                                 writeLatched = false;
-                                incrementWriteLatchesReleased();
                                 bufferCache.unpin(node);
-                                incrementUnpins();
                                 continue;
                             } else {
                                 ctx.pathList.clear();
@@ -924,24 +788,18 @@
                 }
                 node.releaseReadLatch();
                 readLatched = false;
-                incrementReadLatchesReleased();
                 bufferCache.unpin(node);
-                incrementUnpins();
             }
         } finally {
             if (!succeed) {
                 if (readLatched) {
                     node.releaseReadLatch();
                     readLatched = false;
-                    incrementReadLatchesReleased();
                     bufferCache.unpin(node);
-                    incrementUnpins();
                 } else if (writeLatched) {
                     node.releaseWriteLatch();
                     writeLatched = false;
-                    incrementWriteLatchesReleased();
                     bufferCache.unpin(node);
-                    incrementUnpins();
                 }
             }
         }
@@ -994,6 +852,22 @@
         throw new UnsupportedOperationException("RTree Update not implemented.");
     }
 
+    public boolean isEmptyTree(IRTreeLeafFrame leafFrame) throws HyracksDataException {
+        ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), false);
+        rootNode.acquireReadLatch();
+        try {
+            leafFrame.setPage(rootNode);
+            if (leafFrame.getLevel() == 0 && leafFrame.getTupleCount() == 0) {
+                return true;
+            } else {
+                return false;
+            }
+        } finally {
+            rootNode.releaseReadLatch();
+            bufferCache.unpin(rootNode);
+        }
+    }
+
     public final class BulkLoadContext implements IIndexBulkLoadContext {
 
         public ITreeIndexAccessor indexAccessor;
@@ -1006,8 +880,9 @@
 
     @Override
     public IIndexBulkLoadContext beginBulkLoad(float fillFactor) throws HyracksDataException {
-        if (loaded) {
-            throw new HyracksDataException("Trying to bulk-load RTree but RTree has already been loaded.");
+        IRTreeLeafFrame leafFrame = (IRTreeLeafFrame) leafFrameFactory.createFrame();
+        if (!isEmptyTree(leafFrame)) {
+            throw new HyracksDataException("Trying to Bulk-load a non-empty RTree.");
         }
 
         BulkLoadContext ctx = new BulkLoadContext(fillFactor, (IRTreeFrame) leafFrameFactory.createFrame(),
@@ -1027,7 +902,6 @@
 
     @Override
     public void endBulkLoad(IIndexBulkLoadContext ictx) throws HyracksDataException {
-        loaded = true;
     }
 
     private void diskOrderScan(ITreeIndexCursor icursor, RTreeOpContext ctx) throws HyracksDataException {
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
index 7e85a73..8062a08 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
@@ -26,66 +26,64 @@
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
 
 public class RTreeOpContext implements IIndexOpContext {
-	public final MultiComparator cmp;
-	public final IRTreeInteriorFrame interiorFrame;
-	public final IRTreeLeafFrame leafFrame;
-	public IndexOp op;
-	public ITreeIndexCursor cursor;
-	public RTreeCursorInitialState cursorInitialState;
-	public ITreeIndexMetaDataFrame metaFrame;
-	public RTreeSplitKey splitKey;
-	public ITupleReference tuple;
-	public PathList pathList; // used to record the pageIds and pageLsns
-								// of the visited pages
-	public PathList traverseList; // used for traversing the tree
-	private static final int initTraverseListSize = 100;	
-	
-	public RTreeOpContext(IRTreeLeafFrame leafFrame,
-			IRTreeInteriorFrame interiorFrame,
-			ITreeIndexMetaDataFrame metaFrame, IBinaryComparatorFactory[] cmpFactories, int treeHeightHint) {
-		this.cmp = MultiComparator.create(cmpFactories);
-		this.interiorFrame = interiorFrame;
-		this.leafFrame = leafFrame;
-		this.metaFrame = metaFrame;
-		pathList = new PathList(treeHeightHint, treeHeightHint);
-	}
+    private static final int INITIAL_TRAVERSE_LIST_SIZE = 100;
+    public final MultiComparator cmp;
+    public final IRTreeInteriorFrame interiorFrame;
+    public final IRTreeLeafFrame leafFrame;
+    public IndexOp op;
+    public ITreeIndexCursor cursor;
+    public RTreeCursorInitialState cursorInitialState;
+    public ITreeIndexMetaDataFrame metaFrame;
+    public RTreeSplitKey splitKey;
+    public ITupleReference tuple;
+    // Used to record the pageIds and pageLsns of the visited pages.
+    public PathList pathList;
+    // Used for traversing the tree.
+    public PathList traverseList;
 
-	public ITupleReference getTuple() {
-		return tuple;
-	}
+    public RTreeOpContext(IRTreeLeafFrame leafFrame, IRTreeInteriorFrame interiorFrame,
+            ITreeIndexMetaDataFrame metaFrame, IBinaryComparatorFactory[] cmpFactories, int treeHeightHint) {
+        this.cmp = MultiComparator.create(cmpFactories);
+        this.interiorFrame = interiorFrame;
+        this.leafFrame = leafFrame;
+        this.metaFrame = metaFrame;
+        pathList = new PathList(treeHeightHint, treeHeightHint);
+    }
 
-	public void setTuple(ITupleReference tuple) {
-		this.tuple = tuple;
-	}
+    public ITupleReference getTuple() {
+        return tuple;
+    }
 
-	public void reset() {
-		if (pathList != null) {
-			pathList.clear();
-		}
-		if (traverseList != null) {
-			traverseList.clear();
-		}
-	}
+    public void setTuple(ITupleReference tuple) {
+        this.tuple = tuple;
+    }
 
-	@Override
-	public void reset(IndexOp newOp) {
-		if (op != null && newOp == op) {
-			return;
-		}
-		if (op != IndexOp.SEARCH && op != IndexOp.DISKORDERSCAN) {
-			if (splitKey == null) {
-				splitKey = new RTreeSplitKey(interiorFrame.getTupleWriter()
-						.createTupleReference(), interiorFrame.getTupleWriter()
-						.createTupleReference());
-			}
-			if (traverseList == null) {
-				traverseList = new PathList(initTraverseListSize,
-						initTraverseListSize);
-			}
-		}
-		if (cursorInitialState == null) {
-			cursorInitialState = new RTreeCursorInitialState(pathList, 1);
-		}
-		this.op = newOp;
-	}
+    public void reset() {
+        if (pathList != null) {
+            pathList.clear();
+        }
+        if (traverseList != null) {
+            traverseList.clear();
+        }
+    }
+
+    @Override
+    public void reset(IndexOp newOp) {
+        if (op != null && newOp == op) {
+            return;
+        }
+        if (op != IndexOp.SEARCH && op != IndexOp.DISKORDERSCAN) {
+            if (splitKey == null) {
+                splitKey = new RTreeSplitKey(interiorFrame.getTupleWriter().createTupleReference(), interiorFrame
+                        .getTupleWriter().createTupleReference());
+            }
+            if (traverseList == null) {
+                traverseList = new PathList(INITIAL_TRAVERSE_LIST_SIZE, INITIAL_TRAVERSE_LIST_SIZE);
+            }
+        }
+        if (cursorInitialState == null) {
+            cursorInitialState = new RTreeCursorInitialState(pathList, 1);
+        }
+        this.op = newOp;
+    }
 }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
index 32138db..0b1722c 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
@@ -39,7 +39,7 @@
     private SearchPredicate pred;
     private PathList pathList;
     private int rootPage;
-    ITupleReference searchKey;
+    private ITupleReference searchKey;
 
     private int tupleIndex = 0;
     private int tupleIndexInc = 0;
@@ -120,7 +120,7 @@
                             pathList.add(childPageId, pageLsn, -1);
                         }
                     }
-                        
+
                 } else {
                     page = node;
                     leafFrame.setPage(page);
@@ -201,11 +201,12 @@
                         searchKey.getFieldLength(i), searchKey.getFieldData(j), searchKey.getFieldStart(j),
                         searchKey.getFieldLength(j));
                 if (c > 0) {
-                    throw new IllegalArgumentException("The low key point has larger coordinates than the high key point.");
+                    throw new IllegalArgumentException(
+                            "The low key point has larger coordinates than the high key point.");
                 }
             }
         }
-        
+
         pathList.add(this.rootPage, -1, -1);
         tupleIndex = 0;
         fetchNextLeafPage();
@@ -230,8 +231,8 @@
         this.fileId = fileId;
     }
 
-	@Override
-	public boolean exclusiveLatchNodes() {
-		return false;
-	}
+    @Override
+    public boolean exclusiveLatchNodes() {
+        return false;
+    }
 }
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeBulkLoadTest.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeBulkLoadTest.java
index a8f77c1..4dce282 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeBulkLoadTest.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeBulkLoadTest.java
@@ -48,8 +48,8 @@
             rTreeTestUtils.checkScan(ctx);
             rTreeTestUtils.checkDiskOrderScan(ctx);
             rTreeTestUtils.checkRangeSearch(ctx, key);
-            ctx.getIndex().close();
         }
+        ctx.getIndex().close();
     }
 
     @Override
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeTestContext.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeTestContext.java
index b4af787..fa9be1a 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeTestContext.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeTestContext.java
@@ -31,11 +31,6 @@
     }
 
     @Override
-    public void insertCheckTuple(RTreeCheckTuple checkTuple, Collection<RTreeCheckTuple> checkTuples) {
-        checkTuples.add(checkTuple);
-    }
-
-    @Override
     public Collection<RTreeCheckTuple> getCheckTuples() {
         return checkTuples;
     }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeTestUtils.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeTestUtils.java
index 8020be4..93d68ad 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeTestUtils.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeTestUtils.java
@@ -59,7 +59,7 @@
         ArrayList<RTreeCheckTuple> expectedResult = null;
 
         expectedResult = getRangeSearchExpectedResults((ArrayList<RTreeCheckTuple>) ctx.getCheckTuples(), keyCheck);
-        checkExpectedResults(searchCursor, expectedResult, ctx.getFieldSerdes(), ctx.getKeyFieldCount());
+        checkExpectedResults(searchCursor, expectedResult, ctx.getFieldSerdes(), ctx.getKeyFieldCount(), null);
     }
 
     @SuppressWarnings("unchecked")
@@ -142,7 +142,7 @@
 
     @Override
     public void checkExpectedResults(ITreeIndexCursor cursor, Collection checkTuples,
-            ISerializerDeserializer[] fieldSerdes, int keyFieldCount) throws Exception {
+            ISerializerDeserializer[] fieldSerdes, int keyFieldCount, Iterator<CheckTuple> checkIter) throws Exception {
         int actualCount = 0;
         try {
             while (cursor.hasNext()) {
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeBulkLoadTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeBulkLoadTest.java
index 3cf0d86..c4ae180 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeBulkLoadTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeBulkLoadTest.java
@@ -23,14 +23,14 @@
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
-import edu.uci.ics.hyracks.storage.am.btree.tests.IOrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexBulkLoadTest;
+import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
 
 @SuppressWarnings("rawtypes")
 public class BTreeBulkLoadTest extends OrderedIndexBulkLoadTest {
-    
+
     public BTreeBulkLoadTest() {
         super(BTreeTestHarness.LEAF_FRAMES_TO_TEST, 1);
     }
@@ -48,9 +48,10 @@
     }
 
     @Override
-    protected IOrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType) throws Exception {
-        return BTreeTestContext.create(harness.getBufferCache(),
-                harness.getBTreeFileId(), fieldSerdes, numKeys, leafType);
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+            BTreeLeafFrameType leafType) throws Exception {
+        return BTreeTestContext.create(harness.getBufferCache(), harness.getBTreeFileId(), fieldSerdes, numKeys,
+                leafType);
     }
 
     @Override
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java
index e4475fe..8801c2e 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java
@@ -23,14 +23,14 @@
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
-import edu.uci.ics.hyracks.storage.am.btree.tests.IOrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexDeleteTest;
+import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
 
 @SuppressWarnings("rawtypes")
 public class BTreeDeleteTest extends OrderedIndexDeleteTest {
-    
+
     public BTreeDeleteTest() {
         super(BTreeTestHarness.LEAF_FRAMES_TO_TEST);
     }
@@ -48,9 +48,10 @@
     }
 
     @Override
-    protected IOrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType) throws Exception {
-        return BTreeTestContext.create(harness.getBufferCache(),
-                harness.getBTreeFileId(), fieldSerdes, numKeys, leafType);
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+            BTreeLeafFrameType leafType) throws Exception {
+        return BTreeTestContext.create(harness.getBufferCache(), harness.getBTreeFileId(), fieldSerdes, numKeys,
+                leafType);
     }
 
     @Override
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java
index a4d9570..8709360 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java
@@ -23,8 +23,8 @@
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
-import edu.uci.ics.hyracks.storage.am.btree.tests.IOrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexInsertTest;
+import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
 
@@ -56,11 +56,12 @@
     public void tearDown() throws HyracksDataException {
         harness.tearDown();
     }
-    
+
     @Override
-    protected IOrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType) throws Exception {
-        return BTreeTestContext.create(harness.getBufferCache(),
-                harness.getBTreeFileId(), fieldSerdes, numKeys, leafType);
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+            BTreeLeafFrameType leafType) throws Exception {
+        return BTreeTestContext.create(harness.getBufferCache(), harness.getBTreeFileId(), fieldSerdes, numKeys,
+                leafType);
     }
 
     @Override
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateTest.java
index 14f8d18..8ec2dd9 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateTest.java
@@ -23,14 +23,14 @@
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
-import edu.uci.ics.hyracks.storage.am.btree.tests.IOrderedIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexUpdateTest;
 import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
 
 @SuppressWarnings("rawtypes")
 public class BTreeUpdateTest extends OrderedIndexUpdateTest {
-    
+
     public BTreeUpdateTest() {
         super(BTreeTestHarness.LEAF_FRAMES_TO_TEST);
     }
@@ -48,9 +48,10 @@
     }
 
     @Override
-    protected IOrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType) throws Exception {
-        return BTreeTestContext.create(harness.getBufferCache(),
-                harness.getBTreeFileId(), fieldSerdes, numKeys, leafType);
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+            BTreeLeafFrameType leafType) throws Exception {
+        return BTreeTestContext.create(harness.getBufferCache(), harness.getBTreeFileId(), fieldSerdes, numKeys,
+                leafType);
     }
 
     @Override
diff --git a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeBulkLoadTest.java b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeBulkLoadTest.java
index e1af5ad..396dddc 100644
--- a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeBulkLoadTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeBulkLoadTest.java
@@ -23,18 +23,18 @@
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
-import edu.uci.ics.hyracks.storage.am.btree.tests.IOrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexBulkLoadTest;
+import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.util.LSMBTreeTestContext;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.util.LSMBTreeTestHarness;
 
 @SuppressWarnings("rawtypes")
 public class LSMBTreeBulkLoadTest extends OrderedIndexBulkLoadTest {
-    
+
     public LSMBTreeBulkLoadTest() {
         super(LSMBTreeTestHarness.LEAF_FRAMES_TO_TEST, 1);
     }
-    
+
     private final LSMBTreeTestHarness harness = new LSMBTreeTestHarness();
 
     @Before
@@ -48,7 +48,7 @@
     }
 
     @Override
-    protected IOrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
             BTreeLeafFrameType leafType) throws Exception {
         return LSMBTreeTestContext.create(harness.getMemBufferCache(), harness.getMemFreePageManager(),
                 harness.getOnDiskDir(), harness.getDiskBufferCache(), harness.getDiskFileMapProvider(), fieldSerdes,
diff --git a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeDeleteTest.java b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeDeleteTest.java
index 27ef60f..1bc7530 100644
--- a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeDeleteTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeDeleteTest.java
@@ -23,18 +23,18 @@
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
-import edu.uci.ics.hyracks.storage.am.btree.tests.IOrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexDeleteTest;
+import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.util.LSMBTreeTestContext;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.util.LSMBTreeTestHarness;
 
 @SuppressWarnings("rawtypes")
 public class LSMBTreeDeleteTest extends OrderedIndexDeleteTest {
-    
+
     public LSMBTreeDeleteTest() {
         super(LSMBTreeTestHarness.LEAF_FRAMES_TO_TEST);
     }
-    
+
     private final LSMBTreeTestHarness harness = new LSMBTreeTestHarness();
 
     @Before
@@ -48,7 +48,7 @@
     }
 
     @Override
-    protected IOrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
             BTreeLeafFrameType leafType) throws Exception {
         return LSMBTreeTestContext.create(harness.getMemBufferCache(), harness.getMemFreePageManager(),
                 harness.getOnDiskDir(), harness.getDiskBufferCache(), harness.getDiskFileMapProvider(), fieldSerdes,
diff --git a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeInsertTest.java b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeInsertTest.java
index 4ab58a7..b292b26 100644
--- a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeInsertTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeInsertTest.java
@@ -23,14 +23,14 @@
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
-import edu.uci.ics.hyracks.storage.am.btree.tests.IOrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexInsertTest;
+import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.util.LSMBTreeTestContext;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.util.LSMBTreeTestHarness;
 
 @SuppressWarnings("rawtypes")
 public class LSMBTreeInsertTest extends OrderedIndexInsertTest {
-    
+
     public LSMBTreeInsertTest() {
         super(LSMBTreeTestHarness.LEAF_FRAMES_TO_TEST);
     }
@@ -48,7 +48,7 @@
     }
 
     @Override
-    protected IOrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
             BTreeLeafFrameType leafType) throws Exception {
         return LSMBTreeTestContext.create(harness.getMemBufferCache(), harness.getMemFreePageManager(),
                 harness.getOnDiskDir(), harness.getDiskBufferCache(), harness.getDiskFileMapProvider(), fieldSerdes,
diff --git a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeMergeTest.java b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeMergeTest.java
index 911fff4..fb10d4f 100644
--- a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeMergeTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeMergeTest.java
@@ -23,13 +23,13 @@
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
-import edu.uci.ics.hyracks.storage.am.btree.tests.IOrderedIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.util.LSMBTreeTestContext;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.util.LSMBTreeTestHarness;
 
 @SuppressWarnings("rawtypes")
 public class LSMBTreeMergeTest extends LSMBTreeMergeTestDriver {
-    
+
     public LSMBTreeMergeTest() {
         super(LSMBTreeTestHarness.LEAF_FRAMES_TO_TEST);
     }
@@ -47,7 +47,7 @@
     }
 
     @Override
-    protected IOrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
             BTreeLeafFrameType leafType) throws Exception {
         return LSMBTreeTestContext.create(harness.getMemBufferCache(), harness.getMemFreePageManager(),
                 harness.getOnDiskDir(), harness.getDiskBufferCache(), harness.getDiskFileMapProvider(), fieldSerdes,
diff --git a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeMergeTestDriver.java b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeMergeTestDriver.java
index 90c41d9..335db7e 100644
--- a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeMergeTestDriver.java
+++ b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeMergeTestDriver.java
@@ -20,52 +20,55 @@
 import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
 import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
 import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
-import edu.uci.ics.hyracks.storage.am.btree.tests.IOrderedIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexTestDriver;
 import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexTestUtils;
 import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMTreeIndexAccessor;
 
 @SuppressWarnings("rawtypes")
 public abstract class LSMBTreeMergeTestDriver extends OrderedIndexTestDriver {
-    
+
+    private final OrderedIndexTestUtils orderedIndexTestUtils;
+
     public LSMBTreeMergeTestDriver(BTreeLeafFrameType[] leafFrameTypesToTest) {
         super(leafFrameTypesToTest);
+        this.orderedIndexTestUtils = new OrderedIndexTestUtils();
     }
 
     @Override
     protected void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType,
             ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey)
             throws Exception {
-        IOrderedIndexTestContext ctx = createTestContext(fieldSerdes, numKeys, leafType);
-        
+        OrderedIndexTestContext ctx = createTestContext(fieldSerdes, numKeys, leafType);
+
         // Start off with one tree bulk loaded.
         // We assume all fieldSerdes are of the same type. Check the first one
         // to determine which field types to generate.
         if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
-            OrderedIndexTestUtils.bulkLoadIntTuples(ctx, numTuplesToInsert, getRandom());
+            orderedIndexTestUtils.bulkLoadIntTuples(ctx, numTuplesToInsert, getRandom());
         } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
-            OrderedIndexTestUtils.bulkLoadStringTuples(ctx, numTuplesToInsert, getRandom());
+            orderedIndexTestUtils.bulkLoadStringTuples(ctx, numTuplesToInsert, getRandom());
         }
-        
+
         int maxTreesToMerge = 10;
         for (int i = 0; i < maxTreesToMerge; i++) {
             for (int j = 0; j < i; j++) {
                 if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
-                    OrderedIndexTestUtils.bulkLoadIntTuples(ctx, numTuplesToInsert, getRandom());
+                    orderedIndexTestUtils.bulkLoadIntTuples(ctx, numTuplesToInsert, getRandom());
                 } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
-                    OrderedIndexTestUtils.bulkLoadStringTuples(ctx, numTuplesToInsert, getRandom());
+                    orderedIndexTestUtils.bulkLoadStringTuples(ctx, numTuplesToInsert, getRandom());
                 }
             }
 
             ILSMTreeIndexAccessor accessor = (ILSMTreeIndexAccessor) ctx.getIndexAccessor();
             accessor.merge();
-            
-            OrderedIndexTestUtils.checkPointSearches(ctx);
-            OrderedIndexTestUtils.checkOrderedScan(ctx);
-            OrderedIndexTestUtils.checkDiskOrderScan(ctx);
-            OrderedIndexTestUtils.checkRangeSearch(ctx, lowKey, highKey, true, true);
+
+            orderedIndexTestUtils.checkPointSearches(ctx);
+            orderedIndexTestUtils.checkScan(ctx);
+            orderedIndexTestUtils.checkDiskOrderScan(ctx);
+            orderedIndexTestUtils.checkRangeSearch(ctx, lowKey, highKey, true, true);
             if (prefixLowKey != null && prefixHighKey != null) {
-                OrderedIndexTestUtils.checkRangeSearch(ctx, prefixLowKey, prefixHighKey, true, true);
+                orderedIndexTestUtils.checkRangeSearch(ctx, prefixLowKey, prefixHighKey, true, true);
             }
         }
     }
diff --git a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeMultiBulkLoadTest.java b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeMultiBulkLoadTest.java
index bb232c7..a93308f 100644
--- a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeMultiBulkLoadTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeMultiBulkLoadTest.java
@@ -23,8 +23,8 @@
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
-import edu.uci.ics.hyracks.storage.am.btree.tests.IOrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexBulkLoadTest;
+import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.util.LSMBTreeTestContext;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.util.LSMBTreeTestHarness;
 
@@ -34,7 +34,7 @@
         // Using 5 bulk load rounds.
         super(LSMBTreeTestHarness.LEAF_FRAMES_TO_TEST, 5);
     }
-    
+
     private final LSMBTreeTestHarness harness = new LSMBTreeTestHarness();
 
     @Before
@@ -48,7 +48,7 @@
     }
 
     @Override
-    protected IOrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
             BTreeLeafFrameType leafType) throws Exception {
         return LSMBTreeTestContext.create(harness.getMemBufferCache(), harness.getMemFreePageManager(),
                 harness.getOnDiskDir(), harness.getDiskBufferCache(), harness.getDiskFileMapProvider(), fieldSerdes,
diff --git a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeUpdateTest.java b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeUpdateTest.java
index 8fbe9da..2269865 100644
--- a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeUpdateTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeUpdateTest.java
@@ -23,14 +23,14 @@
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
-import edu.uci.ics.hyracks.storage.am.btree.tests.IOrderedIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexUpdateTest;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.util.LSMBTreeTestContext;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.util.LSMBTreeTestHarness;
 
 @SuppressWarnings("rawtypes")
 public class LSMBTreeUpdateTest extends OrderedIndexUpdateTest {
-    
+
     public LSMBTreeUpdateTest() {
         super(LSMBTreeTestHarness.LEAF_FRAMES_TO_TEST);
     }
@@ -48,7 +48,7 @@
     }
 
     @Override
-    protected IOrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
             BTreeLeafFrameType leafType) throws Exception {
         return LSMBTreeTestContext.create(harness.getMemBufferCache(), harness.getMemFreePageManager(),
                 harness.getOnDiskDir(), harness.getDiskBufferCache(), harness.getDiskFileMapProvider(), fieldSerdes,
diff --git a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/util/LSMBTreeTestContext.java b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/util/LSMBTreeTestContext.java
index 4119ead..6daa36e 100644
--- a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/util/LSMBTreeTestContext.java
+++ b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/util/LSMBTreeTestContext.java
@@ -15,15 +15,15 @@
 
 package edu.uci.ics.hyracks.storage.am.lsm.btree.util;
 
-import java.util.TreeSet;
+import java.util.Collection;
 
 import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
 import edu.uci.ics.hyracks.dataflow.common.util.SerdeUtils;
-import edu.uci.ics.hyracks.storage.am.btree.tests.CheckTuple;
 import edu.uci.ics.hyracks.storage.am.btree.tests.OrderedIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.test.CheckTuple;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.impls.LSMBTree;
 import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryBufferCache;
 import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryFreePageManager;
@@ -31,8 +31,8 @@
 import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
 
 @SuppressWarnings("rawtypes")
-public final class LSMBTreeTestContext extends OrderedIndexTestContext {    
-    
+public final class LSMBTreeTestContext extends OrderedIndexTestContext {
+
     public LSMBTreeTestContext(ISerializerDeserializer[] fieldSerdes, ITreeIndex treeIndex) {
         super(fieldSerdes, treeIndex);
     }
@@ -53,13 +53,13 @@
      * Override to provide upsert semantics for the check tuples.
      */
     @Override
-    public void insertCheckTuple(CheckTuple checkTuple, TreeSet<CheckTuple> checkTuples) {        
+    public void insertCheckTuple(CheckTuple checkTuple, Collection<CheckTuple> checkTuples) {
         if (checkTuples.contains(checkTuple)) {
             checkTuples.remove(checkTuple);
         }
         checkTuples.add(checkTuple);
     }
-    
+
     public static LSMBTreeTestContext create(InMemoryBufferCache memBufferCache,
             InMemoryFreePageManager memFreePageManager, String onDiskDir, IBufferCache diskBufferCache,
             IFileMapProvider diskFileMapProvider, ISerializerDeserializer[] fieldSerdes, int numKeyFields, int fileId)
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
index cacb9fc..a379aa5 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
@@ -146,7 +146,7 @@
             checkTuple.add(Math.min(p1y, p2y));
             checkTuple.add(Math.max(p1x, p2x));
             checkTuple.add(Math.max(p1y, p2y));
-            
+
             checkTuples.add(checkTuple);
         }
 
@@ -166,7 +166,7 @@
         rTreeTestUtils.getRangeSearchExpectedResults(checkTuples, keyCheck);
         indexAccessor.search(searchCursor, searchPredicate);
 
-        rTreeTestUtils.checkExpectedResults(searchCursor, expectedResult, fieldSerdes, keyFieldCount);
+        rTreeTestUtils.checkExpectedResults(searchCursor, expectedResult, fieldSerdes, keyFieldCount, null);
 
         rtree.close();
     }