diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java
index e746c02..7bcfd19 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java
@@ -25,7 +25,6 @@
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.api.io.FileReference;
 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.btree.exceptions.BTreeDuplicateKeyException;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
@@ -293,23 +292,32 @@
                     ctx.getBTreeMultiComparator(), ctx.getBTreeMultiComparator());
             ITreeIndexCursor cursor = ctx.memBTreeAccessor.createSearchCursor();
             ctx.memBTreeAccessor.search(cursor, btreeRangePredicate);
-            ITupleReference tupleCopy = null;
+            boolean foundTupleInMemoryBTree = false;
             try {
                 if (cursor.hasNext()) {
-                    cursor.next();
-                    tupleCopy = TupleUtils.copyTuple(cursor.getTuple());
+                    foundTupleInMemoryBTree = true;
                 }
             } finally {
                 cursor.close();
             }
-            if (tupleCopy != null) {
-                ctx.memRTreeAccessor.insert(tupleCopy);
-            } else {
-                ctx.memRTreeAccessor.insert(tuple);
+            if (foundTupleInMemoryBTree) {
+                ctx.memBTreeAccessor.delete(tuple);
             }
+            ctx.memRTreeAccessor.insert(tuple);
 
         } else {
-
+            // For each delete operation, we make sure that we run a true
+            // in-memory RTree delete operation besides from inserting a delete
+            // tuple in the in-memory BTree. The reason for running the RTree
+            // delete operation is that to avoid the following scenario:
+            // 1) Inserter inserts tupleA to the in-memory RTree.
+            // 2) Deleter inserts tupleA to the in-memory BTree.
+            // 3) Inserter inserts tupleA to the in-memory RTree.
+            // Note that all the above operations happened before flushing the
+            // in-memory trees Now, when we search using the LSMRTree search
+            // cursor, it will return tupleA twice! which is not correct! Thus
+            // we run a true RTree delete operation.
+            ctx.memRTreeAccessor.delete(tuple);
             try {
                 ctx.memBTreeAccessor.insert(tuple);
             } catch (BTreeDuplicateKeyException e) {
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexTestUtils.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexTestUtils.java
index 36e5395..8519c02 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexTestUtils.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexTestUtils.java
@@ -357,6 +357,13 @@
     }
 
     @Override
+    protected void setIntPayloadFields(int[] fieldValues, int numKeyFields, int numFields) {
+        for (int j = numKeyFields; j < numFields; j++) {
+            fieldValues[j] = j;
+        }
+    }
+
+    @Override
     protected Collection createCheckTuplesCollection() {
         return new TreeSet<CheckTuple>();
     }
@@ -365,16 +372,17 @@
     protected ArrayTupleBuilder createDeleteTupleBuilder(ITreeIndexTestContext ctx) {
         return new ArrayTupleBuilder(ctx.getKeyFieldCount());
     }
-    
+
     @Override
-    protected boolean checkDiskOrderScanResult(ITupleReference tuple, CheckTuple checkTuple, ITreeIndexTestContext ctx) throws HyracksDataException {    	
-    	@SuppressWarnings("unchecked")
-		TreeSet<CheckTuple> checkTuples = (TreeSet<CheckTuple>) ctx.getCheckTuples();
-    	CheckTuple matchingCheckTuple = checkTuples.floor(checkTuple);
-    	if (matchingCheckTuple == null) {
-    		return false;
-    	}
-    	compareActualAndExpected(tuple, matchingCheckTuple, ctx.getFieldSerdes());
-    	return true;
+    protected boolean checkDiskOrderScanResult(ITupleReference tuple, CheckTuple checkTuple, ITreeIndexTestContext ctx)
+            throws HyracksDataException {
+        @SuppressWarnings("unchecked")
+        TreeSet<CheckTuple> checkTuples = (TreeSet<CheckTuple>) ctx.getCheckTuples();
+        CheckTuple matchingCheckTuple = checkTuples.floor(checkTuple);
+        if (matchingCheckTuple == null) {
+            return false;
+        }
+        compareActualAndExpected(tuple, matchingCheckTuple, ctx.getFieldSerdes());
+        return true;
     }
 }
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TreeIndexTestUtils.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TreeIndexTestUtils.java
index 4c1d6f8..6e2a7ee 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TreeIndexTestUtils.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TreeIndexTestUtils.java
@@ -38,12 +38,15 @@
 
     protected abstract void setIntKeyFields(int[] fieldValues, int numKeyFields, int maxValue, Random rnd);
 
+    protected abstract void setIntPayloadFields(int[] fieldValues, int numKeyFields, int numFields);
+
     protected abstract Collection createCheckTuplesCollection();
 
     protected abstract ArrayTupleBuilder createDeleteTupleBuilder(ITreeIndexTestContext ctx);
-    
+
     // See if tuple with corresponding checkTuple exists in ctx.checkTuples.
-    protected abstract boolean checkDiskOrderScanResult(ITupleReference tuple, CheckTuple checkTuple, ITreeIndexTestContext ctx) throws HyracksDataException;
+    protected abstract boolean checkDiskOrderScanResult(ITupleReference tuple, CheckTuple checkTuple,
+            ITreeIndexTestContext ctx) throws HyracksDataException;
 
     @SuppressWarnings("unchecked")
     public static void createTupleFromCheckTuple(CheckTuple checkTuple, ArrayTupleBuilder tupleBuilder,
@@ -137,9 +140,7 @@
             // Set keys.
             setIntKeyFields(fieldValues, numKeyFields, maxValue, rnd);
             // Set values.
-            for (int j = numKeyFields; j < fieldCount; j++) {
-                fieldValues[j] = j;
-            }
+            setIntPayloadFields(fieldValues, numKeyFields, fieldCount);
             TupleUtils.createIntegerTuple(ctx.getTupleBuilder(), ctx.getTuple(), fieldValues);
             if (LOGGER.isLoggable(Level.INFO)) {
                 if ((i + 1) % (numTuples / Math.min(10, numTuples)) == 0) {
@@ -167,9 +168,7 @@
             // Set keys.
             setIntKeyFields(fieldValues, numKeyFields, maxValue, rnd);
             // Set values.
-            for (int j = numKeyFields; j < fieldCount; j++) {
-                fieldValues[j] = j;
-            }
+            setIntPayloadFields(fieldValues, numKeyFields, fieldCount);
 
             // Set expected values. (We also use these as the pre-sorted stream
             // for ordered indexes bulk loading).
@@ -240,6 +239,7 @@
             checkTuples[checkTupleIdx] = tmp;
             numCheckTuples--;
         }
+        System.out.println();
     }
 
 }
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTestUtils.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTestUtils.java
index c966088..889318c 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTestUtils.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTestUtils.java
@@ -27,6 +27,8 @@
 @SuppressWarnings("rawtypes")
 public class RTreeTestUtils extends TreeIndexTestUtils {
     private static final Logger LOGGER = Logger.getLogger(RTreeTestUtils.class.getName());
+    private int intPayloadValue = 0;
+    private double doublePayloadValue = 0.0;
 
     @SuppressWarnings("unchecked")
     // Create a new ArrayList containing the elements satisfying the search key
@@ -78,9 +80,7 @@
             // Set keys.
             setDoubleKeyFields(fieldValues, numKeyFields, maxValue, rnd);
             // Set values.
-            for (int j = numKeyFields; j < fieldCount; j++) {
-                fieldValues[j] = j;
-            }
+            setDoublePayloadFields(fieldValues, numKeyFields, fieldCount);
             TupleUtils.createDoubleTuple(ctx.getTupleBuilder(), ctx.getTuple(), fieldValues);
             if (LOGGER.isLoggable(Level.INFO)) {
                 if ((i + 1) % (numTuples / Math.min(10, numTuples)) == 0) {
@@ -98,7 +98,7 @@
         }
     }
 
-    protected void setDoubleKeyFields(double[] fieldValues, int numKeyFields, double maxValue, Random rnd) {
+    private void setDoubleKeyFields(double[] fieldValues, int numKeyFields, double maxValue, Random rnd) {
         int maxFieldPos = numKeyFields / 2;
         for (int j = 0; j < maxFieldPos; j++) {
             int k = maxFieldPos + j;
@@ -111,6 +111,12 @@
             fieldValues[k] = secondValue;
         }
     }
+    
+    private void setDoublePayloadFields(double[] fieldValues, int numKeyFields, int numFields) {
+        for (int j = numKeyFields; j < numFields; j++) {
+            fieldValues[j] = doublePayloadValue++;
+        }
+    }
 
     @SuppressWarnings("unchecked")
     protected CheckTuple createDoubleCheckTuple(double[] fieldValues, int numKeyFields) {
@@ -132,9 +138,7 @@
             // Set keys.
             setDoubleKeyFields(fieldValues, numKeyFields, maxValue, rnd);
             // Set values.
-            for (int j = numKeyFields; j < fieldCount; j++) {
-                fieldValues[j] = j;
-            }
+            setDoublePayloadFields(fieldValues, numKeyFields, fieldCount);
 
             // Set expected values.
             ctx.insertCheckTuple(createDoubleCheckTuple(fieldValues, ctx.getKeyFieldCount()), tmpCheckTuples);
@@ -209,6 +213,13 @@
             fieldValues[k] = secondValue;
         }
     }
+    
+    @Override
+    protected void setIntPayloadFields(int[] fieldValues, int numKeyFields, int numFields) {
+        for (int j = numKeyFields; j < numFields; j++) {
+            fieldValues[j] = intPayloadValue++;
+        }
+    }
 
     @Override
     protected Collection createCheckTuplesCollection() {
@@ -219,9 +230,10 @@
     protected ArrayTupleBuilder createDeleteTupleBuilder(ITreeIndexTestContext ctx) {
         return new ArrayTupleBuilder(ctx.getFieldCount());
     }
-    
+
     @Override
-    protected boolean checkDiskOrderScanResult(ITupleReference tuple, CheckTuple checkTuple, ITreeIndexTestContext ctx) throws HyracksDataException {
-    	return ctx.getCheckTuples().contains(checkTuple);
+    protected boolean checkDiskOrderScanResult(ITupleReference tuple, CheckTuple checkTuple, ITreeIndexTestContext ctx)
+            throws HyracksDataException {
+        return ctx.getCheckTuples().contains(checkTuple);
     }
 }
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
index 2d75c6b..3024621 100644
--- 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
@@ -62,16 +62,17 @@
     }
 
     public static LSMRTreeTestContext create(InMemoryBufferCache memBufferCache,
-            InMemoryFreePageManager memFreePageManager, IOManager ioManager, String onDiskDir, IBufferCache diskBufferCache,
-            IFileMapProvider diskFileMapProvider, ISerializerDeserializer[] fieldSerdes,
+            InMemoryFreePageManager memFreePageManager, IOManager ioManager, 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, ioManager, onDiskDir, diskBufferCache,
-                diskFileMapProvider, typeTraits, rtreeCmpFactories, btreeCmpFactories, valueProviderFactories);
+        LSMRTree lsmTree = LSMRTreeUtils.createLSMTree(memBufferCache, memFreePageManager, ioManager, onDiskDir,
+                diskBufferCache, diskFileMapProvider, typeTraits, rtreeCmpFactories, btreeCmpFactories,
+                valueProviderFactories);
         lsmTree.create(fileId);
         lsmTree.open(fileId);
         LSMRTreeTestContext testCtx = new LSMRTreeTestContext(fieldSerdes, lsmTree);