diff --git a/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java
index b35dd75..02047e8 100644
--- a/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java
+++ b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java
@@ -126,4 +126,11 @@
         tupleCopy.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
         return tupleCopy;
     }
+    
+    public static void copyTuple(ArrayTupleBuilder tupleBuilder, ITupleReference tuple, int numFields) throws HyracksDataException {
+        tupleBuilder.reset();
+        for (int i = 0; i < numFields; i++) {
+            tupleBuilder.addField(tuple.getFieldData(i), tuple.getFieldStart(i), tuple.getFieldLength(i));
+        }
+    }
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeFrame.java
index b0fd2d8..ee3fd90 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeFrame.java
@@ -15,7 +15,9 @@
 
 package edu.uci.ics.hyracks.storage.am.btree.api;
 
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext.PageValidationInfo;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
 
@@ -29,4 +31,6 @@
     public void setSmFlag(boolean smFlag);
 
     public boolean getSmFlag();
+
+    public void validate(PageValidationInfo pvi) throws HyracksDataException;
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeInteriorFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeInteriorFrame.java
index 23fdcf5..ffdcc5c 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeInteriorFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeInteriorFrame.java
@@ -15,10 +15,11 @@
 
 package edu.uci.ics.hyracks.storage.am.btree.api;
 
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
 
 public interface IBTreeInteriorFrame extends IBTreeFrame {
-    public int getChildPageId(RangePredicate pred);
+    public int getChildPageId(RangePredicate pred) throws HyracksDataException;
 
     public int getLeftmostChildPageId();
 
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
index 9fadad5..a3ce496 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
@@ -27,6 +27,7 @@
 import edu.uci.ics.hyracks.storage.am.btree.compressors.FieldPrefixCompressor;
 import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeDuplicateKeyException;
 import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNonExistentKeyException;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext.PageValidationInfo;
 import edu.uci.ics.hyracks.storage.am.btree.impls.FieldPrefixPrefixTupleReference;
 import edu.uci.ics.hyracks.storage.am.btree.impls.FieldPrefixSlotManager;
 import edu.uci.ics.hyracks.storage.am.btree.impls.FieldPrefixTupleReference;
@@ -735,4 +736,9 @@
         this.cmp = cmp;
         this.slotManager.setMultiComparator(cmp);
     }
+
+    @Override
+    public void validate(PageValidationInfo pvi) {
+        // Do nothing
+    }
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
index d100772..b26480a 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
@@ -19,9 +19,11 @@
 import java.util.ArrayList;
 import java.util.Collections;
 
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext.PageValidationInfo;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ISplitKey;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
@@ -41,12 +43,14 @@
     private static final int childPtrSize = 4;
 
     private final ITreeIndexTupleReference cmpFrameTuple;
+    private final ITreeIndexTupleReference previousFt;
 
     private MultiComparator cmp;
 
     public BTreeNSMInteriorFrame(ITreeIndexTupleWriter tupleWriter) {
         super(tupleWriter, new OrderedSlotManager());
         cmpFrameTuple = tupleWriter.createTupleReference();
+        previousFt = tupleWriter.createTupleReference();
     }
 
     @Override
@@ -267,7 +271,7 @@
     }
 
     @Override
-    public int getChildPageId(RangePredicate pred) {
+    public int getChildPageId(RangePredicate pred) throws HyracksDataException {
         // Trivial case where there is only a child pointer (and no key).
         if (buf.getInt(tupleCountOff) == 0) {
             return buf.getInt(rightLeafOff);
@@ -318,6 +322,7 @@
         slotOff -= slotManager.getSlotSize();
         frameTuple.resetByTupleOffset(buf, slotManager.getTupleOff(slotOff));
         int childPageOff = getLeftChildPageOff(frameTuple);
+
         return buf.getInt(childPageOff);
     }
 
@@ -373,6 +378,7 @@
         this.cmp = cmp;
         cmpFrameTuple.setFieldCount(cmp.getKeyFieldCount());
         frameTuple.setFieldCount(cmp.getKeyFieldCount());
+        previousFt.setFieldCount(cmp.getKeyFieldCount());
     }
 
     @Override
@@ -403,4 +409,23 @@
         }
         return ret;
     }
+
+    public void validate(PageValidationInfo pvi) throws HyracksDataException {
+        int tupleCount = getTupleCount();
+        for (int i = 0; i < tupleCount; i++) {
+            frameTuple.resetByTupleIndex(this, i);
+            if (!pvi.isLowRangeNull) {
+                assert cmp.compare(pvi.lowRangeTuple, frameTuple) < 0;
+            }
+
+            if (!pvi.isHighRangeNull) {
+                assert cmp.compare(pvi.highRangeTuple, frameTuple) >= 0;
+            }
+
+            if (i > 0) {
+                previousFt.resetByTupleIndex(this, i - 1);
+                assert cmp.compare(previousFt, frameTuple) < 0;
+            }
+        }
+    }
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
index 7185629..ce2a272 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
@@ -17,10 +17,12 @@
 
 import java.nio.ByteBuffer;
 
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeDuplicateKeyException;
 import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNonExistentKeyException;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext.PageValidationInfo;
 import edu.uci.ics.hyracks.storage.am.common.api.ISplitKey;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
@@ -36,8 +38,11 @@
 
     private MultiComparator cmp;
 
+    private final ITreeIndexTupleReference previousFt;
+
     public BTreeNSMLeafFrame(ITreeIndexTupleWriter tupleWriter) {
         super(tupleWriter, new OrderedSlotManager());
+        previousFt = tupleWriter.createTupleReference();
     }
 
     @Override
@@ -225,4 +230,23 @@
     public void setMultiComparator(MultiComparator cmp) {
         this.cmp = cmp;
     }
+
+    public void validate(PageValidationInfo pvi) throws HyracksDataException {
+        int tupleCount = getTupleCount();
+        for (int i = 0; i < tupleCount; i++) {
+            frameTuple.resetByTupleIndex(this, i);
+            if (!pvi.isLowRangeNull) {
+                assert cmp.compare(pvi.lowRangeTuple, frameTuple) < 0;
+            }
+
+            if (!pvi.isHighRangeNull) {
+                assert cmp.compare(pvi.highRangeTuple, frameTuple) >= 0;
+            }
+
+            if (i > 0) {
+                previousFt.resetByTupleIndex(this, i - 1);
+                assert cmp.compare(previousFt, frameTuple) < 0;
+            }
+        }
+    }
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
index c947bcc..ec66015 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
@@ -16,6 +16,8 @@
 package edu.uci.ics.hyracks.storage.am.btree.impls;
 
 import java.util.ArrayList;
+import java.util.List;
+import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.locks.ReadWriteLock;
 import java.util.concurrent.locks.ReentrantReadWriteLock;
 
@@ -24,6 +26,8 @@
 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.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
@@ -32,7 +36,9 @@
 import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNonExistentKeyException;
 import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNotUpdateableException;
 import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext.PageValidationInfo;
 import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexAccessor;
 import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoader;
 import edu.uci.ics.hyracks.storage.am.common.api.IIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.IModificationOperationCallback;
@@ -42,15 +48,16 @@
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
 import edu.uci.ics.hyracks.storage.am.common.api.IndexType;
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
 import edu.uci.ics.hyracks.storage.am.common.frames.FrameOpSpaceStatus;
 import edu.uci.ics.hyracks.storage.am.common.impls.AbstractTreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.impls.NodeFrontier;
 import edu.uci.ics.hyracks.storage.am.common.impls.TreeDiskOrderScanCursor;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexUtils;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
 import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
@@ -61,8 +68,10 @@
     public static final float DEFAULT_FILL_FACTOR = 0.7f;
 
     private final static long RESTART_OP = Long.MIN_VALUE;
+    private final static long FULL_RESTART_OP = Long.MIN_VALUE + 1;
     private final static int MAX_RESTARTS = 10;
 
+    private final AtomicInteger smoCounter;
     private final ReadWriteLock treeLatch;
 
     public BTree(IBufferCache bufferCache, IFileMapProvider fileMapProvider, IFreePageManager freePageManager,
@@ -71,6 +80,7 @@
         super(bufferCache, fileMapProvider, freePageManager, interiorFrameFactory, leafFrameFactory, cmpFactories,
                 fieldCount, file);
         this.treeLatch = new ReentrantReadWriteLock(true);
+        this.smoCounter = new AtomicInteger();
     }
 
     private void diskOrderScan(ITreeIndexCursor icursor, BTreeOpContext ctx) throws HyracksDataException {
@@ -97,6 +107,69 @@
         }
     }
 
+    public void validate() throws HyracksDataException {
+        // Stack validation protocol:
+        //      * parent pushes the validation information onto the stack before validation
+        //      * child pops the validation information off of the stack after validating
+        BTreeAccessor accessor = (BTreeAccessor) createAccessor(NoOpOperationCallback.INSTANCE,
+                NoOpOperationCallback.INSTANCE);
+        PageValidationInfo pvi = accessor.ctx.createPageValidationInfo(null);
+        accessor.ctx.validationInfos.addFirst(pvi);
+        validate(accessor.ctx, rootPage);
+    }
+
+    private void validate(BTreeOpContext ctx, int pageId) throws HyracksDataException {
+        ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+        ctx.interiorFrame.setPage(page);
+        PageValidationInfo currentPvi = ctx.validationInfos.peekFirst();
+
+        boolean isLeaf = ctx.interiorFrame.isLeaf();
+        if (isLeaf) {
+            ctx.leafFrame.setPage(page);
+            ctx.leafFrame.validate(currentPvi);
+        } else {
+            PageValidationInfo nextPvi = ctx.createPageValidationInfo(currentPvi);
+            List<Integer> children = ((BTreeNSMInteriorFrame) ctx.interiorFrame).getChildren(ctx.cmp);
+            ctx.interiorFrame.validate(currentPvi);
+            for (int i = 0; i < children.size(); i++) {
+                ctx.interiorFrame.setPage(page);
+
+                if (children.size() == 1) {
+                    // There is a single child pointer with no keys, so propagate both low and high ranges
+                    nextPvi.propagateLowRangeKey(currentPvi);
+                    nextPvi.propagateHighRangeKey(currentPvi);
+                } else if (i == 0) {
+                    // There is more than one child pointer and this is the left-most child pointer, so:
+                    //      1) propagate the low range key from the parent
+                    //      2) adjust the high range key
+                    nextPvi.propagateLowRangeKey(currentPvi);
+                    ctx.interiorFrameTuple.resetByTupleIndex(ctx.interiorFrame, i);
+                    nextPvi.adjustHighRangeKey(ctx.interiorFrameTuple);
+                } else if (i == children.size() - 1) {
+                    // There is more than one child pointer and this is the right-most child pointer, so:
+                    //      1) propagate the high range key from the parent
+                    //      2) adjust the low range key
+                    nextPvi.propagateHighRangeKey(currentPvi);
+                    ctx.interiorFrameTuple.resetByTupleIndex(ctx.interiorFrame, i - 1);
+                    nextPvi.adjustLowRangeKey(ctx.interiorFrameTuple);
+                } else {
+                    // There is more than one child pointer and this pointer is not the left/right-most pointer, so:
+                    //      1) adjust the low range key
+                    //      2) adjust the high range key
+                    ctx.interiorFrameTuple.resetByTupleIndex(ctx.interiorFrame, i - 1);
+                    nextPvi.adjustLowRangeKey(ctx.interiorFrameTuple);
+                    ctx.interiorFrameTuple.resetByTupleIndex(ctx.interiorFrame, i);
+                    nextPvi.adjustHighRangeKey(ctx.interiorFrameTuple);
+                }
+
+                ctx.validationInfos.addFirst(nextPvi);
+                validate(ctx, children.get(i));
+            }
+        }
+        bufferCache.unpin(page);
+        ctx.validationInfos.removeFirst();
+    }
+
     private void search(ITreeIndexCursor cursor, ISearchPredicate searchPred, BTreeOpContext ctx)
             throws TreeIndexException, HyracksDataException {
         ctx.reset();
@@ -141,6 +214,11 @@
             }
         }
         if (ctx.smPages.size() > 0) {
+            if (ctx.smoCount == Integer.MAX_VALUE) {
+                smoCounter.set(0);
+            } else {
+                smoCounter.incrementAndGet();
+            }
             treeLatch.writeLock().unlock();
             ctx.smPages.clear();
         }
@@ -162,9 +240,13 @@
                         .getBuffer().capacity());
                 ctx.interiorFrame.setPage(newLeftNode);
                 ctx.interiorFrame.setSmFlag(false);
+                // Remember LSN to set it in the root.
+                long leftNodeLSN = ctx.interiorFrame.getPageLsn();
                 // Initialize new root (leftNode becomes new root).
                 ctx.interiorFrame.setPage(leftNode);
                 ctx.interiorFrame.initBuffer((byte) (ctx.interiorFrame.getLevel() + 1));
+                // Copy over LSN.
+                ctx.interiorFrame.setPageLsn(leftNodeLSN);
                 // Will be cleared later in unsetSmPages.
                 ctx.interiorFrame.setSmFlag(true);
                 ctx.splitKey.setLeftPage(newLeftId);
@@ -193,11 +275,18 @@
         // due to ongoing structure modifications during the descent.
         boolean repeatOp = true;
         while (repeatOp && ctx.opRestarts < MAX_RESTARTS) {
+            ctx.smoCount = smoCounter.get();
             performOp(rootPage, null, true, ctx);
             // Do we need to restart from the (possibly new) root?
-            if (!ctx.pageLsns.isEmpty() && ctx.pageLsns.getLast() == RESTART_OP) {
-                ctx.pageLsns.removeLast(); // pop the restart op indicator
-                continue;
+            if (!ctx.pageLsns.isEmpty()) {
+                if (ctx.pageLsns.getLast() == FULL_RESTART_OP) {
+                    ctx.pageLsns.clear();
+                    continue;
+                } else if (ctx.pageLsns.getLast() == RESTART_OP) {
+                    ctx.pageLsns.removeLast(); // pop the restart op indicator
+                    continue;
+                }
+
             }
             // Split key propagated?
             if (ctx.splitKey.getBuffer() != null) {
@@ -290,6 +379,12 @@
         // Lock is released in unsetSmPages(), after sm has fully completed.
         if (!treeLatch.writeLock().tryLock()) {
             return true;
+        } else {
+            int tempSmoCount = smoCounter.get();
+            if (tempSmoCount != ctx.smoCount) {
+                treeLatch.writeLock().unlock();
+                return true;
+            }
         }
         int rightPageId = freePageManager.getFreePage(ctx.metaFrame);
         ICachedPage rightNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rightPageId), true);
@@ -460,25 +555,23 @@
         }
     }
 
-    private boolean isConsistent(int pageId, BTreeOpContext ctx) throws Exception {
+    private ICachedPage isConsistent(int pageId, BTreeOpContext ctx) throws Exception {
         ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
         node.acquireReadLatch();
         ctx.interiorFrame.setPage(node);
-        boolean isConsistent = false;
-        try {
-            isConsistent = ctx.pageLsns.getLast() == ctx.interiorFrame.getPageLsn();
-        } finally {
+        boolean isConsistent = ctx.pageLsns.getLast() == ctx.interiorFrame.getPageLsn();
+        if (!isConsistent) {
             node.releaseReadLatch();
             bufferCache.unpin(node);
+            return null;
         }
-        return isConsistent;
+        return node;
     }
 
     private void performOp(int pageId, ICachedPage parent, boolean parentIsReadLatched, BTreeOpContext ctx)
             throws HyracksDataException, TreeIndexException {
         ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
         ctx.interiorFrame.setPage(node);
-
         // this check performs an unprotected read in the page
         // the following could happen: TODO fill out
         boolean unsafeIsLeaf = ctx.interiorFrame.isLeaf();
@@ -510,23 +603,24 @@
                         int childPageId = ctx.interiorFrame.getChildPageId(ctx.pred);
                         performOp(childPageId, node, isReadLatched, ctx);
 
-                        if (!ctx.pageLsns.isEmpty() && ctx.pageLsns.getLast() == RESTART_OP) {
-                            // Pop the restart op indicator.
-                            ctx.pageLsns.removeLast();
-                            if (isConsistent(pageId, ctx)) {
-                                // Pin and latch page again, since it was unpinned and unlatched in call to performOp (passed as parent).
-                                node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
-                                node.acquireReadLatch();
-                                ctx.interiorFrame.setPage(node);
-                                isReadLatched = true;
-                                // Descend the tree again.                                
-                                continue;
-                            } else {
-                                // Pop pageLsn of this page (version seen by this op during descent).
-                                ctx.pageLsns.removeLast();
-                                // This node is not consistent set the restart indicator for upper level.
-                                ctx.pageLsns.add(RESTART_OP);
+                        if (!ctx.pageLsns.isEmpty()) {
+                            if (ctx.pageLsns.getLast() == FULL_RESTART_OP) {
                                 break;
+                            } else if (ctx.pageLsns.getLast() == RESTART_OP) {
+                                // Pop the restart op indicator.
+                                ctx.pageLsns.removeLast();
+                                node = isConsistent(pageId, ctx);
+                                if (node != null) {
+                                    isReadLatched = true;
+                                    // Descend the tree again.                                
+                                    continue;
+                                } else {
+                                    // Pop pageLsn of this page (version seen by this op during descent).
+                                    ctx.pageLsns.removeLast();
+                                    // This node is not consistent set the restart indicator for upper level.
+                                    ctx.pageLsns.add(RESTART_OP);
+                                    break;
+                                }
                             }
                         }
 
@@ -540,7 +634,7 @@
                                             BufferedFileHandle.getDiskPageId(fileId, pageId), false);
                                     interiorNode.acquireWriteLatch();
                                     try {
-                                        // Insert or update op. Both can cause split keys to propagate upwards.                                            
+                                        // Insert or update op. Both can cause split keys to propagate upwards. 
                                         insertInterior(interiorNode, pageId, ctx.splitKey.getTuple(), ctx);
                                     } finally {
                                         interiorNode.releaseWriteLatch();
@@ -582,8 +676,8 @@
                     // instead we just immediately release the lock. this is
                     // inefficient but still correct and will not cause
                     // latch-deadlock
-                    treeLatch.writeLock().lock();
-                    treeLatch.writeLock().unlock();
+                    treeLatch.readLock().lock();
+                    treeLatch.readLock().unlock();
 
                     // unwind recursion and restart operation, find lowest page
                     // with a pageLsn as seen by this operation during descent
@@ -630,8 +724,11 @@
                     bufferCache.unpin(node);
                 }
                 if (restartOp) {
+                    // Wait for the SMO to finish before restarting.
+                    treeLatch.readLock().lock();
+                    treeLatch.readLock().unlock();
                     ctx.pageLsns.removeLast();
-                    ctx.pageLsns.add(RESTART_OP);
+                    ctx.pageLsns.add(FULL_RESTART_OP);
                 }
             }
         } catch (TreeIndexException e) {
@@ -663,10 +760,10 @@
         }
     }
 
-    private BTreeOpContext createOpContext(IModificationOperationCallback modificationCallback,
-            ISearchOperationCallback searchCallback) {
-        return new BTreeOpContext(leafFrameFactory, interiorFrameFactory, freePageManager.getMetaDataFrameFactory()
-                .createFrame(), cmpFactories, modificationCallback, searchCallback);
+    private BTreeOpContext createOpContext(IIndexAccessor accessor,
+            IModificationOperationCallback modificationCallback, ISearchOperationCallback searchCallback) {
+        return new BTreeOpContext(accessor, leafFrameFactory, interiorFrameFactory, freePageManager
+                .getMetaDataFrameFactory().createFrame(), cmpFactories, modificationCallback, searchCallback);
     }
 
     @Override
@@ -706,9 +803,9 @@
             String keyString;
             if (interiorFrame.isLeaf()) {
                 leafFrame.setPage(node);
-                keyString = TreeIndexUtils.printFrameTuples(leafFrame, keySerdes);
+                keyString = printLeafFrameTuples(leafFrame, keySerdes);
             } else {
-                keyString = TreeIndexUtils.printFrameTuples(interiorFrame, keySerdes);
+                keyString = printInteriorFrameTuples(interiorFrame, keySerdes);
             }
 
             strBuilder.append(keyString + "\n");
@@ -744,7 +841,7 @@
         public BTreeAccessor(BTree btree, IModificationOperationCallback modificationCalback,
                 ISearchOperationCallback searchCallback) {
             this.btree = btree;
-            this.ctx = btree.createOpContext(modificationCalback, searchCallback);
+            this.ctx = btree.createOpContext(this, modificationCalback, searchCallback);
         }
 
         @Override
@@ -913,4 +1010,41 @@
         }
 
     }
+
+    @SuppressWarnings("rawtypes")
+    public static String printLeafFrameTuples(IBTreeLeafFrame leafFrame, ISerializerDeserializer[] fieldSerdes)
+            throws HyracksDataException {
+        StringBuilder strBuilder = new StringBuilder();
+        ITreeIndexTupleReference tuple = leafFrame.createTupleReference();
+        for (int i = 0; i < leafFrame.getTupleCount(); i++) {
+            tuple.resetByTupleIndex(leafFrame, i);
+            String tupleString = TupleUtils.printTuple(tuple, fieldSerdes);
+            strBuilder.append(tupleString + " | ");
+        }
+        // Print right link.
+        int rightPageId = leafFrame.getNextLeaf();
+        strBuilder.append("(" + rightPageId + ")");
+        return strBuilder.toString();
+    }
+
+    @SuppressWarnings("rawtypes")
+    public static String printInteriorFrameTuples(IBTreeInteriorFrame interiorFrame,
+            ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {
+        StringBuilder strBuilder = new StringBuilder();
+        ITreeIndexTupleReference tuple = interiorFrame.createTupleReference();
+        for (int i = 0; i < interiorFrame.getTupleCount(); i++) {
+            tuple.resetByTupleIndex(interiorFrame, i);
+            // Print child pointer.
+            int numFields = tuple.getFieldCount();
+            int childPageId = IntegerSerializerDeserializer.getInt(tuple.getFieldData(numFields - 1),
+                    tuple.getFieldStart(numFields - 1) + tuple.getFieldLength(numFields - 1));
+            strBuilder.append("(" + childPageId + ") ");
+            String tupleString = TupleUtils.printTuple(tuple, fieldSerdes);
+            strBuilder.append(tupleString + " | ");
+        }
+        // Print rightmost pointer.
+        int rightMostChildPageId = interiorFrame.getRightmostChildPageId();
+        strBuilder.append("(" + rightMostChildPageId + ")");
+        return strBuilder.toString();
+    }
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeCursorInitialState.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeCursorInitialState.java
index 60cd455..9d7b612 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeCursorInitialState.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeCursorInitialState.java
@@ -1,6 +1,7 @@
 package edu.uci.ics.hyracks.storage.am.btree.impls;
 
 import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexAccessor;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
@@ -12,9 +13,16 @@
     private ICachedPage page;
     private ISearchOperationCallback searchCallback;
     private MultiComparator originalKeyCmp;
+    private final IIndexAccessor accessor;
 
-    public BTreeCursorInitialState(ICachedPage page, ISearchOperationCallback searchCallback) {
+    public BTreeCursorInitialState(ICachedPage page, ISearchOperationCallback searchCallback, IIndexAccessor accessor) {
         this.page = page;
+        this.searchCallback = searchCallback;
+        this.accessor = accessor;
+    }
+    
+    public IIndexAccessor getAccessor() {
+        return accessor;
     }
 
     public ICachedPage getPage() {
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
index cf5361a..0e6e78e 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
@@ -15,16 +15,26 @@
 
 package edu.uci.ics.hyracks.storage.am.btree.impls;
 
+import java.util.ArrayDeque;
+import java.util.Deque;
+
 import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+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.comm.io.ArrayTupleReference;
+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.api.IBTreeInteriorFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.ITupleAcceptor;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexAccessor;
 import edu.uci.ics.hyracks.storage.am.common.api.IIndexOpContext;
 import edu.uci.ics.hyracks.storage.am.common.api.IModificationOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.LongArrayList;
@@ -33,6 +43,7 @@
 public class BTreeOpContext implements IIndexOpContext {
     private final int INIT_ARRAYLIST_SIZE = 6;
 
+    public IIndexAccessor accessor;
     public MultiComparator cmp;
     public ITreeIndexFrameFactory leafFrameFactory;
     public ITreeIndexFrameFactory interiorFrameFactory;
@@ -52,10 +63,18 @@
     public IModificationOperationCallback modificationCallback;
     public ISearchOperationCallback searchCallback;
     public ITupleAcceptor acceptor;
+    public int smoCount;
 
-    public BTreeOpContext(ITreeIndexFrameFactory leafFrameFactory, ITreeIndexFrameFactory interiorFrameFactory,
-            ITreeIndexMetaDataFrame metaFrame, IBinaryComparatorFactory[] cmpFactories,
-            IModificationOperationCallback modificationCallback, ISearchOperationCallback searchCallback) {
+    // Debug
+    public final Deque<PageValidationInfo> validationInfos;
+    public final ITreeIndexTupleReference interiorFrameTuple;
+    public final ITreeIndexTupleReference leafFrameTuple;
+
+    public BTreeOpContext(IIndexAccessor accessor, ITreeIndexFrameFactory leafFrameFactory,
+            ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexMetaDataFrame metaFrame,
+            IBinaryComparatorFactory[] cmpFactories, IModificationOperationCallback modificationCallback,
+            ISearchOperationCallback searchCallback) {
+        this.accessor = accessor;
         this.cmp = MultiComparator.create(cmpFactories);
         this.leafFrameFactory = leafFrameFactory;
         this.leafFrame = (IBTreeLeafFrame) leafFrameFactory.createFrame();
@@ -69,8 +88,14 @@
         }
         this.metaFrame = metaFrame;
         this.pageLsns = new LongArrayList(INIT_ARRAYLIST_SIZE, INIT_ARRAYLIST_SIZE);
+        this.smoCount = 0;
         this.modificationCallback = modificationCallback;
         this.searchCallback = searchCallback;
+
+        // Debug
+        this.validationInfos = new ArrayDeque<PageValidationInfo>(INIT_ARRAYLIST_SIZE);
+        this.interiorFrameTuple = interiorFrame.createTupleReference();
+        this.leafFrameTuple = leafFrame.createTupleReference();
     }
 
     public void reset() {
@@ -81,6 +106,7 @@
         if (smPages != null)
             smPages.clear();
         opRestarts = 0;
+        smoCount = 0;
         exceptionHandled = false;
     }
 
@@ -88,7 +114,7 @@
     public void reset(IndexOp newOp) {
         if (newOp == IndexOp.SEARCH || newOp == IndexOp.DISKORDERSCAN) {
             if (cursorInitialState == null) {
-                cursorInitialState = new BTreeCursorInitialState(null, searchCallback);
+                cursorInitialState = new BTreeCursorInitialState(null, searchCallback, accessor);
             }
         } else {
             // Insert, delete, update or upsert operation.
@@ -106,6 +132,7 @@
             }
         }
         op = newOp;
+        smoCount = 0;
         exceptionHandled = false;
     }
 
@@ -116,4 +143,72 @@
     public IBTreeInteriorFrame createInteriorFrame() {
         return (IBTreeInteriorFrame) interiorFrameFactory.createFrame();
     }
+
+    public PageValidationInfo createPageValidationInfo(PageValidationInfo parent) throws HyracksDataException {
+        return new PageValidationInfo(parent);
+    }
+
+    public class PageValidationInfo {
+        public final int numKeyFields;
+
+        public final ArrayTupleBuilder lowRangeBuilder;
+        public final ArrayTupleBuilder highRangeBuilder;
+        public final ArrayTupleReference lowRangeTuple;
+        public final ArrayTupleReference highRangeTuple;
+
+        public boolean isLowRangeNull;
+        public boolean isHighRangeNull;
+
+        public PageValidationInfo() {
+            this.numKeyFields = cmp.getKeyFieldCount();
+            this.lowRangeBuilder = new ArrayTupleBuilder(numKeyFields);
+            this.highRangeBuilder = new ArrayTupleBuilder(numKeyFields);
+            this.lowRangeTuple = new ArrayTupleReference();
+            this.highRangeTuple = new ArrayTupleReference();
+            this.isLowRangeNull = true;
+            this.isHighRangeNull = true;
+        }
+
+        public PageValidationInfo(PageValidationInfo copy) throws HyracksDataException {
+            this();
+            if (copy != null) {
+                propagateLowRangeKey(copy);
+                propagateHighRangeKey(copy);
+            }
+        }
+
+        public void propagateLowRangeKey(PageValidationInfo toPropagate) throws HyracksDataException {
+            isLowRangeNull = toPropagate.isLowRangeNull;
+            if (!isLowRangeNull) {
+                adjustRangeKey(lowRangeBuilder, lowRangeTuple, toPropagate.lowRangeTuple);
+            }
+        }
+
+        public void propagateHighRangeKey(PageValidationInfo toPropagate) throws HyracksDataException {
+            isHighRangeNull = toPropagate.isHighRangeNull;
+            if (!isHighRangeNull) {
+                adjustRangeKey(highRangeBuilder, highRangeTuple, toPropagate.highRangeTuple);
+            }
+        }
+
+        public void adjustLowRangeKey(ITupleReference newLowRangeKey) throws HyracksDataException {
+            isLowRangeNull = newLowRangeKey == null ? true : false;
+            if (!isLowRangeNull) {
+                adjustRangeKey(lowRangeBuilder, lowRangeTuple, newLowRangeKey);
+            }
+        }
+
+        public void adjustHighRangeKey(ITupleReference newHighRangeKey) throws HyracksDataException {
+            isHighRangeNull = newHighRangeKey == null ? true : false;
+            if (!isHighRangeNull) {
+                adjustRangeKey(highRangeBuilder, highRangeTuple, newHighRangeKey);
+            }
+        }
+
+        private void adjustRangeKey(ArrayTupleBuilder builder, ArrayTupleReference tuple, ITupleReference newRangeKey)
+                throws HyracksDataException {
+            TupleUtils.copyTuple(builder, newRangeKey, numKeyFields);
+            tuple.reset(builder.getFieldEndOffsets(), builder.getByteArray());
+        }
+    }
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
index d50a2c8..758eb71 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
@@ -16,14 +16,18 @@
 package edu.uci.ics.hyracks.storage.am.btree.impls;
 
 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.comm.io.ArrayTupleReference;
 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.api.IBTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexAccessor;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 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.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleMode;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleNoExactMatchPolicy;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
@@ -46,9 +50,12 @@
     private int tupleIndex = 0;
     private int stopTupleIndex;
 
+    private final RangePredicate reusablePredicate;
+    private final ArrayTupleReference reconciliationTuple;
+    private IIndexAccessor accessor;
     private ISearchOperationCallback searchCb;
-    private ITupleReference reconciliationTuple;
     private MultiComparator originalKeyCmp;
+    private ArrayTupleBuilder tupleBuilder;
 
     private FindTupleMode lowKeyFtm;
     private FindTupleMode highKeyFtm;
@@ -65,6 +72,8 @@
         this.frame = frame;
         this.frameTuple = frame.createTupleReference();
         this.exclusiveLatchNodes = exclusiveLatchNodes;
+        this.reusablePredicate = new RangePredicate();
+        this.reconciliationTuple = new ArrayTupleReference();
     }
 
     @Override
@@ -136,16 +145,21 @@
             }
         }
 
+        if (tupleIndex > stopTupleIndex) {
+            return false;
+        }
+
         frameTuple.resetByTupleIndex(frame, tupleIndex);
         while (true) {
             if (searchCb.proceed(frameTuple)) {
-                if (highKey == null || tupleIndex <= stopTupleIndex) {
-                    return true;
-                }
-                return false;
+                return true;
             } else {
                 // copy the tuple before we unlatch/unpin
-                reconciliationTuple = TupleUtils.copyTuple(frameTuple);
+                if (tupleBuilder == null) {
+                    tupleBuilder = new ArrayTupleBuilder(originalKeyCmp.getKeyFieldCount());
+                }
+                TupleUtils.copyTuple(tupleBuilder, frameTuple, originalKeyCmp.getKeyFieldCount());
+                reconciliationTuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
 
                 // unlatch/unpin
                 if (exclusiveLatchNodes) {
@@ -154,53 +168,27 @@
                     page.releaseReadLatch();
                 }
                 bufferCache.unpin(page);
+                page = null;
 
                 // reconcile
                 searchCb.reconcile(reconciliationTuple);
 
-                // relatch/repin
-                page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
-                if (exclusiveLatchNodes) {
-                    page.acquireWriteLatch();
-                } else {
-                    page.acquireReadLatch();
+                // retraverse the index looking for the reconciled key
+                reusablePredicate.setLowKey(reconciliationTuple, true);
+                try {
+                    accessor.search(this, reusablePredicate);
+                } catch (IndexException e) {
+                    throw new HyracksDataException(e);
                 }
-                frame.setPage(page);
 
-                // validate the tuple or continue the search if the tuple is invalidated
-                while (true) {
-                    tupleIndex = frame.findTupleIndex(reconciliationTuple, frameTuple, originalKeyCmp,
-                            FindTupleMode.INCLUSIVE, FindTupleNoExactMatchPolicy.HIGHER_KEY);
-
-                    if (tupleIndex >= frame.getTupleCount()
-                            || tupleIndex == frame.getSlotManager().getGreatestKeyIndicator()) {
-                        nextLeafPage = frame.getNextLeaf();
-                        if (nextLeafPage < 0) {
-                            return false;
-                        }
-                        fetchNextLeafPage(nextLeafPage);
-                        continue;
-                    }
-                    break;
-                }
-                stopTupleIndex = getHighKeyIndex();
-                if (stopTupleIndex < 0) {
+                if (stopTupleIndex < 0 || tupleIndex > stopTupleIndex) {
                     return false;
                 }
 
+                // see if we found the tuple we reconciled on
                 frameTuple.resetByTupleIndex(frame, tupleIndex);
-
-                // see if we found the tuple we were looking for
                 if (originalKeyCmp.compare(reconciliationTuple, frameTuple) == 0) {
-                    if (highKey == null || tupleIndex <= stopTupleIndex) {
-                        return true;
-                    } else {
-                        return false;
-                    }
-
-                } else { // otherwise do the opCallback dance again with the new tuple we found
-                    reconciliationTuple = null;
-                    continue;
+                    return true;
                 }
             }
         }
@@ -256,6 +244,7 @@
             }
             bufferCache.unpin(page);
         }
+        accessor = ((BTreeCursorInitialState) initialState).getAccessor();
         searchCb = initialState.getSearchOperationCallback();
         originalKeyCmp = initialState.getOriginalKeyComparator();
         pageId = ((BTreeCursorInitialState) initialState).getPageId();
@@ -268,6 +257,10 @@
         lowKey = pred.getLowKey();
         highKey = pred.getHighKey();
 
+        reusablePredicate.setLowKeyComparator(originalKeyCmp);
+        reusablePredicate.setHighKeyComparator(pred.getHighKeyComparator());
+        reusablePredicate.setHighKey(pred.getHighKey(), pred.isHighKeyInclusive());
+
         lowKeyFtm = FindTupleMode.EXCLUSIVE;
         if (pred.lowKeyInclusive) {
             lowKeyFtp = FindTupleNoExactMatchPolicy.LOWER_KEY;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IIndex.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IIndex.java
index c17b03c..6e62a64 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IIndex.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IIndex.java
@@ -115,6 +115,15 @@
     public IIndexBulkLoader createBulkLoader(float fillFactor) throws IndexException;
 
     /**
+     * Ensures that all pages (and tuples) of the index are logically consistent.
+     * An assertion error is thrown if validation fails.
+     * 
+     * @throws HyracksDataException
+     *          if there is an error performing validation
+     */
+    public void validate() throws HyracksDataException;
+
+    /**
      * @return the {@link IBufferCache} underlying this index.
      */
     public IBufferCache getBufferCache();
diff --git a/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/InvertedIndex.java b/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/InvertedIndex.java
index c5f9c2f..c007158 100644
--- a/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/InvertedIndex.java
+++ b/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/InvertedIndex.java
@@ -471,4 +471,9 @@
             throw new IndexException(e);
         }
     }
+
+    @Override
+    public void validate() throws HyracksDataException {
+        throw new UnsupportedOperationException("Validation not implemented for Inverted Indexes.");
+    }
 }
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java
index fe86a2f..cc4a1c7 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java
@@ -328,8 +328,8 @@
         int numDiskBTrees = diskComponents.size();
         int numBTrees = (includeMemComponent) ? numDiskBTrees + 1 : numDiskBTrees;
         LSMBTreeCursorInitialState initialState = new LSMBTreeCursorInitialState(numBTrees, insertLeafFrameFactory,
-                ctx.cmp, includeMemComponent, searcherRefCount, lsmHarness, memBTree.createAccessor(
-                        NoOpOperationCallback.INSTANCE, NoOpOperationCallback.INSTANCE), pred, ctx.searchCallback);
+                ctx.cmp, includeMemComponent, searcherRefCount, lsmHarness, ctx.memBTreeAccessor, pred,
+                ctx.searchCallback);
         lsmTreeCursor.open(initialState, pred);
 
         int cursorIx;
@@ -572,4 +572,13 @@
     public boolean isEmptyIndex() throws HyracksDataException {
         return diskBTrees.isEmpty() && memBTree.isEmptyTree(memBTree.getInteriorFrameFactory().createFrame());
     }
+
+    @Override
+    public void validate() throws HyracksDataException {
+        memBTree.validate();
+        for (Object o : diskBTrees) {
+            BTree btree = (BTree) o;
+            btree.validate();
+        }
+    }
 }
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeCursorInitialState.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeCursorInitialState.java
index 329c412..cb0351d 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeCursorInitialState.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeCursorInitialState.java
@@ -61,10 +61,6 @@
         return leafFrameFactory;
     }
 
-    public MultiComparator getCmp() {
-        return cmp;
-    }
-
     @Override
     public ICachedPage getPage() {
         return null;
@@ -113,4 +109,4 @@
     public void setOriginialKeyComparator(MultiComparator originalCmp) {
         this.cmp = originalCmp;
     }
-}
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
index 0262a2e..720e89c 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
@@ -20,6 +20,8 @@
 import java.util.PriorityQueue;
 
 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.comm.io.ArrayTupleReference;
 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.api.IBTreeLeafFrame;
@@ -27,32 +29,33 @@
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
 import edu.uci.ics.hyracks.storage.am.common.api.IIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeSearchCursor;
 
 public class LSMBTreeRangeSearchCursor extends LSMTreeSearchCursor {
+    private final ArrayTupleReference copyTuple;
+    private final RangePredicate reusablePred;
+
+    private ISearchOperationCallback searchCallback;
     private PriorityQueueComparator pqCmp;
-    private IIndexAccessor memBTreeAccessor;
     private RangePredicate predicate;
-    private RangePredicate reusablePred = new RangePredicate(null, null, true, true, null, null);
+    private IIndexAccessor memBTreeAccessor;
+    private ArrayTupleBuilder tupleBuilder;
 
     public LSMBTreeRangeSearchCursor() {
-        outputElement = null;
-        needPush = false;
+        super();
+        this.copyTuple = new ArrayTupleReference();
+        this.reusablePred = new RangePredicate(null, null, true, true, null, null);
     }
 
     public void initPriorityQueue() throws HyracksDataException {
         int pqInitSize = (rangeCursors.length > 0) ? rangeCursors.length : 1;
         outputPriorityQueue = new PriorityQueue<PriorityQueueElement>(pqInitSize, pqCmp);
         for (int i = 0; i < rangeCursors.length; i++) {
-            PriorityQueueElement element;
-            if (rangeCursors[i].hasNext()) {
-                rangeCursors[i].next();
-                element = new PriorityQueueElement(rangeCursors[i].getTuple(), i);
-                outputPriorityQueue.offer(element);
-            }
+            pushIntoPriorityQueue(new PriorityQueueElement(i));
         }
         checkPriorityQueue();
     }
@@ -62,9 +65,11 @@
         checkPriorityQueue();
         PriorityQueueElement pqHead = outputPriorityQueue.peek();
         if (pqHead == null) {
-            // pq is empty
+            // PQ is empty
             return false;
         }
+        
+        assert outputElement == null;
 
         if (searchCallback.proceed(pqHead.getTuple())) {
             // if proceed is successful, then there's no need for doing the "unlatch dance"
@@ -76,69 +81,61 @@
             boolean inMemElementFound = false;
 
             // scan the PQ for the in-memory component's element
-            if (outputElement != null && outputElement.getCursorIndex() == 0) {
-                inMemElement = outputElement;
-            } else {
-                Iterator<PriorityQueueElement> it = outputPriorityQueue.iterator();
-                while (it.hasNext()) {
-                    inMemElement = it.next();
-                    if (inMemElement.getCursorIndex() == 0) {
-                        inMemElementFound = true;
-                        outputPriorityQueue.remove(inMemElement);
-                        break;
-                    }
+            Iterator<PriorityQueueElement> it = outputPriorityQueue.iterator();
+            while (it.hasNext()) {
+                inMemElement = it.next();
+                if (inMemElement.getCursorIndex() == 0) {
+                    inMemElementFound = true;
+                    it.remove();
+                    break;
                 }
             }
 
-            if (!inMemElementFound && inMemElement != null) {
+            if (!inMemElementFound) {
+                // the in-memory cursor is exhausted
                 searchCallback.reconcile(pqHead.getTuple());
                 return true;
             }
 
             // copy the in-mem tuple
-            ITupleReference inMemTuple = TupleUtils.copyTuple(inMemElement.getTuple());
-            // unlatch
+            if (tupleBuilder == null) {
+                tupleBuilder = new ArrayTupleBuilder(cmp.getKeyFieldCount());
+            }
+            TupleUtils.copyTuple(tupleBuilder, inMemElement.getTuple(), cmp.getKeyFieldCount());
+            copyTuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
+
+            // unlatch/unpin
             rangeCursors[0].reset();
+
             // reconcile
             if (pqHead.getCursorIndex() == 0) {
-                searchCallback.reconcile(inMemTuple);
+                searchCallback.reconcile(copyTuple);
             } else {
                 searchCallback.reconcile(pqHead.getTuple());
             }
 
-            reusablePred.setLowKey(inMemTuple, true);
-            reusablePred.setLowKeyComparator(cmp);
-            reusablePred.setHighKey(predicate.getHighKey(), predicate.isHighKeyInclusive());
-            reusablePred.setHighKeyComparator(predicate.getHighKeyComparator());
+            // retraverse
+            reusablePred.setLowKey(copyTuple, true);
             try {
                 memBTreeAccessor.search(rangeCursors[0], reusablePred);
             } catch (IndexException e) {
                 throw new HyracksDataException(e);
             }
 
-            // todo: make lsmbtreetuplereference copy
-            if (rangeCursors[0].hasNext()) {
-                rangeCursors[0].next();
-                inMemElement.reset(rangeCursors[0].getTuple(), 0);
-                if (inMemElementFound) {
-                    outputPriorityQueue.offer(inMemElement);
-                }
-            } else {
-                rangeCursors[0].close();
+            if (!pushIntoPriorityQueue(inMemElement)) {
+                return !outputPriorityQueue.isEmpty();
             }
         } else {
             searchCallback.reconcile(pqHead.getTuple());
         }
 
         return true;
-        //        return !outputPriorityQueue.isEmpty();
     }
 
     @Override
     public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
-        super.open(initialState, searchPred);
         LSMBTreeCursorInitialState lsmInitialState = (LSMBTreeCursorInitialState) initialState;
-        cmp = lsmInitialState.getCmp();
+        cmp = lsmInitialState.getOriginalKeyComparator();
         int numBTrees = lsmInitialState.getNumBTrees();
         rangeCursors = new BTreeRangeSearchCursor[numBTrees];
         for (int i = 0; i < numBTrees; i++) {
@@ -148,8 +145,12 @@
         includeMemComponent = lsmInitialState.getIncludeMemComponent();
         searcherRefCount = lsmInitialState.getSearcherRefCount();
         lsmHarness = lsmInitialState.getLSMHarness();
+        searchCallback = lsmInitialState.getSearchOperationCallback();
         memBTreeAccessor = lsmInitialState.getMemBTreeAccessor();
         predicate = (RangePredicate) lsmInitialState.getSearchPredicate();
+        reusablePred.setLowKeyComparator(cmp);
+        reusablePred.setHighKey(predicate.getHighKey(), predicate.isHighKeyInclusive());
+        reusablePred.setHighKeyComparator(predicate.getHighKeyComparator());
         setPriorityQueueComparator();
     }
 
@@ -190,4 +191,4 @@
     protected int compare(MultiComparator cmp, ITupleReference tupleA, ITupleReference tupleB) {
         return cmp.compare(tupleA, tupleB);
     }
-}
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/freepage/InMemoryBufferCache.java b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/freepage/InMemoryBufferCache.java
index 8e629e6..d3ee9ce 100644
--- a/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/freepage/InMemoryBufferCache.java
+++ b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/freepage/InMemoryBufferCache.java
@@ -135,6 +135,7 @@
         for (int i = 0; i < numPages; ++i) {
             pages[i] = null;
         }
+        overflowPages.clear();
     }
 
     public class CachedPage implements ICachedPageInternal {
diff --git a/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/LSMTreeSearchCursor.java b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/LSMTreeSearchCursor.java
index 70f1c0f..5d0a420 100644
--- a/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/LSMTreeSearchCursor.java
+++ b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/LSMTreeSearchCursor.java
@@ -20,9 +20,6 @@
 
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
-import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
-import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
-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.ophelpers.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMTreeTupleReference;
@@ -30,17 +27,14 @@
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
 
 public abstract class LSMTreeSearchCursor implements ITreeIndexCursor {
+    protected PriorityQueueElement outputElement;
     protected ITreeIndexCursor[] rangeCursors;
     protected PriorityQueue<PriorityQueueElement> outputPriorityQueue;
     protected MultiComparator cmp;
-
-    protected PriorityQueueElement outputElement;
-    protected PriorityQueueElement reusedElement;
     protected boolean needPush;
     protected boolean includeMemComponent;
     protected AtomicInteger searcherRefCount;
     protected LSMHarness lsmHarness;
-    protected ISearchOperationCallback searchCallback;
 
     public LSMTreeSearchCursor() {
         outputElement = null;
@@ -123,12 +117,16 @@
         return (ITupleReference) outputElement.getTuple();
     }
 
-    protected void pushIntoPriorityQueue(int cursorIndex) throws HyracksDataException {
+    protected boolean pushIntoPriorityQueue(PriorityQueueElement e) throws HyracksDataException {
+        int cursorIndex = e.getCursorIndex();
         if (rangeCursors[cursorIndex].hasNext()) {
             rangeCursors[cursorIndex].next();
-            reusedElement.reset(rangeCursors[cursorIndex].getTuple(), cursorIndex);
-            outputPriorityQueue.offer(reusedElement);
+            e.reset(rangeCursors[cursorIndex].getTuple());
+            outputPriorityQueue.offer(e);
+            return true;
         }
+        rangeCursors[cursorIndex].close();
+        return false;
     }
 
     protected abstract int compare(MultiComparator cmp, ITupleReference tupleA, ITupleReference tupleB);
@@ -159,15 +157,13 @@
                         // the tree of head tuple
 
                         // the head element of PQ is useless now
-                        reusedElement = outputPriorityQueue.poll();
-                        // int treeNum = reusedElement.getTreeNum();
-                        pushIntoPriorityQueue(reusedElement.getCursorIndex());
+                        PriorityQueueElement e = outputPriorityQueue.poll();
+                        pushIntoPriorityQueue(e);
                     } else {
                         // If the previous tuple and the head tuple are different
                         // the info of previous tuple is useless
                         if (needPush == true) {
-                            reusedElement = outputElement;
-                            pushIntoPriorityQueue(outputElement.getCursorIndex());
+                            pushIntoPriorityQueue(outputElement);
                             needPush = false;
                         }
                         outputElement = null;
@@ -175,8 +171,7 @@
                 }
             } else {
                 // the priority queue is empty and needPush
-                reusedElement = outputElement;
-                pushIntoPriorityQueue(outputElement.getCursorIndex());
+                pushIntoPriorityQueue(outputElement);
                 needPush = false;
                 outputElement = null;
             }
@@ -190,10 +185,11 @@
 
     public class PriorityQueueElement {
         private ITupleReference tuple;
-        private int cursorIndex;
+        private final int cursorIndex;
 
-        public PriorityQueueElement(ITupleReference tuple, int cursorIndex) {
-            reset(tuple, cursorIndex);
+        public PriorityQueueElement(int cursorIndex) {
+            tuple = null;
+            this.cursorIndex = cursorIndex;
         }
 
         public ITupleReference getTuple() {
@@ -204,14 +200,8 @@
             return cursorIndex;
         }
 
-        public void reset(ITupleReference tuple, int cursorIndex) {
+        public void reset(ITupleReference tuple) {
             this.tuple = tuple;
-            this.cursorIndex = cursorIndex;
         }
     }
-
-    @Override
-    public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
-        searchCallback = initialState.getSearchOperationCallback();
-    }
-}
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/AbstractLSMRTree.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/AbstractLSMRTree.java
index ff4d87e..6c1395c 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/AbstractLSMRTree.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/AbstractLSMRTree.java
@@ -397,4 +397,8 @@
                 && memComponent.btree.isEmptyTree(memComponent.btree.getInteriorFrameFactory().createFrame())
                 && memComponent.rtree.isEmptyTree(memComponent.rtree.getInteriorFrameFactory().createFrame());
     }
+
+    public void validate() throws HyracksDataException {
+        throw new UnsupportedOperationException("Validation not implemented for LSM R-Trees.");
+    }
 }
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeOpContext.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeOpContext.java
index ef48ac9..54e4343 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeOpContext.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeOpContext.java
@@ -53,8 +53,8 @@
         this.searchCallback = searchCallback;
         this.rtreeOpContext = new RTreeOpContext(rtreeLeafFrame, rtreeInteriorFrame, rtreeMetaFrame, rtreeCmpFactories,
                 rTreeHeightHint, NoOpOperationCallback.INSTANCE, NoOpOperationCallback.INSTANCE);
-        this.btreeOpContext = new BTreeOpContext(btreeLeafFrameFactory, btreeInteriorFrameFactory, btreeMetaFrame,
-                btreeCmpFactories, NoOpOperationCallback.INSTANCE, NoOpOperationCallback.INSTANCE);
+        this.btreeOpContext = new BTreeOpContext(memBtreeAccessor, btreeLeafFrameFactory, btreeInteriorFrameFactory,
+                btreeMetaFrame, btreeCmpFactories, NoOpOperationCallback.INSTANCE, NoOpOperationCallback.INSTANCE);
     }
 
     public void reset(IndexOp newOp) {
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesSearchCursor.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesSearchCursor.java
index b910686..4b34dc9 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesSearchCursor.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesSearchCursor.java
@@ -49,12 +49,7 @@
         int pqInitSize = (rangeCursors.length > 0) ? rangeCursors.length : 1;
         outputPriorityQueue = new PriorityQueue<PriorityQueueElement>(pqInitSize, pqCmp);
         for (int i = 0; i < rangeCursors.length; i++) {
-            PriorityQueueElement element;
-            if (rangeCursors[i].hasNext()) {
-                rangeCursors[i].next();
-                element = new PriorityQueueElement(rangeCursors[i].getTuple(), i);
-                outputPriorityQueue.offer(element);
-            }
+            pushIntoPriorityQueue(new PriorityQueueElement(i));
         }
         checkPriorityQueue();
     }
@@ -136,7 +131,7 @@
         }
 
     }
-    
+
     @Override
     public void reset() throws HyracksDataException {
         if (includeMemComponent) {
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
index 322b8b0..9c27174 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
@@ -969,4 +969,9 @@
             leafFrame.setPage(nodeFrontiers.get(0).page);
         }
     }
+
+    @Override
+    public void validate() throws HyracksDataException {
+        throw new UnsupportedOperationException("Validation not implemented for R-Trees.");
+    }
 }
\ No newline at end of file
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexBulkLoadTest.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexBulkLoadTest.java
index e4953b8..6d89fa9 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexBulkLoadTest.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexBulkLoadTest.java
@@ -57,6 +57,8 @@
                 orderedIndexTestUtils.checkRangeSearch(ctx, prefixLowKey, prefixHighKey, true, true);
             }
         }
+
+        ctx.getIndex().validate();
         ctx.getIndex().deactivate();
         ctx.getIndex().destroy();
     }
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexDeleteTest.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexDeleteTest.java
index 829eef7..b96f252 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexDeleteTest.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexDeleteTest.java
@@ -63,6 +63,8 @@
                 }
             }
         }
+
+        ctx.getIndex().validate();
         ctx.getIndex().deactivate();
         ctx.getIndex().destroy();
     }
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexExamplesTest.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexExamplesTest.java
index 20e0927..d489da9 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexExamplesTest.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexExamplesTest.java
@@ -127,6 +127,7 @@
 
         rangeSearch(cmpFactories, indexAccessor, fieldSerdes, lowKey, highKey);
 
+        treeIndex.validate();
         treeIndex.deactivate();
         treeIndex.destroy();
     }
@@ -208,6 +209,7 @@
         // Prefix-Range search in [-3, 3]
         rangeSearch(cmpFactories, indexAccessor, fieldSerdes, lowKey, highKey);
 
+        treeIndex.validate();
         treeIndex.deactivate();
         treeIndex.destroy();
     }
@@ -258,7 +260,7 @@
             TupleUtils.createTuple(tb, tuple, fieldSerdes, f0, f1);
             if (LOGGER.isLoggable(Level.INFO)) {
                 if (i % 1000 == 0) {
-                    LOGGER.info("Inserting " + f0 + " " + f1);
+                    LOGGER.info("Inserting[" + i + "] " + f0 + " " + f1);
                 }
             }
             try {
@@ -286,6 +288,7 @@
 
         rangeSearch(cmpFactories, indexAccessor, fieldSerdes, lowKey, highKey);
 
+        treeIndex.validate();
         treeIndex.deactivate();
         treeIndex.destroy();
     }
@@ -387,6 +390,7 @@
                 break;
             }
         }
+        treeIndex.validate();
         treeIndex.deactivate();
         treeIndex.destroy();
     }
@@ -473,6 +477,7 @@
             // Do another scan after a round of updates.
             orderedScan(indexAccessor, fieldSerdes);
         }
+        treeIndex.validate();
         treeIndex.deactivate();
         treeIndex.destroy();
     }
@@ -542,6 +547,7 @@
         // Prefix-Range search in [44444, 44500]
         rangeSearch(cmpFactories, indexAccessor, fieldSerdes, lowKey, highKey);
 
+        treeIndex.validate();
         treeIndex.deactivate();
         treeIndex.destroy();
     }
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexInsertTest.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexInsertTest.java
index 48f90d5..32b597c 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexInsertTest.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexInsertTest.java
@@ -62,6 +62,8 @@
         if (prefixLowKey != null && prefixHighKey != null) {
             orderedIndexTestUtils.checkRangeSearch(ctx, prefixLowKey, prefixHighKey, true, true);
         }
+
+        ctx.getIndex().validate();
         ctx.getIndex().deactivate();
         ctx.getIndex().destroy();
     }
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexMultiThreadTest.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexMultiThreadTest.java
index 7744faa..d1c9293 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexMultiThreadTest.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexMultiThreadTest.java
@@ -97,6 +97,7 @@
                 conf.ops, conf.opProbs);
         driver.init(getFileReference());
         long[] times = driver.run(numThreads, 1, NUM_OPERATIONS, batchSize);
+        index.validate();
         driver.deinit();
 
         if (LOGGER.isLoggable(Level.INFO)) {
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexUpdateTest.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexUpdateTest.java
index d7ebfe4..049724e 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexUpdateTest.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexUpdateTest.java
@@ -63,6 +63,10 @@
                 orderedIndexTestUtils.checkRangeSearch(ctx, prefixLowKey, prefixHighKey, true, true);
             }
         }
+
+        ctx.getIndex().validate();
+        ctx.getIndex().deactivate();
+        ctx.getIndex().destroy();
     }
 
     @Override
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexUpsertTest.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexUpsertTest.java
index bde6ec2..d34928f 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexUpsertTest.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexUpsertTest.java
@@ -62,6 +62,7 @@
         if (prefixLowKey != null && prefixHighKey != null) {
             orderedIndexTestUtils.checkRangeSearch(ctx, prefixLowKey, prefixHighKey, true, true);
         }
+        ctx.getIndex().validate();
         ctx.getIndex().deactivate();
         ctx.getIndex().destroy();
     }
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/AbstractTreeIndexTestWorker.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/AbstractTreeIndexTestWorker.java
index 410cc56..ca162ed 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/AbstractTreeIndexTestWorker.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/AbstractTreeIndexTestWorker.java
@@ -27,7 +27,7 @@
 import edu.uci.ics.hyracks.storage.am.common.datagen.TupleBatch;
 
 public abstract class AbstractTreeIndexTestWorker extends Thread implements ITreeIndexTestWorker {
-    private Random rnd = new Random();
+    private final Random rnd;
     private final DataGenThread dataGen;
     private final TestOperationSelector opSelector;
     private final int numBatches;
@@ -39,7 +39,8 @@
         this.dataGen = dataGen;
         this.opSelector = opSelector;
         this.numBatches = numBatches;
-        indexAccessor = index.createAccessor(TestOperationCallback.INSTANCE, TestOperationCallback.INSTANCE);
+        this.rnd = new Random();
+        this.indexAccessor = index.createAccessor(TestOperationCallback.INSTANCE, TestOperationCallback.INSTANCE);
     }
 
     @Override
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TestOperationCallback.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TestOperationCallback.java
index 8189818..4096b45 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TestOperationCallback.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TestOperationCallback.java
@@ -18,13 +18,8 @@
 
     @Override
     public boolean proceed(ITupleReference tuple) {
-        // Fail ~10% of the time
-        int i = random.nextInt(100);
-        if (i < 10) {
-            return false;
-        } else {
-            return true;
-        }
+        // Always fail
+        return false;
     }
 
     @Override