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 04c1f99..8eb856b 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
@@ -357,19 +357,12 @@
     }
 
     @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;
+    protected Collection createCheckTuplesCollection() {
+        return new TreeSet<CheckTuple>();
     }
 
     @Override
-    protected Collection createCheckTuplesCollection() {
-        return new TreeSet<CheckTuple>();
+    protected ArrayTupleBuilder createDeleteTupleBuilder(ITreeIndexTestContext ctx) {
+        return new ArrayTupleBuilder(ctx.getKeyFieldCount());
     }
 }
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/ITreeIndexTestContext.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/ITreeIndexTestContext.java
index cf9ca2e..ec57dbf 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/ITreeIndexTestContext.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/ITreeIndexTestContext.java
@@ -25,7 +25,7 @@
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
 
 @SuppressWarnings("rawtypes")
-public interface ITreeIndexTestContext <T extends CheckTuple>{
+public interface ITreeIndexTestContext<T extends CheckTuple> {
     public int getFieldCount();
 
     public int getKeyFieldCount();
@@ -44,6 +44,8 @@
 
     public void insertCheckTuple(T checkTuple, Collection<T> checkTuples);
 
+    public void deleteCheckTuple(T checkTuple, Collection<T> checkTuples);
+
     public Collection<T> getCheckTuples();
 
 }
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 7e6e932..113fc8e 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
@@ -72,4 +72,9 @@
     public void insertCheckTuple(T checkTuple, Collection<T> checkTuples) {
         checkTuples.add(checkTuple);
     }
+
+    @Override
+    public void deleteCheckTuple(T checkTuple, Collection<T> checkTuples) {
+        checkTuples.remove(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 8bf4ae5..3224851 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
@@ -38,10 +38,10 @@
 
     protected abstract void setIntKeyFields(int[] fieldValues, int numKeyFields, int maxValue, Random rnd);
 
-    protected abstract boolean insertTuple(ITreeIndexTestContext ctx) throws Exception;
-
     protected abstract Collection createCheckTuplesCollection();
 
+    protected abstract ArrayTupleBuilder createDeleteTupleBuilder(ITreeIndexTestContext ctx);
+
     @SuppressWarnings("unchecked")
     public static void createTupleFromCheckTuple(CheckTuple checkTuple, ArrayTupleBuilder tupleBuilder,
             ArrayTupleReference tuple, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {
@@ -143,9 +143,12 @@
                     LOGGER.info("Inserting Tuple " + (i + 1) + "/" + numTuples);
                 }
             }
-            boolean succeeded = insertTuple(ctx);
-            if (succeeded) {
+            try {
+                ctx.getIndexAccessor().insert(ctx.getTuple());
                 ctx.insertCheckTuple(createIntCheckTuple(fieldValues, ctx.getKeyFieldCount()), ctx.getCheckTuples());
+            } catch (TreeIndexException e) {
+                // We set expected values only after insertion succeeds because
+                // we ignore duplicate keys.
             }
         }
     }
@@ -201,7 +204,7 @@
 
     @SuppressWarnings("unchecked")
     public void deleteTuples(ITreeIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
-        ArrayTupleBuilder deleteTupleBuilder = new ArrayTupleBuilder(ctx.getKeyFieldCount());
+        ArrayTupleBuilder deleteTupleBuilder = createDeleteTupleBuilder(ctx);
         ArrayTupleReference deleteTuple = new ArrayTupleReference();
         int numCheckTuples = ctx.getCheckTuples().size();
         // Copy CheckTuple references into array, so we can randomly pick from
@@ -226,7 +229,7 @@
             ctx.getIndexAccessor().delete(deleteTuple);
 
             // Remove check tuple from expected results.
-            ctx.getCheckTuples().remove(checkTuple);
+            ctx.deleteCheckTuple(checkTuple, ctx.getCheckTuples());
 
             // Swap with last "valid" CheckTuple.
             CheckTuple tmp = checkTuples[numCheckTuples - 1];
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeFileNameManager.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeFileNameManager.java
deleted file mode 100644
index f39e2f3..0000000
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeFileNameManager.java
+++ /dev/null
@@ -1,79 +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.lsm.btree.impls;
-
-import java.text.Format;
-import java.text.SimpleDateFormat;
-import java.util.Comparator;
-import java.util.Date;
-
-import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileNameManager;
-
-public class LSMBTreeFileNameManager implements ILSMFileNameManager {
-
-    private final String baseDir;
-    private final Format formatter = new SimpleDateFormat("yyyy_MM_dd_HH_mm_ss_SSS");
-    private final Comparator<String> cmp = new FileNameComparator();
-    
-    public LSMBTreeFileNameManager(String baseDir) {
-        if (!baseDir.endsWith(System.getProperty("file.separator"))) {
-            baseDir += System.getProperty("file.separator");
-        }
-        this.baseDir = baseDir;
-    }
-    
-    @Override
-    public String getFlushFileName() {
-        Date date = new Date();        
-        // "Z" prefix to indicate flush. Relies on "Z" sorting higher than "A".
-        return baseDir + "Z" + formatter.format(date);
-    }
-
-    @Override
-    public String getMergeFileName() {
-        Date date = new Date();
-        // "A" prefix to indicate merge. Relies on "A" sorting lower than "Z".
-        return baseDir + "A" + formatter.format(date);
-    }
-
-    @Override
-    public Comparator<String> getFileNameComparator() {
-        return cmp;
-    }
-
-    /**
-     * Sorts strings in reverse lexicographical order. The way we construct the
-     * file names above guarantees that:
-     * 
-     * 1. Flushed files ("Z" prefix) sort lower than merged files ("A" prefix)
-     * 
-     * 2. Flushed files are sorted from newest to oldest (based on the timestamp
-     * string)
-     * 
-     */
-    private class FileNameComparator implements Comparator<String> {
-        @Override
-        public int compare(String a, String b) {
-            // Consciously ignoring locale.
-            return -a.compareTo(b);
-        }
-    }
-
-    @Override
-    public String getBaseDir() {
-        return baseDir;
-    }
-}
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/util/LSMBTreeUtils.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/util/LSMBTreeUtils.java
index 014cc4f..23f986a 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/util/LSMBTreeUtils.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/util/LSMBTreeUtils.java
@@ -25,24 +25,25 @@
 import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.impls.BTreeFactory;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.impls.LSMBTree;
-import edu.uci.ics.hyracks.storage.am.lsm.btree.impls.LSMBTreeFileNameManager;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.tuples.LSMBTreeCopyTupleWriterFactory;
 import edu.uci.ics.hyracks.storage.am.lsm.btree.tuples.LSMBTreeTupleWriterFactory;
 import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileNameManager;
 import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryBufferCache;
 import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryFreePageManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeFileNameManager;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
 
 public class LSMBTreeUtils {
-    public static LSMBTree createLSMTree(InMemoryBufferCache memBufferCache, InMemoryFreePageManager memFreePageManager,
-            String onDiskDir, IBufferCache diskBufferCache, IFileMapProvider diskFileMapProvider,
-            ITypeTraits[] typeTraits, IBinaryComparatorFactory[] cmpFactories) {
+    public static LSMBTree createLSMTree(InMemoryBufferCache memBufferCache,
+            InMemoryFreePageManager memFreePageManager, String onDiskDir, IBufferCache diskBufferCache,
+            IFileMapProvider diskFileMapProvider, ITypeTraits[] typeTraits, IBinaryComparatorFactory[] cmpFactories) {
         LSMBTreeTupleWriterFactory insertTupleWriterFactory = new LSMBTreeTupleWriterFactory(typeTraits,
                 cmpFactories.length, false);
         LSMBTreeTupleWriterFactory deleteTupleWriterFactory = new LSMBTreeTupleWriterFactory(typeTraits,
                 cmpFactories.length, true);
-        LSMBTreeCopyTupleWriterFactory copyTupleWriterFactory = new LSMBTreeCopyTupleWriterFactory(typeTraits, cmpFactories.length);
+        LSMBTreeCopyTupleWriterFactory copyTupleWriterFactory = new LSMBTreeCopyTupleWriterFactory(typeTraits,
+                cmpFactories.length);
         ITreeIndexFrameFactory insertLeafFrameFactory = new BTreeNSMLeafFrameFactory(insertTupleWriterFactory);
         ITreeIndexFrameFactory copyTupleLeafFrameFactory = new BTreeNSMLeafFrameFactory(copyTupleWriterFactory);
         ITreeIndexFrameFactory deleteLeafFrameFactory = new BTreeNSMLeafFrameFactory(deleteTupleWriterFactory);
@@ -54,10 +55,10 @@
                 typeTraits.length, interiorFrameFactory, copyTupleLeafFrameFactory);
         BTreeFactory bulkLoadBTreeFactory = new BTreeFactory(diskBufferCache, freePageManagerFactory, cmpFactories,
                 typeTraits.length, interiorFrameFactory, insertLeafFrameFactory);
-        ILSMFileNameManager fileNameManager = new LSMBTreeFileNameManager(onDiskDir);
-        LSMBTree lsmTree = new LSMBTree(memBufferCache, memFreePageManager, interiorFrameFactory, insertLeafFrameFactory,
-                deleteLeafFrameFactory, fileNameManager, diskBTreeFactory, bulkLoadBTreeFactory, diskFileMapProvider,
-                typeTraits.length, cmpFactories);
+        ILSMFileNameManager fileNameManager = new LSMTreeFileNameManager(onDiskDir);
+        LSMBTree lsmTree = new LSMBTree(memBufferCache, memFreePageManager, interiorFrameFactory,
+                insertLeafFrameFactory, deleteLeafFrameFactory, fileNameManager, diskBTreeFactory,
+                bulkLoadBTreeFactory, diskFileMapProvider, typeTraits.length, cmpFactories);
         return lsmTree;
     }
 }
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java
index 9804f0c..c8d584c 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java
@@ -57,7 +57,8 @@
 
     @Override
     public void reset() {
-        // do nothing
+        currentCursror = 0;
+        foundNext = false;
     }
 
     @Override
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/utils/LSMRTreeUtils.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/utils/LSMRTreeUtils.java
new file mode 100644
index 0000000..d2e2e4f
--- /dev/null
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/utils/LSMRTreeUtils.java
@@ -0,0 +1,73 @@
+/*
+ * 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.lsm.rtree.utils;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileNameManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryBufferCache;
+import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryFreePageManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.BTreeFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeFileNameManager;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.LSMRTree;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.RTreeFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.tuples.LSMTypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public class LSMRTreeUtils {
+    public static LSMRTree createLSMTree(InMemoryBufferCache memBufferCache,
+            InMemoryFreePageManager memFreePageManager, String onDiskDir, IBufferCache diskBufferCache,
+            IFileMapProvider diskFileMapProvider, ITypeTraits[] typeTraits,
+            IBinaryComparatorFactory[] rtreeCmpFactories, IBinaryComparatorFactory[] btreeCmpFactories,
+            IPrimitiveValueProviderFactory[] valueProviderFactories) {
+        LSMTypeAwareTupleWriterFactory rtreeTupleWriterFactory = new LSMTypeAwareTupleWriterFactory(typeTraits, false);
+        LSMTypeAwareTupleWriterFactory btreeTupleWriterFactory = new LSMTypeAwareTupleWriterFactory(typeTraits, true);
+
+        ITreeIndexFrameFactory rtreeInteriorFrameFactory = new RTreeNSMInteriorFrameFactory(rtreeTupleWriterFactory,
+                valueProviderFactories);
+        ITreeIndexFrameFactory rtreeLeafFrameFactory = new RTreeNSMLeafFrameFactory(rtreeTupleWriterFactory,
+                valueProviderFactories);
+
+        ITreeIndexFrameFactory btreeInteriorFrameFactory = new BTreeNSMInteriorFrameFactory(btreeTupleWriterFactory);
+        ITreeIndexFrameFactory btreeLeafFrameFactory = new BTreeNSMLeafFrameFactory(btreeTupleWriterFactory);
+
+        ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+        LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(diskBufferCache,
+                metaFrameFactory);
+
+        RTreeFactory diskRTreeFactory = new RTreeFactory(diskBufferCache, freePageManagerFactory, rtreeCmpFactories,
+                typeTraits.length, rtreeInteriorFrameFactory, rtreeLeafFrameFactory);
+        BTreeFactory diskBTreeFactory = new BTreeFactory(diskBufferCache, freePageManagerFactory, btreeCmpFactories,
+                typeTraits.length, btreeInteriorFrameFactory, btreeLeafFrameFactory);
+
+        ILSMFileNameManager fileNameManager = new LSMTreeFileNameManager(onDiskDir);
+        LSMRTree lsmTree = new LSMRTree(memBufferCache, memFreePageManager, rtreeInteriorFrameFactory,
+                rtreeLeafFrameFactory, btreeInteriorFrameFactory, btreeLeafFrameFactory, fileNameManager,
+                diskRTreeFactory, diskBTreeFactory, diskFileMapProvider, typeTraits.length, rtreeCmpFactories,
+                btreeCmpFactories);
+        return lsmTree;
+    }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
index 103cd45..ebfb4b4 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
@@ -28,45 +28,46 @@
     @Override
     public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, MultiComparator multiCmp,
             FindTupleMode mode, FindTupleNoExactMatchPolicy matchPolicy) {
+        if (searchKey.getFieldCount() == frameTuple.getFieldCount()) {
+            int maxFieldPos = multiCmp.getKeyFieldCount() / 2;
+            for (int i = 0; i < frame.getTupleCount(); i++) {
+                frameTuple.resetByTupleIndex(frame, i);
 
-        int maxFieldPos = multiCmp.getKeyFieldCount() / 2;
-        for (int i = 0; i < frame.getTupleCount(); i++) {
-            frameTuple.resetByTupleIndex(frame, i);
+                boolean foundTuple = true;
+                for (int j = 0; j < maxFieldPos; j++) {
+                    int k = maxFieldPos + j;
+                    int c1 = multiCmp.getComparators()[j].compare(frameTuple.getFieldData(j),
+                            frameTuple.getFieldStart(j), frameTuple.getFieldLength(j), searchKey.getFieldData(j),
+                            searchKey.getFieldStart(j), searchKey.getFieldLength(j));
 
-            boolean foundTuple = true;
-            for (int j = 0; j < maxFieldPos; j++) {
-                int k = maxFieldPos + j;
-                int c1 = multiCmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
-                        frameTuple.getFieldLength(j), searchKey.getFieldData(j), searchKey.getFieldStart(j),
-                        searchKey.getFieldLength(j));
-
-                if (c1 != 0) {
-                    foundTuple = false;
-                    break;
+                    if (c1 != 0) {
+                        foundTuple = false;
+                        break;
+                    }
+                    int c2 = multiCmp.getComparators()[k].compare(frameTuple.getFieldData(k),
+                            frameTuple.getFieldStart(k), frameTuple.getFieldLength(k), searchKey.getFieldData(k),
+                            searchKey.getFieldStart(k), searchKey.getFieldLength(k));
+                    if (c2 != 0) {
+                        foundTuple = false;
+                        break;
+                    }
                 }
-                int c2 = multiCmp.getComparators()[k].compare(frameTuple.getFieldData(k), frameTuple.getFieldStart(k),
-                        frameTuple.getFieldLength(k), searchKey.getFieldData(k), searchKey.getFieldStart(k),
-                        searchKey.getFieldLength(k));
-                if (c2 != 0) {
-                    foundTuple = false;
-                    break;
+                int remainingFieldCount = frameTuple.getFieldCount() - multiCmp.getKeyFieldCount();
+                for (int j = multiCmp.getKeyFieldCount(); j < multiCmp.getKeyFieldCount() + remainingFieldCount; j++) {
+                    if (!compareField(searchKey, frameTuple, j)) {
+                        foundTuple = false;
+                        break;
+                    }
                 }
-            }
-            int remainingFieldCount = frameTuple.getFieldCount() - multiCmp.getKeyFieldCount();
-            for (int j = multiCmp.getKeyFieldCount(); j < multiCmp.getKeyFieldCount() + remainingFieldCount; j++) {
-                if (!compareField(searchKey, frameTuple, j)) {
-                    foundTuple = false;
-                    break;
+                if (foundTuple) {
+                    return i;
                 }
             }
-            if (foundTuple) {
-                return i;
-            }
         }
         return -1;
     }
 
-    public boolean compareField(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, int fIdx) {
+    private boolean compareField(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, int fIdx) {
         int searchKeyFieldLength = searchKey.getFieldLength(fIdx);
         int frameTupleFieldLength = frameTuple.getFieldLength(fIdx);
 
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 4dce282..a9108d4 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
@@ -22,7 +22,7 @@
 import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
 
 @SuppressWarnings("rawtypes")
-public abstract class AbstractRTreeBulkLoadTest extends RTreeTestDriver {
+public abstract class AbstractRTreeBulkLoadTest extends AbstractRTreeTestDriver {
 
     private final RTreeTestUtils rTreeTestUtils;
     private final int bulkLoadRounds;
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeDeleteTest.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeDeleteTest.java
index 796ba33..245178a 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeDeleteTest.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeDeleteTest.java
@@ -22,7 +22,7 @@
 import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
 
 @SuppressWarnings("rawtypes")
-public abstract class AbstractRTreeDeleteTest extends RTreeTestDriver {
+public abstract class AbstractRTreeDeleteTest extends AbstractRTreeTestDriver {
 
     private final RTreeTestUtils rTreeTestUtils;
 
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeExamplesTest.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeExamplesTest.java
index 6f23a38..c472b70 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeExamplesTest.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeExamplesTest.java
@@ -49,7 +49,8 @@
     protected static final Logger LOGGER = Logger.getLogger(AbstractRTreeExamplesTest.class.getName());
     protected final Random rnd = new Random(50);
 
-    protected abstract ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparatorFactory[] cmpFactories,
+    protected abstract ITreeIndex createTreeIndex(ITypeTraits[] typeTraits,
+            IBinaryComparatorFactory[] rtreeCmpFactories, IBinaryComparatorFactory[] btreeCmpFactories,
             IPrimitiveValueProviderFactory[] valueProviderFactories) throws TreeIndexException;
 
     protected abstract int getIndexFileId();
@@ -82,20 +83,30 @@
                 IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE,
                 IntegerSerializerDeserializer.INSTANCE };
 
-        // Declare keys.
-        int keyFieldCount = 4;
-        IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
-        cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
-        cmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
-        cmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
-        cmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        // Declare RTree keys.
+        int rtreeKeyFieldCount = 4;
+        IBinaryComparatorFactory[] rtreeCmpFactories = new IBinaryComparatorFactory[rtreeKeyFieldCount];
+        rtreeCmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        rtreeCmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        rtreeCmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        rtreeCmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+        // Declare BTree keys, this will only be used for LSMRTree
+        int btreeKeyFieldCount = 6;
+        IBinaryComparatorFactory[] btreeCmpFactories = new IBinaryComparatorFactory[btreeKeyFieldCount];
+        btreeCmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        btreeCmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        btreeCmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        btreeCmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        btreeCmpFactories[4] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        btreeCmpFactories[5] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
 
         // create value providers
         IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
-                cmpFactories.length, IntegerPointable.FACTORY);
+                rtreeCmpFactories.length, IntegerPointable.FACTORY);
 
         int indexFileId = getIndexFileId();
-        ITreeIndex treeIndex = createTreeIndex(typeTraits, cmpFactories, valueProviderFactories);
+        ITreeIndex treeIndex = createTreeIndex(typeTraits, rtreeCmpFactories, btreeCmpFactories, valueProviderFactories);
         treeIndex.create(indexFileId);
         treeIndex.open(indexFileId);
 
@@ -138,11 +149,11 @@
         diskOrderScan(indexAccessor, fieldSerdes);
 
         // Build key.
-        ArrayTupleBuilder keyTb = new ArrayTupleBuilder(keyFieldCount);
+        ArrayTupleBuilder keyTb = new ArrayTupleBuilder(rtreeKeyFieldCount);
         ArrayTupleReference key = new ArrayTupleReference();
         TupleUtils.createIntegerTuple(keyTb, key, -1000, -1000, 1000, 1000);
 
-        rangeSearch(cmpFactories, indexAccessor, fieldSerdes, key);
+        rangeSearch(rtreeCmpFactories, indexAccessor, fieldSerdes, key);
 
         treeIndex.close();
     }
@@ -176,22 +187,33 @@
                 DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
                 DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE };
 
-        // Declare keys.
-        int keyFieldCount = 6;
-        IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
-        cmpFactories[0] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
-        cmpFactories[1] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
-        cmpFactories[2] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
-        cmpFactories[3] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
-        cmpFactories[4] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
-        cmpFactories[5] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+        // Declare RTree keys.
+        int rtreeKeyFieldCount = 6;
+        IBinaryComparatorFactory[] rtreeCmpFactories = new IBinaryComparatorFactory[rtreeKeyFieldCount];
+        rtreeCmpFactories[0] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+        rtreeCmpFactories[1] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+        rtreeCmpFactories[2] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+        rtreeCmpFactories[3] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+        rtreeCmpFactories[4] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+        rtreeCmpFactories[5] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+
+        // Declare RTree keys.
+        int btreeKeyFieldCount = 7;
+        IBinaryComparatorFactory[] btreeCmpFactories = new IBinaryComparatorFactory[btreeKeyFieldCount];
+        btreeCmpFactories[0] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+        btreeCmpFactories[1] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+        btreeCmpFactories[2] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+        btreeCmpFactories[3] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+        btreeCmpFactories[4] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+        btreeCmpFactories[5] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+        btreeCmpFactories[6] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
 
         // create value providers
         IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
-                cmpFactories.length, DoublePointable.FACTORY);
+                rtreeCmpFactories.length, DoublePointable.FACTORY);
 
         int indexFileId = getIndexFileId();
-        ITreeIndex treeIndex = createTreeIndex(typeTraits, cmpFactories, valueProviderFactories);
+        ITreeIndex treeIndex = createTreeIndex(typeTraits, rtreeCmpFactories, btreeCmpFactories, valueProviderFactories);
         treeIndex.create(indexFileId);
         treeIndex.open(indexFileId);
 
@@ -236,11 +258,11 @@
         diskOrderScan(indexAccessor, fieldSerdes);
 
         // Build key.
-        ArrayTupleBuilder keyTb = new ArrayTupleBuilder(keyFieldCount);
+        ArrayTupleBuilder keyTb = new ArrayTupleBuilder(rtreeKeyFieldCount);
         ArrayTupleReference key = new ArrayTupleReference();
         TupleUtils.createDoubleTuple(keyTb, key, -1000.0, -1000.0, -1000.0, 1000.0, 1000.0, 1000.0);
 
-        rangeSearch(cmpFactories, indexAccessor, fieldSerdes, key);
+        rangeSearch(rtreeCmpFactories, indexAccessor, fieldSerdes, key);
 
         treeIndex.close();
     }
@@ -268,20 +290,29 @@
         typeTraits[3] = IntegerPointable.TYPE_TRAITS;
         typeTraits[4] = IntegerPointable.TYPE_TRAITS;
 
-        // Declare keys.
-        int keyFieldCount = 4;
-        IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
-        cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
-        cmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
-        cmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
-        cmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        // Declare RTree keys.
+        int rtreeKeyFieldCount = 4;
+        IBinaryComparatorFactory[] rtreeCmpFactories = new IBinaryComparatorFactory[rtreeKeyFieldCount];
+        rtreeCmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        rtreeCmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        rtreeCmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        rtreeCmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+        // Declare BTree keys.
+        int btreeKeyFieldCount = 5;
+        IBinaryComparatorFactory[] btreeCmpFactories = new IBinaryComparatorFactory[btreeKeyFieldCount];
+        btreeCmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        btreeCmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        btreeCmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        btreeCmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        btreeCmpFactories[4] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
 
         // create value providers
         IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
-                cmpFactories.length, IntegerPointable.FACTORY);
+                rtreeCmpFactories.length, IntegerPointable.FACTORY);
 
         int indexFileId = getIndexFileId();
-        ITreeIndex treeIndex = createTreeIndex(typeTraits, cmpFactories, valueProviderFactories);
+        ITreeIndex treeIndex = createTreeIndex(typeTraits, rtreeCmpFactories, btreeCmpFactories, valueProviderFactories);
         treeIndex.create(indexFileId);
         treeIndex.open(indexFileId);
 
@@ -391,20 +422,29 @@
                 IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE,
                 IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
 
-        // Declare keys.
-        int keyFieldCount = 4;
-        IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
-        cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
-        cmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
-        cmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
-        cmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        // Declare RTree keys.
+        int rtreeKeyFieldCount = 4;
+        IBinaryComparatorFactory[] rtreeCmpFactories = new IBinaryComparatorFactory[rtreeKeyFieldCount];
+        rtreeCmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        rtreeCmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        rtreeCmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        rtreeCmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+        // Declare BTree keys.
+        int btreeKeyFieldCount = 5;
+        IBinaryComparatorFactory[] btreeCmpFactories = new IBinaryComparatorFactory[btreeKeyFieldCount];
+        btreeCmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        btreeCmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        btreeCmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        btreeCmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        btreeCmpFactories[4] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
 
         // create value providers
         IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
-                cmpFactories.length, IntegerPointable.FACTORY);
+                rtreeCmpFactories.length, IntegerPointable.FACTORY);
 
         int indexFileId = getIndexFileId();
-        ITreeIndex treeIndex = createTreeIndex(typeTraits, cmpFactories, valueProviderFactories);
+        ITreeIndex treeIndex = createTreeIndex(typeTraits, rtreeCmpFactories, btreeCmpFactories, valueProviderFactories);
         treeIndex.create(indexFileId);
         treeIndex.open(indexFileId);
 
@@ -440,11 +480,11 @@
         ITreeIndexAccessor indexAccessor = treeIndex.createAccessor();
 
         // Build key.
-        ArrayTupleBuilder keyTb = new ArrayTupleBuilder(keyFieldCount);
+        ArrayTupleBuilder keyTb = new ArrayTupleBuilder(rtreeKeyFieldCount);
         ArrayTupleReference key = new ArrayTupleReference();
         TupleUtils.createIntegerTuple(keyTb, key, -1000, -1000, 1000, 1000);
 
-        rangeSearch(cmpFactories, indexAccessor, fieldSerdes, key);
+        rangeSearch(rtreeCmpFactories, indexAccessor, fieldSerdes, key);
 
         treeIndex.close();
     }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeInsertTest.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeInsertTest.java
index c23cbaf..f24ee8f 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeInsertTest.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeInsertTest.java
@@ -31,7 +31,7 @@
  * 
  */
 @SuppressWarnings("rawtypes")
-public abstract class AbstractRTreeInsertTest extends RTreeTestDriver {
+public abstract class AbstractRTreeInsertTest extends AbstractRTreeTestDriver {
 
     private final RTreeTestUtils rTreeTestUtils;
 
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeTestDriver.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeTestDriver.java
similarity index 92%
rename from hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeTestDriver.java
rename to hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeTestDriver.java
index febb5b5..0467039 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeTestDriver.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeTestDriver.java
@@ -32,8 +32,8 @@
 import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
 
 @SuppressWarnings("rawtypes")
-public abstract class RTreeTestDriver {
-    protected final Logger LOGGER = Logger.getLogger(RTreeTestDriver.class.getName());
+public abstract class AbstractRTreeTestDriver {
+    protected final Logger LOGGER = Logger.getLogger(AbstractRTreeTestDriver.class.getName());
 
     protected static final int numTuplesToInsert = 10000;
 
@@ -55,7 +55,7 @@
 
         ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE,
                 IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE,
-                IntegerSerializerDeserializer.INSTANCE };
+                IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
 
         int numKeys = 4;
         IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
@@ -76,7 +76,7 @@
 
         ISerializerDeserializer[] fieldSerdes = { DoubleSerializerDeserializer.INSTANCE,
                 DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
-                DoubleSerializerDeserializer.INSTANCE };
+                DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE };
 
         int numKeys = 4;
         IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
@@ -99,7 +99,7 @@
                 DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
                 DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
                 DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
-                DoubleSerializerDeserializer.INSTANCE };
+                DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE };
 
         int numKeys = 8;
         IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeCheckTuple.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeCheckTuple.java
index d1792f9..02c3efe 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeCheckTuple.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeCheckTuple.java
@@ -27,7 +27,7 @@
     @Override
     public boolean equals(Object o) {
         RTreeCheckTuple<T> other = (RTreeCheckTuple<T>) o;
-        for (int i = 0; i < numKeys; i++) {
+        for (int i = 0; i < tuple.length; i++) {
             int cmp = tuple[i].compareTo(other.get(i));
             if (cmp != 0) {
                 return false;
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 93d68ad..8ed6292 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
@@ -10,10 +10,12 @@
 import java.util.logging.Logger;
 
 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.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
 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;
@@ -63,6 +65,39 @@
     }
 
     @SuppressWarnings("unchecked")
+    public void insertIntDeleteTuples(ITreeIndexTestContext 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.
+            setIntKeyFields(fieldValues, numKeyFields, maxValue, rnd);
+            // 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());
+                ctx.insertCheckTuple(createIntCheckTuple(fieldValues, ctx.getKeyFieldCount()), ctx.getCheckTuples());
+            } catch (TreeIndexException e) {
+                // We set expected values only after insertion succeeds because
+                // we
+                // ignore duplicate keys.
+            }
+        }
+    }
+
+    @SuppressWarnings("unchecked")
     public void insertDoubleTuples(ITreeIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
         int fieldCount = ctx.getFieldCount();
         int numKeyFields = ctx.getKeyFieldCount();
@@ -84,9 +119,13 @@
                     LOGGER.info("Inserting Tuple " + (i + 1) + "/" + numTuples);
                 }
             }
-            boolean succeeded = insertTuple(ctx);
-            if (succeeded) {
+            try {
+                ctx.getIndexAccessor().insert(ctx.getTuple());
                 ctx.insertCheckTuple(createDoubleCheckTuple(fieldValues, ctx.getKeyFieldCount()), ctx.getCheckTuples());
+            } catch (TreeIndexException e) {
+                // We set expected values only after insertion succeeds because
+                // we
+                // ignore duplicate keys.
             }
         }
     }
@@ -204,14 +243,13 @@
     }
 
     @Override
-    protected boolean insertTuple(ITreeIndexTestContext ctx) throws Exception {
-        ctx.getIndexAccessor().insert(ctx.getTuple());
-        return true;
+    protected Collection createCheckTuplesCollection() {
+        return new ArrayList<RTreeCheckTuple>();
     }
 
     @Override
-    protected Collection createCheckTuplesCollection() {
-        return new ArrayList<RTreeCheckTuple>();
+    protected ArrayTupleBuilder createDeleteTupleBuilder(ITreeIndexTestContext ctx) {
+        return new ArrayTupleBuilder(ctx.getFieldCount());
     }
 
 }
diff --git a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeFileNameManagerTest.java b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeFileNameManagerTest.java
deleted file mode 100644
index f01e4e8..0000000
--- a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeFileNameManagerTest.java
+++ /dev/null
@@ -1,125 +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.lsm.btree;
-
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.fail;
-
-import java.text.SimpleDateFormat;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.Date;
-import java.util.HashSet;
-import java.util.LinkedList;
-import java.util.List;
-
-import org.junit.Before;
-import org.junit.Test;
-
-import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
-import edu.uci.ics.hyracks.storage.am.lsm.btree.impls.LSMBTreeFileNameManager;
-import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileNameManager;
-
-public class LSMBTreeFileNameManagerTest {
-    protected final static SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
-    protected final static String tmpDir = System.getProperty("java.io.tmpdir");
-    protected final static String sep = System.getProperty("file.separator");
-    protected String baseDir;
-
-    @Before
-    public void setUp() throws HyracksDataException {
-        baseDir = tmpDir + sep + "lsm_btree" + simpleDateFormat.format(new Date()) + sep;
-    }
-
-    public void flushFileNamesTest(boolean testFlushFileName) throws InterruptedException {
-        ILSMFileNameManager fileNameManager = new LSMBTreeFileNameManager(baseDir);
-        LinkedList<String> fileNames = new LinkedList<String>();
-
-        int numFileNames = 100;
-        long sleepTime = 5;
-        for (int i = 0; i < numFileNames; i++) {
-            String fileName = null;
-            if (testFlushFileName) {
-                fileName = fileNameManager.getFlushFileName();
-            } else {
-                fileName = fileNameManager.getMergeFileName();
-            }
-            fileNames.addFirst(fileName);
-            Thread.sleep(sleepTime);
-        }
-
-        List<String> sortedFileNames = new ArrayList<String>();
-        sortedFileNames.addAll(fileNames);        
-
-        // Make sure the comparator sorts in the correct order (i.e., the
-        // reverse insertion order in this case).
-        Comparator<String> cmp = fileNameManager.getFileNameComparator();
-        Collections.sort(sortedFileNames, cmp);
-        for (int i = 0; i < numFileNames; i++) {
-            assertEquals(fileNames.get(i), sortedFileNames.get(i));
-        }
-    }
-
-    @Test
-    public void individualFileNamesTest() throws InterruptedException {
-        flushFileNamesTest(true);
-        flushFileNamesTest(false);
-    }
-
-    @Test
-    public void mixedFileNamesTest() throws InterruptedException {
-        ILSMFileNameManager fileNameManager = new LSMBTreeFileNameManager(baseDir);
-        List<String> fileNames = new ArrayList<String>();
-        HashSet<String> flushFileNames = new HashSet<String>();
-        HashSet<String> mergeFileNames = new HashSet<String>();
-        
-        int numFileNames = 100;
-        long sleepTime = 5;
-        for (int i = 0; i < numFileNames; i++) {
-            String fileName = null;
-            if (i % 2 == 0) {
-                fileName = fileNameManager.getFlushFileName();
-                flushFileNames.add(fileName);
-            } else {
-                fileName = fileNameManager.getMergeFileName();
-                mergeFileNames.add(fileName);
-            }
-            fileNames.add(fileName);
-            Thread.sleep(sleepTime);
-        }
-
-        // Make sure the comparator sorts in the correct order.
-        // We only need to check whether the flushed files and merged files are
-        // clustered.
-        // We verified the secondary sort order (based on timestamp) in the
-        // individualFileNamesTest().
-        Comparator<String> cmp = fileNameManager.getFileNameComparator();
-        Collections.sort(fileNames, cmp);
-        // We expect flush file names at the front.
-        int i = 0;
-        while (flushFileNames.contains(fileNames.get(i))) {
-            i++;
-        }
-        // We expect only merge file names from here on.
-        while (i < numFileNames) {
-            if (!mergeFileNames.contains(fileNames.get(i))) {
-                fail("Expected a merge file name at position: " + i);
-            }
-            i++;
-        }
-    }
-}
diff --git a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeBulkLoadTest.java b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeBulkLoadTest.java
new file mode 100644
index 0000000..96ff631
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeBulkLoadTest.java
@@ -0,0 +1,63 @@
+/*
+ * 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.lsm.rtree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.util.LSMRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.util.LSMRTreeTestHarness;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeBulkLoadTest;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeTestContext;
+
+@SuppressWarnings("rawtypes")
+public class LSMRTreeBulkLoadTest extends AbstractRTreeBulkLoadTest {
+
+    public LSMRTreeBulkLoadTest() {
+        super(1);
+    }
+
+    private final LSMRTreeTestHarness harness = new LSMRTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+            IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
+        return LSMRTreeTestContext.create(harness.getMemBufferCache(), harness.getMemFreePageManager(),
+                harness.getOnDiskDir(), harness.getDiskBufferCache(), harness.getDiskFileMapProvider(), fieldSerdes,
+                valueProviderFactories, numKeys, harness.getFileId());
+
+    }
+
+    @Override
+    protected Random getRandom() {
+        return harness.getRandom();
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeDeleteTest.java b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeDeleteTest.java
new file mode 100644
index 0000000..4b44895
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeDeleteTest.java
@@ -0,0 +1,59 @@
+/*
+ * 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.lsm.rtree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.util.LSMRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.util.LSMRTreeTestHarness;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeDeleteTest;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeTestContext;
+
+@SuppressWarnings("rawtypes")
+public class LSMRTreeDeleteTest extends AbstractRTreeDeleteTest {
+
+    private final LSMRTreeTestHarness harness = new LSMRTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+            IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
+        return LSMRTreeTestContext.create(harness.getMemBufferCache(), harness.getMemFreePageManager(),
+                harness.getOnDiskDir(), harness.getDiskBufferCache(), harness.getDiskFileMapProvider(), fieldSerdes,
+                valueProviderFactories, numKeys, harness.getFileId());
+
+    }
+
+    @Override
+    protected Random getRandom() {
+        return harness.getRandom();
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeExamplesTest.java b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeExamplesTest.java
new file mode 100644
index 0000000..4bb5ab9
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeExamplesTest.java
@@ -0,0 +1,57 @@
+/*
+ * 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.lsm.rtree;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.util.LSMRTreeTestHarness;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.utils.LSMRTreeUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeExamplesTest;
+
+public class LSMRTreeExamplesTest extends AbstractRTreeExamplesTest {
+    private final LSMRTreeTestHarness harness = new LSMRTreeTestHarness();
+
+    @Override
+    protected ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparatorFactory[] rtreeCmpFactories,
+            IBinaryComparatorFactory[] btreeCmpFactories, IPrimitiveValueProviderFactory[] valueProviderFactories)
+            throws TreeIndexException {
+        return LSMRTreeUtils.createLSMTree(harness.getMemBufferCache(), harness.getMemFreePageManager(),
+                harness.getOnDiskDir(), harness.getDiskBufferCache(), harness.getDiskFileMapProvider(), typeTraits,
+                rtreeCmpFactories, btreeCmpFactories, valueProviderFactories);
+    }
+
+    @Override
+    protected int getIndexFileId() {
+        return harness.getFileId();
+    }
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeInsertTest.java b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeInsertTest.java
new file mode 100644
index 0000000..887bde7
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeInsertTest.java
@@ -0,0 +1,59 @@
+/*
+ * 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.lsm.rtree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.util.LSMRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.util.LSMRTreeTestHarness;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeInsertTest;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeTestContext;
+
+@SuppressWarnings("rawtypes")
+public class LSMRTreeInsertTest extends AbstractRTreeInsertTest {
+
+    private final LSMRTreeTestHarness harness = new LSMRTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+            IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
+        return LSMRTreeTestContext.create(harness.getMemBufferCache(), harness.getMemFreePageManager(),
+                harness.getOnDiskDir(), harness.getDiskBufferCache(), harness.getDiskFileMapProvider(), fieldSerdes,
+                valueProviderFactories, numKeys, harness.getFileId());
+
+    }
+
+    @Override
+    protected Random getRandom() {
+        return harness.getRandom();
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeMergeTest.java b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeMergeTest.java
new file mode 100644
index 0000000..b91cdac
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeMergeTest.java
@@ -0,0 +1,58 @@
+/*
+ * 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.lsm.rtree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.util.LSMRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.util.LSMRTreeTestHarness;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeTestContext;
+
+@SuppressWarnings("rawtypes")
+public class LSMRTreeMergeTest extends LSMRTreeMergeTestDriver {
+
+    private final LSMRTreeTestHarness harness = new LSMRTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+            IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
+        return LSMRTreeTestContext.create(harness.getMemBufferCache(), harness.getMemFreePageManager(),
+                harness.getOnDiskDir(), harness.getDiskBufferCache(), harness.getDiskFileMapProvider(), fieldSerdes,
+                valueProviderFactories, numKeys, harness.getFileId());
+
+    }
+
+    @Override
+    protected Random getRandom() {
+        return harness.getRandom();
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeMergeTestDriver.java b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeMergeTestDriver.java
new file mode 100644
index 0000000..11e5ba4
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeMergeTestDriver.java
@@ -0,0 +1,77 @@
+/*
+ * 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.lsm.rtree;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
+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.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMTreeIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeTestDriver;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.RTreeTestUtils;
+
+@SuppressWarnings("rawtypes")
+public abstract class LSMRTreeMergeTestDriver extends AbstractRTreeTestDriver {
+
+    private final RTreeTestUtils rTreeTestUtils;
+
+    public LSMRTreeMergeTestDriver() {
+        this.rTreeTestUtils = new RTreeTestUtils();
+    }
+
+    @Override
+    protected void runTest(ISerializerDeserializer[] fieldSerdes,
+            IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys, ITupleReference key) throws Exception {
+
+        AbstractRTreeTestContext ctx = createTestContext(fieldSerdes, valueProviderFactories, numKeys);
+
+        // 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) {
+            rTreeTestUtils.insertIntTuples(ctx, numTuplesToInsert, getRandom());
+        } else if (fieldSerdes[0] instanceof DoubleSerializerDeserializer) {
+            rTreeTestUtils.insertDoubleTuples(ctx, numTuplesToInsert, getRandom());
+        }
+
+        int maxTreesToMerge = 3;
+        for (int i = 0; i < maxTreesToMerge; i++) {
+            for (int j = 0; j < i; j++) {
+                if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
+                    rTreeTestUtils.bulkLoadIntTuples(ctx, numTuplesToInsert, getRandom());
+                } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
+                    rTreeTestUtils.bulkLoadDoubleTuples(ctx, numTuplesToInsert, getRandom());
+                }
+            }
+
+            ILSMTreeIndexAccessor accessor = (ILSMTreeIndexAccessor) ctx.getIndexAccessor();
+            accessor.merge();
+
+            rTreeTestUtils.checkScan(ctx);
+            rTreeTestUtils.checkDiskOrderScan(ctx);
+            rTreeTestUtils.checkRangeSearch(ctx, key);
+        }
+        ctx.getIndex().close();
+    }
+
+    @Override
+    protected String getTestOpName() {
+        return "LSM Merge";
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeMultiBulkLoadTest.java b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeMultiBulkLoadTest.java
new file mode 100644
index 0000000..c2ef5a4
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeMultiBulkLoadTest.java
@@ -0,0 +1,63 @@
+/*
+ * 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.lsm.rtree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.util.LSMRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.util.LSMRTreeTestHarness;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeBulkLoadTest;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeTestContext;
+
+@SuppressWarnings("rawtypes")
+public class LSMRTreeMultiBulkLoadTest extends AbstractRTreeBulkLoadTest {
+    public LSMRTreeMultiBulkLoadTest() {
+        // Using 5 bulk load rounds.
+        super(5);
+    }
+
+    private final LSMRTreeTestHarness harness = new LSMRTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+            IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
+        return LSMRTreeTestContext.create(harness.getMemBufferCache(), harness.getMemFreePageManager(),
+                harness.getOnDiskDir(), harness.getDiskBufferCache(), harness.getDiskFileMapProvider(), fieldSerdes,
+                valueProviderFactories, numKeys, harness.getFileId());
+
+    }
+
+    @Override
+    protected Random getRandom() {
+        return harness.getRandom();
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/util/LSMRTreeTestContext.java b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/util/LSMRTreeTestContext.java
new file mode 100644
index 0000000..fc3405a
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/util/LSMRTreeTestContext.java
@@ -0,0 +1,79 @@
+/*
+ * 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.lsm.rtree.util;
+
+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.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryBufferCache;
+import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryFreePageManager;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.LSMRTree;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.utils.LSMRTreeUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.RTreeCheckTuple;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+@SuppressWarnings("rawtypes")
+public final class LSMRTreeTestContext extends AbstractRTreeTestContext {
+
+    public LSMRTreeTestContext(ISerializerDeserializer[] fieldSerdes, ITreeIndex treeIndex) {
+        super(fieldSerdes, treeIndex);
+    }
+
+    @Override
+    public int getKeyFieldCount() {
+        LSMRTree lsmTree = (LSMRTree) treeIndex;
+        return lsmTree.getComparatorFactories().length;
+    }
+
+    /**
+     * Override to provide delete semantics for the check tuples.
+     */
+    @Override
+    public void deleteCheckTuple(RTreeCheckTuple checkTuple, Collection<RTreeCheckTuple> checkTuples) {
+        while (checkTuples.remove(checkTuple)) {
+        }
+    }
+
+    @Override
+    public IBinaryComparatorFactory[] getComparatorFactories() {
+        LSMRTree lsmTree = (LSMRTree) treeIndex;
+        return lsmTree.getComparatorFactories();
+    }
+
+    public static LSMRTreeTestContext create(InMemoryBufferCache memBufferCache,
+            InMemoryFreePageManager memFreePageManager, String onDiskDir, IBufferCache diskBufferCache,
+            IFileMapProvider diskFileMapProvider, ISerializerDeserializer[] fieldSerdes,
+            IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeyFields, int fileId) throws Exception {
+        ITypeTraits[] typeTraits = SerdeUtils.serdesToTypeTraits(fieldSerdes);
+        IBinaryComparatorFactory[] rtreeCmpFactories = SerdeUtils
+                .serdesToComparatorFactories(fieldSerdes, numKeyFields);
+        IBinaryComparatorFactory[] btreeCmpFactories = SerdeUtils.serdesToComparatorFactories(fieldSerdes,
+                fieldSerdes.length);
+        LSMRTree lsmTree = LSMRTreeUtils.createLSMTree(memBufferCache, memFreePageManager, onDiskDir, diskBufferCache,
+                diskFileMapProvider, typeTraits, rtreeCmpFactories, btreeCmpFactories, valueProviderFactories);
+        lsmTree.create(fileId);
+        lsmTree.open(fileId);
+        LSMRTreeTestContext testCtx = new LSMRTreeTestContext(fieldSerdes, lsmTree);
+        return testCtx;
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/util/LSMRTreeTestHarness.java b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/util/LSMRTreeTestHarness.java
new file mode 100644
index 0000000..57976fe
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/util/LSMRTreeTestHarness.java
@@ -0,0 +1,162 @@
+/*
+ * 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.lsm.rtree.util;
+
+import java.io.File;
+import java.text.SimpleDateFormat;
+import java.util.Date;
+import java.util.Random;
+import java.util.logging.Logger;
+
+import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryBufferCache;
+import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryFreePageManager;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.LSMRTreeInMemoryBufferCache;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.LSMRTreeInMemoryFreePageManager;
+import edu.uci.ics.hyracks.storage.common.buffercache.HeapBufferAllocator;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public class LSMRTreeTestHarness {
+    protected static final Logger LOGGER = Logger.getLogger(LSMRTreeTestHarness.class.getName());
+
+    private static final long RANDOM_SEED = 50;
+    private static final int DEFAULT_DISK_PAGE_SIZE = 256;
+    private static final int DEFAULT_DISK_NUM_PAGES = 1000;
+    private static final int DEFAULT_DISK_MAX_OPEN_FILES = 2000;
+    private static final int DEFAULT_MEM_PAGE_SIZE = 256;
+    private static final int DEFAULT_MEM_NUM_PAGES = 100;
+    // private static final int DEFAULT_MEM_NUM_PAGES = 10;
+    private static final int DEFAULT_HYRACKS_FRAME_SIZE = 128;
+    private static final int DUMMY_FILE_ID = -1;
+
+    protected final int diskPageSize;
+    protected final int diskNumPages;
+    protected final int diskMaxOpenFiles;
+    protected final int memPageSize;
+    protected final int memNumPages;
+    protected final int hyracksFrameSize;
+
+    protected IBufferCache diskBufferCache;
+    protected IFileMapProvider diskFileMapProvider;
+    protected LSMRTreeInMemoryBufferCache memBufferCache;
+    protected LSMRTreeInMemoryFreePageManager memFreePageManager;
+    protected IHyracksTaskContext ctx;
+
+    protected final Random rnd = new Random();
+    protected final static SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
+    protected final static String tmpDir = System.getProperty("java.io.tmpdir");
+    protected final static String sep = System.getProperty("file.separator");
+    protected String onDiskDir;
+
+    public LSMRTreeTestHarness() {
+        this.diskPageSize = DEFAULT_DISK_PAGE_SIZE;
+        this.diskNumPages = DEFAULT_DISK_NUM_PAGES;
+        this.diskMaxOpenFiles = DEFAULT_DISK_MAX_OPEN_FILES;
+        this.memPageSize = DEFAULT_MEM_PAGE_SIZE;
+        this.memNumPages = DEFAULT_MEM_NUM_PAGES;
+        this.hyracksFrameSize = DEFAULT_HYRACKS_FRAME_SIZE;
+    }
+
+    public LSMRTreeTestHarness(int diskPageSize, int diskNumPages, int diskMaxOpenFiles, int memPageSize,
+            int memNumPages, int hyracksFrameSize) {
+        this.diskPageSize = diskPageSize;
+        this.diskNumPages = diskNumPages;
+        this.diskMaxOpenFiles = diskMaxOpenFiles;
+        this.memPageSize = memPageSize;
+        this.memNumPages = memNumPages;
+        this.hyracksFrameSize = hyracksFrameSize;
+    }
+
+    public void setUp() throws HyracksDataException {
+        onDiskDir = tmpDir + sep + "lsm_rtree_" + simpleDateFormat.format(new Date()) + sep;
+        ctx = TestUtils.create(getHyracksFrameSize());
+        TestStorageManagerComponentHolder.init(diskPageSize, diskNumPages, diskMaxOpenFiles);
+        diskBufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+        diskFileMapProvider = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+        memBufferCache = new LSMRTreeInMemoryBufferCache(new HeapBufferAllocator(), memPageSize, memNumPages);
+        memFreePageManager = new LSMRTreeInMemoryFreePageManager(memNumPages, new LIFOMetaDataFrameFactory());
+        rnd.setSeed(RANDOM_SEED);
+    }
+
+    public void tearDown() throws HyracksDataException {
+        diskBufferCache.close();
+        File f = new File(onDiskDir);
+        // TODO: For some reason the dir fails to be deleted. Ask Vinayak about
+        // this.
+        f.deleteOnExit();
+    }
+
+    public int getDiskPageSize() {
+        return diskPageSize;
+    }
+
+    public int getDiskNumPages() {
+        return diskNumPages;
+    }
+
+    public int getDiskMaxOpenFiles() {
+        return diskMaxOpenFiles;
+    }
+
+    public int getMemPageSize() {
+        return memPageSize;
+    }
+
+    public int getMemNumPages() {
+        return memNumPages;
+    }
+
+    public int getHyracksFrameSize() {
+        return hyracksFrameSize;
+    }
+
+    public int getFileId() {
+        return DUMMY_FILE_ID;
+    }
+
+    public IBufferCache getDiskBufferCache() {
+        return diskBufferCache;
+    }
+
+    public IFileMapProvider getDiskFileMapProvider() {
+        return diskFileMapProvider;
+    }
+
+    public InMemoryBufferCache getMemBufferCache() {
+        return memBufferCache;
+    }
+
+    public InMemoryFreePageManager getMemFreePageManager() {
+        return memFreePageManager;
+    }
+
+    public IHyracksTaskContext getHyracksTastContext() {
+        return ctx;
+    }
+
+    public String getOnDiskDir() {
+        return onDiskDir;
+    }
+
+    public Random getRandom() {
+        return rnd;
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeBulkLoadTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeBulkLoadTest.java
index 9eeaf26..38f3a66 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeBulkLoadTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeBulkLoadTest.java
@@ -50,8 +50,8 @@
     @Override
     protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
             IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
-        return (AbstractRTreeTestContext) RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(),
-                fieldSerdes, valueProviderFactories, numKeys);
+        return RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(), fieldSerdes,
+                valueProviderFactories, numKeys);
     }
 
     @Override
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeDeleteTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeDeleteTest.java
index 86b3684..5f1d647 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeDeleteTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeDeleteTest.java
@@ -46,8 +46,8 @@
     @Override
     protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
             IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
-        return (AbstractRTreeTestContext) RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(),
-                fieldSerdes, valueProviderFactories, numKeys);
+        return RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(), fieldSerdes,
+                valueProviderFactories, numKeys);
     }
 
     @Override
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeExamplesTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeExamplesTest.java
index 9f31352..40c96b4 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeExamplesTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeExamplesTest.java
@@ -41,12 +41,15 @@
         harness.tearDown();
     }
 
-    protected ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparatorFactory[] cmpFactories,
-            IPrimitiveValueProviderFactory[] valueProviderFactories) throws TreeIndexException {
+    @Override
+    protected ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparatorFactory[] rtreeCmpFactories,
+            IBinaryComparatorFactory[] btreeCmpFactories, IPrimitiveValueProviderFactory[] valueProviderFactories)
+            throws TreeIndexException {
         return RTreeUtils.createRTree(harness.getBufferCache(), harness.getTreeFileId(), typeTraits,
-                valueProviderFactories, cmpFactories);
+                valueProviderFactories, rtreeCmpFactories);
     }
 
+    @Override
     protected int getIndexFileId() {
         return harness.getTreeFileId();
     }
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java
index 6a0cb6b..943c477 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java
@@ -56,8 +56,8 @@
     @Override
     protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
             IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
-        return (AbstractRTreeTestContext) RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(),
-                fieldSerdes, valueProviderFactories, numKeys);
+        return RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(), fieldSerdes,
+                valueProviderFactories, numKeys);
     }
 
     @Override
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 a379aa5..d167538 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
@@ -133,7 +133,7 @@
             int p2x = rnd.nextInt();
             int p2y = rnd.nextInt();
 
-            int pk = 5;
+            int pk = rnd.nextInt();;
 
             TupleUtils.createIntegerTuple(tb, tuple, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
                     Math.max(p1y, p2y), pk);
@@ -146,6 +146,7 @@
             checkTuple.add(Math.min(p1y, p2y));
             checkTuple.add(Math.max(p1x, p2x));
             checkTuple.add(Math.max(p1y, p2y));
+            checkTuple.add(pk);
 
             checkTuples.add(checkTuple);
         }