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
new file mode 100644
index 0000000..b9a0907
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeCursor.java
@@ -0,0 +1,28 @@
+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/api/IRTreeFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
index b07c284..75a74ca 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
@@ -11,6 +11,8 @@
 
 public interface IRTreeFrame extends ITreeIndexFrame {
     
+    public ITreeIndexTupleReference createTupleReference();
+    
     public boolean recomputeMBR(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
 
     public void computeMBR(ISplitKey splitKey, MultiComparator cmp);
@@ -44,7 +46,9 @@
     public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey,
             TupleEntryArrayList entries1, TupleEntryArrayList entries2, Rectangle[] rec) throws Exception;
 
-    public Rectangle intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
+    public boolean intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
+    
+    public Rectangle checkIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
 
     public int getChildPageIdIfIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
 
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
index 1cd795d..e4bdf93 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
@@ -32,11 +32,10 @@
     private static final double splitFactor = 0.4;
     private static final int nearMinimumOverlapFactor = 32;
 
-    public NSMRTreeFrame(ITreeIndexTupleWriter tupleWriter) {
+    public NSMRTreeFrame(ITreeIndexTupleWriter tupleWriter, int keyFieldCount) {
         super(tupleWriter, new UnorderedSlotManager());
-        // TODO: change this to number of dim * 2 (at least it must be 4)
-        this.tuples = new ITreeIndexTupleReference[4];
-        for (int i = 0; i < 4; i++) {
+        this.tuples = new ITreeIndexTupleReference[keyFieldCount];
+        for (int i = 0; i < keyFieldCount; i++) {
             this.tuples[i] = tupleWriter.createTupleReference();
         }
         cmpFrameTuple = tupleWriter.createTupleReference();
@@ -105,77 +104,6 @@
     public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey,
             TupleEntryArrayList entries1, TupleEntryArrayList entries2, Rectangle[] rec) throws Exception {
 
-        // RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
-        // RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame =
-        // ((RTreeTypeAwareTupleWriter) tupleWriter);
-        // RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame =
-        // ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
-        // frameTuple.setFieldCount(cmp.getFieldCount());
-        // rightFrame.setPageTupleFieldCount(cmp.getFieldCount());
-        //
-        // ByteBuffer right = rightFrame.getBuffer();
-        // int tupleCount = getTupleCount();
-        //
-        // int tuplesToLeft;
-        // int mid = tupleCount / 2;
-        // ITreeIndexFrame targetFrame = null;
-        // int tupleOff = slotManager.getTupleOff(slotManager.getSlotOff(mid));
-        // frameTuple.resetByTupleOffset(buf, tupleOff);
-        // if (cmp.compare(tuple, frameTuple) >= 0) {
-        // tuplesToLeft = mid + (tupleCount % 2);
-        // targetFrame = rightFrame;
-        // } else {
-        // tuplesToLeft = mid;
-        // targetFrame = this;
-        // }
-        // int tuplesToRight = tupleCount - tuplesToLeft;
-        //
-        // // copy entire page
-        // System.arraycopy(buf.array(), 0, right.array(), 0, buf.capacity());
-        //
-        // // on right page we need to copy rightmost slots to left
-        // int src = rightFrame.getSlotManager().getSlotEndOff();
-        // int dest = rightFrame.getSlotManager().getSlotEndOff() + tuplesToLeft
-        // * rightFrame.getSlotManager().getSlotSize();
-        // int length = rightFrame.getSlotManager().getSlotSize() *
-        // tuplesToRight;
-        // System.arraycopy(right.array(), src, right.array(), dest, length);
-        // right.putInt(tupleCountOff, tuplesToRight);
-        //
-        // // on left page only change the tupleCount indicator
-        // buf.putInt(tupleCountOff, tuplesToLeft);
-        //
-        // // compact both pages
-        // rightFrame.compact(cmp);
-        // compact(cmp);
-        //
-        // // insert last key
-        // targetFrame.insert(tuple, cmp);
-        //
-        // // set split key to be highest value in left page
-        // // TODO: find a better way to find the key size
-        // tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
-        // frameTuple.resetByTupleOffset(buf, tupleOff);
-        //
-        // int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0,
-        // cmp.getKeyFieldCount());
-        // splitKey.initData(splitKeySize);
-        // this.adjustMBR(tuples, cmp);
-        // rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0,
-        // rTreeSplitKey.getLeftPageBuffer(), 0);
-        // rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(),
-        // 0);
-        //
-        // ((IRTreeFrame) rightFrame).adjustMBR(((NSMRTreeFrame)
-        // rightFrame).getTuples(), cmp);
-        // rTreeTupleWriterRightFrame.writeTupleFields(((NSMRTreeFrame)
-        // rightFrame).getTuples(), 0,
-        // rTreeSplitKey.getRightPageBuffer(), 0);
-        // rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(),
-        // 0);
-        //
-        // return 0;
-
         RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
         RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
         RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame = ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
@@ -361,6 +289,11 @@
     }
 
     @Override
+    public ITreeIndexTupleReference createTupleReference() {
+        return tupleWriter.createTupleReference();
+    }
+    
+    @Override
     public int getBestChildPageId(MultiComparator cmp) {
         return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
     }
@@ -731,7 +664,30 @@
     }
 
     @Override
-    public Rectangle intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
+    public boolean intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
+        frameTuple.setFieldCount(cmp.getFieldCount());
+        frameTuple.resetByTupleIndex(this, tupleIndex);
+        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        for (int i = 0; i < maxFieldPos; i++) {
+            int j = maxFieldPos + i;
+            int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
+                    tuple.getFieldLength(i), frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+                    frameTuple.getFieldLength(j));
+            if (c > 0) {
+                return false;
+            }
+            c = cmp.getComparators()[i].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
+                    frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
+
+            if (c < 0) {
+                return false;
+            }
+        }
+        return true;
+    }
+    
+    @Override
+    public Rectangle checkIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
         frameTuple.setFieldCount(cmp.getFieldCount());
         frameTuple.resetByTupleIndex(this, tupleIndex);
         int maxFieldPos = cmp.getKeyFieldCount() / 2;
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrameFactory.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrameFactory.java
index 729bf36..56875b7 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrameFactory.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrameFactory.java
@@ -23,13 +23,15 @@
 
     private static final long serialVersionUID = 1L;
     private ITreeIndexTupleWriterFactory tupleWriterFactory;
+    private int keyFieldCount;
 
-    public NSMRTreeFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory) {
+    public NSMRTreeFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory, int keyFieldCount) {
         this.tupleWriterFactory = tupleWriterFactory;
+        this.keyFieldCount = keyFieldCount;
     }
 
     @Override
     public IRTreeFrame getFrame() {
-        return new NSMRTreeFrame(tupleWriterFactory.createTupleWriter());
+        return new NSMRTreeFrame(tupleWriterFactory.createTupleWriter(), keyFieldCount);
     }
 }
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 9cc6e00..0c6fb24 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
@@ -14,6 +14,7 @@
 import edu.uci.ics.hyracks.storage.am.common.frames.FrameOpSpaceStatus;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.TreeIndexOp;
+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.api.IRTreeFrameFactory;
 import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMRTreeFrame;
@@ -38,7 +39,6 @@
     private final IRTreeFrameFactory leafFrameFactory;
     private final MultiComparator interiorCmp;
     private final MultiComparator leafCmp;
-    public final int dim;
 
     public int rootSplits = 0;
     public int[] splitsByLevel = new int[500];
@@ -51,14 +51,13 @@
     public byte currentLevel = 0;
 
     public RTree(IBufferCache bufferCache, IFreePageManager freePageManager, IRTreeFrameFactory interiorFrameFactory,
-            IRTreeFrameFactory leafFrameFactory, MultiComparator interiorCmp, MultiComparator leafCmp, int dim) {
+            IRTreeFrameFactory leafFrameFactory, MultiComparator interiorCmp, MultiComparator leafCmp) {
         this.bufferCache = bufferCache;
         this.freePageManager = freePageManager;
         this.interiorFrameFactory = interiorFrameFactory;
         this.leafFrameFactory = leafFrameFactory;
         this.interiorCmp = interiorCmp;
         this.leafCmp = leafCmp;
-        this.dim = dim;
         globalNsn = new AtomicInteger();
         this.treeLatch = new ReentrantReadWriteLock(true);
     }
@@ -169,7 +168,7 @@
             incrementReadLatchesReleased();
             bufferCache.unpin(node);
             incrementUnpins();
-            e.printStackTrace();
+            throw e;
         }
     }
 
@@ -220,7 +219,8 @@
     public RTreeOpContext createOpContext(TreeIndexOp op, IRTreeFrame interiorFrame, IRTreeFrame leafFrame,
             ITreeIndexMetaDataFrame metaFrame, String threadName) {
         // TODO: figure out better tree-height hint
-        return new RTreeOpContext(op, interiorFrame, leafFrame, metaFrame, 8, dim, threadName);
+        return new RTreeOpContext(op, interiorFrame, leafFrame, metaFrame, 8, interiorCmp.getKeyFieldCount() / 2,
+                threadName);
     }
 
     public void insert(ITupleReference tuple, RTreeOpContext ctx) throws Exception {
@@ -821,6 +821,16 @@
         }
     }
 
+    public void search(IRTreeCursor cursor, ITupleReference searchKey, 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);
+    }
+
     public void search(Stack<Integer> s, ITupleReference tuple, RTreeOpContext ctx, ArrayList<Rectangle> results)
             throws Exception {
         ctx.reset();
@@ -857,7 +867,7 @@
                         // check intersection, if intersect, add the tuple to
                         // the
                         // result set
-                        Rectangle rec = ctx.leafFrame.intersect(ctx.tuple, i, leafCmp);
+                        Rectangle rec = ctx.leafFrame.checkIntersect(ctx.tuple, i, leafCmp);
                         if (rec != null) {
                             // add the tuple to the result set
                             results.add(rec);
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 0faea4e..91a2e24 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
@@ -3,12 +3,14 @@
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.TreeIndexOp;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeCursor;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
 
 public final class RTreeOpContext {
     public final TreeIndexOp op;
     public final IRTreeFrame interiorFrame;
     public final IRTreeFrame leafFrame;
+    public IRTreeCursor cursor;
     public final ITreeIndexMetaDataFrame metaFrame;
     public final RTreeSplitKey splitKey;
     public final SpatialUtils spatialUtils;
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/SearchCursor.java
new file mode 100644
index 0000000..f8ad9ca
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchCursor.java
@@ -0,0 +1,173 @@
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+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.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 {
+
+    private int fileId = -1;
+    private ICachedPage page = null;
+    private IRTreeFrame interiorFrame = null;
+    private IRTreeFrame leafFrame = null;
+    private IBufferCache bufferCache = null;
+
+    private PathList pathList;
+    private int rootPage;
+    ITupleReference searchKey;
+
+    private int tupleIndex = 0;
+    private int tupleIndexInc = 0;
+
+    private MultiComparator leafCmp;
+    private MultiComparator interiorCmp;
+
+    private ITreeIndexTupleReference frameTuple;
+
+    private int pin = 0;
+    private int unpin = 0;
+    
+    public SearchCursor(IRTreeFrame interiorFrame, IRTreeFrame leafFrame) {
+        this.interiorFrame = interiorFrame;
+        this.leafFrame = leafFrame;
+        this.frameTuple = leafFrame.createTupleReference();
+    }
+
+    @Override
+    public void close() throws Exception {
+        if (page != null) {
+            page.releaseReadLatch();
+            bufferCache.unpin(page);
+        }
+        tupleIndex = 0;
+        tupleIndexInc = 0;
+        page = null;
+        pathList.clear();
+    }
+
+    public ITupleReference getTuple() {
+        return frameTuple;
+    }
+
+    @Override
+    public ICachedPage getPage() {
+        return page;
+    }
+
+    public boolean fetchNextLeafPage() throws HyracksDataException {
+        while (!pathList.isEmpty()) {
+            int pageId = pathList.getLastPageId();
+            int parentLsn = pathList.getLastPageLsn();
+            pathList.removeLast();
+            ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+            pin++;
+            node.acquireReadLatch();
+            interiorFrame.setPage(node);
+            boolean isLeaf = interiorFrame.isLeaf();
+            int pageLsn = interiorFrame.getPageLsn();
+
+            if (pageId != rootPage && parentLsn < interiorFrame.getPageNsn()) {
+                // Concurrent split detected, we need to visit the right page
+                int rightPage = interiorFrame.getRightPage();
+                if (rightPage != -1) {
+                    pathList.add(rightPage, parentLsn, -1);
+                }
+            }
+
+            if (!isLeaf) {
+                for (int i = 0; i < interiorFrame.getTupleCount(); i++) {
+                    int childPageId = interiorFrame.getChildPageIdIfIntersect(searchKey, i, interiorCmp);
+                    if (childPageId != -1) {
+                        pathList.add(childPageId, pageLsn, -1);
+                    }
+                }
+            } else {
+                if (page != null) {
+                    page.releaseReadLatch();
+                    bufferCache.unpin(page);
+                    unpin++;
+                }
+                page = node;
+                leafFrame.setPage(page);
+                tupleIndex = 0;
+                return true;
+            }
+            node.releaseReadLatch();
+            bufferCache.unpin(node);
+            unpin++;
+        }
+        return false;
+    }
+
+    @Override
+    public boolean hasNext() throws Exception {
+        if (tupleIndex == leafFrame.getTupleCount()) {
+            if (!fetchNextLeafPage()) {
+                return false;
+            }
+        }
+
+        do {
+            for (int i = tupleIndex; i < leafFrame.getTupleCount(); i++) {
+                if (leafFrame.intersect(searchKey, i, leafCmp)) {
+                    frameTuple.resetByTupleIndex(leafFrame, i);
+                    tupleIndexInc = i + 1;
+                    return true;
+                }
+            }
+        } while (fetchNextLeafPage());
+        return false;
+    }
+
+    @Override
+    public void next() throws Exception {
+        tupleIndex = tupleIndexInc;
+    }
+
+    @Override
+    public void open(PathList pathList, ITupleReference searchKey, int rootPage, MultiComparator interiorCmp,
+            MultiComparator leafCmp) 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();
+        }
+
+        this.pathList = pathList;
+        this.searchKey = searchKey;
+        this.rootPage = rootPage;
+        this.interiorCmp = interiorCmp;
+        this.leafCmp = leafCmp;
+
+        this.pathList.add(this.rootPage, -1, -1);
+        frameTuple.setFieldCount(this.leafCmp.getFieldCount());
+        tupleIndex = 0;
+        fetchNextLeafPage();
+    }
+
+    @Override
+    public void reset() {
+        try {
+            close();
+        } catch (Exception e) {
+            e.printStackTrace();
+        }
+    }
+
+    @Override
+    public void setBufferCache(IBufferCache bufferCache) {
+        this.bufferCache = bufferCache;
+    }
+
+    @Override
+    public void setFileId(int fileId) {
+        this.fileId = fileId;
+    }
+}
\ No newline at end of file
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml b/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
index 36d4988..2090bb2 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
@@ -2,12 +2,12 @@
   <modelVersion>4.0.0</modelVersion>
   <groupId>edu.uci.ics.hyracks</groupId>
   <artifactId>hyracks-storage-am-rtree-test</artifactId>
-  <version>0.1.4</version>
+  <version>0.1.5</version>
 
   <parent>
     <groupId>edu.uci.ics.hyracks</groupId>
     <artifactId>hyracks-tests</artifactId>
-    <version>0.1.4</version>
+    <version>0.1.5</version>
   </parent>
 
   <build>
@@ -40,14 +40,14 @@
   	<dependency>
   		<groupId>edu.uci.ics.hyracks</groupId>
   		<artifactId>hyracks-storage-am-rtree</artifactId>
-  		<version>0.1.4</version>
+  		<version>0.1.5</version>
   		<type>jar</type>
   		<scope>compile</scope>
   	</dependency>
   	<dependency>
   		<groupId>edu.uci.ics.hyracks</groupId>
   		<artifactId>hyracks-test-support</artifactId>
-  		<version>0.1.4</version>
+  		<version>0.1.5</version>
   		<type>jar</type>
   		<scope>test</scope>
   	</dependency>
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeFrameTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeFrameTest.java
deleted file mode 100644
index f93a6b6..0000000
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeFrameTest.java
+++ /dev/null
@@ -1,133 +0,0 @@
-/*
- * package edu.uci.ics.hyracks.storage.am.rtree;
- * 
- * import java.io.DataOutput; import java.io.File; import java.nio.ByteBuffer;
- * import java.util.Random;
- * 
- * import org.junit.Test;
- * 
- * import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor; 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.ISerializerDeserializer; import
- * edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait; import
- * edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor; import
- * edu.uci.ics.hyracks.api.dataflow.value.TypeTrait; import
- * edu.uci.ics.hyracks.api.io.FileReference; 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.data.accessors.FrameTupleReference;
- * 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.MultiComparator; import
- * edu.uci.ics.hyracks.storage.am.btree.impls.SpaceStatus; import
- * edu.uci.ics.hyracks.storage.am.btree.tuples.TypeAwareTupleWriter; import
- * edu.uci.ics.hyracks.storage.am.rtree.frames.NSMRTreeFrame; 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; import
- * edu.uci.ics.hyracks.storage.common.file.IFileMapProvider; import
- * edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder; import
- * edu.uci.ics.hyracks.test.support.TestUtils;
- * 
- * public class RTreeFrameTest extends AbstractRTreeTest {
- * 
- * private static final int PAGE_SIZE = 256; private static final int NUM_PAGES
- * = 10; private static final int HYRACKS_FRAME_SIZE = 128; private
- * IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
- * 
- * private String tmpDir = System.getProperty("java.io.tmpdir");
- * 
- * @Test public void frameInsertTest() throws Exception {
- * 
- * TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES); IBufferCache
- * bufferCache = TestStorageManagerComponentHolder .getBufferCache(ctx);
- * IFileMapProvider fmp = TestStorageManagerComponentHolder
- * .getFileMapProvider(ctx); FileReference file = new FileReference(new
- * File(fileName)); bufferCache.createFile(file); int fileId =
- * fmp.lookupFileId(file); bufferCache.openFile(fileId);
- * 
- * // declare fields int fieldCount = 5; ITypeTrait[] typeTraits = new
- * ITypeTrait[fieldCount]; typeTraits[0] = new TypeTrait(8); typeTraits[1] = new
- * TypeTrait(8); typeTraits[2] = new TypeTrait(8); typeTraits[3] = new
- * TypeTrait(8); typeTraits[4] = new TypeTrait(4);
- * 
- * // declare keys int keyFieldCount = 4; IBinaryComparator[] cmps = new
- * IBinaryComparator[keyFieldCount]; cmps[0] =
- * DoubleBinaryComparatorFactory.INSTANCE.createBinaryComparator(); cmps[1] =
- * cmps[0]; cmps[2] = cmps[0]; cmps[3] = cmps[0];
- * 
- * MultiComparator cmp = new MultiComparator(typeTraits, cmps);
- * 
- * TypeAwareTupleWriter tupleWriter = new TypeAwareTupleWriter(typeTraits);
- * //SimpleTupleWriter tupleWriter = new SimpleTupleWriter(); NSMRTreeFrame
- * rtreeFrame = new NSMRTreeFrame(tupleWriter);
- * 
- * ByteBuffer hyracksFrame = ctx.allocateFrame(); FrameTupleAppender appender =
- * new FrameTupleAppender(ctx.getFrameSize()); ArrayTupleBuilder tb = new
- * ArrayTupleBuilder(cmp.getFieldCount()); DataOutput dos = tb.getDataOutput();
- * 
- * ISerializerDeserializer[] recDescSers = {
- * DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
- * DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
- * DoubleSerializerDeserializer.INSTANCE }; RecordDescriptor recDesc = new
- * RecordDescriptor(recDescSers); IFrameTupleAccessor accessor = new
- * FrameTupleAccessor(ctx .getFrameSize(), recDesc); FrameTupleReference tuple =
- * new FrameTupleReference();
- * 
- * ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId,
- * 0), true); try {
- * 
- * rtreeFrame.setPage(page); rtreeFrame.initBuffer((byte)0);
- * 
- * // insert some random stuff...
- * 
- * Random rnd = new Random(50);
- * 
- * int numInserts = 10; for (int i = 0; i < numInserts; i++) { double p1x =
- * rnd.nextDouble(); double p1y = rnd.nextDouble(); double p2x =
- * rnd.nextDouble(); double p2y = rnd.nextDouble();
- * 
- * int pk = rnd.nextInt();
- * 
- * tb.reset(); DoubleSerializerDeserializer.INSTANCE.serialize(p1x, dos);
- * tb.addFieldEndOffset(); DoubleSerializerDeserializer.INSTANCE.serialize(p1y,
- * dos); tb.addFieldEndOffset();
- * DoubleSerializerDeserializer.INSTANCE.serialize(p2x, dos);
- * tb.addFieldEndOffset(); DoubleSerializerDeserializer.INSTANCE.serialize(p2y,
- * dos); tb.addFieldEndOffset();
- * IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
- * tb.addFieldEndOffset();
- * 
- * appender.reset(hyracksFrame, true); appender.append(tb.getFieldEndOffsets(),
- * tb.getByteArray(), 0, tb.getSize());
- * 
- * tuple.reset(accessor, 0);
- * 
- * SpaceStatus status = rtreeFrame.hasSpaceInsert(tuple, cmp); switch(status) {
- * case SUFFICIENT_CONTIGUOUS_SPACE: { rtreeFrame.insert(tuple, cmp); break; }
- * 
- * case SUFFICIENT_SPACE: { rtreeFrame.compact(cmp); rtreeFrame.insert(tuple,
- * cmp); break; }
- * 
- * case INSUFFICIENT_SPACE: { // split
- * System.out.println("PLEASE STOP, NO MORE SPACE"); break; } }
- * 
- * 
- * 
- * String contents = rtreeFrame.printKeys(cmp, recDescSers);
- * System.out.println(contents);
- * 
- * } } finally { bufferCache.unpin(page); }
- * 
- * bufferCache.closeFile(fileId); bufferCache.close();
- * 
- * }
- * 
- * }
- */
\ No newline at end of file
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 815ef19..b105588 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
@@ -53,7 +53,7 @@
     private static final int HYRACKS_FRAME_SIZE = 128;
     private IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
 
-     @Test
+    @Test
     public void test01() throws Exception {
 
         TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES);
@@ -97,8 +97,8 @@
                 interiorTypeTraits);
         RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
 
-        IRTreeFrameFactory interiorFrameFactory = new NSMRTreeFrameFactory(interiorTupleWriterFactory);
-        IRTreeFrameFactory leafFrameFactory = new NSMRTreeFrameFactory(leafTupleWriterFactory);
+        IRTreeFrameFactory interiorFrameFactory = new NSMRTreeFrameFactory(interiorTupleWriterFactory, keyFieldCount);
+        IRTreeFrameFactory leafFrameFactory = new NSMRTreeFrameFactory(leafTupleWriterFactory, keyFieldCount);
         ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
         ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
 
@@ -106,9 +106,8 @@
         IRTreeFrame leafFrame = leafFrameFactory.getFrame();
         IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
 
-        int dim = 2;
         RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, interiorCmp,
-                leafCmp, dim);
+                leafCmp);
         rtree.create(fileId, leafFrame, metaFrame);
         rtree.open(fileId);
 
@@ -126,7 +125,8 @@
         accessor.reset(hyracksFrame);
         FrameTupleReference tuple = new FrameTupleReference();
 
-        RTreeOpContext insertOpCtx = rtree.createOpContext(TreeIndexOp.TI_INSERT, interiorFrame, leafFrame, metaFrame, "unittest");
+        RTreeOpContext insertOpCtx = rtree.createOpContext(TreeIndexOp.TI_INSERT, interiorFrame, leafFrame, metaFrame,
+                "unittest");
 
         Random rnd = new Random();
         rnd.setSeed(50);
@@ -172,7 +172,8 @@
         // rtree.printTree(leafFrame, interiorFrame, recDescSers);
         // System.out.println();
 
-        RTreeOpContext searchOpCtx = rtree.createOpContext(TreeIndexOp.TI_SEARCH, interiorFrame, leafFrame, metaFrame, "unittest");
+        RTreeOpContext searchOpCtx = rtree.createOpContext(TreeIndexOp.TI_SEARCH, interiorFrame, leafFrame, metaFrame,
+                "unittest");
         ArrayList<Rectangle> results = new ArrayList<Rectangle>();
         rtree.search(s, tuple, searchOpCtx, results);
 
@@ -194,7 +195,7 @@
 
     }
 
-    //@Test
+    // @Test
     public void test02() throws Exception {
 
         TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES);
@@ -238,8 +239,8 @@
                 interiorTypeTraits);
         RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
 
-        IRTreeFrameFactory interiorFrameFactory = new NSMRTreeFrameFactory(interiorTupleWriterFactory);
-        IRTreeFrameFactory leafFrameFactory = new NSMRTreeFrameFactory(leafTupleWriterFactory);
+        IRTreeFrameFactory interiorFrameFactory = new NSMRTreeFrameFactory(interiorTupleWriterFactory, keyFieldCount);
+        IRTreeFrameFactory leafFrameFactory = new NSMRTreeFrameFactory(leafTupleWriterFactory, keyFieldCount);
         ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
         ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
 
@@ -247,9 +248,8 @@
         IRTreeFrame leafFrame = leafFrameFactory.getFrame();
         IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
 
-        int dim = 2;
         RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, interiorCmp,
-                leafCmp, dim);
+                leafCmp);
         rtree.create(fileId, leafFrame, metaFrame);
         rtree.open(fileId);
 
@@ -267,7 +267,8 @@
         accessor.reset(hyracksFrame);
         FrameTupleReference tuple = new FrameTupleReference();
 
-        RTreeOpContext insertOpCtx = rtree.createOpContext(TreeIndexOp.TI_INSERT, interiorFrame, leafFrame, metaFrame, "unittest");
+        RTreeOpContext insertOpCtx = rtree.createOpContext(TreeIndexOp.TI_INSERT, interiorFrame, leafFrame, metaFrame,
+                "unittest");
 
         File datasetFile = new File("/home/salsubaiee/dataset.txt");
         BufferedReader reader = new BufferedReader(new FileReader(datasetFile));
@@ -284,7 +285,7 @@
 
             double p1x = 0;
             double p1y = 0;
-            
+
             try {
                 p1x = Double.valueOf(splittedLine2[1].trim()).doubleValue();
                 p1y = Double.valueOf(splittedLine2[2].trim()).doubleValue();
@@ -294,7 +295,6 @@
             }
             double p2x = p1x;
             double p2y = p1y;
-            
 
             int pk = rnd.nextInt();
 
@@ -325,21 +325,22 @@
             } catch (Exception e) {
                 e.printStackTrace();
             }
-            
+
             if (index == 1000) {
                 break;
             }
             inputLine = reader.readLine();
             index++;
 
-//            rtree.printTree(leafFrame, interiorFrame, recDescSers);
-//            System.out.println();
+            // rtree.printTree(leafFrame, interiorFrame, recDescSers);
+            // System.out.println();
         }
 
-        //rtree.printTree(leafFrame, interiorFrame, recDescSers);
-        //System.out.println();
+        // rtree.printTree(leafFrame, interiorFrame, recDescSers);
+        // System.out.println();
 
-        RTreeOpContext searchOpCtx = rtree.createOpContext(TreeIndexOp.TI_SEARCH, interiorFrame, leafFrame, metaFrame, "unittest");
+        RTreeOpContext searchOpCtx = rtree.createOpContext(TreeIndexOp.TI_SEARCH, interiorFrame, leafFrame, metaFrame,
+                "unittest");
 
         File querysetFile = new File("/home/salsubaiee/queryset.txt");
         BufferedReader reader2 = new BufferedReader(new FileReader(querysetFile));
@@ -353,7 +354,6 @@
             String[] splittedLine1 = inputLine.split(",");
             String[] splittedLine2 = splittedLine1[0].split("\\s");
 
-            
             double p1x;
             double p1y;
             double p2x;
@@ -368,7 +368,7 @@
                 inputLine = reader2.readLine();
                 continue;
             }
-            
+
             int pk = rnd.nextInt();
 
             tb.reset();
@@ -408,16 +408,12 @@
 
         System.out.println("Number of Results: " + totalResults);
 
-//        String stats = rtree.printStats();
-//        print(stats);
-        
-        
-        
-        
-        
-        RTreeOpContext deleteOpCtx = rtree.createOpContext(TreeIndexOp.TI_DELETE, interiorFrame, leafFrame, metaFrame, "unittest");
+        // String stats = rtree.printStats();
+        // print(stats);
 
-        
+        RTreeOpContext deleteOpCtx = rtree.createOpContext(TreeIndexOp.TI_DELETE, interiorFrame, leafFrame, metaFrame,
+                "unittest");
+
         BufferedReader reader3 = new BufferedReader(new FileReader(datasetFile));
         inputLine = reader3.readLine();
         index = 0;
@@ -429,7 +425,7 @@
 
             double p1x = 0;
             double p1y = 0;
-            
+
             try {
                 p1x = Double.valueOf(splittedLine2[1].trim()).doubleValue();
                 p1y = Double.valueOf(splittedLine2[2].trim()).doubleValue();
@@ -468,22 +464,17 @@
             } catch (Exception e) {
                 e.printStackTrace();
             }
-            
+
             if (index == 1000) {
                 break;
             }
             inputLine = reader3.readLine();
             index++;
 
-//            rtree.printTree(leafFrame, interiorFrame, recDescSers);
-//            System.out.println();
+            // rtree.printTree(leafFrame, interiorFrame, recDescSers);
+            // System.out.println();
         }
-        
-        
-        
-        
-        
-        
+
         BufferedReader reader4 = new BufferedReader(new FileReader(querysetFile));
 
         inputLine = reader4.readLine();
@@ -538,19 +529,12 @@
 
         System.out.println("Number of Results: " + totalResults);
 
-//        stats = rtree.printStats();
-//        print(stats);
-        
-        
-        
-        
-        
+        // stats = rtree.printStats();
+        // print(stats);
+
         rtree.printTree(leafFrame, interiorFrame, recDescSers);
         System.out.println();
 
-
-        
-
         rtree.close();
         bufferCache.closeFile(fileId);
         bufferCache.close();
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
new file mode 100644
index 0000000..a5f0594
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
@@ -0,0 +1,198 @@
+package edu.uci.ics.hyracks.storage.am.rtree;
+
+import java.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.io.DataOutput;
+import java.io.File;
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.Random;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
+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.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.dataflow.value.TypeTrait;
+import edu.uci.ics.hyracks.api.io.FileReference;
+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.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.common.api.IFreePageManager;
+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.api.TreeIndexException;
+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.common.ophelpers.TreeIndexOp;
+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.api.IRTreeFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMRTreeFrameFactory;
+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.tuples.RTreeTypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public class SearchCursorTest extends AbstractRTreeTest {
+    private static final int PAGE_SIZE = 256;
+    private static final int NUM_PAGES = 10;
+    private static final int HYRACKS_FRAME_SIZE = 128;
+    private IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+    @Test
+    public void searchCursorTest() throws Exception {
+
+        TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES);
+        IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+        IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+        FileReference file = new FileReference(new File(fileName));
+        bufferCache.createFile(file);
+        int fileId = fmp.lookupFileId(file);
+        bufferCache.openFile(fileId);
+
+        // declare interior-frame-tuple fields
+        int interiorFieldCount = 5;
+        ITypeTrait[] interiorTypeTraits = new ITypeTrait[interiorFieldCount];
+        interiorTypeTraits[0] = new TypeTrait(8);
+        interiorTypeTraits[1] = new TypeTrait(8);
+        interiorTypeTraits[2] = new TypeTrait(8);
+        interiorTypeTraits[3] = new TypeTrait(8);
+        interiorTypeTraits[4] = new TypeTrait(4);
+
+        // declare keys
+        int keyFieldCount = 4;
+        IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
+        cmps[0] = DoubleBinaryComparatorFactory.INSTANCE.createBinaryComparator();
+        cmps[1] = cmps[0];
+        cmps[2] = cmps[0];
+        cmps[3] = cmps[0];
+
+        // declare leaf-frame-tuple fields
+        int leafFieldCount = 5;
+        ITypeTrait[] leafTypeTraits = new ITypeTrait[leafFieldCount];
+        leafTypeTraits[0] = new TypeTrait(8);
+        leafTypeTraits[1] = new TypeTrait(8);
+        leafTypeTraits[2] = new TypeTrait(8);
+        leafTypeTraits[3] = new TypeTrait(8);
+        leafTypeTraits[4] = new TypeTrait(4);
+
+        MultiComparator interiorCmp = new MultiComparator(interiorTypeTraits, cmps);
+        MultiComparator leafCmp = new MultiComparator(leafTypeTraits, cmps);
+
+        RTreeTypeAwareTupleWriterFactory interiorTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(
+                interiorTypeTraits);
+        RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
+
+        IRTreeFrameFactory interiorFrameFactory = new NSMRTreeFrameFactory(interiorTupleWriterFactory, keyFieldCount);
+        IRTreeFrameFactory leafFrameFactory = new NSMRTreeFrameFactory(leafTupleWriterFactory, keyFieldCount);
+        ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+        ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
+
+        IRTreeFrame interiorFrame = interiorFrameFactory.getFrame();
+        IRTreeFrame leafFrame = leafFrameFactory.getFrame();
+        IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
+
+        RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, interiorCmp,
+                leafCmp);
+        rtree.create(fileId, leafFrame, metaFrame);
+        rtree.open(fileId);
+
+        ByteBuffer hyracksFrame = ctx.allocateFrame();
+        FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
+        ArrayTupleBuilder tb = new ArrayTupleBuilder(leafCmp.getFieldCount());
+        DataOutput dos = tb.getDataOutput();
+
+        @SuppressWarnings("rawtypes")
+        ISerializerDeserializer[] recDescSers = { DoubleSerializerDeserializer.INSTANCE,
+                DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
+                DoubleSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+        RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
+        IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
+        accessor.reset(hyracksFrame);
+        FrameTupleReference tuple = new FrameTupleReference();
+
+        RTreeOpContext insertOpCtx = rtree.createOpContext(TreeIndexOp.TI_INSERT, interiorFrame, leafFrame, metaFrame,
+                "unittest");
+
+        Random rnd = new Random();
+        rnd.setSeed(50);
+        for (int i = 0; i < 10000; i++) {
+
+            double p1x = rnd.nextDouble();
+            double p1y = rnd.nextDouble();
+            double p2x = rnd.nextDouble();
+            double p2y = rnd.nextDouble();
+
+            int pk = rnd.nextInt();
+
+            tb.reset();
+            DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1x, p2x), dos);
+            tb.addFieldEndOffset();
+            DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1y, p2y), dos);
+            tb.addFieldEndOffset();
+            DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1x, p2x), dos);
+            tb.addFieldEndOffset();
+            DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1y, p2y), dos);
+            tb.addFieldEndOffset();
+            IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
+            tb.addFieldEndOffset();
+
+            appender.reset(hyracksFrame, true);
+            appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+
+            tuple.reset(accessor, 0);
+
+            print("INSERTING " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " " + Math.max(p1x, p2x)
+                    + " " + Math.max(p1y, p2y) + "\n");
+
+            try {
+                rtree.insert(tuple, insertOpCtx);
+            } catch (TreeIndexException e) {
+            } catch (Exception e) {
+                e.printStackTrace();
+            }
+
+        }
+
+        IRTreeCursor searchCursor = new SearchCursor(interiorFrame, leafFrame);
+        RTreeOpContext searchOpCtx = rtree.createOpContext(TreeIndexOp.TI_SEARCH, interiorFrame, leafFrame, metaFrame,
+                "cursortest");
+        rtree.search(searchCursor, tuple, searchOpCtx);
+
+        ArrayList<Integer> results = new ArrayList<Integer>();
+        try {
+            while (searchCursor.hasNext()) {
+                searchCursor.next();
+                ITupleReference frameTuple = searchCursor.getTuple();
+                ByteArrayInputStream inStream = new ByteArrayInputStream(frameTuple.getFieldData(0),
+                        frameTuple.getFieldStart(0), frameTuple.getFieldLength(0));
+                DataInput dataIn = new DataInputStream(inStream);
+                Integer res = IntegerSerializerDeserializer.INSTANCE.deserialize(dataIn);
+                results.add(res);
+            }
+        } catch (Exception e) {
+            e.printStackTrace();
+        } finally {
+            searchCursor.close();
+        }
+
+        rtree.close();
+        bufferCache.closeFile(fileId);
+        bufferCache.close();
+    }
+}
diff --git a/hyracks-tests/pom.xml b/hyracks-tests/pom.xml
index 64b150f..a4d2c04 100644
--- a/hyracks-tests/pom.xml
+++ b/hyracks-tests/pom.xml
@@ -14,5 +14,6 @@
   <modules>
     <module>hyracks-storage-am-btree-test</module>
     <module>hyracks-storage-am-invertedindex-test</module>
+    <module>hyracks-storage-am-rtree-test</module>
   </modules>
 </project>
diff --git a/pom.xml b/pom.xml
index e4ba074..643f2d1 100644
--- a/pom.xml
+++ b/pom.xml
@@ -64,6 +64,7 @@
     <module>hyracks-storage-am-common</module>
     <module>hyracks-storage-am-btree</module>
     <module>hyracks-storage-am-invertedindex</module>
+    <module>hyracks-storage-am-rtree</module>
     <module>hyracks-test-support</module>
     <module>hyracks-tests</module>
     <module>hyracks-server</module>