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 75a74ca..49adc87 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
@@ -7,24 +7,23 @@
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.Rectangle;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.TraverseList;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.TupleEntryArrayList;
 
 public interface IRTreeFrame extends ITreeIndexFrame {
-    
+
     public ITreeIndexTupleReference createTupleReference();
-    
+
     public boolean recomputeMBR(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
 
     public void computeMBR(ISplitKey splitKey, MultiComparator cmp);
-    
+
     public void delete(int tupleIndex, MultiComparator cmp) throws Exception;
-    
+
     public int findTupleByPointer(int pageId, MultiComparator cmp);
-    
+
     public int findTupleByPointer(ITupleReference tuple, TraverseList traverseList, int parentId, MultiComparator cmp);
 
     public int findTupleByPointer(ITupleReference tuple, MultiComparator cmp);
-    
+
     public int findTupleIndex(ITupleReference tuple, MultiComparator cmp);
 
     public int getPageNsn();
@@ -37,17 +36,14 @@
 
     public int getBestChildPageId(MultiComparator cmp);
 
-    public boolean findBestChild(ITupleReference tuple, TupleEntryArrayList entries, MultiComparator cmp);
+    public boolean findBestChild(ITupleReference tuple, MultiComparator cmp);
 
     public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp);
 
     public void adjustKey(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
 
-    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey,
-            TupleEntryArrayList entries1, TupleEntryArrayList entries2, Rectangle[] rec) throws Exception;
-
     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 e4bdf93..805c084 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
@@ -16,6 +16,7 @@
 import edu.uci.ics.hyracks.storage.am.rtree.impls.EntriesOrder;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSplitKey;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.Rectangle;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SpatialUtils;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.TraverseList;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.TupleEntryArrayList;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.UnorderedSlotManager;
@@ -26,8 +27,11 @@
     protected static final int rightPageOff = pageNsnOff + 4;
 
     private ITreeIndexTupleReference[] tuples;
-
     private ITreeIndexTupleReference cmpFrameTuple;
+    public final SpatialUtils spatialUtils;
+    public TupleEntryArrayList tupleEntries1; // used for split and checking enlargement
+    public TupleEntryArrayList tupleEntries2; // used for split
+    public Rectangle[] rec;
 
     private static final double splitFactor = 0.4;
     private static final int nearMinimumOverlapFactor = 32;
@@ -39,6 +43,14 @@
             this.tuples[i] = tupleWriter.createTupleReference();
         }
         cmpFrameTuple = tupleWriter.createTupleReference();
+        spatialUtils = new SpatialUtils();
+        // TODO: find a better way to know number of entries per node
+        tupleEntries1 = new TupleEntryArrayList(100, 100, spatialUtils);
+        tupleEntries2 = new TupleEntryArrayList(100, 100, spatialUtils);
+        rec = new Rectangle[4];
+        for (int i = 0; i < 4; i++) {
+            rec[i] = new Rectangle(keyFieldCount / 2);
+        }
     }
 
     @Override
@@ -101,8 +113,7 @@
     }
 
     @Override
-    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey,
-            TupleEntryArrayList entries1, TupleEntryArrayList entries2, Rectangle[] rec) throws Exception {
+    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey) throws Exception {
 
         RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
         RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
@@ -130,27 +141,27 @@
                 double UpperKey = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(j),
                         frameTuple.getFieldStart(j));
 
-                entries1.add(k, LowerKey);
-                entries2.add(k, UpperKey);
+                tupleEntries1.add(k, LowerKey);
+                tupleEntries2.add(k, UpperKey);
             }
             double LowerKey = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(i), tuple.getFieldStart(i));
             double UpperKey = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(j), tuple.getFieldStart(j));
 
-            entries1.add(-1, LowerKey);
-            entries2.add(-1, UpperKey);
+            tupleEntries1.add(-1, LowerKey);
+            tupleEntries2.add(-1, UpperKey);
 
-            entries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
-            entries2.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
+            tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
+            tupleEntries2.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
 
             double lowerMargin = 0.0, upperMargin = 0.0;
             // generate distribution
             for (int k = 1; k <= splitDistribution; ++k) {
                 int d = m - 1 + k;
 
-                generateDist(tuple, entries1, rec[0], 0, d);
-                generateDist(tuple, entries2, rec[1], 0, d);
-                generateDist(tuple, entries1, rec[2], d, getTupleCount() + 1);
-                generateDist(tuple, entries2, rec[3], d, getTupleCount() + 1);
+                generateDist(tuple, tupleEntries1, rec[0], 0, d);
+                generateDist(tuple, tupleEntries2, rec[1], 0, d);
+                generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1);
+                generateDist(tuple, tupleEntries2, rec[3], d, getTupleCount() + 1);
 
                 // calculate the margin of the distributions
                 lowerMargin += rec[0].margin() + rec[2].margin();
@@ -165,20 +176,20 @@
                 sortOrder = (lowerMargin < upperMargin) ? 0 : 2;
             }
 
-            entries1.clear();
-            entries2.clear();
+            tupleEntries1.clear();
+            tupleEntries2.clear();
         }
 
         for (int i = 0; i < getTupleCount(); ++i) {
             frameTuple.resetByTupleIndex(this, i);
             double key = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(splitAxis + sortOrder),
                     frameTuple.getFieldStart(splitAxis + sortOrder));
-            entries1.add(i, key);
+            tupleEntries1.add(i, key);
         }
         double key = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(splitAxis + sortOrder),
                 tuple.getFieldStart(splitAxis + sortOrder));
-        entries1.add(-1, key);
-        entries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
+        tupleEntries1.add(-1, key);
+        tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
 
         double minArea = Double.MAX_VALUE;
         double minOverlap = Double.MAX_VALUE;
@@ -186,8 +197,8 @@
         for (int i = 1; i <= splitDistribution; ++i) {
             int d = m - 1 + i;
 
-            generateDist(tuple, entries1, rec[0], 0, d);
-            generateDist(tuple, entries1, rec[2], d, getTupleCount() + 1);
+            generateDist(tuple, tupleEntries1, rec[0], 0, d);
+            generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1);
 
             double overlap = rec[0].overlappedArea(rec[2]);
             if (overlap < minOverlap) {
@@ -215,11 +226,11 @@
         for (int i = startIndex; i < endIndex; i++) { // TODO: is there a better
                                                       // way
             // to split the entries?
-            if (entries1.get(i).getTupleIndex() != -1) {
-                frameTuple.resetByTupleIndex(this, entries1.get(i).getTupleIndex());
+            if (tupleEntries1.get(i).getTupleIndex() != -1) {
+                frameTuple.resetByTupleIndex(this, tupleEntries1.get(i).getTupleIndex());
                 rightFrame.insert(frameTuple, cmp, -1);
                 ((UnorderedSlotManager) slotManager).modifySlot(
-                        slotManager.getSlotOff(entries1.get(i).getTupleIndex()), -1);
+                        slotManager.getSlotOff(tupleEntries1.get(i).getTupleIndex()), -1);
                 totalBytes += tupleWriter.bytesRequired(frameTuple);
                 numOfDeletedTuples++;
             } else {
@@ -256,7 +267,8 @@
                 rTreeSplitKey.getRightPageBuffer(), 0);
         rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(), 0);
 
-        entries1.clear();
+        tupleEntries1.clear();
+        tupleEntries2.clear();
         return 0;
     }
 
@@ -299,7 +311,7 @@
     }
 
     @Override
-    public boolean findBestChild(ITupleReference tuple, TupleEntryArrayList entries, MultiComparator cmp) {
+    public boolean findBestChild(ITupleReference tuple, MultiComparator cmp) {
         cmpFrameTuple.setFieldCount(cmp.getFieldCount());
         frameTuple.setFieldCount(cmp.getFieldCount());
 
@@ -313,19 +325,19 @@
             for (int i = 0; i < getTupleCount(); ++i) {
                 frameTuple.resetByTupleIndex(this, i);
                 double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
-                entries.add(i, enlargedArea);
+                tupleEntries1.add(i, enlargedArea);
                 if (enlargedArea < minEnlargedArea) {
                     minEnlargedArea = enlargedArea;
                     bestChild = i;
                 }
             }
-            if (minEnlargedArea < entries.getDoubleEpsilon() || minEnlargedArea > entries.getDoubleEpsilon()) {
+            if (minEnlargedArea < tupleEntries1.getDoubleEpsilon() || minEnlargedArea > tupleEntries1.getDoubleEpsilon()) {
                 minEnlargedArea = Double.MAX_VALUE;
                 int k;
                 if (getTupleCount() > nearMinimumOverlapFactor) {
                     // sort the entries based on their area enlargement needed
                     // to include the object
-                    entries.sort(EntriesOrder.ASCENDING, getTupleCount());
+                    tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount());
                     k = nearMinimumOverlapFactor;
                 } else {
                     k = getTupleCount();
@@ -337,7 +349,7 @@
                     double difference = 0.0;
                     for (int j = 0; j < getTupleCount(); ++j) {
                         frameTuple.resetByTupleIndex(this, j);
-                        cmpFrameTuple.resetByTupleIndex(this, entries.get(i).getTupleIndex());
+                        cmpFrameTuple.resetByTupleIndex(this, tupleEntries1.get(i).getTupleIndex());
 
                         int c = cmp.getIntCmp().compare(frameTuple.getFieldData(cmp.getKeyFieldCount()),
                                 frameTuple.getFieldStart(cmp.getKeyFieldCount()),
@@ -392,7 +404,7 @@
                 }
             }
         }
-        entries.clear();
+        tupleEntries1.clear();
 
         frameTuple.resetByTupleIndex(this, bestChild);
         if (minEnlargedArea > 0.0) {
@@ -712,13 +724,6 @@
     }
 
     @Override
-    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey)
-            throws Exception {
-        // TODO Auto-generated method stub
-        return 0;
-    }
-
-    @Override
     public void computeMBR(ISplitKey splitKey, MultiComparator cmp) {
         RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
         RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/InteriorFrameSchema.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/InteriorFrameSchema.java
new file mode 100644
index 0000000..d8801a7
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/InteriorFrameSchema.java
@@ -0,0 +1,26 @@
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.TypeTrait;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+
+public class InteriorFrameSchema {
+
+    private MultiComparator interiorCmp;
+
+    public InteriorFrameSchema(MultiComparator leafCmp) {
+        // 1 for node's pointer
+        ITypeTrait[] interiorTypeTraits = new ITypeTrait[leafCmp.getKeyFieldCount() + 1];
+        for (int i = 0; i < leafCmp.getKeyFieldCount(); i++) {
+            interiorTypeTraits[i] = new TypeTrait(leafCmp.getTypeTraits()[i].getStaticallyKnownDataLength());
+        }
+
+        // the pointer is of type int (size: 4 bytes)
+        interiorTypeTraits[leafCmp.getKeyFieldCount()] = new TypeTrait(4);
+        interiorCmp = new MultiComparator(interiorTypeTraits, leafCmp.getComparators());
+    }
+
+    public MultiComparator getInteriorCmp() {
+        return interiorCmp;
+    }
+}
\ No newline at end of file
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 ed70d1b..612ef85 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
@@ -12,8 +12,8 @@
 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.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeCursor;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrameFactory;
@@ -215,11 +215,10 @@
         fileId = -1;
     }
 
-    public RTreeOpContext createOpContext(IndexOp op, IRTreeFrame interiorFrame, IRTreeFrame leafFrame,
+    public RTreeOpContext createOpContext(IndexOp op, IRTreeFrame leafFrame, IRTreeFrame interiorFrame,
             ITreeIndexMetaDataFrame metaFrame, String threadName) {
         // TODO: figure out better tree-height hint
-        return new RTreeOpContext(op, interiorFrame, leafFrame, metaFrame, 8, interiorCmp.getKeyFieldCount() / 2,
-                threadName);
+        return new RTreeOpContext(op, leafFrame, interiorFrame, metaFrame, 8, threadName);
     }
 
     public void insert(ITupleReference tuple, RTreeOpContext ctx) throws Exception {
@@ -316,8 +315,7 @@
 
             if (!isLeaf) {
                 // checkEnlargement must be called *before* getBestChildPageId
-                boolean needsEnlargement = ctx.interiorFrame.findBestChild(ctx.getTuple(), ctx.tupleEntries1,
-                        interiorCmp);
+                boolean needsEnlargement = ctx.interiorFrame.findBestChild(ctx.getTuple(), interiorCmp);
                 int childPageId = ctx.interiorFrame.getBestChildPageId(interiorCmp);
 
                 if (needsEnlargement) {
@@ -380,9 +378,9 @@
             throws Exception {
         FrameOpSpaceStatus spaceStatus;
         if (!isLeaf) {
-            spaceStatus = ctx.interiorFrame.hasSpaceInsert(ctx.getTuple(), interiorCmp);
+            spaceStatus = ctx.interiorFrame.hasSpaceInsert(tuple, interiorCmp);
         } else {
-            spaceStatus = ctx.leafFrame.hasSpaceInsert(ctx.getTuple(), leafCmp);
+            spaceStatus = ctx.leafFrame.hasSpaceInsert(tuple, leafCmp);
         }
 
         switch (spaceStatus) {
@@ -433,8 +431,7 @@
                         rightFrame.setPage(rightNode);
                         rightFrame.initBuffer((byte) ctx.interiorFrame.getLevel());
                         rightFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
-                        ret = ctx.interiorFrame.split(rightFrame, tuple, interiorCmp, ctx.splitKey, ctx.tupleEntries1,
-                                ctx.tupleEntries2, ctx.rec);
+                        ret = ctx.interiorFrame.split(rightFrame, tuple, interiorCmp, ctx.splitKey);
                         ctx.interiorFrame.setRightPage(rightPageId);
                         rightFrame.setPageNsn(ctx.interiorFrame.getPageNsn());
                         incrementGlobalNsn();
@@ -448,8 +445,7 @@
                         rightFrame.setPage(rightNode);
                         rightFrame.initBuffer((byte) 0);
                         rightFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
-                        ret = ctx.leafFrame.split(rightFrame, tuple, leafCmp, ctx.splitKey, ctx.tupleEntries1,
-                                ctx.tupleEntries2, ctx.rec);
+                        ret = ctx.leafFrame.split(rightFrame, tuple, leafCmp, ctx.splitKey);
                         ctx.leafFrame.setRightPage(rightPageId);
                         rightFrame.setPageNsn(ctx.leafFrame.getPageNsn());
                         incrementGlobalNsn();
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 976c45e..91c6e26 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
@@ -13,33 +13,23 @@
     public IRTreeCursor cursor;
     public final ITreeIndexMetaDataFrame metaFrame;
     public final RTreeSplitKey splitKey;
-    public final SpatialUtils spatialUtils;
     public ITupleReference tuple;
-    public TupleEntryArrayList tupleEntries1; // used for split and checking enlargement
-    public TupleEntryArrayList tupleEntries2; // used for split
-    public final PathList pathList; // used to record the pageIds and pageLsns of the visited pages 
+    public final PathList pathList; // used to record the pageIds and pageLsns
+                                    // of the visited pages
     public final TraverseList traverseList; // used for traversing the tree
-    public Rectangle[] rec;
     public String threadName; // for debugging
 
-    public RTreeOpContext(IndexOp op, IRTreeFrame interiorFrame, IRTreeFrame leafFrame,
-            ITreeIndexMetaDataFrame metaFrame, int treeHeightHint, int dim, String threadName) {
+    public RTreeOpContext(IndexOp op, IRTreeFrame leafFrame, IRTreeFrame interiorFrame,
+            ITreeIndexMetaDataFrame metaFrame, int treeHeightHint, String threadName) {
         this.op = op;
         this.interiorFrame = interiorFrame;
         this.leafFrame = leafFrame;
         this.metaFrame = metaFrame;
         splitKey = new RTreeSplitKey(interiorFrame.getTupleWriter().createTupleReference(), interiorFrame
                 .getTupleWriter().createTupleReference());
-        spatialUtils = new SpatialUtils();
-        // TODO: find a better way to know number of entries per node
-        tupleEntries1 = new TupleEntryArrayList(100, 100, spatialUtils);
-        tupleEntries2 = new TupleEntryArrayList(100, 100, spatialUtils);
+
         pathList = new PathList(treeHeightHint, treeHeightHint);
         traverseList = new TraverseList(100, 100);
-        rec = new Rectangle[4];
-        for (int i = 0; i < 4; i++) {
-            rec[i] = new Rectangle(dim);
-        }
         this.threadName = threadName;
     }
 
@@ -52,12 +42,6 @@
     }
 
     public void reset() {
-        if (tupleEntries1 != null) {
-            tupleEntries1.clear();
-        }
-        if (tupleEntries2 != null) {
-            tupleEntries2.clear();
-        }
         if (pathList != null) {
             pathList.clear();
         }
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml b/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
index 2090bb2..5e76687 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
@@ -34,7 +34,7 @@
   	<dependency>
   		<groupId>edu.uci.ics.hyracks</groupId>
   		<artifactId>hyracks-control-nc</artifactId>
-  		<version>0.1.4</version>
+  		<version>0.1.5</version>
   		<scope>compile</scope>
   	</dependency>
   	<dependency>
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 6ed84f2..ad123bb 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
@@ -32,11 +32,12 @@
 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.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrameFactory;
 import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMRTreeFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.InteriorFrameSchema;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.Rectangle;
@@ -65,15 +66,6 @@
         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];
@@ -83,19 +75,21 @@
         cmps[3] = cmps[0];
 
         // declare leaf-frame-tuple fields
-        int leafFieldCount = 5;
+        int leafFieldCount = 7;
         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);
+        leafTypeTraits[4] = new TypeTrait(8);
+        leafTypeTraits[5] = new TypeTrait(4);
+        leafTypeTraits[6] = new TypeTrait(8);
 
-        MultiComparator interiorCmp = new MultiComparator(interiorTypeTraits, cmps);
         MultiComparator leafCmp = new MultiComparator(leafTypeTraits, cmps);
+        InteriorFrameSchema interiorFrameSchema = new InteriorFrameSchema(leafCmp);
 
         RTreeTypeAwareTupleWriterFactory interiorTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(
-                interiorTypeTraits);
+                interiorFrameSchema.getInteriorCmp().getTypeTraits());
         RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
 
         IRTreeFrameFactory interiorFrameFactory = new NSMRTreeFrameFactory(interiorTupleWriterFactory, keyFieldCount);
@@ -107,8 +101,8 @@
         IRTreeFrame leafFrame = leafFrameFactory.getFrame();
         IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
 
-        RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, interiorCmp,
-                leafCmp);
+        RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory,
+                interiorFrameSchema.getInteriorCmp(), leafCmp);
         rtree.create(fileId, leafFrame, metaFrame);
         rtree.open(fileId);
 
@@ -120,17 +114,21 @@
         @SuppressWarnings("rawtypes")
         ISerializerDeserializer[] recDescSers = { DoubleSerializerDeserializer.INSTANCE,
                 DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
-                DoubleSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+                DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
+                IntegerSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE };
         RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
         IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
         accessor.reset(hyracksFrame);
         FrameTupleReference tuple = new FrameTupleReference();
 
-        RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, interiorFrame, leafFrame, metaFrame,
+        RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, leafFrame, interiorFrame, metaFrame,
                 "unittest");
 
         Random rnd = new Random();
         rnd.setSeed(50);
+
+        Random rnd2 = new Random();
+        rnd2.setSeed(50);
         Stack<Integer> s = new Stack<Integer>();
         for (int i = 0; i < 10000; i++) {
 
@@ -139,7 +137,9 @@
             double p2x = rnd.nextDouble();
             double p2y = rnd.nextDouble();
 
-            int pk = rnd.nextInt();
+            double pk1 = rnd2.nextDouble();
+            int pk2 = rnd2.nextInt();
+            double pk3 = rnd2.nextDouble();
 
             tb.reset();
             DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1x, p2x), dos);
@@ -150,7 +150,11 @@
             tb.addFieldEndOffset();
             DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1y, p2y), dos);
             tb.addFieldEndOffset();
-            IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
+            DoubleSerializerDeserializer.INSTANCE.serialize(pk1, dos);
+            tb.addFieldEndOffset();
+            IntegerSerializerDeserializer.INSTANCE.serialize(pk2, dos);
+            tb.addFieldEndOffset();
+            DoubleSerializerDeserializer.INSTANCE.serialize(pk3, dos);
             tb.addFieldEndOffset();
 
             appender.reset(hyracksFrame, true);
@@ -173,7 +177,7 @@
         // rtree.printTree(leafFrame, interiorFrame, recDescSers);
         // System.out.println();
 
-        RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, interiorFrame, leafFrame, metaFrame,
+        RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame,
                 "unittest");
         ArrayList<Rectangle> results = new ArrayList<Rectangle>();
         rtree.search(s, tuple, searchOpCtx, results);
@@ -190,6 +194,13 @@
         String stats = rtree.printStats();
         print(stats);
 
+        // TreeIndexStatsGatherer statsGatherer = new
+        // TreeIndexStatsGatherer(bufferCache, freePageManager, fileId, 1);
+        // TreeIndexStats stats = statsGatherer.gatherStats(leafFrame,
+        // interiorFrame, metaFrame);
+        // String string = stats.toString();
+        // System.out.println(string);
+
         rtree.close();
         bufferCache.closeFile(fileId);
         bufferCache.close();
@@ -268,7 +279,7 @@
         accessor.reset(hyracksFrame);
         FrameTupleReference tuple = new FrameTupleReference();
 
-        RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, interiorFrame, leafFrame, metaFrame,
+        RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, leafFrame, interiorFrame, metaFrame,
                 "unittest");
 
         File datasetFile = new File("/home/salsubaiee/dataset.txt");
@@ -340,7 +351,7 @@
         // rtree.printTree(leafFrame, interiorFrame, recDescSers);
         // System.out.println();
 
-        RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, interiorFrame, leafFrame, metaFrame,
+        RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame,
                 "unittest");
 
         File querysetFile = new File("/home/salsubaiee/queryset.txt");
@@ -412,7 +423,7 @@
         // String stats = rtree.printStats();
         // print(stats);
 
-        RTreeOpContext deleteOpCtx = rtree.createOpContext(IndexOp.DELETE, interiorFrame, leafFrame, metaFrame,
+        RTreeOpContext deleteOpCtx = rtree.createOpContext(IndexOp.DELETE, leafFrame, interiorFrame, metaFrame,
                 "unittest");
 
         BufferedReader reader3 = new BufferedReader(new FileReader(datasetFile));
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
index e3d8aa4..d0d988fb 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
@@ -33,12 +33,13 @@
 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.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeCursor;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrameFactory;
 import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMRTreeFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.InteriorFrameSchema;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchCursor;
@@ -66,15 +67,6 @@
         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];
@@ -92,11 +84,11 @@
         leafTypeTraits[3] = new TypeTrait(8);
         leafTypeTraits[4] = new TypeTrait(4);
 
-        MultiComparator interiorCmp = new MultiComparator(interiorTypeTraits, cmps);
         MultiComparator leafCmp = new MultiComparator(leafTypeTraits, cmps);
+        InteriorFrameSchema interiorFrameSchema = new InteriorFrameSchema(leafCmp);
 
         RTreeTypeAwareTupleWriterFactory interiorTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(
-                interiorTypeTraits);
+                interiorFrameSchema.getInteriorCmp().getTypeTraits());
         RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
 
         IRTreeFrameFactory interiorFrameFactory = new NSMRTreeFrameFactory(interiorTupleWriterFactory, keyFieldCount);
@@ -108,8 +100,8 @@
         IRTreeFrame leafFrame = leafFrameFactory.getFrame();
         IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
 
-        RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, interiorCmp,
-                leafCmp);
+        RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory,
+                interiorFrameSchema.getInteriorCmp(), leafCmp);
         rtree.create(fileId, leafFrame, metaFrame);
         rtree.open(fileId);
 
@@ -127,7 +119,7 @@
         accessor.reset(hyracksFrame);
         FrameTupleReference tuple = new FrameTupleReference();
 
-        RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, interiorFrame, leafFrame, metaFrame,
+        RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, leafFrame, interiorFrame, metaFrame,
                 "unittest");
 
         Random rnd = new Random();
@@ -171,7 +163,7 @@
         }
 
         IRTreeCursor searchCursor = new SearchCursor(interiorFrame, leafFrame);
-        RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, interiorFrame, leafFrame, metaFrame,
+        RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame,
                 "cursortest");
         rtree.search(searchCursor, tuple, searchOpCtx);