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 8eb856b..4048f19 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
@@ -365,4 +365,16 @@
     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;
+    }
 }
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 3224851..4073f59 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
@@ -41,6 +41,9 @@
     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;
 
     @SuppressWarnings("unchecked")
     public static void createTupleFromCheckTuple(CheckTuple checkTuple, ArrayTupleBuilder tupleBuilder,
@@ -96,7 +99,7 @@
                     ITupleReference tuple = diskOrderCursor.getTuple();
                     CheckTuple checkTuple = createCheckTupleFromTuple(tuple, ctx.getFieldSerdes(),
                             ctx.getKeyFieldCount());
-                    if (!ctx.getCheckTuples().contains(checkTuple)) {
+                    if (!checkDiskOrderScanResult(tuple, checkTuple, ctx)) {
                         fail("Disk-order scan returned unexpected answer: " + checkTuple.toString());
                     }
                     actualCount++;
diff --git a/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/LSMHarness.java b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/LSMHarness.java
index 47588d0..afacc1f 100644
--- a/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/LSMHarness.java
+++ b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/LSMHarness.java
@@ -36,6 +36,14 @@
  * synchronizing LSM operations, and delegates the concrete implementations of
  * actual operations to ILSMTree (passed in the c'tor).
  * 
+ * Concurrency behavior:
+ * 
+ * All operations except merge (insert/update/delete/search) are blocked during a flush.
+ * 
+ * During a merge, all operations (except another merge) can proceed concurrently.
+ * 
+ * A merge and a flush can proceed concurrently.
+ * 
  */
 public class LSMHarness {
 	protected final Logger LOGGER = Logger.getLogger(LSMHarness.class.getName());
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 8ed6292..52228f4 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,6 +10,7 @@
 import java.util.logging.Logger;
 
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 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;
@@ -251,5 +252,9 @@
     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);
+    }
 }