diff --git a/hyracks-storage-am-rtree/.project b/hyracks-storage-am-rtree/.project
new file mode 100644
index 0000000..4989318
--- /dev/null
+++ b/hyracks-storage-am-rtree/.project
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+	<name>hyracks-storage-am-rtree</name>
+	<comment></comment>
+	<projects>
+	</projects>
+	<buildSpec>
+		<buildCommand>
+			<name>org.eclipse.jdt.core.javabuilder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+		<buildCommand>
+			<name>org.maven.ide.eclipse.maven2Builder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+	</buildSpec>
+	<natures>
+		<nature>org.eclipse.jdt.core.javanature</nature>
+		<nature>org.maven.ide.eclipse.maven2Nature</nature>
+	</natures>
+</projectDescription>
diff --git a/hyracks-storage-am-rtree/.settings/org.eclipse.jdt.core.prefs b/hyracks-storage-am-rtree/.settings/org.eclipse.jdt.core.prefs
new file mode 100644
index 0000000..6884501
--- /dev/null
+++ b/hyracks-storage-am-rtree/.settings/org.eclipse.jdt.core.prefs
@@ -0,0 +1,6 @@
+#Wed Feb 02 19:49:23 PST 2011
+eclipse.preferences.version=1
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
+org.eclipse.jdt.core.compiler.compliance=1.6
+org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning
+org.eclipse.jdt.core.compiler.source=1.6
diff --git a/hyracks-storage-am-rtree/.settings/org.maven.ide.eclipse.prefs b/hyracks-storage-am-rtree/.settings/org.maven.ide.eclipse.prefs
new file mode 100644
index 0000000..ba4f536
--- /dev/null
+++ b/hyracks-storage-am-rtree/.settings/org.maven.ide.eclipse.prefs
@@ -0,0 +1,9 @@
+#Wed Feb 02 19:49:19 PST 2011
+activeProfiles=
+eclipse.preferences.version=1
+fullBuildGoals=process-test-resources
+includeModules=false
+resolveWorkspaceProjects=true
+resourceFilterGoals=process-resources resources\:testResources
+skipCompilerPlugin=true
+version=1
diff --git a/hyracks-storage-am-rtree/pom.xml b/hyracks-storage-am-rtree/pom.xml
new file mode 100644
index 0000000..d0c48c1
--- /dev/null
+++ b/hyracks-storage-am-rtree/pom.xml
@@ -0,0 +1,70 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+  <modelVersion>4.0.0</modelVersion>
+  <groupId>edu.uci.ics.hyracks</groupId>
+  <artifactId>hyracks-storage-am-rtree</artifactId>
+  <version>0.1.4</version>
+
+  <parent>
+    <groupId>edu.uci.ics.hyracks</groupId>
+    <artifactId>hyracks</artifactId>
+    <version>0.1.4</version>
+  </parent>
+
+  <build>
+    <plugins>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-compiler-plugin</artifactId>
+        <version>2.0.2</version>
+        <configuration>
+          <source>1.6</source>
+          <target>1.6</target>
+        </configuration>
+      </plugin>
+    </plugins>
+  </build>
+  <dependencies>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-storage-am-common</artifactId>
+  		<version>0.1.4</version>
+  		<type>jar</type>
+  		<scope>compile</scope>
+  	</dependency>  	
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-dataflow-common</artifactId>
+  		<version>0.1.4</version>
+  		<type>jar</type>
+  		<scope>compile</scope>
+  	</dependency>  	
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-dataflow-std</artifactId>
+  		<version>0.1.4</version>
+  		<type>jar</type>
+  		<scope>compile</scope>
+  	</dependency>  	
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-control-nc</artifactId>
+  		<version>0.1.4</version>
+  		<type>jar</type>
+  		<scope>compile</scope>
+  	</dependency>  	
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-storage-am-btree</artifactId>
+  		<version>0.1.4</version>
+  		<type>jar</type>
+  		<scope>compile</scope>
+  	</dependency>  	
+  	<dependency>
+  		<groupId>junit</groupId>
+  		<artifactId>junit</artifactId>
+  		<version>4.8.1</version>
+  		<type>jar</type>
+  		<scope>test</scope>
+  	</dependency>  	  		
+  </dependencies>
+</project>
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
new file mode 100644
index 0000000..6cfa40e
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
@@ -0,0 +1,19 @@
+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.api.ITreeIndexFrame;
+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.impls.RTreeSplitKey;
+
+public interface IRTreeFrame extends ITreeIndexFrame {
+
+    public int getChildPageId(ITupleReference tuple, MultiComparator cmp);
+    
+    public int split(IRTreeFrame rightFrame, ITupleReference tuple, MultiComparator cmp, RTreeSplitKey leftSplitKey,
+            RTreeSplitKey rightSplitKey) throws Exception;
+    
+    public void adjustNode(ITreeIndexTupleReference[] tuples, MultiComparator cmp);
+
+    public void adjustTuple(ITupleReference tuple, MultiComparator cmp);
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrameFactory.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrameFactory.java
new file mode 100644
index 0000000..177c8a1
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrameFactory.java
@@ -0,0 +1,22 @@
+/*
+ * 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.api;
+
+import java.io.Serializable;
+
+public interface IRTreeFrameFactory extends Serializable {
+    public IRTreeFrame getFrame();
+}
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
new file mode 100644
index 0000000..61af92b
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
@@ -0,0 +1,292 @@
+package edu.uci.ics.hyracks.storage.am.rtree.frames;
+
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.comparators.IntegerBinaryComparatorFactory;
+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.ISplitKey;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.frames.TreeIndexNSMFrame;
+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.RTreeSplitKey;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.UnorderedSlotManager;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriter;
+
+public class NSMRTreeFrame extends TreeIndexNSMFrame implements IRTreeFrame {
+
+    public ITreeIndexTupleReference[] tuples;
+    private final IBinaryComparator intComp = IntegerBinaryComparatorFactory.INSTANCE.createBinaryComparator();
+
+    public NSMRTreeFrame(ITreeIndexTupleWriter tupleWriter) {
+        super(tupleWriter, new UnorderedSlotManager());
+        this.tuples = new ITreeIndexTupleReference[4]; // change this to number
+                                                       // of dim * 2
+        for (int i = 0; i < 4; i++) {
+            this.tuples[i] = tupleWriter.createTupleReference();
+        }
+    }
+    
+    public ITreeIndexTupleReference[] getTuples() {
+        return tuples;
+    }
+
+    public void setTuples(ITreeIndexTupleReference[] tuples) {
+        this.tuples = tuples;
+    }
+
+    // for debugging
+    public ArrayList<Integer> getChildren(MultiComparator cmp) {
+        ArrayList<Integer> ret = new ArrayList<Integer>();
+        frameTuple.setFieldCount(cmp.getKeyFieldCount());
+        int tupleCount = buf.getInt(tupleCountOff);
+        for (int i = 0; i < tupleCount; i++) {
+            int tupleOff = slotManager.getTupleOff(slotManager.getSlotOff(i));
+            frameTuple.resetByTupleOffset(buf, tupleOff);
+
+            int intVal = IntegerSerializerDeserializer.getInt(
+                    buf.array(),
+                    frameTuple.getFieldStart(frameTuple.getFieldCount() - 1)
+                            + frameTuple.getFieldLength(frameTuple.getFieldCount() - 1));
+            ret.add(intVal);
+        }
+        return ret;
+    }
+
+    @Override
+    public int split(IRTreeFrame rightFrame, ITupleReference tuple, MultiComparator cmp, RTreeSplitKey leftSplitKey,
+            RTreeSplitKey rightSplitKey) throws Exception {
+
+        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;
+        IRTreeFrame 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());
+        leftSplitKey.initData(splitKeySize);
+        this.adjustNode(tuples, cmp);
+        rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, leftSplitKey.getBuffer(), 0);
+        leftSplitKey.getTuple().resetByTupleOffset(leftSplitKey.getBuffer(), 0);
+
+        rightSplitKey.initData(splitKeySize);
+        rightFrame.adjustNode(((NSMRTreeFrame) rightFrame).getTuples(), cmp);
+        rTreeTupleWriterRightFrame.writeTupleFields(((NSMRTreeFrame) rightFrame).getTuples(), 0, rightSplitKey.getBuffer(), 0);
+        rightSplitKey.getTuple().resetByTupleOffset(rightSplitKey.getBuffer(), 0);
+
+        return 0;
+    }
+
+    @Override
+    public void insertSorted(ITupleReference tuple, MultiComparator cmp) throws HyracksDataException {
+        try {
+            insert(tuple, cmp);
+        } catch (Exception e) {
+            e.printStackTrace();
+        }
+    }
+
+    @Override
+    public int getChildPageId(ITupleReference tuple, MultiComparator cmp) {
+        // find least overlap enlargement, use minimum enlarged area to
+        // break tie, if tie still exists use minimum area to break it
+
+        int bestChild = 0;
+        double minEnlargedArea = Double.MAX_VALUE;
+
+        // if (getLevel() == 1) {
+        for (int i = 0; i < getTupleCount(); i++) {
+            frameTuple.resetByTupleIndex(this, i);
+            double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
+            if (enlargedArea < minEnlargedArea) {
+                minEnlargedArea = enlargedArea;
+                bestChild = i;
+            }
+
+            else if (enlargedArea == minEnlargedArea) {
+                double area = area(frameTuple, cmp);
+                frameTuple.resetByTupleIndex(this, bestChild);
+                double bestArea = area(frameTuple, cmp);
+                if (area < bestArea) {
+                    bestChild = i;
+                }
+            }
+        }
+        // } else { // find minimum enlarged area, use minimum area to break
+        // tie
+
+        // }
+        frameTuple.resetByTupleIndex(this, bestChild);
+        if (minEnlargedArea > 0.0) {
+            enlarge(frameTuple, tuple, cmp);
+        }
+
+        // return the page id of the bestChild tuple
+        return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
+    }
+
+    public double area(ITupleReference tuple, MultiComparator cmp) {
+        double area = 1.0;
+        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        for (int i = 0; i < maxFieldPos; i++) {
+            int j = maxFieldPos + i;
+            area *= DoubleSerializerDeserializer.getDouble(tuple.getFieldData(j), tuple.getFieldStart(j))
+                    - DoubleSerializerDeserializer.getDouble(tuple.getFieldData(i), tuple.getFieldStart(i));
+        }
+        return area;
+    }
+
+    public double enlargedArea(ITupleReference tuple, ITupleReference tupleToBeInserted, MultiComparator cmp) {
+        double areaBeforeEnlarge = area(tuple, cmp);
+        double areaAfterEnlarge = 1.0;
+
+        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        for (int i = 0; i < maxFieldPos; i++) {
+            int j = maxFieldPos + i;
+            double pHigh, pLow;
+            int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
+                    tuple.getFieldLength(i), tupleToBeInserted.getFieldData(i), tupleToBeInserted.getFieldStart(i),
+                    tupleToBeInserted.getFieldLength(i));
+            if (c < 0) {
+                pLow = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(i), tuple.getFieldStart(i));
+            } else {
+                pLow = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(i),
+                        tupleToBeInserted.getFieldStart(i));
+            }
+
+            c = cmp.getComparators()[j].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
+                    tupleToBeInserted.getFieldData(j), tupleToBeInserted.getFieldStart(j),
+                    tupleToBeInserted.getFieldLength(j));
+            if (c > 0) {
+                pHigh = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(j), tuple.getFieldStart(j));
+            } else {
+                pHigh = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(j),
+                        tupleToBeInserted.getFieldStart(j));
+            }
+            areaAfterEnlarge *= pHigh - pLow;
+        }
+        return areaAfterEnlarge - areaBeforeEnlarge;
+    }
+
+    public void enlarge(ITupleReference tuple, ITupleReference tupleToBeInserted, MultiComparator cmp) {
+        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), tupleToBeInserted.getFieldData(i), tupleToBeInserted.getFieldStart(i),
+                    tupleToBeInserted.getFieldLength(i));
+            if (c > 0) {
+                System.arraycopy(tupleToBeInserted.getFieldData(i), tupleToBeInserted.getFieldStart(i),
+                        tuple.getFieldData(i), tuple.getFieldStart(i), tupleToBeInserted.getFieldLength(i));
+            }
+            c = cmp.getComparators()[j].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
+                    tupleToBeInserted.getFieldData(j), tupleToBeInserted.getFieldStart(j),
+                    tupleToBeInserted.getFieldLength(j));
+            if (c < 0) {
+                System.arraycopy(tupleToBeInserted.getFieldData(j), tupleToBeInserted.getFieldStart(j),
+                        tuple.getFieldData(j), tuple.getFieldStart(j), tupleToBeInserted.getFieldLength(j));
+            }
+        }
+    }
+
+    @Override
+    public void adjustTuple(ITupleReference tuple, MultiComparator cmp) {
+        frameTuple.setFieldCount(cmp.getFieldCount());
+        for (int i = 0; i < getTupleCount(); i++) {
+            frameTuple.resetByTupleIndex(this, i);
+
+            int c = intComp.compare(frameTuple.getFieldData(cmp.getKeyFieldCount()),
+                    frameTuple.getFieldStart(cmp.getKeyFieldCount()),
+                    frameTuple.getFieldLength(cmp.getKeyFieldCount()), tuple.getFieldData(cmp.getKeyFieldCount()),
+                    tuple.getFieldStart(cmp.getKeyFieldCount()), tuple.getFieldLength(cmp.getKeyFieldCount()));
+            if (c == 0) {
+                tupleWriter.writeTuple(tuple, buf, getTupleOffset(i));
+                break;
+            }
+        }
+    }
+
+    @Override
+    public void adjustNode(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
+        for (int i = 0; i < tuples.length; i++) {
+            tuples[i].setFieldCount(cmp.getKeyFieldCount());
+            tuples[i].resetByTupleIndex(this, 0);
+        }
+
+        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        for (int i = 1; i < getTupleCount(); i++) {
+            frameTuple.resetByTupleIndex(this, i);
+            for (int j = 0; j < maxFieldPos; j++) {
+                int k = maxFieldPos + j;
+                int c = cmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+                        frameTuple.getFieldLength(j), tuples[j].getFieldData(j), tuples[j].getFieldStart(j),
+                        tuples[j].getFieldLength(j));
+                if (c < 0) {
+                    tuples[j].resetByTupleIndex(this, i);
+                }
+                c = cmp.getComparators()[k].compare(frameTuple.getFieldData(k), frameTuple.getFieldStart(k),
+                        frameTuple.getFieldLength(k), tuples[k].getFieldData(k), tuples[k].getFieldStart(k),
+                        tuples[k].getFieldLength(k));
+                if (c > 0) {
+                    tuples[k].resetByTupleIndex(this, i);
+                }
+            }
+        }
+    }
+
+    @Override
+    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey)
+            throws Exception {
+        // TODO Auto-generated method stub
+        return 0;
+    }
+}
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
new file mode 100644
index 0000000..729bf36
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrameFactory.java
@@ -0,0 +1,35 @@
+/*
+ * 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.frames;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrameFactory;
+
+public class NSMRTreeFrameFactory implements IRTreeFrameFactory {
+
+    private static final long serialVersionUID = 1L;
+    private ITreeIndexTupleWriterFactory tupleWriterFactory;
+
+    public NSMRTreeFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory) {
+        this.tupleWriterFactory = tupleWriterFactory;
+    }
+
+    @Override
+    public IRTreeFrame getFrame() {
+        return new NSMRTreeFrame(tupleWriterFactory.createTupleWriter());
+    }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/ByteArrayList.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/ByteArrayList.java
new file mode 100644
index 0000000..7fa5ba4
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/ByteArrayList.java
@@ -0,0 +1,49 @@
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+public class ByteArrayList {
+    private byte[] data;
+    private int size;
+    private final int growth;
+
+    public ByteArrayList(int initialCapacity, int growth) {
+        data = new byte[initialCapacity];
+        size = 0;
+        this.growth = growth;
+    }
+
+    public int size() {
+        return size;
+    }
+
+    public void add(byte i) {
+        if (size == data.length) {
+            byte[] newData = new byte[data.length + growth];
+            System.arraycopy(data, 0, newData, 0, data.length);
+            data = newData;
+        }
+
+        data[size++] = i;
+    }
+
+    public void removeLast() {
+        if (size > 0)
+            size--;
+    }
+
+    // WARNING: caller is responsible for checking size > 0
+    public int getLast() {
+        return data[size - 1];
+    }
+
+    public int get(int i) {
+        return data[i];
+    }
+
+    public void clear() {
+        size = 0;
+    }
+
+    public boolean isEmpty() {
+        return size == 0;
+    }
+}
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
new file mode 100644
index 0000000..ca7404a
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
@@ -0,0 +1,374 @@
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+import java.util.ArrayList;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
+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.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.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrameFactory;
+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;
+
+public class RTree {
+
+    private boolean created = false;
+    private final int metaDataPage = 0; // page containing meta data, e.g.,
+                                        // maxPage
+    private final int rootPage = 1; // the root page never changes
+
+    private final IFreePageManager freePageManager;
+    private final IBufferCache bufferCache;
+    private int fileId;
+
+    private final IRTreeFrameFactory interiorFrameFactory;
+    private final IRTreeFrameFactory leafFrameFactory;
+    private final MultiComparator interiorCmp;
+    private final MultiComparator leafCmp;
+
+    public long pins = 0;
+    public long unpins = 0;
+    public byte currentLevel = 0;
+
+    public RTree(IBufferCache bufferCache, IFreePageManager freePageManager, IRTreeFrameFactory interiorFrameFactory,
+            IRTreeFrameFactory leafFrameFactory, MultiComparator interiorCmp, MultiComparator leafCmp) {
+        this.bufferCache = bufferCache;
+        this.freePageManager = freePageManager;
+        this.interiorFrameFactory = interiorFrameFactory;
+        this.leafFrameFactory = leafFrameFactory;
+        this.interiorCmp = interiorCmp;
+        this.leafCmp = leafCmp;
+    }
+
+    public void printTree(IRTreeFrame leafFrame, IRTreeFrame interiorFrame, ISerializerDeserializer[] fields)
+            throws Exception {
+        printTree(rootPage, null, false, leafFrame, interiorFrame, fields);
+    }
+
+    public void printTree(int pageId, ICachedPage parent, boolean unpin, IRTreeFrame leafFrame,
+            IRTreeFrame interiorFrame, ISerializerDeserializer[] fields) throws Exception {
+
+        ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+        pins++;
+
+        try {
+            if (parent != null && unpin == true) {
+                bufferCache.unpin(parent);
+                unpins++;
+            }
+
+            interiorFrame.setPage(node);
+            int level = interiorFrame.getLevel();
+
+            System.out.format("%1d ", level);
+            System.out.format("%3d ", pageId);
+            for (int i = 0; i < currentLevel - level; i++)
+                System.out.format("    ");
+
+            String keyString;
+            if (interiorFrame.isLeaf()) {
+                leafFrame.setPage(node);
+                keyString = leafFrame.printKeys(leafCmp, fields);
+            } else {
+                keyString = interiorFrame.printKeys(interiorCmp, fields);
+            }
+
+            System.out.format(keyString);
+            if (!interiorFrame.isLeaf()) {
+                ArrayList<Integer> children = ((NSMRTreeFrame) (interiorFrame)).getChildren(interiorCmp);
+
+                //System.out.println("num of children for page id " + pageId + " is: "+ children.size());
+                for (int i = 0; i < children.size(); i++) {
+                    printTree(children.get(i), node, i == children.size() - 1, leafFrame, interiorFrame, fields);
+                }
+                //System.out.println();
+            } else {
+                bufferCache.unpin(node);
+                unpins++;
+            }
+        } catch (Exception e) {
+            bufferCache.unpin(node);
+            unpins++;
+            e.printStackTrace();
+        }
+    }
+
+    public void create(int fileId, IRTreeFrame leafFrame, ITreeIndexMetaDataFrame metaFrame) throws Exception {
+        if (created)
+            return;
+
+        // initialize meta data page
+        ICachedPage metaNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, metaDataPage), false);
+        pins++;
+
+        metaNode.acquireWriteLatch();
+        try {
+            metaFrame.setPage(metaNode);
+            metaFrame.initBuffer((byte) -1);
+            metaFrame.setMaxPage(rootPage);
+        } finally {
+            bufferCache.unpin(metaNode);
+            unpins++;
+        }
+
+        // initialize root page
+        ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), true);
+        pins++;
+
+        try {
+            leafFrame.setPage(rootNode);
+            leafFrame.initBuffer((byte) 0);
+        } finally {
+            bufferCache.unpin(rootNode);
+            unpins++;
+        }
+        currentLevel = 0;
+        created = true;
+    }
+
+    public void open(int fileId) {
+        this.fileId = fileId;
+    }
+
+    public void close() {
+        fileId = -1;
+    }
+
+    public RTreeOpContext createOpContext(TreeIndexOp op, IRTreeFrame interiorFrame, IRTreeFrame leafFrame,
+            ITreeIndexMetaDataFrame metaFrame) {
+        // TODO: figure out better tree-height hint
+        return new RTreeOpContext(op, interiorFrame, leafFrame, metaFrame, 6);
+    }
+
+    private void createNewRoot(RTreeOpContext ctx) throws Exception {
+        currentLevel++;
+
+        // make sure the root is always at the same level
+        ICachedPage leftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, ctx.leftSplitKey.getPage()),
+                false);
+        pins++;
+        try {
+            ICachedPage rightNode = bufferCache.pin(
+                    BufferedFileHandle.getDiskPageId(fileId, ctx.rightSplitKey.getPage()), false);
+            pins++;
+            try {
+                int newLeftId = freePageManager.getFreePage(ctx.metaFrame);
+                ICachedPage newLeftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, newLeftId), true);
+                pins++;
+                try {
+                    // copy left child to new left child
+                    System.arraycopy(leftNode.getBuffer().array(), 0, newLeftNode.getBuffer().array(), 0, newLeftNode
+                            .getBuffer().capacity());
+
+                    // initialize new root (leftNode becomes new root)
+                    ctx.interiorFrame.setPage(leftNode);
+                    ctx.interiorFrame.initBuffer((byte) (ctx.interiorFrame.getLevel() + 1));
+
+                    ctx.leftSplitKey.setPage(newLeftId);
+                    
+                    ctx.interiorFrame.insert(ctx.leftSplitKey.getTuple(), interiorCmp);
+                    ctx.interiorFrame.insert(ctx.rightSplitKey.getTuple(), interiorCmp);
+
+                    //System.out.println("R Created page id: " + newLeftId + "level: " + ctx.interiorFrame.getLevel());
+                    
+                    System.out.println("Created new root");
+
+                } finally {
+                    bufferCache.unpin(newLeftNode);
+                    unpins++;
+                }
+            } finally {
+                bufferCache.unpin(rightNode);
+                unpins++;
+            }
+        } finally {
+            bufferCache.unpin(leftNode);
+            unpins++;
+        }
+    }
+
+    public int temp = 0;
+
+    public void insert(ITupleReference tuple, RTreeOpContext ctx) throws Exception {
+        ctx.reset();
+        ctx.setTuple(tuple);
+        ctx.leftSplitKey.reset();
+        ctx.rightSplitKey.reset();
+        ctx.leftSplitKey.getTuple().setFieldCount(interiorCmp.getFieldCount());
+        ctx.rightSplitKey.getTuple().setFieldCount(interiorCmp.getFieldCount());
+        ctx.interiorFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
+        temp++;
+        insertImpl(rootPage, null, (byte) 0, ctx);
+
+        // we split the root, here is the key for a new root
+        if (ctx.leftSplitKey.getBuffer() != null && ctx.rightSplitKey.getBuffer() != null) {
+            createNewRoot(ctx);
+        }
+    }
+
+    public void insertImpl(int pageId, ICachedPage parent, byte desiredLevel, RTreeOpContext ctx) throws Exception {
+        ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+        pins++;
+        ctx.interiorFrame.setPage(node);
+
+        // latch coupling TODO: check the correctness of this
+        if (parent != null) {
+            bufferCache.unpin(parent);
+            unpins++;
+        }
+        if (temp >= 36) {
+            //System.out.println("HHHHHHHHHHHHHH");
+        }
+        boolean isLeaf = ctx.interiorFrame.isLeaf();
+        //System.out.println("level: " + ctx.interiorFrame.getLevel());
+        // the children pointers in the node point to leaves
+        if (ctx.interiorFrame.getLevel() > desiredLevel) {
+            int childPageId = ctx.interiorFrame.getChildPageId(ctx.getTuple(), interiorCmp);
+            //System.out.println("PAGE ID: " + childPageId);
+            insertImpl(childPageId, node, desiredLevel, ctx);
+
+            if (ctx.leftSplitKey.getBuffer() != null && ctx.rightSplitKey.getBuffer() != null) { // TODO:
+                                                                                                 // checking
+                                                                                                 // one
+                                                                                                 // is
+                                                                                                 // enough?
+                node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+                pins++;
+                try {
+                    ctx.interiorFrame.setPage(node);
+                    ctx.interiorFrame.adjustTuple(ctx.leftSplitKey.getTuple(), interiorCmp);
+                    insertTuple(pageId, ctx.rightSplitKey.getTuple(), ctx, isLeaf);
+                    // RTreeSplitKey splitKey =
+                    // ctx.rightSplitKey.duplicate(ctx.interiorFrame.getTupleWriter().createTupleReference());
+                    // insertTuple(pageId, splitKey.getTuple(), ctx, isLeaf);
+                } finally {
+                    bufferCache.unpin(node);
+                    unpins++;
+                }
+            }
+        } else {
+            try {
+                if (isLeaf) {
+                    ctx.leafFrame.setPage(node);
+                    ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
+                }
+                insertTuple(pageId, ctx.getTuple(), ctx, isLeaf);
+            } finally {
+                bufferCache.unpin(node);
+                unpins++;
+            }
+        }
+    }
+
+    private void insertTuple(int pageId, ITupleReference tuple, RTreeOpContext ctx, boolean isLeaf) throws Exception {
+        FrameOpSpaceStatus spaceStatus;
+        if (!isLeaf) {
+            spaceStatus = ctx.interiorFrame.hasSpaceInsert(ctx.getTuple(), interiorCmp);
+        } else {
+            spaceStatus = ctx.leafFrame.hasSpaceInsert(ctx.getTuple(), leafCmp);
+        }
+
+        switch (spaceStatus) {
+            case SUFFICIENT_CONTIGUOUS_SPACE: {
+                if (!isLeaf) {
+                    ctx.interiorFrame.insert(tuple, interiorCmp);
+                } else {
+                    ctx.leafFrame.insert(tuple, leafCmp);
+                }
+                ctx.leftSplitKey.reset();
+                ctx.rightSplitKey.reset();
+                break;
+            }
+
+            case SUFFICIENT_SPACE: {
+                if (!isLeaf) {
+                    ctx.interiorFrame.compact(interiorCmp);
+                    ctx.interiorFrame.insert(tuple, interiorCmp);
+                } else {
+                    ctx.leafFrame.compact(leafCmp);
+                    ctx.leafFrame.insert(tuple, leafCmp);
+                }
+                ctx.leftSplitKey.reset();
+                ctx.rightSplitKey.reset();
+                break;
+            }
+
+            case INSUFFICIENT_SPACE: {
+                int rightPageId = freePageManager.getFreePage(ctx.metaFrame);
+                ICachedPage rightNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rightPageId), true);
+                pins++;
+
+                try {
+                    IRTreeFrame rightFrame;
+                    int ret;
+                    if (!isLeaf) {
+                        rightFrame = interiorFrameFactory.getFrame();
+                        rightFrame.setPage(rightNode);
+                        rightFrame.initBuffer((byte) ctx.interiorFrame.getLevel());
+                        rightFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
+                        ret = ctx.interiorFrame.split(rightFrame, tuple, interiorCmp, ctx.leftSplitKey,
+                                ctx.rightSplitKey);
+                        rightFrame.setPageLsn(rightFrame.getPageLsn() + 1);
+                        ctx.interiorFrame.setPageLsn(ctx.interiorFrame.getPageLsn() + 1);
+
+//                         System.out.println("I Created page id: " +
+//                         rightPageId + "level: "
+//                         + ctx.interiorFrame.getLevel());
+                    } else {
+                        rightFrame = leafFrameFactory.getFrame();
+                        rightFrame.setPage(rightNode);
+                        rightFrame.initBuffer((byte) 0);
+                        rightFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
+                        ret = ctx.leafFrame.split(rightFrame, tuple, leafCmp, ctx.leftSplitKey, ctx.rightSplitKey);
+                        rightFrame.setPageLsn(rightFrame.getPageLsn() + 1);
+                        ctx.leafFrame.setPageLsn(ctx.leafFrame.getPageLsn() + 1);
+
+//                         System.out.println("L Created page id: " +
+//                         rightPageId + "level: " + 0);
+                    }
+
+                    if (ret != 0) {
+                        ctx.leftSplitKey.reset();
+                        ctx.rightSplitKey.reset();
+                    } else {
+                        ctx.leftSplitKey.setPage(pageId);
+                        ctx.rightSplitKey.setPage(rightPageId);
+                    }
+
+                } finally {
+                    bufferCache.unpin(rightNode);
+                    unpins++;
+                }
+                // System.out.println("Splitted");
+                break;
+            }
+        }
+    }
+
+    public IRTreeFrameFactory getInteriorFrameFactory() {
+        return interiorFrameFactory;
+    }
+
+    public IRTreeFrameFactory getLeafFrameFactory() {
+        return leafFrameFactory;
+    }
+
+    public MultiComparator getInteriorCmp() {
+        return interiorCmp;
+    }
+
+    public MultiComparator getLeafCmp() {
+        return leafCmp;
+    }
+
+    public IFreePageManager getFreePageManager() {
+        return freePageManager;
+    }
+}
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
new file mode 100644
index 0000000..94e16d2
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
@@ -0,0 +1,42 @@
+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.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.TreeIndexOp;
+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 final ITreeIndexMetaDataFrame metaFrame;
+    public final ByteArrayList overflowArray;
+    public final RTreeSplitKey leftSplitKey;
+    public final RTreeSplitKey rightSplitKey;
+    public int insertLevel;
+    public ITupleReference tuple;
+
+    public RTreeOpContext(TreeIndexOp op, IRTreeFrame interiorFrame, IRTreeFrame leafFrame,
+            ITreeIndexMetaDataFrame metaFrame, int treeHeightHint) {
+        this.op = op;
+        this.interiorFrame = interiorFrame;
+        this.leafFrame = leafFrame;
+        this.metaFrame = metaFrame;
+        leftSplitKey = new RTreeSplitKey(leafFrame.getTupleWriter().createTupleReference());
+        rightSplitKey = new RTreeSplitKey(leafFrame.getTupleWriter().createTupleReference());
+        overflowArray = new ByteArrayList(treeHeightHint, treeHeightHint);
+    }
+
+    public ITupleReference getTuple() {
+        return tuple;
+    }
+
+    public void setTuple(ITupleReference tuple) {
+        this.tuple = tuple;
+    }
+
+    public void reset() {
+        if (overflowArray != null)
+            overflowArray.clear();
+    }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSplitKey.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSplitKey.java
new file mode 100644
index 0000000..7c33a9a
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSplitKey.java
@@ -0,0 +1,62 @@
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+
+public class RTreeSplitKey {
+    public byte[] data = null;
+    public ByteBuffer buf = null;
+    public ITreeIndexTupleReference tuple;
+    public int keySize = 0;
+
+    public RTreeSplitKey(ITreeIndexTupleReference tuple) {
+        this.tuple = tuple;
+    }
+
+    public void initData(int keySize) {
+        // try to reuse existing memory from a lower-level split if possible
+        this.keySize = keySize;
+        if (data != null) {
+            if (data.length < keySize + 4) {
+                data = new byte[keySize + 4]; // add 4 for the page
+                buf = ByteBuffer.wrap(data);
+            }
+        } else {
+            data = new byte[keySize + 4]; // add 4 for the page
+            buf = ByteBuffer.wrap(data);
+        }
+
+        tuple.resetByTupleOffset(buf, 0);
+    }
+
+    public void reset() {
+        data = null;
+        buf = null;
+    }
+
+    public ByteBuffer getBuffer() {
+        return buf;
+    }
+
+    public ITreeIndexTupleReference getTuple() {
+        return tuple;
+    }
+
+    public int getPage() {
+        return buf.getInt(keySize);
+    }
+
+    public void setPage(int Page) {
+        buf.putInt(keySize, Page);
+    }
+
+    public RTreeSplitKey duplicate(ITreeIndexTupleReference copyTuple) {
+        RTreeSplitKey copy = new RTreeSplitKey(copyTuple);
+        copy.data = data.clone();
+        copy.buf = ByteBuffer.wrap(copy.data);
+        copy.tuple.setFieldCount(tuple.getFieldCount());
+        copy.tuple.resetByTupleOffset(copy.buf, 0);
+        return copy;
+    }
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
new file mode 100644
index 0000000..95a89bc
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
@@ -0,0 +1,32 @@
+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.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.frames.AbstractSlotManager;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleMode;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleNoExactMatchPolicy;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+
+public class UnorderedSlotManager extends AbstractSlotManager {
+    public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, MultiComparator multiCmp,
+            FindTupleMode mode, FindTupleNoExactMatchPolicy matchPolicy) {
+        if (mode == FindTupleMode.FTM_EXACT) {
+            for (int i = 0; i < frame.getTupleCount(); i++) {
+                frameTuple.resetByTupleIndex(frame, i);
+                int cmp = multiCmp.compare(searchKey, frameTuple);
+                if (cmp == 0) {
+                    return i;
+                }
+            }
+        }
+        return -1;
+    }
+
+    @Override
+    public int insertSlot(int tupleIndex, int tupleOff) {
+        int slotOff = getSlotEndOff() - slotSize;
+        setSlot(slotOff, tupleOff);
+        return slotOff;
+    }
+
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tuples/RTreeTypeAwareTupleWriter.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tuples/RTreeTypeAwareTupleWriter.java
new file mode 100644
index 0000000..f512cc8
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tuples/RTreeTypeAwareTupleWriter.java
@@ -0,0 +1,45 @@
+package edu.uci.ics.hyracks.storage.am.rtree.tuples;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriter;
+
+public class RTreeTypeAwareTupleWriter extends TypeAwareTupleWriter {
+
+    public RTreeTypeAwareTupleWriter(ITypeTrait[] typeTraits) {
+        super(typeTraits);
+    }
+
+    public int writeTupleFields(ITreeIndexTupleReference[] refs, int startField, ByteBuffer targetBuf, int targetOff) {
+        int runner = targetOff;
+        int nullFlagsBytes = getNullFlagsBytes(refs.length);
+        // write null indicator bits
+        for (int i = 0; i < nullFlagsBytes; i++) {
+            targetBuf.put(runner++, (byte) 0);
+        }
+
+        // write field slots for variable length fields
+        // since the r-tree has fixed length keys, we don't actually need this?
+        encDec.reset(targetBuf.array(), runner);
+        for (int i = startField; i < startField + refs.length; i++) {
+            if (typeTraits[i].getStaticallyKnownDataLength() == ITypeTrait.VARIABLE_LENGTH) {
+                encDec.encode(refs[i].getFieldLength(i));
+            }
+        }
+        runner = encDec.getPos();
+
+        // write data
+        for (int i = 0; i < refs.length; i++) {
+            double d3 = DoubleSerializerDeserializer.getDouble(refs[i].getFieldData(i), refs[i].getFieldStart(i));
+            
+            System.arraycopy(refs[i].getFieldData(i), refs[i].getFieldStart(i), targetBuf.array(), runner,
+                    refs[i].getFieldLength(i));
+            runner += refs[i].getFieldLength(i);
+        }
+        return runner - targetOff;
+
+    }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tuples/RTreeTypeAwareTupleWriterFactory.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tuples/RTreeTypeAwareTupleWriterFactory.java
new file mode 100644
index 0000000..18fbd71
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tuples/RTreeTypeAwareTupleWriterFactory.java
@@ -0,0 +1,21 @@
+package edu.uci.ics.hyracks.storage.am.rtree.tuples;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
+
+public class RTreeTypeAwareTupleWriterFactory implements ITreeIndexTupleWriterFactory {
+
+    private static final long serialVersionUID = 1L;
+    private ITypeTrait[] typeTraits;
+
+    public RTreeTypeAwareTupleWriterFactory(ITypeTrait[] typeTraits) {
+        this.typeTraits = typeTraits;
+    }
+
+    @Override
+    public ITreeIndexTupleWriter createTupleWriter() {
+        return new RTreeTypeAwareTupleWriter(typeTraits);
+    }
+
+}
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/.project b/hyracks-tests/hyracks-storage-am-rtree-test/.project
new file mode 100644
index 0000000..ea7e36b
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/.project
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+	<name>hyracks-storage-am-rtree-test</name>
+	<comment></comment>
+	<projects>
+	</projects>
+	<buildSpec>
+		<buildCommand>
+			<name>org.eclipse.jdt.core.javabuilder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+		<buildCommand>
+			<name>org.maven.ide.eclipse.maven2Builder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+	</buildSpec>
+	<natures>
+		<nature>org.eclipse.jdt.core.javanature</nature>
+		<nature>org.maven.ide.eclipse.maven2Nature</nature>
+	</natures>
+</projectDescription>
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/.settings/org.eclipse.jdt.core.prefs b/hyracks-tests/hyracks-storage-am-rtree-test/.settings/org.eclipse.jdt.core.prefs
new file mode 100644
index 0000000..3cd389e
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/.settings/org.eclipse.jdt.core.prefs
@@ -0,0 +1,6 @@
+#Thu Jan 06 11:27:16 PST 2011
+eclipse.preferences.version=1
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
+org.eclipse.jdt.core.compiler.compliance=1.6
+org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning
+org.eclipse.jdt.core.compiler.source=1.6
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/.settings/org.maven.ide.eclipse.prefs b/hyracks-tests/hyracks-storage-am-rtree-test/.settings/org.maven.ide.eclipse.prefs
new file mode 100644
index 0000000..99b89a6
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/.settings/org.maven.ide.eclipse.prefs
@@ -0,0 +1,9 @@
+#Thu Jan 06 11:27:16 PST 2011
+activeProfiles=
+eclipse.preferences.version=1
+fullBuildGoals=process-test-resources
+includeModules=false
+resolveWorkspaceProjects=true
+resourceFilterGoals=process-resources resources\:testResources
+skipCompilerPlugin=true
+version=1
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml b/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
new file mode 100644
index 0000000..36d4988
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
@@ -0,0 +1,55 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+  <modelVersion>4.0.0</modelVersion>
+  <groupId>edu.uci.ics.hyracks</groupId>
+  <artifactId>hyracks-storage-am-rtree-test</artifactId>
+  <version>0.1.4</version>
+
+  <parent>
+    <groupId>edu.uci.ics.hyracks</groupId>
+    <artifactId>hyracks-tests</artifactId>
+    <version>0.1.4</version>
+  </parent>
+
+  <build>
+    <plugins>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-compiler-plugin</artifactId>
+        <version>2.0.2</version>
+        <configuration>
+          <source>1.6</source>
+          <target>1.6</target>
+        </configuration>
+      </plugin>
+    </plugins>
+  </build>
+  <dependencies>
+  	<dependency>
+  		<groupId>junit</groupId>
+  		<artifactId>junit</artifactId>
+  		<version>4.8.1</version>
+  		<type>jar</type>
+  		<scope>test</scope>
+  	</dependency>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-control-nc</artifactId>
+  		<version>0.1.4</version>
+  		<scope>compile</scope>
+  	</dependency>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-storage-am-rtree</artifactId>
+  		<version>0.1.4</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>
+  		<type>jar</type>
+  		<scope>test</scope>
+  	</dependency>
+  </dependencies>
+</project>
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTest.java
new file mode 100644
index 0000000..54c6cb3
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTest.java
@@ -0,0 +1,25 @@
+package edu.uci.ics.hyracks.storage.am.rtree;
+
+import java.io.File;
+import java.text.SimpleDateFormat;
+import java.util.Date;
+
+import org.junit.AfterClass;
+
+public abstract class AbstractRTreeTest {
+
+    protected final static SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
+    protected final static String tmpDir = System.getProperty("java.io.tmpdir");
+    protected final static String sep = System.getProperty("file.separator");
+    protected final static String fileName = tmpDir + sep + simpleDateFormat.format(new Date());
+
+    protected void print(String str) {
+        System.out.print(str);
+    }
+
+    @AfterClass
+    public static void cleanup() throws Exception {
+        File f = new File(fileName);
+        f.deleteOnExit();
+    }
+}
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
new file mode 100644
index 0000000..01a3989
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeFrameTest.java
@@ -0,0 +1,166 @@
+/*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
new file mode 100644
index 0000000..f92855c
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
@@ -0,0 +1,189 @@
+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.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.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.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 RTreeTest 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 test01() 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 interiorTieldCount = 5;
+        ITypeTrait[] interiorTypeTraits = new ITypeTrait[interiorTieldCount];
+        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);
+        IRTreeFrameFactory leafFrameFactory = new NSMRTreeFrameFactory(leafTupleWriterFactory);
+        ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+        ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
+
+        IRTreeFrame interiorFrame = interiorFrameFactory.getFrame();
+        IRTreeFrame leafFrame = leafFrameFactory.getFrame();
+        IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0);
+        
+        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);
+        
+        Random rnd = new Random();
+        rnd.setSeed(50);
+        
+        for (int i = 0; i < 33; i++) {
+
+            double p1x = rnd.nextDouble();
+            double p1y = rnd.nextDouble();
+            double p2x = rnd.nextDouble();
+            double p2y = rnd.nextDouble();
+            
+//            System.out.println(p1x);
+//            System.out.println(p1y);
+//            System.out.println(p2x);
+//            System.out.println(p2y);
+//            
+           System.out.println("=================================");
+            
+            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);
+
+            //if (i % 1000 == 0) {
+                long end = System.currentTimeMillis();
+                print("INSERTING " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " " + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y) + "\n");
+            //}
+
+            try {
+                if(i == 22)
+                    System.out.print("");
+                rtree.insert(tuple, insertOpCtx);
+            } catch (TreeIndexException e) {
+            } catch (Exception e) {
+                e.printStackTrace();
+            }
+            rtree.printTree(leafFrame, interiorFrame, recDescSers);
+            System.out.println();
+        }
+
+//        rtree.printTree(leafFrame, interiorFrame, recDescSers);
+//        System.out.println();
+        rtree.close();
+        bufferCache.closeFile(fileId);
+        bufferCache.close();
+
+    }
+}
diff --git a/hyracks-tests/pom.xml b/hyracks-tests/pom.xml
index f4e1984..c79442d 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 619c635..0b59a29 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>