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 3c9a67a..06c8581 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
@@ -246,9 +246,11 @@
 
 	@Override
 	public void diskOrderScan(ITreeIndexCursor icursor,
-			ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame)
+			ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame, IndexOpContext ictx)
 			throws HyracksDataException {
 	    BTreeDiskOrderScanCursor cursor = (BTreeDiskOrderScanCursor)icursor;
+	    BTreeOpContext ctx = (BTreeOpContext) ictx;
+	    ctx.reset();
 	    
 	    int currentPageId = rootPage + 1;
 		int maxPageId = freePageManager.getMaxPage(metaFrame);
@@ -260,7 +262,8 @@
 		cursor.setFileId(fileId);
 		cursor.setCurrentPageId(currentPageId);
 		cursor.setMaxPageId(maxPageId);
-		cursor.open(page, diskOrderScanPredicate);
+		ctx.cursorInitialState.setPage(page);
+		cursor.open(ctx.cursorInitialState, diskOrderScanPredicate);
 	}
 
 	public void search(ITreeIndexCursor cursor, RangePredicate pred,
@@ -1060,7 +1063,8 @@
 					break;
 
 				case SEARCH: {
-					ctx.cursor.open(node, ctx.pred);
+				    ctx.cursorInitialState.setPage(node);
+					ctx.cursor.open(ctx.cursorInitialState, ctx.pred);
 				}
 					break;
 				}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeDiskOrderScanCursor.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeDiskOrderScanCursor.java
index c80a6d4..5b69991 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeDiskOrderScanCursor.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeDiskOrderScanCursor.java
@@ -17,6 +17,7 @@
 
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 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.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
@@ -106,14 +107,14 @@
     }
 
     @Override
-    public void open(ICachedPage page, ISearchPredicate searchPred) throws HyracksDataException {
+    public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
         // in case open is called multiple times without closing
-        if (this.page != null) {
-            this.page.releaseReadLatch();
-            bufferCache.unpin(this.page);
+        if (page != null) {
+            page.releaseReadLatch();
+            bufferCache.unpin(page);
         }
 
-        this.page = page;
+        page = ((CursorInitialState) initialState).getPage();
         tupleIndex = 0;
         frame.setPage(page);
         RangePredicate pred = (RangePredicate) searchPred;
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 975a946..0014a2c 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
@@ -29,6 +29,7 @@
     public final IBTreeInteriorFrame interiorFrame;
     public final ITreeIndexMetaDataFrame metaFrame;
     public ITreeIndexCursor cursor;
+    public CursorInitialState cursorInitialState;
     public RangePredicate pred;
     public final BTreeSplitKey splitKey;
     public int opRestarts = 0;
@@ -44,7 +45,7 @@
         this.metaFrame = metaFrame;
 
         pageLsns = new IntArrayList(treeHeightHint, treeHeightHint);
-        if (op != IndexOp.SEARCH) {
+        if (op != IndexOp.SEARCH && op != IndexOp.DISKORDERSCAN) {
             smPages = new IntArrayList(treeHeightHint, treeHeightHint);
             freePages = new IntArrayList(treeHeightHint, treeHeightHint);
             pred = new RangePredicate(true, null, null, true, true, null, null);
@@ -53,6 +54,7 @@
             smPages = null;
             freePages = null;
             splitKey = null;
+            cursorInitialState = new CursorInitialState(null);
         }
     }
 
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 a8d76c3..46e76c9 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
@@ -18,6 +18,7 @@
 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.common.api.ICursorInitialState;
 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;
@@ -173,14 +174,14 @@
     }
 
     @Override
-    public void open(ICachedPage page, ISearchPredicate searchPred) throws Exception {
+    public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws Exception {
         // in case open is called multiple times without closing
-        if (this.page != null) {
-            this.page.releaseReadLatch();
-            bufferCache.unpin(this.page);
+        if (page != null) {
+            page.releaseReadLatch();
+            bufferCache.unpin(page);
         }
 
-        this.page = page;
+        page = ((CursorInitialState) initialState).getPage();
         frame.setPage(page);
 
         pred = (RangePredicate) searchPred;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/CursorInitialState.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/CursorInitialState.java
new file mode 100644
index 0000000..f66814f
--- /dev/null
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/CursorInitialState.java
@@ -0,0 +1,21 @@
+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.common.buffercache.ICachedPage;
+
+public class CursorInitialState implements ICursorInitialState {
+
+    private ICachedPage page;
+
+    public CursorInitialState(ICachedPage page) {
+        this.page = page;
+    }
+
+    public ICachedPage getPage() {
+        return page;
+    }
+
+    public void setPage(ICachedPage page) {
+        this.page = page;
+    }
+}
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ICursorInitialState.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ICursorInitialState.java
new file mode 100644
index 0000000..83db63d
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ICursorInitialState.java
@@ -0,0 +1,20 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.common.api;
+
+
+public interface ICursorInitialState {
+}
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchPredicate.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchPredicate.java
index 71ab7af..33883c4 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchPredicate.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchPredicate.java
@@ -18,5 +18,4 @@
 import java.io.Serializable;
 
 public interface ISearchPredicate extends Serializable {
-    public boolean isForward();
 }
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndex.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndex.java
index 0dea866..2d77f06 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndex.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndex.java
@@ -6,57 +6,47 @@
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
 
 public interface ITreeIndex {
-	// init:
+    // init:
 
-	public void create(int indexFileId, ITreeIndexFrame leafFrame,
-			ITreeIndexMetaDataFrame metaFrame) throws Exception;
+    public void create(int indexFileId, ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame) throws Exception;
 
-	public void open(int indexFileId);
+    public void open(int indexFileId);
 
-	// operations:
+    // operations:
 
-	public void insert(ITupleReference tuple, IndexOpContext ictx)
-			throws Exception;
+    public void insert(ITupleReference tuple, IndexOpContext ictx) throws Exception;
 
-	public void update(ITupleReference tuple, IndexOpContext ictx)
-			throws Exception;
+    public void update(ITupleReference tuple, IndexOpContext ictx) throws Exception;
 
-	public void delete(ITupleReference tuple, IndexOpContext ictx)
-			throws Exception;
+    public void delete(ITupleReference tuple, IndexOpContext ictx) throws Exception;
 
-	public IndexOpContext createOpContext(IndexOp op,
-			ITreeIndexFrame leafFrame, ITreeIndexFrame interiorFrame,
-			ITreeIndexMetaDataFrame metaFrame);
+    public IndexOpContext createOpContext(IndexOp op, ITreeIndexFrame leafFrame, ITreeIndexFrame interiorFrame,
+            ITreeIndexMetaDataFrame metaFrame);
 
-	// bulk loading:
+    // bulk loading:
 
-	public IIndexBulkLoadContext beginBulkLoad(float fillFactor,
-			ITreeIndexFrame leafFrame, ITreeIndexFrame interiorFrame,
-			ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException;
+    public IIndexBulkLoadContext beginBulkLoad(float fillFactor, ITreeIndexFrame leafFrame,
+            ITreeIndexFrame interiorFrame, ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException;
 
-	public void bulkLoadAddTuple(IIndexBulkLoadContext ictx,
-			ITupleReference tuple) throws HyracksDataException;
+    public void bulkLoadAddTuple(IIndexBulkLoadContext ictx, ITupleReference tuple) throws HyracksDataException;
 
-	public void endBulkLoad(IIndexBulkLoadContext ictx)
-			throws HyracksDataException;
+    public void endBulkLoad(IIndexBulkLoadContext ictx) throws HyracksDataException;
 
-	// search:
-	public void diskOrderScan(ITreeIndexCursor icursor, ITreeIndexFrame leafFrame,
-			ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException;
-	
-	
+    // search:
+    public void diskOrderScan(ITreeIndexCursor icursor, ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame,
+            IndexOpContext ictx) throws HyracksDataException;
 
-	// utility:
+    // utility:
 
-	public IFreePageManager getFreePageManager();
+    public IFreePageManager getFreePageManager();
 
-	public int getRootPageId();
+    public int getRootPageId();
 
-	public ITreeIndexFrameFactory getLeafFrameFactory();
+    public ITreeIndexFrameFactory getLeafFrameFactory();
 
-	public ITreeIndexFrameFactory getInteriorFrameFactory();
+    public ITreeIndexFrameFactory getInteriorFrameFactory();
 
-	public int getFieldCount();
-	
-	public IndexType getIndexType();
+    public int getFieldCount();
+
+    public IndexType getIndexType();
 }
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexCursor.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexCursor.java
index 49f2d7f..22b2b6f 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexCursor.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexCursor.java
@@ -26,7 +26,7 @@
 
     public void next() throws Exception;
 
-    public void open(ICachedPage page, ISearchPredicate searchPred) throws Exception;
+    public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws Exception;
 
     public ICachedPage getPage();
 
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorDescriptor.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorDescriptor.java
index f02f10e..73b5323 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorDescriptor.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorDescriptor.java
@@ -32,10 +32,10 @@
     private static final long serialVersionUID = 1L;
 
     public TreeIndexDiskOrderScanOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc,
-            IStorageManagerInterface storageManager, IIndexRegistryProvider<ITreeIndex> btreeRegistryProvider,
+            IStorageManagerInterface storageManager, IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider,
             IFileSplitProvider fileSplitProvider, ITreeIndexFrameFactory interiorFrameFactory,
             ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] typeTraits, ITreeIndexOpHelperFactory opHelperFactory) {
-        super(spec, 0, 1, recDesc, storageManager, btreeRegistryProvider, fileSplitProvider, interiorFrameFactory,
+        super(spec, 0, 1, recDesc, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
                 leafFrameFactory, typeTraits, null, opHelperFactory);
     }
 
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorNodePushable.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorNodePushable.java
index a8a1b64..5ec6083 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorNodePushable.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorNodePushable.java
@@ -28,6 +28,8 @@
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
 import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
 
 public class TreeIndexDiskOrderScanOperatorNodePushable extends AbstractUnaryOutputSourceOperatorNodePushable {
     private final TreeIndexOpHelper treeIndexOpHelper;
@@ -44,12 +46,14 @@
         ITreeIndexCursor cursor = treeIndexOpHelper.createDiskOrderScanCursor(cursorFrame);
         ITreeIndexMetaDataFrame metaFrame = new LIFOMetaDataFrame();
 
+        IndexOpContext diskOrderScanOpCtx = treeIndexOpHelper.getTreeIndex().createOpContext(IndexOp.DISKORDERSCAN,
+                cursorFrame, null, null);
         try {
         
         	treeIndexOpHelper.init();
         	
         	try {
-        		treeIndexOpHelper.getTreeIndex().diskOrderScan(cursor, cursorFrame, metaFrame);
+        		treeIndexOpHelper.getTreeIndex().diskOrderScan(cursor, cursorFrame, metaFrame, diskOrderScanOpCtx);
 
         		int fieldCount = treeIndexOpHelper.getTreeIndex().getFieldCount();
         		ByteBuffer frame = treeIndexOpHelper.getHyracksStageletContext().allocateFrame();
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorDescriptor.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorDescriptor.java
index 2ab24e7..0961a4f 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorDescriptor.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorDescriptor.java
@@ -29,10 +29,10 @@
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
 import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
 
-// re-create in-memory state for a btree that has already been built (i.e., the file exists):
+// re-create in-memory state for a tree index that has already been built (i.e., the file exists):
 // 1. register files in file manager (FileManager)
 // 2. create file mappings (FileMappingProvider)
-// 3. register btree instance (BTreeRegistry)
+// 3. register tree index instance (IndexRegistry)
 
 public class TreeIndexFileEnlistmentOperatorDescriptor extends AbstractTreeIndexOperatorDescriptor {
 
@@ -41,7 +41,8 @@
     public TreeIndexFileEnlistmentOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc,
             IStorageManagerInterface storageManager, IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider,
             IFileSplitProvider fileSplitProvider, ITreeIndexFrameFactory interiorFrameFactory,
-            ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] typeTraits, IBinaryComparatorFactory[] comparatorFactories, ITreeIndexOpHelperFactory opHelperFactory) {
+            ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] typeTraits,
+            IBinaryComparatorFactory[] comparatorFactories, ITreeIndexOpHelperFactory opHelperFactory) {
         super(spec, 0, 0, recDesc, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
                 leafFrameFactory, typeTraits, comparatorFactories, opHelperFactory);
     }
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorNodePushable.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorNodePushable.java
index 11c8363..8ff6586 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorNodePushable.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorNodePushable.java
@@ -23,11 +23,12 @@
 
 public class TreeIndexFileEnlistmentOperatorNodePushable extends AbstractOperatorNodePushable {
 
-    private final TreeIndexOpHelper btreeOpHelper;
+    private final TreeIndexOpHelper treeIndexOpHelper;
 
-    public TreeIndexFileEnlistmentOperatorNodePushable(AbstractTreeIndexOperatorDescriptor opDesc, IHyracksStageletContext ctx,
-            int partition) {
-        btreeOpHelper = opDesc.getTreeIndexOpHelperFactory().createTreeIndexOpHelper(opDesc, ctx, partition, IndexHelperOpenMode.ENLIST);
+    public TreeIndexFileEnlistmentOperatorNodePushable(AbstractTreeIndexOperatorDescriptor opDesc,
+            IHyracksStageletContext ctx, int partition) {
+        treeIndexOpHelper = opDesc.getTreeIndexOpHelperFactory().createTreeIndexOpHelper(opDesc, ctx, partition,
+                IndexHelperOpenMode.ENLIST);
     }
 
     @Override
@@ -47,10 +48,9 @@
     @Override
     public void initialize() throws HyracksDataException {
         try {
-        	btreeOpHelper.init();
-        }
-        finally {
-        	btreeOpHelper.deinit();
+            treeIndexOpHelper.init();
+        } finally {
+            treeIndexOpHelper.deinit();
         }
     }
 
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorDescriptor.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorDescriptor.java
index a1af38c..c8141b9 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorDescriptor.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorDescriptor.java
@@ -38,11 +38,12 @@
     private IndexOp op;
 
     public TreeIndexInsertUpdateDeleteOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc,
-            IStorageManagerInterface storageManager, IIndexRegistryProvider<ITreeIndex> btreeRegistryProvider,
+            IStorageManagerInterface storageManager, IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider,
             IFileSplitProvider fileSplitProvider, ITreeIndexFrameFactory interiorFrameFactory,
             ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] typeTraits,
-            IBinaryComparatorFactory[] comparatorFactories, int[] fieldPermutation, IndexOp op, ITreeIndexOpHelperFactory opHelperFactory) {
-        super(spec, 1, 1, recDesc, storageManager, btreeRegistryProvider, fileSplitProvider, interiorFrameFactory,
+            IBinaryComparatorFactory[] comparatorFactories, int[] fieldPermutation, IndexOp op,
+            ITreeIndexOpHelperFactory opHelperFactory) {
+        super(spec, 1, 1, recDesc, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
                 leafFrameFactory, typeTraits, comparatorFactories, opHelperFactory);
         this.fieldPermutation = fieldPermutation;
         this.op = op;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorNodePushable.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorNodePushable.java
index d41848b..533a047 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorNodePushable.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorNodePushable.java
@@ -87,7 +87,7 @@
 
                     default: {
                         throw new HyracksDataException("Unsupported operation " + op
-                                + " in BTree InsertUpdateDelete operator");
+                                + " in tree index InsertUpdateDelete operator");
                     }
 
                 }
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexOpHelper.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexOpHelper.java
index a48bec4..741a5a5 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexOpHelper.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexOpHelper.java
@@ -63,7 +63,7 @@
 		case OPEN: {
 			if (!fileIsMapped) {
 				throw new HyracksDataException(
-						"Trying to open btree from unmapped file " + f.toString());
+						"Trying to open tree index from unmapped file " + f.toString());
 			}
 		}
 		break;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOp.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOp.java
index 61474f7..e40c5c8 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOp.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOp.java
@@ -16,5 +16,5 @@
 package edu.uci.ics.hyracks.storage.am.common.ophelpers;
 
 public enum IndexOp {
-    INSERT, DELETE, UPDATE, SEARCH
+    INSERT, DELETE, UPDATE, SEARCH, DISKORDERSCAN
 }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeCursor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeCursor.java
deleted file mode 100644
index b9a0907..0000000
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeCursor.java
+++ /dev/null
@@ -1,28 +0,0 @@
-package edu.uci.ics.hyracks.storage.am.rtree.api;
-
-import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
-import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.PathList;
-import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
-import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
-
-public interface IRTreeCursor {
-    public void reset();
-
-    public boolean hasNext() throws Exception;
-
-    public void next() throws Exception;
-
-    public void open(PathList pathList, ITupleReference searchKey, int rootPage, MultiComparator interiorCmp,
-            MultiComparator leafCmp) throws Exception;
-
-    public ICachedPage getPage();
-
-    public void close() throws Exception;
-
-    public void setBufferCache(IBufferCache bufferCache);
-
-    public void setFileId(int fileId);
-
-    public ITupleReference getTuple();
-}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeOpHelper.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeOpHelper.java
new file mode 100644
index 0000000..61091cc
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeOpHelper.java
@@ -0,0 +1,133 @@
+package edu.uci.ics.hyracks.storage.am.rtree.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.ITreeIndexOperatorDescriptorHelper;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.IndexHelperOpenMode;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.IndexRegistry;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.TreeIndexOpHelper;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.InteriorFrameSchema;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public class RTreeOpHelper extends TreeIndexOpHelper {
+
+    protected MultiComparator interiorCmp;
+
+    public RTreeOpHelper(ITreeIndexOperatorDescriptorHelper opDesc, IHyracksStageletContext ctx, int partition,
+            IndexHelperOpenMode mode) {
+        super(opDesc, ctx, partition, mode);
+    }
+
+    public void init() throws HyracksDataException {
+        IBufferCache bufferCache = opDesc.getStorageManager().getBufferCache(ctx);
+        IFileMapProvider fileMapProvider = opDesc.getStorageManager().getFileMapProvider(ctx);
+        IFileSplitProvider fileSplitProvider = opDesc.getTreeIndexFileSplitProvider();
+
+        FileReference f = fileSplitProvider.getFileSplits()[partition].getLocalFile();
+        boolean fileIsMapped = fileMapProvider.isMapped(f);
+
+        switch (mode) {
+
+            case OPEN: {
+                if (!fileIsMapped) {
+                    throw new HyracksDataException("Trying to open rtree from unmapped file " + f.toString());
+                }
+            }
+                break;
+
+            case CREATE:
+            case ENLIST: {
+                if (!fileIsMapped) {
+                    bufferCache.createFile(f);
+                }
+            }
+                break;
+
+        }
+
+        int fileId = fileMapProvider.lookupFileId(f);
+        try {
+            bufferCache.openFile(fileId);
+        } catch (HyracksDataException e) {
+            // revert state of buffer cache since file failed to open
+            if (!fileIsMapped) {
+                bufferCache.deleteFile(fileId);
+            }
+            throw e;
+        }
+
+        // only set indexFileId member when openFile() succeeds,
+        // otherwise deinit() will try to close the file that failed to open
+        indexFileId = fileId;
+
+        interiorFrame = opDesc.getTreeIndexInteriorFactory().createFrame();
+        leafFrame = opDesc.getTreeIndexLeafFactory().createFrame();
+
+        IndexRegistry<ITreeIndex> treeIndexRegistry = opDesc.getTreeIndexRegistryProvider().getRegistry(ctx);
+        treeIndex = treeIndexRegistry.get(indexFileId);
+        if (treeIndex == null) {
+
+            // create new tree and register it
+            treeIndexRegistry.lock();
+            try {
+                // check if tree has already been registered by another thread
+                treeIndex = treeIndexRegistry.get(indexFileId);
+                if (treeIndex == null) {
+                    // this thread should create and register the tree
+
+                    IBinaryComparator[] comparators = new IBinaryComparator[opDesc.getTreeIndexComparatorFactories().length];
+                    for (int i = 0; i < opDesc.getTreeIndexComparatorFactories().length; i++) {
+                        comparators[i] = opDesc.getTreeIndexComparatorFactories()[i].createBinaryComparator();
+                    }
+
+                    cmp = new MultiComparator(opDesc.getTreeIndexTypeTraits(), comparators);
+                    InteriorFrameSchema interiorFrameSchema = new InteriorFrameSchema(cmp);
+                    interiorCmp = interiorFrameSchema.getInteriorCmp();
+
+                    treeIndex = createTreeIndex();
+                    if (mode == IndexHelperOpenMode.CREATE) {
+                        ITreeIndexMetaDataFrame metaFrame = treeIndex.getFreePageManager().getMetaDataFrameFactory()
+                                .createFrame();
+                        try {
+                            treeIndex.create(indexFileId, leafFrame, metaFrame);
+                        } catch (Exception e) {
+                            throw new HyracksDataException(e);
+                        }
+                    }
+                    treeIndex.open(indexFileId);
+                    treeIndexRegistry.register(indexFileId, treeIndex);
+                }
+            } finally {
+                treeIndexRegistry.unlock();
+            }
+        }
+    }
+
+    public ITreeIndex createTreeIndex() throws HyracksDataException {
+        IBufferCache bufferCache = opDesc.getStorageManager().getBufferCache(ctx);
+        ITreeIndexMetaDataFrameFactory metaDataFrameFactory = new LIFOMetaDataFrameFactory();
+        IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, indexFileId, 0,
+                metaDataFrameFactory);
+
+        return new RTree(bufferCache, freePageManager, opDesc.getTreeIndexInteriorFactory(),
+                opDesc.getTreeIndexLeafFactory(), interiorCmp, cmp);
+    }
+    
+    public ITreeIndexCursor createDiskOrderScanCursor(ITreeIndexFrame leafFrame) throws HyracksDataException {
+        throw new HyracksDataException("createDiskOrderScanCursor Operation not implemented.");
+    }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeOpHelperFactory.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeOpHelperFactory.java
new file mode 100644
index 0000000..59030f5
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeOpHelperFactory.java
@@ -0,0 +1,27 @@
+package edu.uci.ics.hyracks.storage.am.rtree.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.ITreeIndexOpHelperFactory;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.ITreeIndexOperatorDescriptorHelper;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.IndexHelperOpenMode;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.TreeIndexOpHelper;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeDiskOrderScanCursor;
+
+public class RTreeOpHelperFactory implements ITreeIndexOpHelperFactory {
+    
+    private static final long serialVersionUID = 1L;
+
+    @Override
+    public TreeIndexOpHelper createTreeIndexOpHelper(ITreeIndexOperatorDescriptorHelper opDesc,
+            IHyracksStageletContext ctx, int partition, IndexHelperOpenMode mode) {        
+        return new RTreeOpHelper(opDesc, ctx, partition, mode);
+    }
+    
+    public ITreeIndexCursor createDiskOrderScanCursor(ITreeIndexFrame leafFrame) throws HyracksDataException {
+        return new RTreeDiskOrderScanCursor((IRTreeFrame)leafFrame);
+    }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorDescriptor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorDescriptor.java
new file mode 100644
index 0000000..1da8730
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorDescriptor.java
@@ -0,0 +1,40 @@
+package edu.uci.ics.hyracks.storage.am.rtree.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.IOperatorNodePushable;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.job.IOperatorEnvironment;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.AbstractTreeIndexOperatorDescriptor;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.IIndexRegistryProvider;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.ITreeIndexOpHelperFactory;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public class RTreeSearchOperatorDescriptor extends AbstractTreeIndexOperatorDescriptor {
+
+    private static final long serialVersionUID = 1L;
+
+    private int[] keyFields; // fields in input tuple to be used as keys
+
+    public RTreeSearchOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc,
+            IStorageManagerInterface storageManager, IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider,
+            IFileSplitProvider fileSplitProvider, ITreeIndexFrameFactory interiorFrameFactory,
+            ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] leafTypeTraits,
+            IBinaryComparatorFactory[] comparatorFactories, int[] keyFields, ITreeIndexOpHelperFactory opHelperFactory) {
+        super(spec, 1, 1, recDesc, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
+                leafFrameFactory, leafTypeTraits, comparatorFactories, opHelperFactory);
+        this.keyFields = keyFields;
+    }
+
+    @Override
+    public IOperatorNodePushable createPushRuntime(final IHyracksStageletContext ctx, final IOperatorEnvironment env,
+            IRecordDescriptorProvider recordDescProvider, int partition, int nPartitions) {
+        return new RTreeSearchOperatorNodePushable(this, ctx, partition, recordDescProvider, keyFields);
+    }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java
new file mode 100644
index 0000000..c1b6df3
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java
@@ -0,0 +1,168 @@
+package edu.uci.ics.hyracks.storage.am.rtree.dataflow;
+
+import java.io.DataOutput;
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+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.FrameTupleAccessor;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
+import edu.uci.ics.hyracks.dataflow.common.comm.util.FrameUtils;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.std.base.AbstractUnaryInputUnaryOutputOperatorNodePushable;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.AbstractTreeIndexOperatorDescriptor;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.IndexHelperOpenMode;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.PermutingFrameTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.TreeIndexOpHelper;
+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.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
+
+public class RTreeSearchOperatorNodePushable extends AbstractUnaryInputUnaryOutputOperatorNodePushable {
+    private TreeIndexOpHelper treeIndexOpHelper;
+    private FrameTupleAccessor accessor;
+
+    private ByteBuffer writeBuffer;
+    private FrameTupleAppender appender;
+    private ArrayTupleBuilder tb;
+    private DataOutput dos;
+
+    private RTree rtree;
+    private PermutingFrameTupleReference searchKey;
+    private SearchPredicate searchPred;
+    private MultiComparator interiorCmp;
+    private MultiComparator leafCmp;
+    private ITreeIndexCursor cursor;
+    private ITreeIndexFrame interiorFrame;
+    private ITreeIndexFrame leafFrame;
+    private RTreeOpContext opCtx;
+
+    private RecordDescriptor recDesc;
+
+    public RTreeSearchOperatorNodePushable(AbstractTreeIndexOperatorDescriptor opDesc, IHyracksStageletContext ctx,
+            int partition, IRecordDescriptorProvider recordDescProvider, int[] keyFields) {
+        treeIndexOpHelper = opDesc.getTreeIndexOpHelperFactory().createTreeIndexOpHelper(opDesc, ctx, partition,
+                IndexHelperOpenMode.OPEN);
+
+        this.recDesc = recordDescProvider.getInputRecordDescriptor(opDesc.getOperatorId(), 0);
+        if (keyFields != null && keyFields.length > 0) {
+            searchKey = new PermutingFrameTupleReference();
+            searchKey.setFieldPermutation(keyFields);
+        }
+    }
+
+    @Override
+    public void open() throws HyracksDataException {
+        AbstractTreeIndexOperatorDescriptor opDesc = (AbstractTreeIndexOperatorDescriptor) treeIndexOpHelper
+                .getOperatorDescriptor();
+        accessor = new FrameTupleAccessor(treeIndexOpHelper.getHyracksStageletContext().getFrameSize(), recDesc);
+
+        interiorFrame = opDesc.getTreeIndexInteriorFactory().createFrame();
+        leafFrame = opDesc.getTreeIndexLeafFactory().createFrame();
+        cursor = new RTreeSearchCursor((IRTreeFrame) interiorFrame, (IRTreeFrame) leafFrame);
+
+        try {
+
+            treeIndexOpHelper.init();
+            rtree = (RTree) treeIndexOpHelper.getTreeIndex();
+
+            int keySearchFields = rtree.getLeafCmp().getComparators().length;
+
+            IBinaryComparator[] keySearchComparators = new IBinaryComparator[keySearchFields];
+            for (int i = 0; i < keySearchFields; i++) {
+                keySearchComparators[i] = rtree.getLeafCmp().getComparators()[i];
+            }
+            interiorCmp = new MultiComparator(rtree.getInteriorCmp().getTypeTraits(), keySearchComparators);
+            leafCmp = new MultiComparator(rtree.getLeafCmp().getTypeTraits(), keySearchComparators);
+
+            searchPred = new SearchPredicate(searchKey, interiorCmp, leafCmp);
+            accessor = new FrameTupleAccessor(treeIndexOpHelper.getHyracksStageletContext().getFrameSize(), recDesc);
+
+            writeBuffer = treeIndexOpHelper.getHyracksStageletContext().allocateFrame();
+            tb = new ArrayTupleBuilder(rtree.getLeafCmp().getFieldCount());
+            dos = tb.getDataOutput();
+            appender = new FrameTupleAppender(treeIndexOpHelper.getHyracksStageletContext().getFrameSize());
+            appender.reset(writeBuffer, true);
+
+            opCtx = rtree.createOpContext(IndexOp.SEARCH, treeIndexOpHelper.getLeafFrame(),
+                    treeIndexOpHelper.getInteriorFrame(), null);
+
+        } catch (Exception e) {
+            treeIndexOpHelper.deinit();
+        }
+    }
+
+    private void writeSearchResults() throws Exception {
+        while (cursor.hasNext()) {
+            tb.reset();
+            cursor.next();
+
+            ITupleReference frameTuple = cursor.getTuple();
+            for (int i = 0; i < frameTuple.getFieldCount(); i++) {
+                dos.write(frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
+                tb.addFieldEndOffset();
+            }
+
+            if (!appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize())) {
+                FrameUtils.flushFrame(writeBuffer, writer);
+                appender.reset(writeBuffer, true);
+                if (!appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize())) {
+                    throw new IllegalStateException();
+                }
+            }
+        }
+    }
+
+    @Override
+    public void nextFrame(ByteBuffer buffer) throws HyracksDataException {
+        accessor.reset(buffer);
+
+        int tupleCount = accessor.getTupleCount();
+        try {
+            for (int i = 0; i < tupleCount; i++) {
+                searchKey.reset(accessor, i);
+
+                searchPred.setSearchKey(searchKey);
+                cursor.reset();
+                rtree.search(cursor, searchPred, opCtx);
+                writeSearchResults();
+            }
+        } catch (Exception e) {
+            throw new HyracksDataException(e);
+        }
+    }
+
+    @Override
+    public void close() throws HyracksDataException {
+        try {
+            if (appender.getTupleCount() > 0) {
+                FrameUtils.flushFrame(writeBuffer, writer);
+            }
+            writer.close();
+            try {
+                cursor.close();
+            } catch (Exception e) {
+                throw new HyracksDataException(e);
+            }
+        } finally {
+            treeIndexOpHelper.deinit();
+        }
+    }
+
+    @Override
+    public void flush() throws HyracksDataException {
+        if (appender.getTupleCount() > 0) {
+            FrameUtils.flushFrame(writeBuffer, writer);
+        }
+    }
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/CursorInitialState.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/CursorInitialState.java
new file mode 100644
index 0000000..9d77288
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/CursorInitialState.java
@@ -0,0 +1,36 @@
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public class CursorInitialState implements ICursorInitialState {
+
+    private PathList pathList;
+    private int rootPage;
+    private ICachedPage page; // for disk order scan
+
+    public CursorInitialState(PathList pathList, int rootPage) {
+        this.pathList = pathList;
+        this.rootPage = rootPage;
+    }
+
+    public PathList getPathList() {
+        return pathList;
+    }
+
+    public int getRootPage() {
+        return rootPage;
+    }
+
+    public void setRootPage(int rootPage) {
+        this.rootPage = rootPage;
+    }
+
+    public ICachedPage getPage() {
+        return page;
+    }
+
+    public void setPage(ICachedPage page) {
+        this.page = page;
+    }
+}
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 c471e37..f7cbef9 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
@@ -22,7 +22,6 @@
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeCursor;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
 import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMFrame;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
@@ -42,6 +41,7 @@
     private final IBufferCache bufferCache;
     private int fileId;
 
+    private final SearchPredicate diskOrderScanPredicate;
     private final ITreeIndexFrameFactory interiorFrameFactory;
     private final ITreeIndexFrameFactory leafFrameFactory;
     private final MultiComparator interiorCmp;
@@ -57,8 +57,9 @@
     public AtomicLong unpins = new AtomicLong();
     public byte currentLevel = 0;
 
-    public RTree(IBufferCache bufferCache, IFreePageManager freePageManager, ITreeIndexFrameFactory interiorFrameFactory,
-            ITreeIndexFrameFactory leafFrameFactory, MultiComparator interiorCmp, MultiComparator leafCmp) {
+    public RTree(IBufferCache bufferCache, IFreePageManager freePageManager,
+            ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory,
+            MultiComparator interiorCmp, MultiComparator leafCmp) {
         this.bufferCache = bufferCache;
         this.freePageManager = freePageManager;
         this.interiorFrameFactory = interiorFrameFactory;
@@ -67,6 +68,7 @@
         this.leafCmp = leafCmp;
         globalNsn = new AtomicInteger();
         this.treeLatch = new ReentrantReadWriteLock(true);
+        this.diskOrderScanPredicate = new SearchPredicate(null, interiorCmp, leafCmp);
     }
 
     public void incrementGlobalNsn() {
@@ -221,11 +223,11 @@
     public void close() {
         fileId = -1;
     }
-    
+
     @Override
     public RTreeOpContext createOpContext(IndexOp op, ITreeIndexFrame leafFrame, ITreeIndexFrame interiorFrame,
             ITreeIndexMetaDataFrame metaFrame) {
-        return new RTreeOpContext(op, (IRTreeFrame)leafFrame, (IRTreeFrame)interiorFrame, metaFrame, 8);
+        return new RTreeOpContext(op, (IRTreeFrame) leafFrame, (IRTreeFrame) interiorFrame, metaFrame, 8);
     }
 
     @Override
@@ -436,7 +438,7 @@
                     numOfPages++; // debug
                     if (!isLeaf) {
                         splitsByLevel[ctx.interiorFrame.getLevel()]++; // debug
-                        rightFrame = (IRTreeFrame)interiorFrameFactory.createFrame();
+                        rightFrame = (IRTreeFrame) interiorFrameFactory.createFrame();
                         rightFrame.setPage(rightNode);
                         rightFrame.initBuffer((byte) ctx.interiorFrame.getLevel());
                         rightFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
@@ -450,7 +452,7 @@
                         ctx.interiorFrame.setPageLsn(newNsn);
                     } else {
                         splitsByLevel[0]++; // debug
-                        rightFrame = (IRTreeFrame)leafFrameFactory.createFrame();
+                        rightFrame = (IRTreeFrame) leafFrameFactory.createFrame();
                         rightFrame.setPage(rightNode);
                         rightFrame.initBuffer((byte) 0);
                         rightFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
@@ -827,14 +829,14 @@
         }
     }
 
-    public void search(IRTreeCursor cursor, ITupleReference searchKey, RTreeOpContext ctx) throws Exception {
+    public void search(ITreeIndexCursor cursor, SearchPredicate pred, RTreeOpContext ctx) throws Exception {
         ctx.reset();
-        ctx.tuple = searchKey;
         ctx.cursor = cursor;
 
         cursor.setBufferCache(bufferCache);
         cursor.setFileId(fileId);
-        ctx.cursor.open(ctx.pathList, ctx.tuple, rootPage, interiorCmp, leafCmp);
+        ctx.cursorInitialState.setRootPage(rootPage);
+        ctx.cursor.open(ctx.cursorInitialState, pred);
     }
 
     public void search(Stack<Integer> s, ITupleReference tuple, RTreeOpContext ctx, ArrayList<Rectangle> results)
@@ -916,10 +918,6 @@
         throw new Exception("RTree Update not implemented.");
     }
 
-    
-
-   
-
     @Override
     public IIndexBulkLoadContext beginBulkLoad(float fillFactor, ITreeIndexFrame leafFrame,
             ITreeIndexFrame interiorFrame, ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
@@ -937,16 +935,32 @@
     }
 
     @Override
-    public void diskOrderScan(ITreeIndexCursor icursor, ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame)
+    public void diskOrderScan(ITreeIndexCursor icursor,
+            ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame, IndexOpContext ictx)
             throws HyracksDataException {
-        throw new HyracksDataException("RTree disk order not implemented.");
+        RTreeDiskOrderScanCursor cursor = (RTreeDiskOrderScanCursor)icursor;
+        RTreeOpContext ctx = (RTreeOpContext) ictx;
+        ctx.reset();
         
+        int currentPageId = rootPage + 1;
+        int maxPageId = freePageManager.getMaxPage(metaFrame);
+
+        ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(
+                fileId, currentPageId), false);
+        page.acquireReadLatch();
+        cursor.setBufferCache(bufferCache);
+        cursor.setFileId(fileId);
+        cursor.setCurrentPageId(currentPageId);
+        cursor.setMaxPageId(maxPageId);
+        ctx.cursorInitialState.setPage(page);
+        cursor.open(ctx.cursorInitialState, diskOrderScanPredicate);
     }
 
+
     @Override
     public int getRootPageId() {
         return rootPage;
-    } 
+    }
 
     @Override
     public int getFieldCount() {
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeDiskOrderScanCursor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeDiskOrderScanCursor.java
new file mode 100644
index 0000000..de66e77
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeDiskOrderScanCursor.java
@@ -0,0 +1,155 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+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.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+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;
+
+public class RTreeDiskOrderScanCursor implements ITreeIndexCursor {
+
+    // TODO: might want to return tuples in physical order, not logical order to
+    // speed up access
+
+    private int tupleIndex = 0;
+    private int fileId = -1;
+    int currentPageId = -1;
+    int maxPageId = -1; // TODO: figure out how to scan to the end of file, this
+    // is dirty and may not with concurrent updates
+    private ICachedPage page = null;
+    private IRTreeFrame frame = null;
+    private IBufferCache bufferCache = null;
+
+    private ITreeIndexTupleReference frameTuple;
+
+    public RTreeDiskOrderScanCursor(IRTreeFrame frame) {
+        this.frame = frame;
+        this.frameTuple = frame.getTupleWriter().createTupleReference();
+    }
+
+    @Override
+    public void close() throws Exception {
+        page.releaseReadLatch();
+        bufferCache.unpin(page);
+        page = null;
+    }
+
+    @Override
+    public ITreeIndexTupleReference getTuple() {
+        return frameTuple;
+    }
+
+    @Override
+    public ICachedPage getPage() {
+        return page;
+    }
+
+    private boolean positionToNextLeaf(boolean skipCurrent) throws HyracksDataException {
+        while ((frame.getLevel() != 0 || skipCurrent) && (currentPageId <= maxPageId) || (frame.getTupleCount() == 0)) {
+            currentPageId++;
+
+            ICachedPage nextPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, currentPageId), false);
+            nextPage.acquireReadLatch();
+
+            page.releaseReadLatch();
+            bufferCache.unpin(page);
+
+            page = nextPage;
+            frame.setPage(page);
+            tupleIndex = 0;
+            skipCurrent = false;
+        }
+        if (currentPageId <= maxPageId)
+            return true;
+        else
+            return false;
+    }
+
+    @Override
+    public boolean hasNext() throws Exception {
+        if (tupleIndex >= frame.getTupleCount()) {
+            boolean nextLeafExists = positionToNextLeaf(true);
+            if (nextLeafExists) {
+                frameTuple.resetByTupleIndex(frame, tupleIndex);
+                return true;
+            } else {
+                return false;
+            }
+        }
+
+        frameTuple.resetByTupleIndex(frame, tupleIndex);
+        return true;
+    }
+
+    @Override
+    public void next() throws Exception {
+        tupleIndex++;
+    }
+
+    @Override
+    public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
+        // in case open is called multiple times without closing
+        if (page != null) {
+            page.releaseReadLatch();
+            bufferCache.unpin(page);
+        }
+
+        page = ((CursorInitialState) initialState).getPage();
+        tupleIndex = 0;
+        frame.setPage(page);
+        SearchPredicate pred = (SearchPredicate) searchPred;
+        MultiComparator leafCmp = pred.getLeafCmp();
+        frameTuple.setFieldCount(leafCmp.getFieldCount());
+        boolean leafExists = positionToNextLeaf(false);
+        if (!leafExists) {
+            throw new HyracksDataException(
+                    "Failed to open disk-order scan cursor for R-tree. Traget R-tree has no leaves.");
+        }
+    }
+
+    @Override
+    public void reset() {
+        tupleIndex = 0;
+        currentPageId = -1;
+        maxPageId = -1;
+        page = null;
+    }
+
+    @Override
+    public void setBufferCache(IBufferCache bufferCache) {
+        this.bufferCache = bufferCache;
+    }
+
+    @Override
+    public void setFileId(int fileId) {
+        this.fileId = fileId;
+    }
+
+    public void setCurrentPageId(int currentPageId) {
+        this.currentPageId = currentPageId;
+    }
+
+    public void setMaxPageId(int maxPageId) {
+        this.maxPageId = maxPageId;
+    }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
index 6922141..f377bba 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
@@ -1,17 +1,18 @@
 package edu.uci.ics.hyracks.storage.am.rtree.impls;
 
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
-import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeCursor;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
 
 public final class RTreeOpContext implements IndexOpContext {
     public final IndexOp op;
     public final IRTreeFrame interiorFrame;
     public final IRTreeFrame leafFrame;
-    public IRTreeCursor cursor;
+    public ITreeIndexCursor cursor;
+    public CursorInitialState cursorInitialState;
     public final ITreeIndexMetaDataFrame metaFrame;
     public final RTreeSplitKey splitKey;
     public ITupleReference tuple;
@@ -25,11 +26,16 @@
         this.interiorFrame = interiorFrame;
         this.leafFrame = leafFrame;
         this.metaFrame = metaFrame;
-        splitKey = new RTreeSplitKey(interiorFrame.getTupleWriter().createTupleReference(), interiorFrame
-                .getTupleWriter().createTupleReference());
-
         pathList = new PathList(treeHeightHint, treeHeightHint);
-        traverseList = new TraverseList(100, 100);
+        if (op != IndexOp.SEARCH && op != IndexOp.DISKORDERSCAN) {
+            splitKey = new RTreeSplitKey(interiorFrame.getTupleWriter().createTupleReference(), interiorFrame
+                    .getTupleWriter().createTupleReference());
+            traverseList = new TraverseList(100, 100);
+        } else {
+            splitKey = null;
+            traverseList = null;
+            cursorInitialState = new CursorInitialState(pathList, 1);
+        }
     }
 
     public ITupleReference getTuple() {
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchCursor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
similarity index 83%
rename from hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchCursor.java
rename to hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
index f8ad9ca..478acb2 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchCursor.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
@@ -2,15 +2,17 @@
 
 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.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.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeCursor;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
 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;
 
-public class SearchCursor implements IRTreeCursor {
+public class RTreeSearchCursor implements ITreeIndexCursor {
 
     private int fileId = -1;
     private ICachedPage page = null;
@@ -18,6 +20,7 @@
     private IRTreeFrame leafFrame = null;
     private IBufferCache bufferCache = null;
 
+    private SearchPredicate pred;
     private PathList pathList;
     private int rootPage;
     ITupleReference searchKey;
@@ -32,8 +35,8 @@
 
     private int pin = 0;
     private int unpin = 0;
-    
-    public SearchCursor(IRTreeFrame interiorFrame, IRTreeFrame leafFrame) {
+
+    public RTreeSearchCursor(IRTreeFrame interiorFrame, IRTreeFrame leafFrame) {
         this.interiorFrame = interiorFrame;
         this.leafFrame = leafFrame;
         this.frameTuple = leafFrame.createTupleReference();
@@ -131,23 +134,24 @@
     }
 
     @Override
-    public void open(PathList pathList, ITupleReference searchKey, int rootPage, MultiComparator interiorCmp,
-            MultiComparator leafCmp) throws Exception {
+    public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws Exception {
         // in case open is called multiple times without closing
         if (this.page != null) {
             this.page.releaseReadLatch();
             bufferCache.unpin(this.page);
-            this.pathList.clear();
+            pathList.clear();
         }
 
-        this.pathList = pathList;
-        this.searchKey = searchKey;
-        this.rootPage = rootPage;
-        this.interiorCmp = interiorCmp;
-        this.leafCmp = leafCmp;
+        pathList = ((CursorInitialState) initialState).getPathList();
+        rootPage = ((CursorInitialState) initialState).getRootPage();
 
-        this.pathList.add(this.rootPage, -1, -1);
-        frameTuple.setFieldCount(this.leafCmp.getFieldCount());
+        pred = (SearchPredicate) searchPred;
+        interiorCmp = pred.getInteriorCmp();
+        leafCmp = pred.getLeafCmp();
+        searchKey = pred.getSearchKey();
+
+        pathList.add(this.rootPage, -1, -1);
+        frameTuple.setFieldCount(leafCmp.getFieldCount());
         tupleIndex = 0;
         fetchNextLeafPage();
     }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchPredicate.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchPredicate.java
new file mode 100644
index 0000000..c83f0e2
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchPredicate.java
@@ -0,0 +1,36 @@
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+
+public class SearchPredicate implements ISearchPredicate {
+
+    private static final long serialVersionUID = 1L;
+
+    protected ITupleReference searchKey;
+    protected MultiComparator interiorCmp;
+    protected MultiComparator leafCmp;
+
+    public SearchPredicate(ITupleReference searchKey, MultiComparator interiorCmp, MultiComparator leafCmp) {
+        this.searchKey = searchKey;
+        this.interiorCmp = interiorCmp;
+        this.leafCmp = leafCmp;
+    }
+
+    public ITupleReference getSearchKey() {
+        return searchKey;
+    }
+
+    public void setSearchKey(ITupleReference searchKey) {
+        this.searchKey = searchKey;
+    }
+
+    public MultiComparator getInteriorCmp() {
+        return interiorCmp;
+    }
+
+    public MultiComparator getLeafCmp() {
+        return leafCmp;
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
index e8c8065..ace0bb8 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
@@ -227,7 +227,9 @@
 		// disk-order scan
 		print("DISK-ORDER SCAN:\n");
 		BTreeDiskOrderScanCursor diskOrderCursor = new BTreeDiskOrderScanCursor(leafFrame);
-		btree.diskOrderScan(diskOrderCursor, leafFrame, metaFrame);
+		BTreeOpContext diskOrderScanOpCtx = btree.createOpContext(IndexOp.DISKORDERSCAN,
+		        leafFrame, null, null);
+		btree.diskOrderScan(diskOrderCursor, leafFrame, metaFrame, diskOrderScanOpCtx);
 		try {
 			while (diskOrderCursor.hasNext()) {
 				diskOrderCursor.next();
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
index e710eda..e90cc0d 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
@@ -23,9 +23,11 @@
 import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
 import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.FrameTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.dataflow.common.data.comparators.DoubleBinaryComparatorFactory;
 import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
 import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
@@ -39,6 +41,7 @@
 import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMFrameFactory;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.InteriorFrameSchema;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeDiskOrderScanCursor;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.Rectangle;
 import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriterFactory;
@@ -192,6 +195,26 @@
         String stats = rtree.printStats();
         print(stats);
 
+        
+        // disk-order scan
+        print("DISK-ORDER SCAN:\n");
+        RTreeDiskOrderScanCursor diskOrderCursor = new RTreeDiskOrderScanCursor(leafFrame);
+        RTreeOpContext diskOrderScanOpCtx = rtree.createOpContext(IndexOp.DISKORDERSCAN,
+                leafFrame, null, null);
+        rtree.diskOrderScan(diskOrderCursor, leafFrame, metaFrame, diskOrderScanOpCtx);
+        try {
+            while (diskOrderCursor.hasNext()) {
+                diskOrderCursor.next();
+                ITupleReference frameTuple = diskOrderCursor.getTuple();
+                String rec = leafCmp.printTuple(frameTuple, recDescSers);
+                print(rec + "\n");
+            }
+        } catch (Exception e) {
+            e.printStackTrace();
+        } finally {
+            diskOrderCursor.close();
+        }
+        
         // TreeIndexStatsGatherer statsGatherer = new
         // TreeIndexStatsGatherer(bufferCache, freePageManager, fileId, rtree.getRootPageId());
         // TreeIndexStats stats = statsGatherer.gatherStats(leafFrame,
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
index 1ce979c..f750edc 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
@@ -28,6 +28,7 @@
 import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
 import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
 import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+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.ITreeIndexMetaDataFrameFactory;
@@ -36,13 +37,13 @@
 import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
 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.rtree.api.IRTreeCursor;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
 import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMFrameFactory;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.InteriorFrameSchema;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchCursor;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
 import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriterFactory;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
@@ -161,9 +162,12 @@
 
         }
 
-        IRTreeCursor searchCursor = new SearchCursor(interiorFrame, leafFrame);
+        ITreeIndexCursor searchCursor = new RTreeSearchCursor(interiorFrame, leafFrame);
+        SearchPredicate searchPredicate = new SearchPredicate(tuple, interiorFrameSchema.getInteriorCmp(), leafCmp);
+        
+
         RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame);
-        rtree.search(searchCursor, tuple, searchOpCtx);
+        rtree.search(searchCursor, searchPredicate, searchOpCtx);
 
         ArrayList<Integer> results = new ArrayList<Integer>();
         try {