diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
index 0014a2c..efe762c 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
@@ -19,9 +19,9 @@
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.common.api.IntArrayList;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
 
 public final class BTreeOpContext implements IndexOpContext {
     public final IndexOp op;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IntArrayList.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IntArrayList.java
deleted file mode 100644
index c232ba8..0000000
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IntArrayList.java
+++ /dev/null
@@ -1,64 +0,0 @@
-/*
- * Copyright 2009-2010 by The Regents of the University of California
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * you may obtain a copy of the License from
- * 
- *     http://www.apache.org/licenses/LICENSE-2.0
- * 
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package edu.uci.ics.hyracks.storage.am.common.api;
-
-public class IntArrayList {
-    private int[] data;
-    private int size;
-    private final int growth;
-
-    public IntArrayList(int initialCapacity, int growth) {
-        data = new int[initialCapacity];
-        size = 0;
-        this.growth = growth;
-    }
-
-    public int size() {
-        return size;
-    }
-
-    public void add(int i) {
-        if (size == data.length) {
-            int[] newData = new int[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/IntArrayList.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IntArrayList.java
similarity index 96%
rename from hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/IntArrayList.java
rename to hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IntArrayList.java
index 4be3b38..8902713 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/IntArrayList.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IntArrayList.java
@@ -13,7 +13,7 @@
  * limitations under the License.
  */
 
-package edu.uci.ics.hyracks.storage.am.rtree.impls;
+package edu.uci.ics.hyracks.storage.am.common.ophelpers;
 
 public class IntArrayList {
     private int[] data;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java
index 4b3445e..6524eb7 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java
@@ -92,10 +92,6 @@
         this.cmps = cmps;
     }
 
-    public int size() {
-        return cmps.length;
-    }
-
     public int getFieldCount() {
         return typeTraits.length;
     }
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java
index 8fe9db4..3e7fed9 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java
@@ -7,7 +7,7 @@
 import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.common.api.IntArrayList;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
 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;
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 49adc87..45ae3a1 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
@@ -6,26 +6,20 @@
 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.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 generateDist(ITupleReference tuple, TupleEntryArrayList entries, Rectangle rec, int start, int end);
 
     public void computeMBR(ISplitKey splitKey, MultiComparator cmp);
 
+    public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception;
+    
     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();
 
     public void setPageNsn(int pageNsn);
@@ -34,19 +28,6 @@
 
     public void setRightPage(int rightPage);
 
-    public int getBestChildPageId(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 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);
-
-    public void enlarge(ITupleReference tuple, MultiComparator cmp);
 }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeInteriorFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeInteriorFrame.java
new file mode 100644
index 0000000..a59e411
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeInteriorFrame.java
@@ -0,0 +1,24 @@
+package edu.uci.ics.hyracks.storage.am.rtree.api;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.TraverseList;
+
+public interface IRTreeInteriorFrame extends IRTreeFrame {
+
+    public boolean findBestChild(ITupleReference tuple, MultiComparator cmp);
+
+    public int getBestChildPageId(MultiComparator cmp);
+
+    public int getChildPageIdIfIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
+
+    public int findTupleByPointer(ITupleReference tuple, MultiComparator cmp);
+
+    public int findTupleByPointer(ITupleReference tuple, TraverseList traverseList, int parentId, MultiComparator cmp);
+
+    public void adjustKey(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
+
+    public boolean recomputeMBR(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
+
+    public void enlarge(ITupleReference tuple, MultiComparator cmp);
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeLeafFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeLeafFrame.java
new file mode 100644
index 0000000..7d66ade
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeLeafFrame.java
@@ -0,0 +1,11 @@
+package edu.uci.ics.hyracks.storage.am.rtree.api;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+
+public interface IRTreeLeafFrame extends IRTreeFrame {
+
+    public int findTupleIndex(ITupleReference tuple, MultiComparator cmp);
+
+    public boolean intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeOpHelper.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeOpHelper.java
index 61091cc..bb5d9cd 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeOpHelper.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeOpHelper.java
@@ -1,27 +1,20 @@
 package edu.uci.ics.hyracks.storage.am.rtree.dataflow;
 
 import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
-import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
-import edu.uci.ics.hyracks.api.io.FileReference;
-import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
 import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.dataflow.ITreeIndexOperatorDescriptorHelper;
 import edu.uci.ics.hyracks.storage.am.common.dataflow.IndexHelperOpenMode;
-import edu.uci.ics.hyracks.storage.am.common.dataflow.IndexRegistry;
 import edu.uci.ics.hyracks.storage.am.common.dataflow.TreeIndexOpHelper;
 import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.InteriorFrameSchema;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
-import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
 
 public class RTreeOpHelper extends TreeIndexOpHelper {
 
@@ -32,91 +25,6 @@
         super(opDesc, ctx, partition, mode);
     }
 
-    public void init() throws HyracksDataException {
-        IBufferCache bufferCache = opDesc.getStorageManager().getBufferCache(ctx);
-        IFileMapProvider fileMapProvider = opDesc.getStorageManager().getFileMapProvider(ctx);
-        IFileSplitProvider fileSplitProvider = opDesc.getTreeIndexFileSplitProvider();
-
-        FileReference f = fileSplitProvider.getFileSplits()[partition].getLocalFile();
-        boolean fileIsMapped = fileMapProvider.isMapped(f);
-
-        switch (mode) {
-
-            case OPEN: {
-                if (!fileIsMapped) {
-                    throw new HyracksDataException("Trying to open rtree from unmapped file " + f.toString());
-                }
-            }
-                break;
-
-            case CREATE:
-            case ENLIST: {
-                if (!fileIsMapped) {
-                    bufferCache.createFile(f);
-                }
-            }
-                break;
-
-        }
-
-        int fileId = fileMapProvider.lookupFileId(f);
-        try {
-            bufferCache.openFile(fileId);
-        } catch (HyracksDataException e) {
-            // revert state of buffer cache since file failed to open
-            if (!fileIsMapped) {
-                bufferCache.deleteFile(fileId);
-            }
-            throw e;
-        }
-
-        // only set indexFileId member when openFile() succeeds,
-        // otherwise deinit() will try to close the file that failed to open
-        indexFileId = fileId;
-
-        interiorFrame = opDesc.getTreeIndexInteriorFactory().createFrame();
-        leafFrame = opDesc.getTreeIndexLeafFactory().createFrame();
-
-        IndexRegistry<ITreeIndex> treeIndexRegistry = opDesc.getTreeIndexRegistryProvider().getRegistry(ctx);
-        treeIndex = treeIndexRegistry.get(indexFileId);
-        if (treeIndex == null) {
-
-            // create new tree and register it
-            treeIndexRegistry.lock();
-            try {
-                // check if tree has already been registered by another thread
-                treeIndex = treeIndexRegistry.get(indexFileId);
-                if (treeIndex == null) {
-                    // this thread should create and register the tree
-
-                    IBinaryComparator[] comparators = new IBinaryComparator[opDesc.getTreeIndexComparatorFactories().length];
-                    for (int i = 0; i < opDesc.getTreeIndexComparatorFactories().length; i++) {
-                        comparators[i] = opDesc.getTreeIndexComparatorFactories()[i].createBinaryComparator();
-                    }
-
-                    cmp = new MultiComparator(opDesc.getTreeIndexTypeTraits(), comparators);
-                    InteriorFrameSchema interiorFrameSchema = new InteriorFrameSchema(cmp);
-                    interiorCmp = interiorFrameSchema.getInteriorCmp();
-
-                    treeIndex = createTreeIndex();
-                    if (mode == IndexHelperOpenMode.CREATE) {
-                        ITreeIndexMetaDataFrame metaFrame = treeIndex.getFreePageManager().getMetaDataFrameFactory()
-                                .createFrame();
-                        try {
-                            treeIndex.create(indexFileId, leafFrame, metaFrame);
-                        } catch (Exception e) {
-                            throw new HyracksDataException(e);
-                        }
-                    }
-                    treeIndex.open(indexFileId);
-                    treeIndexRegistry.register(indexFileId, treeIndex);
-                }
-            } finally {
-                treeIndexRegistry.unlock();
-            }
-        }
-    }
-
     public ITreeIndex createTreeIndex() throws HyracksDataException {
         IBufferCache bufferCache = opDesc.getStorageManager().getBufferCache(ctx);
         ITreeIndexMetaDataFrameFactory metaDataFrameFactory = new LIFOMetaDataFrameFactory();
@@ -124,7 +32,7 @@
                 metaDataFrameFactory);
 
         return new RTree(bufferCache, freePageManager, opDesc.getTreeIndexInteriorFactory(),
-                opDesc.getTreeIndexLeafFactory(), interiorCmp, cmp);
+                opDesc.getTreeIndexLeafFactory(), cmp);
     }
     
     public ITreeIndexCursor createDiskOrderScanCursor(ITreeIndexFrame leafFrame) throws HyracksDataException {
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorDescriptor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorDescriptor.java
index 1da8730..5bb0056 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorDescriptor.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorDescriptor.java
@@ -25,10 +25,10 @@
     public RTreeSearchOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc,
             IStorageManagerInterface storageManager, IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider,
             IFileSplitProvider fileSplitProvider, ITreeIndexFrameFactory interiorFrameFactory,
-            ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] leafTypeTraits,
+            ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] typeTraits,
             IBinaryComparatorFactory[] comparatorFactories, int[] keyFields, ITreeIndexOpHelperFactory opHelperFactory) {
         super(spec, 1, 1, recDesc, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
-                leafFrameFactory, leafTypeTraits, comparatorFactories, opHelperFactory);
+                leafFrameFactory, typeTraits, comparatorFactories, opHelperFactory);
         this.keyFields = keyFields;
     }
 
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java
index c1b6df3..a98157e 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java
@@ -22,7 +22,8 @@
 import edu.uci.ics.hyracks.storage.am.common.dataflow.TreeIndexOpHelper;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSearchCursor;
@@ -40,8 +41,7 @@
     private RTree rtree;
     private PermutingFrameTupleReference searchKey;
     private SearchPredicate searchPred;
-    private MultiComparator interiorCmp;
-    private MultiComparator leafCmp;
+    private MultiComparator cmp;
     private ITreeIndexCursor cursor;
     private ITreeIndexFrame interiorFrame;
     private ITreeIndexFrame leafFrame;
@@ -69,27 +69,26 @@
 
         interiorFrame = opDesc.getTreeIndexInteriorFactory().createFrame();
         leafFrame = opDesc.getTreeIndexLeafFactory().createFrame();
-        cursor = new RTreeSearchCursor((IRTreeFrame) interiorFrame, (IRTreeFrame) leafFrame);
+        cursor = new RTreeSearchCursor((IRTreeInteriorFrame) interiorFrame, (IRTreeLeafFrame) leafFrame);
 
         try {
 
             treeIndexOpHelper.init();
             rtree = (RTree) treeIndexOpHelper.getTreeIndex();
 
-            int keySearchFields = rtree.getLeafCmp().getComparators().length;
+            int keySearchFields = rtree.getCmp().getComparators().length;
 
             IBinaryComparator[] keySearchComparators = new IBinaryComparator[keySearchFields];
             for (int i = 0; i < keySearchFields; i++) {
-                keySearchComparators[i] = rtree.getLeafCmp().getComparators()[i];
+                keySearchComparators[i] = rtree.getCmp().getComparators()[i];
             }
-            interiorCmp = new MultiComparator(rtree.getInteriorCmp().getTypeTraits(), keySearchComparators);
-            leafCmp = new MultiComparator(rtree.getLeafCmp().getTypeTraits(), keySearchComparators);
+            cmp = new MultiComparator(rtree.getCmp().getTypeTraits(), keySearchComparators);
 
-            searchPred = new SearchPredicate(searchKey, interiorCmp, leafCmp);
+            searchPred = new SearchPredicate(searchKey, cmp);
             accessor = new FrameTupleAccessor(treeIndexOpHelper.getHyracksStageletContext().getFrameSize(), recDesc);
 
             writeBuffer = treeIndexOpHelper.getHyracksStageletContext().allocateFrame();
-            tb = new ArrayTupleBuilder(rtree.getLeafCmp().getFieldCount());
+            tb = new ArrayTupleBuilder(rtree.getCmp().getFieldCount());
             dos = tb.getDataOutput();
             appender = new FrameTupleAppender(treeIndexOpHelper.getHyracksStageletContext().getFrameSize());
             appender.reset(writeBuffer, true);
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMFrame.java
index 6387264..9edb815 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMFrame.java
@@ -4,37 +4,34 @@
 
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
-import edu.uci.ics.hyracks.dataflow.common.data.marshalling.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.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;
 import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriter;
 
-public class NSMFrame extends TreeIndexNSMFrame implements IRTreeFrame {
+public abstract class NSMFrame extends TreeIndexNSMFrame implements IRTreeFrame {
     protected static final int pageNsnOff = smFlagOff + 1;
     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;
+    protected ITreeIndexTupleReference[] tuples;
+    protected ITreeIndexTupleReference cmpFrameTuple;
+    protected final SpatialUtils spatialUtils;
+    protected TupleEntryArrayList tupleEntries1; // used for split and checking
+                                                 // enlargement
+    protected TupleEntryArrayList tupleEntries2; // used for split
+    protected Rectangle[] rec;
 
-    private static final double splitFactor = 0.4;
-    private static final int nearMinimumOverlapFactor = 32;
+    protected static final double splitFactor = 0.4;
+    protected static final int nearMinimumOverlapFactor = 32;
 
     public NSMFrame(ITreeIndexTupleWriter tupleWriter, int keyFieldCount) {
         super(tupleWriter, new UnorderedSlotManager());
@@ -90,7 +87,7 @@
         buf.putInt(rightPageOff, rightPage);
     }
 
-    private ITreeIndexTupleReference[] getTuples() {
+    protected ITreeIndexTupleReference[] getTuples() {
         return tuples;
     }
 
@@ -112,167 +109,7 @@
         return ret;
     }
 
-    @Override
-    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey) throws Exception {
-
-        RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
-        RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
-        RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame = ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
-        rightFrame.setPageTupleFieldCount(cmp.getFieldCount());
-        frameTuple.setFieldCount(cmp.getFieldCount());
-
-        // calculations are based on the R*-tree paper
-        int m = (int) Math.floor((getTupleCount() + 1) * splitFactor);
-        int splitDistribution = getTupleCount() - (2 * m) + 2;
-
-        // to calculate the minimum margin in order to pick the split axis
-        double minMargin = Double.MAX_VALUE;
-        int splitAxis = 0, sortOrder = 0;
-
-        int maxFieldPos = cmp.getKeyFieldCount() / 2;
-        for (int i = 0; i < maxFieldPos; i++) {
-            int j = maxFieldPos + i;
-            for (int k = 0; k < getTupleCount(); ++k) {
-
-                frameTuple.resetByTupleIndex(this, k);
-
-                double LowerKey = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(i),
-                        frameTuple.getFieldStart(i));
-                double UpperKey = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(j),
-                        frameTuple.getFieldStart(j));
-
-                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));
-
-            tupleEntries1.add(-1, LowerKey);
-            tupleEntries2.add(-1, UpperKey);
-
-            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, 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();
-                upperMargin += rec[1].margin() + rec[3].margin();
-            }
-            double margin = Math.min(lowerMargin, upperMargin);
-
-            // store minimum margin as split axis
-            if (margin < minMargin) {
-                minMargin = margin;
-                splitAxis = i;
-                sortOrder = (lowerMargin < upperMargin) ? 0 : 2;
-            }
-
-            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));
-            tupleEntries1.add(i, key);
-        }
-        double key = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(splitAxis + sortOrder),
-                tuple.getFieldStart(splitAxis + sortOrder));
-        tupleEntries1.add(-1, key);
-        tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
-
-        double minArea = Double.MAX_VALUE;
-        double minOverlap = Double.MAX_VALUE;
-        int splitPoint = 0;
-        for (int i = 1; i <= splitDistribution; ++i) {
-            int d = m - 1 + i;
-
-            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) {
-                splitPoint = d;
-                minOverlap = overlap;
-                minArea = rec[0].area() + rec[2].area();
-            } else if (overlap == minOverlap) {
-                double area = rec[0].area() + rec[2].area();
-                if (area < minArea) {
-                    splitPoint = d;
-                    minArea = area;
-                }
-            }
-        }
-        int startIndex, endIndex;
-        if (splitPoint < (getTupleCount() + 1) / 2) {
-            startIndex = 0;
-            endIndex = splitPoint;
-        } else {
-            startIndex = splitPoint;
-            endIndex = (getTupleCount() + 1);
-        }
-        boolean tupleInserted = false;
-        int totalBytes = 0, numOfDeletedTuples = 0;
-        for (int i = startIndex; i < endIndex; i++) { // TODO: is there a better
-                                                      // way
-            // to split the entries?
-            if (tupleEntries1.get(i).getTupleIndex() != -1) {
-                frameTuple.resetByTupleIndex(this, tupleEntries1.get(i).getTupleIndex());
-                rightFrame.insert(frameTuple, cmp, -1);
-                ((UnorderedSlotManager) slotManager).modifySlot(
-                        slotManager.getSlotOff(tupleEntries1.get(i).getTupleIndex()), -1);
-                totalBytes += tupleWriter.bytesRequired(frameTuple);
-                numOfDeletedTuples++;
-            } else {
-                rightFrame.insert(tuple, cmp, -1);
-                tupleInserted = true;
-            }
-        }
-
-        ((UnorderedSlotManager) slotManager).deleteEmptySlots();
-
-        // maintain space information
-        buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + totalBytes
-                + (slotManager.getSlotSize() * numOfDeletedTuples));
-
-        // compact both pages
-        rightFrame.compact(cmp);
-        compact(cmp);
-
-        if (!tupleInserted) {
-            insert(tuple, cmp, -1);
-        }
-
-        int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
-        frameTuple.resetByTupleOffset(buf, tupleOff);
-        int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
-
-        splitKey.initData(splitKeySize);
-        this.adjustMBR(tuples, cmp);
-        rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
-        rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(), 0);
-
-        ((IRTreeFrame) rightFrame).adjustMBR(((NSMFrame) rightFrame).getTuples(), cmp);
-        rTreeTupleWriterRightFrame.writeTupleFields(((NSMFrame) rightFrame).getTuples(), 0,
-                rTreeSplitKey.getRightPageBuffer(), 0);
-        rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(), 0);
-
-        tupleEntries1.clear();
-        tupleEntries2.clear();
-        return 0;
-    }
-
-    private void generateDist(ITupleReference tuple, TupleEntryArrayList entries, Rectangle rec, int start, int end) {
+    public void generateDist(ITupleReference tuple, TupleEntryArrayList entries, Rectangle rec, int start, int end) {
         int j = 0;
         while (entries.get(j).getTupleIndex() == -1) {
             j++;
@@ -304,333 +141,8 @@
     public ITreeIndexTupleReference createTupleReference() {
         return tupleWriter.createTupleReference();
     }
-    
-    @Override
-    public int getBestChildPageId(MultiComparator cmp) {
-        return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
-    }
 
-    @Override
-    public boolean findBestChild(ITupleReference tuple, MultiComparator cmp) {
-        cmpFrameTuple.setFieldCount(cmp.getFieldCount());
-        frameTuple.setFieldCount(cmp.getFieldCount());
-
-        int bestChild = 0;
-        double minEnlargedArea = Double.MAX_VALUE;
-
-        // the children pointers in the node point to leaves
-        if (getLevel() == 1) {
-            // find least overlap enlargement, use minimum enlarged area to
-            // break tie, if tie still exists use minimum area to break it
-            for (int i = 0; i < getTupleCount(); ++i) {
-                frameTuple.resetByTupleIndex(this, i);
-                double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
-                tupleEntries1.add(i, enlargedArea);
-                if (enlargedArea < minEnlargedArea) {
-                    minEnlargedArea = enlargedArea;
-                    bestChild = i;
-                }
-            }
-            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
-                    tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount());
-                    k = nearMinimumOverlapFactor;
-                } else {
-                    k = getTupleCount();
-                }
-
-                double minOverlap = Double.MAX_VALUE;
-                int id = 0;
-                for (int i = 0; i < k; ++i) {
-                    double difference = 0.0;
-                    for (int j = 0; j < getTupleCount(); ++j) {
-                        frameTuple.resetByTupleIndex(this, j);
-                        cmpFrameTuple.resetByTupleIndex(this, tupleEntries1.get(i).getTupleIndex());
-
-                        int c = cmp.getIntCmp().compare(frameTuple.getFieldData(cmp.getKeyFieldCount()),
-                                frameTuple.getFieldStart(cmp.getKeyFieldCount()),
-                                frameTuple.getFieldLength(cmp.getKeyFieldCount()),
-                                cmpFrameTuple.getFieldData(cmp.getKeyFieldCount()),
-                                cmpFrameTuple.getFieldStart(cmp.getKeyFieldCount()),
-                                cmpFrameTuple.getFieldLength(cmp.getKeyFieldCount()));
-                        if (c != 0) {
-                            double intersection = overlappedArea(frameTuple, tuple, cmpFrameTuple, cmp);
-                            if (intersection != 0.0) {
-                                difference += intersection - overlappedArea(frameTuple, null, cmpFrameTuple, cmp);
-                            }
-                        } else {
-                            id = j;
-                        }
-                    }
-
-                    double enlargedArea = enlargedArea(cmpFrameTuple, tuple, cmp);
-                    if (difference < minOverlap) {
-                        minOverlap = difference;
-                        minEnlargedArea = enlargedArea;
-                        bestChild = id;
-                    } else if (difference == minOverlap) {
-                        if (enlargedArea < minEnlargedArea) {
-                            minEnlargedArea = enlargedArea;
-                            bestChild = id;
-                        } else if (enlargedArea == minEnlargedArea) {
-                            double area = area(cmpFrameTuple, cmp);
-                            frameTuple.resetByTupleIndex(this, bestChild);
-                            double minArea = area(frameTuple, cmp);
-                            if (area < minArea) {
-                                bestChild = id;
-                            }
-                        }
-                    }
-                }
-            }
-        } else { // find minimum enlarged area, use minimum area to break tie
-            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 minArea = area(frameTuple, cmp);
-                    if (area < minArea) {
-                        bestChild = i;
-                    }
-                }
-            }
-        }
-        tupleEntries1.clear();
-
-        frameTuple.resetByTupleIndex(this, bestChild);
-        if (minEnlargedArea > 0.0) {
-            return true;
-        } else {
-            return false;
-        }
-    }
-
-    private 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;
-    }
-
-    private double overlappedArea(ITupleReference tuple1, ITupleReference tupleToBeInserted, ITupleReference tuple2,
-            MultiComparator cmp) {
-        double area = 1.0;
-        double f1, f2;
-
-        int maxFieldPos = cmp.getKeyFieldCount() / 2;
-        for (int i = 0; i < maxFieldPos; i++) {
-            int j = maxFieldPos + i;
-            double pHigh1, pLow1;
-            if (tupleToBeInserted != null) {
-                int c = cmp.getComparators()[i].compare(tuple1.getFieldData(i), tuple1.getFieldStart(i),
-                        tuple1.getFieldLength(i), tupleToBeInserted.getFieldData(i),
-                        tupleToBeInserted.getFieldStart(i), tupleToBeInserted.getFieldLength(i));
-                if (c < 0) {
-                    pLow1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(i), tuple1.getFieldStart(i));
-                } else {
-                    pLow1 = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(i),
-                            tupleToBeInserted.getFieldStart(i));
-                }
-
-                c = cmp.getComparators()[j].compare(tuple1.getFieldData(j), tuple1.getFieldStart(j),
-                        tuple1.getFieldLength(j), tupleToBeInserted.getFieldData(j),
-                        tupleToBeInserted.getFieldStart(j), tupleToBeInserted.getFieldLength(j));
-                if (c > 0) {
-                    pHigh1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(j), tuple1.getFieldStart(j));
-                } else {
-                    pHigh1 = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(j),
-                            tupleToBeInserted.getFieldStart(j));
-                }
-            } else {
-                pLow1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(i), tuple1.getFieldStart(i));
-                pHigh1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(j), tuple1.getFieldStart(j));
-            }
-
-            double pLow2 = DoubleSerializerDeserializer.getDouble(tuple2.getFieldData(i), tuple2.getFieldStart(i));
-            double pHigh2 = DoubleSerializerDeserializer.getDouble(tuple2.getFieldData(j), tuple2.getFieldStart(j));
-
-            if (pLow1 > pHigh2 || pHigh1 < pLow2) {
-                return 0.0;
-            }
-
-            f1 = Math.max(pLow1, pLow2);
-            f2 = Math.min(pHigh1, pHigh2);
-            area *= f2 - f1;
-        }
-        return area;
-    }
-
-    private 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;
-    }
-
-    @Override
-    public void enlarge(ITupleReference tuple, MultiComparator cmp) {
-        int maxFieldPos = cmp.getKeyFieldCount() / 2;
-        for (int i = 0; i < maxFieldPos; i++) {
-            int j = maxFieldPos + i;
-            int c = cmp.getComparators()[i].compare(frameTuple.getFieldData(i), frameTuple.getFieldStart(i),
-                    frameTuple.getFieldLength(i), tuple.getFieldData(i), tuple.getFieldStart(i),
-                    tuple.getFieldLength(i));
-            if (c > 0) {
-                System.arraycopy(tuple.getFieldData(i), tuple.getFieldStart(i), frameTuple.getFieldData(i),
-                        frameTuple.getFieldStart(i), tuple.getFieldLength(i));
-            }
-            c = cmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
-                    frameTuple.getFieldLength(j), tuple.getFieldData(j), tuple.getFieldStart(j),
-                    tuple.getFieldLength(j));
-            if (c < 0) {
-                System.arraycopy(tuple.getFieldData(j), tuple.getFieldStart(j), frameTuple.getFieldData(j),
-                        frameTuple.getFieldStart(j), tuple.getFieldLength(j));
-            }
-        }
-    }
-
-    @Override
-    public void adjustKey(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
-        frameTuple.setFieldCount(cmp.getFieldCount());
-        if (tupleIndex == -1) {
-            tupleIndex = findTupleByPointer(tuple, cmp);
-        }
-        if (tupleIndex != -1) {
-            tupleWriter.writeTuple(tuple, buf, getTupleOffset(tupleIndex));
-        }
-    }
-
-    @Override
-    public int findTupleIndex(ITupleReference tuple, MultiComparator cmp) {
-        frameTuple.setFieldCount(cmp.getFieldCount());
-        return slotManager.findTupleIndex(tuple, frameTuple, cmp, null, null);
-    }
-
-    @Override
-    public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception {
-        frameTuple.setFieldCount(cmp.getFieldCount());
-        slotManager.insertSlot(-1, buf.getInt(freeSpaceOff));
-        int bytesWritten = tupleWriter.writeTuple(tuple, buf, buf.getInt(freeSpaceOff));
-
-        buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
-        buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + bytesWritten);
-        buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - bytesWritten - slotManager.getSlotSize());
-    }
-
-    @Override
-    public void delete(int tupleIndex, MultiComparator cmp) throws Exception {
-        frameTuple.setFieldCount(cmp.getFieldCount());
-        int slotOff = slotManager.getSlotOff(tupleIndex);
-
-        int tupleOff = slotManager.getTupleOff(slotOff);
-        frameTuple.resetByTupleOffset(buf, tupleOff);
-        int tupleSize = tupleWriter.bytesRequired(frameTuple);
-
-        // perform deletion (we just do a memcpy to overwrite the slot)
-        int slotStartOff = slotManager.getSlotEndOff();
-        int length = slotOff - slotStartOff;
-        System.arraycopy(buf.array(), slotStartOff, buf.array(), slotStartOff + slotManager.getSlotSize(), length);
-
-        // maintain space information
-        buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
-        buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + tupleSize + slotManager.getSlotSize());
-    }
-
-    @Override
-    public int findTupleByPointer(int pageId, MultiComparator cmp) {
-        frameTuple.setFieldCount(cmp.getFieldCount());
-        for (int i = 0; i < getTupleCount(); i++) {
-            frameTuple.resetByTupleIndex(this, i);
-            int id = IntegerSerializerDeserializer.getInt(frameTuple.getFieldData(cmp.getKeyFieldCount()),
-                    frameTuple.getFieldStart(cmp.getKeyFieldCount()));
-            if (id == pageId) {
-                return i;
-            }
-        }
-        return -1;
-    }
-
-    @Override
-    public int findTupleByPointer(ITupleReference tuple, MultiComparator cmp) {
-        frameTuple.setFieldCount(cmp.getFieldCount());
-        for (int i = 0; i < getTupleCount(); i++) {
-            frameTuple.resetByTupleIndex(this, i);
-            int c = cmp.getIntCmp().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) {
-                return i;
-            }
-        }
-        return -1;
-    }
-
-    @Override
-    public int findTupleByPointer(ITupleReference tuple, TraverseList traverseList, int parentIndex, MultiComparator cmp) {
-        frameTuple.setFieldCount(cmp.getFieldCount());
-        for (int i = 0; i < getTupleCount(); i++) {
-            frameTuple.resetByTupleIndex(this, i);
-            int c = cmp.getIntCmp().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) {
-                return i;
-            } else {
-                int pageId = IntegerSerializerDeserializer.getInt(frameTuple.getFieldData(cmp.getKeyFieldCount()),
-                        frameTuple.getFieldStart(cmp.getKeyFieldCount()));
-                traverseList.add(pageId, -1, parentIndex);
-            }
-        }
-        return -1;
-    }
-
-    @Override
-    public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
-        for (int i = 0; i < tuples.length; i++) {
-            tuples[i].setFieldCount(cmp.getKeyFieldCount());
-            tuples[i].resetByTupleIndex(this, 0);
-        }
-
+    public void adjustMBRImpl(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
         int maxFieldPos = cmp.getKeyFieldCount() / 2;
         for (int i = 1; i < getTupleCount(); i++) {
             frameTuple.resetByTupleIndex(this, i);
@@ -653,77 +165,6 @@
     }
 
     @Override
-    public int getChildPageIdIfIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
-        frameTuple.setFieldCount(cmp.getFieldCount());
-        frameTuple.resetByTupleIndex(this, tupleIndex);
-        int maxFieldPos = cmp.getKeyFieldCount() / 2;
-        for (int i = 0; i < maxFieldPos; i++) {
-            int j = maxFieldPos + i;
-            int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
-                    tuple.getFieldLength(i), frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
-                    frameTuple.getFieldLength(j));
-            if (c > 0) {
-                return -1;
-            }
-            c = cmp.getComparators()[i].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
-                    frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
-
-            if (c < 0) {
-                return -1;
-            }
-        }
-        return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
-    }
-
-    @Override
-    public boolean intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
-        frameTuple.setFieldCount(cmp.getFieldCount());
-        frameTuple.resetByTupleIndex(this, tupleIndex);
-        int maxFieldPos = cmp.getKeyFieldCount() / 2;
-        for (int i = 0; i < maxFieldPos; i++) {
-            int j = maxFieldPos + i;
-            int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
-                    tuple.getFieldLength(i), frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
-                    frameTuple.getFieldLength(j));
-            if (c > 0) {
-                return false;
-            }
-            c = cmp.getComparators()[i].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
-                    frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
-
-            if (c < 0) {
-                return false;
-            }
-        }
-        return true;
-    }
-    
-    @Override
-    public Rectangle checkIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
-        frameTuple.setFieldCount(cmp.getFieldCount());
-        frameTuple.resetByTupleIndex(this, tupleIndex);
-        int maxFieldPos = cmp.getKeyFieldCount() / 2;
-        for (int i = 0; i < maxFieldPos; i++) {
-            int j = maxFieldPos + i;
-            int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
-                    tuple.getFieldLength(i), frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
-                    frameTuple.getFieldLength(j));
-            if (c > 0) {
-                return null;
-            }
-            c = cmp.getComparators()[i].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
-                    frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
-
-            if (c < 0) {
-                return null;
-            }
-        }
-        Rectangle rec = new Rectangle(maxFieldPos);
-        rec.set(frameTuple);
-        return rec;
-    }
-
-    @Override
     public void computeMBR(ISplitKey splitKey, MultiComparator cmp) {
         RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
         RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
@@ -740,31 +181,6 @@
     }
 
     @Override
-    public boolean recomputeMBR(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
-        frameTuple.setFieldCount(cmp.getFieldCount());
-        frameTuple.resetByTupleIndex(this, tupleIndex);
-
-        int maxFieldPos = cmp.getKeyFieldCount() / 2;
-        for (int i = 0; i < maxFieldPos; i++) {
-            int j = maxFieldPos + i;
-            int c = cmp.getComparators()[i].compare(frameTuple.getFieldData(i), frameTuple.getFieldStart(i),
-                    frameTuple.getFieldLength(i), tuple.getFieldData(i), tuple.getFieldStart(i),
-                    tuple.getFieldLength(i));
-            if (c != 0) {
-                return true;
-            }
-            c = cmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
-                    frameTuple.getFieldLength(j), tuple.getFieldData(j), tuple.getFieldStart(j),
-                    tuple.getFieldLength(j));
-
-            if (c != 0) {
-                return true;
-            }
-        }
-        return false;
-    }
-
-    @Override
     public int getPageHeaderSize() {
         return rightPageOff;
     }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMFrameFactory.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMFrameFactory.java
deleted file mode 100644
index 0b84a77..0000000
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMFrameFactory.java
+++ /dev/null
@@ -1,22 +0,0 @@
-package edu.uci.ics.hyracks.storage.am.rtree.frames;
-
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
-import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
-
-public class NSMFrameFactory implements ITreeIndexFrameFactory {
-
-    private static final long serialVersionUID = 1L;
-    private ITreeIndexTupleWriterFactory tupleWriterFactory;
-    private int keyFieldCount;
-
-    public NSMFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory, int keyFieldCount) {
-        this.tupleWriterFactory = tupleWriterFactory;
-        this.keyFieldCount = keyFieldCount;
-    }
-
-    @Override
-    public IRTreeFrame createFrame() {
-        return new NSMFrame(tupleWriterFactory.createTupleWriter(), keyFieldCount);
-    }
-}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMInteriorFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMInteriorFrame.java
new file mode 100644
index 0000000..7cd8bc3
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMInteriorFrame.java
@@ -0,0 +1,633 @@
+package edu.uci.ics.hyracks.storage.am.rtree.frames;
+
+import java.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.util.ArrayList;
+import java.util.Collections;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.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.FrameOpSpaceStatus;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.SlotOffTupleOff;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
+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.TraverseList;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.UnorderedSlotManager;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriter;
+
+public class NSMInteriorFrame extends NSMFrame implements IRTreeInteriorFrame {
+
+    private static final int childPtrSize = 4;
+
+    public NSMInteriorFrame(ITreeIndexTupleWriter tupleWriter, int keyFieldCount) {
+        super(tupleWriter, keyFieldCount);
+    }
+
+    @Override
+    public String printKeys(MultiComparator cmp, ISerializerDeserializer[] fields) throws HyracksDataException {
+        StringBuilder strBuilder = new StringBuilder();
+        int tupleCount = buf.getInt(tupleCountOff);
+        frameTuple.setFieldCount(cmp.getKeyFieldCount());
+        for (int i = 0; i < tupleCount; i++) {
+            frameTuple.resetByTupleIndex(this, i);
+            for (int j = 0; j < cmp.getKeyFieldCount(); j++) {
+                ByteArrayInputStream inStream = new ByteArrayInputStream(frameTuple.getFieldData(j),
+                        frameTuple.getFieldStart(j), frameTuple.getFieldLength(j));
+                DataInput dataIn = new DataInputStream(inStream);
+                Object o = fields[j].deserialize(dataIn);
+                strBuilder.append(o.toString() + " ");
+            }
+            strBuilder.append(" | ");
+        }
+        strBuilder.append("\n");
+        return strBuilder.toString();
+    }
+
+    @Override
+    public boolean findBestChild(ITupleReference tuple, MultiComparator cmp) {
+        cmpFrameTuple.setFieldCount(cmp.getKeyFieldCount());
+        frameTuple.setFieldCount(cmp.getKeyFieldCount());
+
+        int bestChild = 0;
+        double minEnlargedArea = Double.MAX_VALUE;
+
+        // the children pointers in the node point to leaves
+        if (getLevel() == 1) {
+            // find least overlap enlargement, use minimum enlarged area to
+            // break tie, if tie still exists use minimum area to break it
+            for (int i = 0; i < getTupleCount(); ++i) {
+                frameTuple.resetByTupleIndex(this, i);
+                double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
+                tupleEntries1.add(i, enlargedArea);
+                if (enlargedArea < minEnlargedArea) {
+                    minEnlargedArea = enlargedArea;
+                    bestChild = i;
+                }
+            }
+            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
+                    tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount());
+                    k = nearMinimumOverlapFactor;
+                } else {
+                    k = getTupleCount();
+                }
+
+                double minOverlap = Double.MAX_VALUE;
+                int id = 0;
+                for (int i = 0; i < k; ++i) {
+                    double difference = 0.0;
+                    for (int j = 0; j < getTupleCount(); ++j) {
+                        frameTuple.resetByTupleIndex(this, j);
+                        cmpFrameTuple.resetByTupleIndex(this, tupleEntries1.get(i).getTupleIndex());
+
+                        int c = pointerCmp(frameTuple, cmpFrameTuple, cmp);
+                        if (c != 0) {
+                            double intersection = overlappedArea(frameTuple, tuple, cmpFrameTuple, cmp);
+                            if (intersection != 0.0) {
+                                difference += intersection - overlappedArea(frameTuple, null, cmpFrameTuple, cmp);
+                            }
+                        } else {
+                            id = j;
+                        }
+                    }
+
+                    double enlargedArea = enlargedArea(cmpFrameTuple, tuple, cmp);
+                    if (difference < minOverlap) {
+                        minOverlap = difference;
+                        minEnlargedArea = enlargedArea;
+                        bestChild = id;
+                    } else if (difference == minOverlap) {
+                        if (enlargedArea < minEnlargedArea) {
+                            minEnlargedArea = enlargedArea;
+                            bestChild = id;
+                        } else if (enlargedArea == minEnlargedArea) {
+                            double area = area(cmpFrameTuple, cmp);
+                            frameTuple.resetByTupleIndex(this, bestChild);
+                            double minArea = area(frameTuple, cmp);
+                            if (area < minArea) {
+                                bestChild = id;
+                            }
+                        }
+                    }
+                }
+            }
+        } else { // find minimum enlarged area, use minimum area to break tie
+            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 minArea = area(frameTuple, cmp);
+                    if (area < minArea) {
+                        bestChild = i;
+                    }
+                }
+            }
+        }
+        tupleEntries1.clear();
+
+        frameTuple.resetByTupleIndex(this, bestChild);
+        if (minEnlargedArea > 0.0) {
+            return true;
+        } else {
+            return false;
+        }
+    }
+    
+    @Override
+    public int getBestChildPageId(MultiComparator cmp) {
+        return buf.getInt(getChildPointerOff(frameTuple, cmp));
+    }
+
+    @Override
+    public int findTupleByPointer(ITupleReference tuple, MultiComparator cmp) {
+        frameTuple.setFieldCount(cmp.getKeyFieldCount());
+        for (int i = 0; i < getTupleCount(); i++) {
+            frameTuple.resetByTupleIndex(this, i);
+            int c = pointerCmp(frameTuple, tuple, cmp);
+            if (c == 0) {
+                return i;
+            }
+        }
+        return -1;
+    }
+    
+    @Override
+    public int getChildPageIdIfIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
+        frameTuple.setFieldCount(cmp.getKeyFieldCount());
+        frameTuple.resetByTupleIndex(this, tupleIndex);
+        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        for (int i = 0; i < maxFieldPos; i++) {
+            int j = maxFieldPos + i;
+            int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
+                    tuple.getFieldLength(i), frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+                    frameTuple.getFieldLength(j));
+            if (c > 0) {
+                return -1;
+            }
+            c = cmp.getComparators()[i].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
+                    frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
+            if (c < 0) {
+                return -1;
+            }
+        }
+        // return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
+        return buf.getInt(getChildPointerOff(frameTuple, cmp));
+    }
+
+    @Override
+    public int findTupleByPointer(ITupleReference tuple, TraverseList traverseList, int parentIndex, MultiComparator cmp) {
+        frameTuple.setFieldCount(cmp.getKeyFieldCount());
+        for (int i = 0; i < getTupleCount(); i++) {
+            frameTuple.resetByTupleIndex(this, i);
+
+            int c = pointerCmp(frameTuple, tuple, cmp);
+            if (c == 0) {
+                return i;
+            } else {
+                int pageId = IntegerSerializerDeserializer.getInt(frameTuple.getFieldData(cmp.getKeyFieldCount() - 1),
+                        getChildPointerOff(frameTuple, cmp));
+                traverseList.add(pageId, -1, parentIndex);
+            }
+        }
+        return -1;
+    }
+
+    @Override
+    public boolean compact(MultiComparator cmp) {
+        resetSpaceParams();
+        frameTuple.setFieldCount(cmp.getKeyFieldCount());
+
+        int tupleCount = buf.getInt(tupleCountOff);
+        int freeSpace = buf.getInt(freeSpaceOff);
+
+        ArrayList<SlotOffTupleOff> sortedTupleOffs = new ArrayList<SlotOffTupleOff>();
+        sortedTupleOffs.ensureCapacity(tupleCount);
+        for (int i = 0; i < tupleCount; i++) {
+            int slotOff = slotManager.getSlotOff(i);
+            int tupleOff = slotManager.getTupleOff(slotOff);
+            sortedTupleOffs.add(new SlotOffTupleOff(i, slotOff, tupleOff));
+        }
+        Collections.sort(sortedTupleOffs);
+
+        for (int i = 0; i < sortedTupleOffs.size(); i++) {
+            int tupleOff = sortedTupleOffs.get(i).tupleOff;
+            frameTuple.resetByTupleOffset(buf, tupleOff);
+
+            int tupleEndOff = frameTuple.getFieldStart(frameTuple.getFieldCount() - 1)
+                    + frameTuple.getFieldLength(frameTuple.getFieldCount() - 1);
+            int tupleLength = tupleEndOff - tupleOff + childPtrSize;
+            System.arraycopy(buf.array(), tupleOff, buf.array(), freeSpace, tupleLength);
+
+            slotManager.setSlot(sortedTupleOffs.get(i).slotOff, freeSpace);
+            freeSpace += tupleLength;
+        }
+
+        buf.putInt(freeSpaceOff, freeSpace);
+        buf.putInt(totalFreeSpaceOff, buf.capacity() - freeSpace - tupleCount * slotManager.getSlotSize());
+
+        return false;
+    }
+
+    @Override
+    public FrameOpSpaceStatus hasSpaceInsert(ITupleReference tuple, MultiComparator cmp) {
+        int bytesRequired = tupleWriter.bytesRequired(tuple) + childPtrSize; // for
+                                                                             // the
+                                                                             // child
+                                                                             // pointer
+        if (bytesRequired + slotManager.getSlotSize() <= buf.capacity() - buf.getInt(freeSpaceOff)
+                - (buf.getInt(tupleCountOff) * slotManager.getSlotSize()))
+            return FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
+        else if (bytesRequired + slotManager.getSlotSize() <= buf.getInt(totalFreeSpaceOff))
+            return FrameOpSpaceStatus.SUFFICIENT_SPACE;
+        else
+            return FrameOpSpaceStatus.INSUFFICIENT_SPACE;
+    }
+
+    
+
+    @Override
+    public void adjustKey(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
+        frameTuple.setFieldCount(cmp.getKeyFieldCount());
+        if (tupleIndex == -1) {
+            tupleIndex = findTupleByPointer(tuple, cmp);
+        }
+        if (tupleIndex != -1) {
+            tupleWriter.writeTuple(tuple, buf, getTupleOffset(tupleIndex));
+        }
+    }
+
+    private int pointerCmp(ITupleReference tupleA, ITupleReference tupleB, MultiComparator cmp) {
+        return cmp.getIntCmp().compare(tupleA.getFieldData(cmp.getKeyFieldCount() - 1),
+                getChildPointerOff(tupleA, cmp), childPtrSize, tupleB.getFieldData(cmp.getKeyFieldCount() - 1),
+                getChildPointerOff(tupleB, cmp), childPtrSize);
+    }
+
+    @Override
+    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey)
+            throws Exception {
+
+        rightFrame.setPageTupleFieldCount(cmp.getKeyFieldCount());
+        frameTuple.setFieldCount(cmp.getKeyFieldCount());
+
+        RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
+        RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
+        RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame = ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
+
+        // calculations are based on the R*-tree paper
+        int m = (int) Math.floor((getTupleCount() + 1) * splitFactor);
+        int splitDistribution = getTupleCount() - (2 * m) + 2;
+
+        // to calculate the minimum margin in order to pick the split axis
+        double minMargin = Double.MAX_VALUE;
+        int splitAxis = 0, sortOrder = 0;
+
+        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        for (int i = 0; i < maxFieldPos; i++) {
+            int j = maxFieldPos + i;
+            for (int k = 0; k < getTupleCount(); ++k) {
+
+                frameTuple.resetByTupleIndex(this, k);
+
+                double LowerKey = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(i),
+                        frameTuple.getFieldStart(i));
+                double UpperKey = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(j),
+                        frameTuple.getFieldStart(j));
+
+                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));
+
+            tupleEntries1.add(-1, LowerKey);
+            tupleEntries2.add(-1, UpperKey);
+
+            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, 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();
+                upperMargin += rec[1].margin() + rec[3].margin();
+            }
+            double margin = Math.min(lowerMargin, upperMargin);
+
+            // store minimum margin as split axis
+            if (margin < minMargin) {
+                minMargin = margin;
+                splitAxis = i;
+                sortOrder = (lowerMargin < upperMargin) ? 0 : 2;
+            }
+
+            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));
+            tupleEntries1.add(i, key);
+        }
+        double key = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(splitAxis + sortOrder),
+                tuple.getFieldStart(splitAxis + sortOrder));
+        tupleEntries1.add(-1, key);
+        tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
+
+        double minArea = Double.MAX_VALUE;
+        double minOverlap = Double.MAX_VALUE;
+        int splitPoint = 0;
+        for (int i = 1; i <= splitDistribution; ++i) {
+            int d = m - 1 + i;
+
+            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) {
+                splitPoint = d;
+                minOverlap = overlap;
+                minArea = rec[0].area() + rec[2].area();
+            } else if (overlap == minOverlap) {
+                double area = rec[0].area() + rec[2].area();
+                if (area < minArea) {
+                    splitPoint = d;
+                    minArea = area;
+                }
+            }
+        }
+        int startIndex, endIndex;
+        if (splitPoint < (getTupleCount() + 1) / 2) {
+            startIndex = 0;
+            endIndex = splitPoint;
+        } else {
+            startIndex = splitPoint;
+            endIndex = (getTupleCount() + 1);
+        }
+        boolean tupleInserted = false;
+        int totalBytes = 0, numOfDeletedTuples = 0;
+        for (int i = startIndex; i < endIndex; i++) { 
+            if (tupleEntries1.get(i).getTupleIndex() != -1) {
+                frameTuple.resetByTupleIndex(this, tupleEntries1.get(i).getTupleIndex());
+                rightFrame.insert(frameTuple, cmp, -1);
+                ((UnorderedSlotManager) slotManager).modifySlot(
+                        slotManager.getSlotOff(tupleEntries1.get(i).getTupleIndex()), -1);
+                totalBytes += tupleWriter.bytesRequired(frameTuple) + childPtrSize;
+                numOfDeletedTuples++;
+            } else {
+                rightFrame.insert(tuple, cmp, -1);
+                tupleInserted = true;
+            }
+        }
+
+        ((UnorderedSlotManager) slotManager).deleteEmptySlots();
+
+        // maintain space information
+        buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + totalBytes
+                + (slotManager.getSlotSize() * numOfDeletedTuples));
+
+        // compact both pages
+        rightFrame.compact(cmp);
+        compact(cmp);
+
+        if (!tupleInserted) {
+            insert(tuple, cmp, -1);
+        }
+
+        int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
+        frameTuple.resetByTupleOffset(buf, tupleOff);
+        int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
+
+        splitKey.initData(splitKeySize);
+        this.adjustMBR(tuples, cmp);
+        rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
+        rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(), 0);
+
+        ((IRTreeFrame) rightFrame).adjustMBR(((NSMFrame) rightFrame).getTuples(), cmp);
+        rTreeTupleWriterRightFrame.writeTupleFields(((NSMFrame) rightFrame).getTuples(), 0,
+                rTreeSplitKey.getRightPageBuffer(), 0);
+        rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(), 0);
+
+        tupleEntries1.clear();
+        tupleEntries2.clear();
+        return 0;
+    }
+
+    private int getChildPointerOff(ITupleReference tuple, MultiComparator cmp) {
+        return tuple.getFieldStart(cmp.getKeyFieldCount() - 1) + tuple.getFieldLength(cmp.getKeyFieldCount() - 1);
+    }
+
+    @Override
+    public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception {
+        frameTuple.setFieldCount(cmp.getKeyFieldCount());
+        slotManager.insertSlot(-1, buf.getInt(freeSpaceOff));
+        int freeSpace = buf.getInt(freeSpaceOff);
+        int bytesWritten = tupleWriter.writeTupleFields(tuple, 0, cmp.getKeyFieldCount(), buf, freeSpace);
+        System.arraycopy(tuple.getFieldData(cmp.getKeyFieldCount() - 1), getChildPointerOff(tuple, cmp), buf.array(),
+                freeSpace + bytesWritten, childPtrSize);
+        int tupleSize = bytesWritten + childPtrSize;
+
+        buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
+        buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + tupleSize);
+        buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - tupleSize - slotManager.getSlotSize());
+
+    }
+
+    @Override
+    public void delete(int tupleIndex, MultiComparator cmp) throws Exception {
+        frameTuple.setFieldCount(cmp.getKeyFieldCount());
+        int slotOff = slotManager.getSlotOff(tupleIndex);
+
+        int tupleOff = slotManager.getTupleOff(slotOff);
+        frameTuple.resetByTupleOffset(buf, tupleOff);
+        int tupleSize = tupleWriter.bytesRequired(frameTuple);
+
+        // perform deletion (we just do a memcpy to overwrite the slot)
+        int slotStartOff = slotManager.getSlotEndOff();
+        int length = slotOff - slotStartOff;
+        System.arraycopy(buf.array(), slotStartOff, buf.array(), slotStartOff + slotManager.getSlotSize(), length);
+
+        // maintain space information
+        buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
+        buf.putInt(totalFreeSpaceOff,
+                buf.getInt(totalFreeSpaceOff) + tupleSize + childPtrSize + slotManager.getSlotSize());
+    }
+
+    @Override
+    public boolean recomputeMBR(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
+        frameTuple.setFieldCount(cmp.getKeyFieldCount());
+        frameTuple.resetByTupleIndex(this, tupleIndex);
+
+        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        for (int i = 0; i < maxFieldPos; i++) {
+            int j = maxFieldPos + i;
+            int c = cmp.getComparators()[i].compare(frameTuple.getFieldData(i), frameTuple.getFieldStart(i),
+                    frameTuple.getFieldLength(i), tuple.getFieldData(i), tuple.getFieldStart(i),
+                    tuple.getFieldLength(i));
+            if (c != 0) {
+                return true;
+            }
+            c = cmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+                    frameTuple.getFieldLength(j), tuple.getFieldData(j), tuple.getFieldStart(j),
+                    tuple.getFieldLength(j));
+
+            if (c != 0) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    private double overlappedArea(ITupleReference tuple1, ITupleReference tupleToBeInserted, ITupleReference tuple2,
+            MultiComparator cmp) {
+        double area = 1.0;
+        double f1, f2;
+
+        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        for (int i = 0; i < maxFieldPos; i++) {
+            int j = maxFieldPos + i;
+            double pHigh1, pLow1;
+            if (tupleToBeInserted != null) {
+                int c = cmp.getComparators()[i].compare(tuple1.getFieldData(i), tuple1.getFieldStart(i),
+                        tuple1.getFieldLength(i), tupleToBeInserted.getFieldData(i),
+                        tupleToBeInserted.getFieldStart(i), tupleToBeInserted.getFieldLength(i));
+                if (c < 0) {
+                    pLow1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(i), tuple1.getFieldStart(i));
+                } else {
+                    pLow1 = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(i),
+                            tupleToBeInserted.getFieldStart(i));
+                }
+
+                c = cmp.getComparators()[j].compare(tuple1.getFieldData(j), tuple1.getFieldStart(j),
+                        tuple1.getFieldLength(j), tupleToBeInserted.getFieldData(j),
+                        tupleToBeInserted.getFieldStart(j), tupleToBeInserted.getFieldLength(j));
+                if (c > 0) {
+                    pHigh1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(j), tuple1.getFieldStart(j));
+                } else {
+                    pHigh1 = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(j),
+                            tupleToBeInserted.getFieldStart(j));
+                }
+            } else {
+                pLow1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(i), tuple1.getFieldStart(i));
+                pHigh1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(j), tuple1.getFieldStart(j));
+            }
+
+            double pLow2 = DoubleSerializerDeserializer.getDouble(tuple2.getFieldData(i), tuple2.getFieldStart(i));
+            double pHigh2 = DoubleSerializerDeserializer.getDouble(tuple2.getFieldData(j), tuple2.getFieldStart(j));
+
+            if (pLow1 > pHigh2 || pHigh1 < pLow2) {
+                return 0.0;
+            }
+
+            f1 = Math.max(pLow1, pLow2);
+            f2 = Math.min(pHigh1, pHigh2);
+            area *= f2 - f1;
+        }
+        return area;
+    }
+
+    private 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;
+    }
+
+    private 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;
+    }
+
+    @Override
+    public void enlarge(ITupleReference tuple, MultiComparator cmp) {
+        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        for (int i = 0; i < maxFieldPos; i++) {
+            int j = maxFieldPos + i;
+            int c = cmp.getComparators()[i].compare(frameTuple.getFieldData(i), frameTuple.getFieldStart(i),
+                    frameTuple.getFieldLength(i), tuple.getFieldData(i), tuple.getFieldStart(i),
+                    tuple.getFieldLength(i));
+            if (c > 0) {
+                System.arraycopy(tuple.getFieldData(i), tuple.getFieldStart(i), frameTuple.getFieldData(i),
+                        frameTuple.getFieldStart(i), tuple.getFieldLength(i));
+            }
+            c = cmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+                    frameTuple.getFieldLength(j), tuple.getFieldData(j), tuple.getFieldStart(j),
+                    tuple.getFieldLength(j));
+            if (c < 0) {
+                System.arraycopy(tuple.getFieldData(j), tuple.getFieldStart(j), frameTuple.getFieldData(j),
+                        frameTuple.getFieldStart(j), tuple.getFieldLength(j));
+            }
+        }
+    }
+
+    @Override
+    public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
+        for (int i = 0; i < tuples.length; i++) {
+            tuples[i].setFieldCount(cmp.getKeyFieldCount());
+            tuples[i].resetByTupleIndex(this, 0);
+        }
+
+        adjustMBRImpl(tuples, cmp);
+    }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMInteriorFrameFactory.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMInteriorFrameFactory.java
new file mode 100644
index 0000000..690592f
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMInteriorFrameFactory.java
@@ -0,0 +1,22 @@
+package edu.uci.ics.hyracks.storage.am.rtree.frames;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
+
+public class NSMInteriorFrameFactory implements ITreeIndexFrameFactory {
+
+    private static final long serialVersionUID = 1L;
+    private ITreeIndexTupleWriterFactory tupleWriterFactory;
+    private int keyFieldCount;
+
+    public NSMInteriorFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory, int keyFieldCount) {
+        this.tupleWriterFactory = tupleWriterFactory;
+        this.keyFieldCount = keyFieldCount;
+    }
+
+    @Override
+    public IRTreeInteriorFrame createFrame() {
+        return new NSMInteriorFrame(tupleWriterFactory.createTupleWriter(), keyFieldCount);
+    }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMLeafFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMLeafFrame.java
new file mode 100644
index 0000000..14938b3
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMLeafFrame.java
@@ -0,0 +1,251 @@
+package edu.uci.ics.hyracks.storage.am.rtree.frames;
+
+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.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.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
+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.UnorderedSlotManager;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriter;
+
+public class NSMLeafFrame extends NSMFrame implements IRTreeLeafFrame {
+
+    public NSMLeafFrame(ITreeIndexTupleWriter tupleWriter, int keyFieldCount) {
+        super(tupleWriter, keyFieldCount);
+    }
+
+    @Override
+    public int findTupleIndex(ITupleReference tuple, MultiComparator cmp) {
+        frameTuple.setFieldCount(cmp.getFieldCount());
+        return slotManager.findTupleIndex(tuple, frameTuple, cmp, null, null);
+    }
+
+    @Override
+    public boolean intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
+        frameTuple.setFieldCount(cmp.getFieldCount());
+        frameTuple.resetByTupleIndex(this, tupleIndex);
+        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        for (int i = 0; i < maxFieldPos; i++) {
+            int j = maxFieldPos + i;
+            int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
+                    tuple.getFieldLength(i), frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+                    frameTuple.getFieldLength(j));
+            if (c > 0) {
+                return false;
+            }
+            c = cmp.getComparators()[i].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
+                    frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
+
+            if (c < 0) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    @Override
+    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey)
+            throws Exception {
+
+        rightFrame.setPageTupleFieldCount(cmp.getFieldCount());
+        frameTuple.setFieldCount(cmp.getFieldCount());
+
+        RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
+        RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
+        RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame = ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
+
+        // calculations are based on the R*-tree paper
+        int m = (int) Math.floor((getTupleCount() + 1) * splitFactor);
+        int splitDistribution = getTupleCount() - (2 * m) + 2;
+
+        // to calculate the minimum margin in order to pick the split axis
+        double minMargin = Double.MAX_VALUE;
+        int splitAxis = 0, sortOrder = 0;
+
+        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        for (int i = 0; i < maxFieldPos; i++) {
+            int j = maxFieldPos + i;
+            for (int k = 0; k < getTupleCount(); ++k) {
+
+                frameTuple.resetByTupleIndex(this, k);
+
+                double LowerKey = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(i),
+                        frameTuple.getFieldStart(i));
+                double UpperKey = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(j),
+                        frameTuple.getFieldStart(j));
+
+                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));
+
+            tupleEntries1.add(-1, LowerKey);
+            tupleEntries2.add(-1, UpperKey);
+
+            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, 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();
+                upperMargin += rec[1].margin() + rec[3].margin();
+            }
+            double margin = Math.min(lowerMargin, upperMargin);
+
+            // store minimum margin as split axis
+            if (margin < minMargin) {
+                minMargin = margin;
+                splitAxis = i;
+                sortOrder = (lowerMargin < upperMargin) ? 0 : 2;
+            }
+
+            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));
+            tupleEntries1.add(i, key);
+        }
+        double key = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(splitAxis + sortOrder),
+                tuple.getFieldStart(splitAxis + sortOrder));
+        tupleEntries1.add(-1, key);
+        tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
+
+        double minArea = Double.MAX_VALUE;
+        double minOverlap = Double.MAX_VALUE;
+        int splitPoint = 0;
+        for (int i = 1; i <= splitDistribution; ++i) {
+            int d = m - 1 + i;
+
+            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) {
+                splitPoint = d;
+                minOverlap = overlap;
+                minArea = rec[0].area() + rec[2].area();
+            } else if (overlap == minOverlap) {
+                double area = rec[0].area() + rec[2].area();
+                if (area < minArea) {
+                    splitPoint = d;
+                    minArea = area;
+                }
+            }
+        }
+        int startIndex, endIndex;
+        if (splitPoint < (getTupleCount() + 1) / 2) {
+            startIndex = 0;
+            endIndex = splitPoint;
+        } else {
+            startIndex = splitPoint;
+            endIndex = (getTupleCount() + 1);
+        }
+        boolean tupleInserted = false;
+        int totalBytes = 0, numOfDeletedTuples = 0;
+        for (int i = startIndex; i < endIndex; i++) {
+            if (tupleEntries1.get(i).getTupleIndex() != -1) {
+                frameTuple.resetByTupleIndex(this, tupleEntries1.get(i).getTupleIndex());
+                rightFrame.insert(frameTuple, cmp, -1);
+                ((UnorderedSlotManager) slotManager).modifySlot(
+                        slotManager.getSlotOff(tupleEntries1.get(i).getTupleIndex()), -1);
+                totalBytes += tupleWriter.bytesRequired(frameTuple);
+                numOfDeletedTuples++;
+            } else {
+                rightFrame.insert(tuple, cmp, -1);
+                tupleInserted = true;
+            }
+        }
+
+        ((UnorderedSlotManager) slotManager).deleteEmptySlots();
+
+        // maintain space information
+        buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + totalBytes
+                + (slotManager.getSlotSize() * numOfDeletedTuples));
+
+        // compact both pages
+        rightFrame.compact(cmp);
+        compact(cmp);
+
+        if (!tupleInserted) {
+            insert(tuple, cmp, -1);
+        }
+
+        int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
+        frameTuple.resetByTupleOffset(buf, tupleOff);
+        int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
+
+        splitKey.initData(splitKeySize);
+        this.adjustMBR(tuples, cmp);
+        rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
+        rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(), 0);
+
+        ((IRTreeFrame) rightFrame).adjustMBR(((NSMFrame) rightFrame).getTuples(), cmp);
+        rTreeTupleWriterRightFrame.writeTupleFields(((NSMFrame) rightFrame).getTuples(), 0,
+                rTreeSplitKey.getRightPageBuffer(), 0);
+        rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(), 0);
+
+        tupleEntries1.clear();
+        tupleEntries2.clear();
+        return 0;
+    }
+
+    @Override
+    public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception {
+        frameTuple.setFieldCount(cmp.getFieldCount());
+        slotManager.insertSlot(-1, buf.getInt(freeSpaceOff));
+        int bytesWritten = tupleWriter.writeTuple(tuple, buf, buf.getInt(freeSpaceOff));
+
+        buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
+        buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + bytesWritten);
+        buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - bytesWritten - slotManager.getSlotSize());
+    }
+
+    @Override
+    public void delete(int tupleIndex, MultiComparator cmp) throws Exception {
+        frameTuple.setFieldCount(cmp.getFieldCount());
+        int slotOff = slotManager.getSlotOff(tupleIndex);
+
+        int tupleOff = slotManager.getTupleOff(slotOff);
+        frameTuple.resetByTupleOffset(buf, tupleOff);
+        int tupleSize = tupleWriter.bytesRequired(frameTuple);
+
+        // perform deletion (we just do a memcpy to overwrite the slot)
+        int slotStartOff = slotManager.getSlotEndOff();
+        int length = slotOff - slotStartOff;
+        System.arraycopy(buf.array(), slotStartOff, buf.array(), slotStartOff + slotManager.getSlotSize(), length);
+
+        // maintain space information
+        buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
+        buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + tupleSize + slotManager.getSlotSize());
+    }
+
+    @Override
+    public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
+        for (int i = 0; i < tuples.length; i++) {
+            tuples[i].setFieldCount(cmp.getFieldCount());
+            tuples[i].resetByTupleIndex(this, 0);
+        }
+
+        adjustMBRImpl(tuples, cmp);
+    }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMLeafFrameFactory.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMLeafFrameFactory.java
new file mode 100644
index 0000000..01811d2
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMLeafFrameFactory.java
@@ -0,0 +1,22 @@
+package edu.uci.ics.hyracks.storage.am.rtree.frames;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
+
+public class NSMLeafFrameFactory implements ITreeIndexFrameFactory {
+
+    private static final long serialVersionUID = 1L;
+    private ITreeIndexTupleWriterFactory tupleWriterFactory;
+    private int keyFieldCount;
+
+    public NSMLeafFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory, int keyFieldCount) {
+        this.tupleWriterFactory = tupleWriterFactory;
+        this.keyFieldCount = keyFieldCount;
+    }
+
+    @Override
+    public IRTreeLeafFrame createFrame() {
+        return new NSMLeafFrame(tupleWriterFactory.createTupleWriter(), keyFieldCount);
+    }
+}
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
deleted file mode 100644
index c6aebea..0000000
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/ByteArrayList.java
+++ /dev/null
@@ -1,53 +0,0 @@
-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 byte getLast() {
-        return data[size - 1];
-    }
-
-    public byte get(int i) {
-        return data[i];
-    }
-    
-    public void set(int i, byte b) {
-        data[i] = b;
-    }
-
-    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/InteriorFrameSchema.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/InteriorFrameSchema.java
deleted file mode 100644
index d8801a7..0000000
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/InteriorFrameSchema.java
+++ /dev/null
@@ -1,26 +0,0 @@
-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/PathList.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/PathList.java
index 093bc8c..80ddfab 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/PathList.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/PathList.java
@@ -15,6 +15,8 @@
 
 package edu.uci.ics.hyracks.storage.am.rtree.impls;
 
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
+
 public class PathList {
     private IntArrayList pageIds;
     private IntArrayList pageLsns;
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 f7cbef9..5494217 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
@@ -23,6 +23,8 @@
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMFrame;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
@@ -31,6 +33,7 @@
 public class RTree implements ITreeIndex {
 
     private boolean created = false;
+    private boolean loaded = false;
     private final int rootPage = 1; // the root page never changes
 
     private final AtomicInteger globalNsn; // Global node sequence number
@@ -44,8 +47,7 @@
     private final SearchPredicate diskOrderScanPredicate;
     private final ITreeIndexFrameFactory interiorFrameFactory;
     private final ITreeIndexFrameFactory leafFrameFactory;
-    private final MultiComparator interiorCmp;
-    private final MultiComparator leafCmp;
+    private final MultiComparator cmp;
 
     public int rootSplits = 0;
     public int[] splitsByLevel = new int[500];
@@ -58,17 +60,15 @@
     public byte currentLevel = 0;
 
     public RTree(IBufferCache bufferCache, IFreePageManager freePageManager,
-            ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory,
-            MultiComparator interiorCmp, MultiComparator leafCmp) {
+            ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory, MultiComparator cmp) {
         this.bufferCache = bufferCache;
         this.freePageManager = freePageManager;
         this.interiorFrameFactory = interiorFrameFactory;
         this.leafFrameFactory = leafFrameFactory;
-        this.interiorCmp = interiorCmp;
-        this.leafCmp = leafCmp;
+        this.cmp = cmp;
         globalNsn = new AtomicInteger();
         this.treeLatch = new ReentrantReadWriteLock(true);
-        this.diskOrderScanPredicate = new SearchPredicate(null, interiorCmp, leafCmp);
+        this.diskOrderScanPredicate = new SearchPredicate(null, cmp);
     }
 
     public void incrementGlobalNsn() {
@@ -154,14 +154,14 @@
             String keyString;
             if (interiorFrame.isLeaf()) {
                 leafFrame.setPage(node);
-                keyString = leafFrame.printKeys(leafCmp, fields);
+                keyString = leafFrame.printKeys(cmp, fields);
             } else {
-                keyString = interiorFrame.printKeys(interiorCmp, fields);
+                keyString = interiorFrame.printKeys(cmp, fields);
             }
 
             System.out.format(keyString);
             if (!interiorFrame.isLeaf()) {
-                ArrayList<Integer> children = ((NSMFrame) (interiorFrame)).getChildren(interiorCmp);
+                ArrayList<Integer> children = ((NSMFrame) (interiorFrame)).getChildren(cmp);
                 for (int i = 0; i < children.size(); i++) {
                     printTree(children.get(i), node, i == children.size() - 1, leafFrame, interiorFrame, fields);
                 }
@@ -227,7 +227,7 @@
     @Override
     public RTreeOpContext createOpContext(IndexOp op, ITreeIndexFrame leafFrame, ITreeIndexFrame interiorFrame,
             ITreeIndexMetaDataFrame metaFrame) {
-        return new RTreeOpContext(op, (IRTreeFrame) leafFrame, (IRTreeFrame) interiorFrame, metaFrame, 8);
+        return new RTreeOpContext(op, (IRTreeLeafFrame) leafFrame, (IRTreeInteriorFrame) interiorFrame, metaFrame, 8);
     }
 
     @Override
@@ -236,10 +236,10 @@
         ctx.reset();
         ctx.setTuple(tuple);
         ctx.splitKey.reset();
-        ctx.splitKey.getLeftTuple().setFieldCount(interiorCmp.getFieldCount());
-        ctx.splitKey.getRightTuple().setFieldCount(interiorCmp.getFieldCount());
-        ctx.interiorFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
-        ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
+        ctx.splitKey.getLeftTuple().setFieldCount(cmp.getKeyFieldCount());
+        ctx.splitKey.getRightTuple().setFieldCount(cmp.getKeyFieldCount());
+        ctx.interiorFrame.setPageTupleFieldCount(cmp.getKeyFieldCount());
+        ctx.leafFrame.setPageTupleFieldCount(cmp.getFieldCount());
 
         ICachedPage leafNode = findLeaf(ctx);
 
@@ -259,7 +259,6 @@
         incrementWriteLatchesReleased();
         bufferCache.unpin(leafNode);
         incrementUnpins();
-
     }
 
     public ICachedPage findLeaf(RTreeOpContext ctx) throws Exception {
@@ -325,57 +324,43 @@
             ctx.pathList.add(pageId, pageLsn, -1);
 
             if (!isLeaf) {
-                // checkEnlargement must be called *before* getBestChildPageId
-                boolean needsEnlargement = ctx.interiorFrame.findBestChild(ctx.getTuple(), interiorCmp);
-                int childPageId = ctx.interiorFrame.getBestChildPageId(interiorCmp);
+                // findBestChild must be called *before* getBestChildPageId
+                ctx.interiorFrame.findBestChild(ctx.getTuple(), cmp);
+                int childPageId = ctx.interiorFrame.getBestChildPageId(cmp);
 
-                if (needsEnlargement) {
-                    if (!writeLatched) {
-                        node.releaseReadLatch();
-                        incrementReadLatchesReleased();
-                        // TODO: do we need to un-pin and pin again?
-                        bufferCache.unpin(node);
-                        incrementUnpins();
-
-                        node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
-                        incrementPins();
-                        node.acquireWriteLatch();
-                        incrementWriteLatchesAcquired();
-                        ctx.interiorFrame.setPage(node);
-                        writeLatched = true;
-
-                        if (ctx.interiorFrame.getPageLsn() != pageLsn) {
-                            // The page was changed while we unlocked it; thus,
-                            // retry (re-choose best child)
-
-                            ctx.pathList.removeLast();
-                            continue;
-                        }
-                    }
-
-                    // We don't need to reset the frameTuple because it is
-                    // already pointing to the best child
-                    ctx.interiorFrame.enlarge(ctx.getTuple(), interiorCmp);
-
-                    node.releaseWriteLatch();
-                    incrementWriteLatchesReleased();
+                if (!writeLatched) {
+                    node.releaseReadLatch();
+                    incrementReadLatchesReleased();
+                    // TODO: do we need to un-pin and pin again?
                     bufferCache.unpin(node);
                     incrementUnpins();
-                    writeLatched = false;
-                } else {
-                    if (writeLatched) {
-                        node.releaseWriteLatch();
-                        incrementWriteLatchesReleased();
-                        bufferCache.unpin(node);
-                        incrementUnpins();
-                        writeLatched = false;
-                    } else {
-                        node.releaseReadLatch();
-                        incrementReadLatchesReleased();
-                        bufferCache.unpin(node);
-                        incrementUnpins();
+
+                    node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+                    incrementPins();
+                    node.acquireWriteLatch();
+                    incrementWriteLatchesAcquired();
+                    ctx.interiorFrame.setPage(node);
+                    writeLatched = true;
+
+                    if (ctx.interiorFrame.getPageLsn() != pageLsn) {
+                        // The page was changed while we unlocked it; thus,
+                        // retry (re-choose best child)
+
+                        ctx.pathList.removeLast();
+                        continue;
                     }
                 }
+
+                // We don't need to reset the frameTuple because it is
+                // already pointing to the best child
+                ctx.interiorFrame.enlarge(ctx.getTuple(), cmp);
+
+                node.releaseWriteLatch();
+                incrementWriteLatchesReleased();
+                bufferCache.unpin(node);
+                incrementUnpins();
+                writeLatched = false;
+
                 pageId = childPageId;
                 parentLsn = pageLsn;
             } else {
@@ -389,19 +374,19 @@
             throws Exception {
         FrameOpSpaceStatus spaceStatus;
         if (!isLeaf) {
-            spaceStatus = ctx.interiorFrame.hasSpaceInsert(tuple, interiorCmp);
+            spaceStatus = ctx.interiorFrame.hasSpaceInsert(tuple, cmp);
         } else {
-            spaceStatus = ctx.leafFrame.hasSpaceInsert(tuple, leafCmp);
+            spaceStatus = ctx.leafFrame.hasSpaceInsert(tuple, cmp);
         }
 
         switch (spaceStatus) {
             case SUFFICIENT_CONTIGUOUS_SPACE: {
                 if (!isLeaf) {
-                    ctx.interiorFrame.insert(tuple, interiorCmp, -1);
+                    ctx.interiorFrame.insert(tuple, cmp, -1);
                     incrementGlobalNsn();
                     ctx.interiorFrame.setPageLsn(getGlobalNsn());
                 } else {
-                    ctx.leafFrame.insert(tuple, leafCmp, -1);
+                    ctx.leafFrame.insert(tuple, cmp, -1);
                     incrementGlobalNsn();
                     ctx.leafFrame.setPageLsn(getGlobalNsn());
                 }
@@ -411,13 +396,13 @@
 
             case SUFFICIENT_SPACE: {
                 if (!isLeaf) {
-                    ctx.interiorFrame.compact(interiorCmp);
-                    ctx.interiorFrame.insert(tuple, interiorCmp, -1);
+                    ctx.interiorFrame.compact(cmp);
+                    ctx.interiorFrame.insert(tuple, cmp, -1);
                     incrementGlobalNsn();
                     ctx.interiorFrame.setPageLsn(getGlobalNsn());
                 } else {
-                    ctx.leafFrame.compact(leafCmp);
-                    ctx.leafFrame.insert(tuple, leafCmp, -1);
+                    ctx.leafFrame.compact(cmp);
+                    ctx.leafFrame.insert(tuple, cmp, -1);
                     incrementGlobalNsn();
                     ctx.leafFrame.setPageLsn(getGlobalNsn());
                 }
@@ -441,8 +426,8 @@
                         rightFrame = (IRTreeFrame) interiorFrameFactory.createFrame();
                         rightFrame.setPage(rightNode);
                         rightFrame.initBuffer((byte) ctx.interiorFrame.getLevel());
-                        rightFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
-                        ret = ctx.interiorFrame.split(rightFrame, tuple, interiorCmp, ctx.splitKey);
+                        rightFrame.setPageTupleFieldCount(cmp.getKeyFieldCount());
+                        ret = ctx.interiorFrame.split(rightFrame, tuple, cmp, ctx.splitKey);
                         ctx.interiorFrame.setRightPage(rightPageId);
                         rightFrame.setPageNsn(ctx.interiorFrame.getPageNsn());
                         incrementGlobalNsn();
@@ -455,8 +440,8 @@
                         rightFrame = (IRTreeFrame) leafFrameFactory.createFrame();
                         rightFrame.setPage(rightNode);
                         rightFrame.initBuffer((byte) 0);
-                        rightFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
-                        ret = ctx.leafFrame.split(rightFrame, tuple, leafCmp, ctx.splitKey);
+                        rightFrame.setPageTupleFieldCount(cmp.getFieldCount());
+                        ret = ctx.leafFrame.split(rightFrame, tuple, cmp, ctx.splitKey);
                         ctx.leafFrame.setRightPage(rightPageId);
                         rightFrame.setPageNsn(ctx.leafFrame.getPageNsn());
                         incrementGlobalNsn();
@@ -494,8 +479,8 @@
 
                             ctx.splitKey.setLeftPage(newLeftId);
 
-                            ctx.interiorFrame.insert(ctx.splitKey.getLeftTuple(), interiorCmp, -1);
-                            ctx.interiorFrame.insert(ctx.splitKey.getRightTuple(), interiorCmp, -1);
+                            ctx.interiorFrame.insert(ctx.splitKey.getLeftTuple(), cmp, -1);
+                            ctx.interiorFrame.insert(ctx.splitKey.getRightTuple(), cmp, -1);
 
                             incrementGlobalNsn();
                             int newNsn = getGlobalNsn();
@@ -532,7 +517,7 @@
         if (ctx.interiorFrame.getPageLsn() != ctx.pathList.getLastPageLsn()) {
             foundParent = false;
             while (true) {
-                if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), interiorCmp) != -1) {
+                if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), cmp) != -1) {
                     // found the parent
                     foundParent = true;
                     break;
@@ -556,7 +541,7 @@
             }
         }
         if (foundParent) {
-            ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), -1, interiorCmp);
+            ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), -1, cmp);
             insertTuple(parentNode, parentId, ctx.splitKey.getRightTuple(), ctx, ctx.interiorFrame.isLeaf());
             ctx.pathList.removeLast();
 
@@ -605,8 +590,7 @@
             }
             parentLsn = pageLsn;
 
-            if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), ctx.traverseList, pageIndex,
-                    interiorCmp) != -1) {
+            if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), ctx.traverseList, pageIndex, cmp) != -1) {
                 fillPath(ctx, pageIndex);
 
                 node.releaseReadLatch();
@@ -635,9 +619,9 @@
         ctx.reset();
         ctx.setTuple(tuple);
         ctx.splitKey.reset();
-        ctx.splitKey.getLeftTuple().setFieldCount(interiorCmp.getFieldCount());
-        ctx.interiorFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
-        ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
+        ctx.splitKey.getLeftTuple().setFieldCount(cmp.getKeyFieldCount());
+        ctx.interiorFrame.setPageTupleFieldCount(cmp.getKeyFieldCount());
+        ctx.leafFrame.setPageTupleFieldCount(cmp.getFieldCount());
 
         int tupleIndex = findTupleToDelete(ctx);
 
@@ -674,7 +658,7 @@
         if (ctx.interiorFrame.getPageLsn() != ctx.pathList.getLastPageLsn()) {
             foundParent = false;
             while (true) {
-                tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), interiorCmp);
+                tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), cmp);
                 if (tupleIndex != -1) {
                     // found the parent
                     foundParent = true;
@@ -700,12 +684,12 @@
         }
         if (foundParent) {
             if (tupleIndex == -1) {
-                tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), interiorCmp);
+                tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), cmp);
             }
-            boolean recomputeMBR = ctx.interiorFrame.recomputeMBR(ctx.splitKey.getLeftTuple(), tupleIndex, interiorCmp);
+            boolean recomputeMBR = ctx.interiorFrame.recomputeMBR(ctx.splitKey.getLeftTuple(), tupleIndex, cmp);
 
             if (recomputeMBR) {
-                ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), tupleIndex, interiorCmp);
+                ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), tupleIndex, cmp);
                 ctx.pathList.removeLast();
 
                 incrementGlobalNsn();
@@ -713,7 +697,7 @@
 
                 ctx.splitKey.reset();
                 if (!ctx.pathList.isEmpty()) {
-                    ctx.interiorFrame.computeMBR(ctx.splitKey, interiorCmp);
+                    ctx.interiorFrame.computeMBR(ctx.splitKey, cmp);
                     ctx.splitKey.setLeftPage(parentId);
                 }
             } else {
@@ -768,7 +752,7 @@
 
             if (!isLeaf) {
                 for (int i = 0; i < ctx.interiorFrame.getTupleCount(); i++) {
-                    int childPageId = ctx.interiorFrame.getChildPageIdIfIntersect(ctx.tuple, i, interiorCmp);
+                    int childPageId = ctx.interiorFrame.getChildPageIdIfIntersect(ctx.tuple, i, cmp);
                     if (childPageId != -1) {
                         ctx.traverseList.add(childPageId, -1, pageIndex);
                         ctx.pathList.add(childPageId, pageLsn, ctx.traverseList.size() - 1);
@@ -776,7 +760,7 @@
                 }
             } else {
                 ctx.leafFrame.setPage(node);
-                int tupleIndex = ctx.leafFrame.findTupleIndex(ctx.tuple, leafCmp);
+                int tupleIndex = ctx.leafFrame.findTupleIndex(ctx.tuple, cmp);
                 if (tupleIndex != -1) {
 
                     node.releaseReadLatch();
@@ -793,7 +777,7 @@
                     if (ctx.leafFrame.getPageLsn() != pageLsn) {
                         // The page was changed while we unlocked it
 
-                        tupleIndex = ctx.leafFrame.findTupleIndex(ctx.tuple, leafCmp);
+                        tupleIndex = ctx.leafFrame.findTupleIndex(ctx.tuple, cmp);
                         if (tupleIndex == -1) {
                             ctx.traverseList.add(pageId, -1, parentIndex);
                             ctx.pathList.add(pageId, parentLsn, ctx.traverseList.size() - 1);
@@ -818,13 +802,13 @@
     }
 
     public void deleteTuple(int pageId, int tupleIndex, RTreeOpContext ctx) throws Exception {
-        ctx.leafFrame.delete(tupleIndex, leafCmp);
+        ctx.leafFrame.delete(tupleIndex, cmp);
         incrementGlobalNsn();
         ctx.leafFrame.setPageLsn(getGlobalNsn());
 
         // if the page is empty, just leave it there for future inserts
         if (pageId != rootPage && ctx.leafFrame.getTupleCount() > 0) {
-            ctx.leafFrame.computeMBR(ctx.splitKey, leafCmp);
+            ctx.leafFrame.computeMBR(ctx.splitKey, cmp);
             ctx.splitKey.setLeftPage(pageId);
         }
     }
@@ -839,60 +823,6 @@
         ctx.cursor.open(ctx.cursorInitialState, pred);
     }
 
-    public void search(Stack<Integer> s, ITupleReference tuple, RTreeOpContext ctx, ArrayList<Rectangle> results)
-            throws Exception {
-        ctx.reset();
-        ctx.setTuple(tuple);
-        ctx.interiorFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
-        ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
-        s.push(rootPage);
-        while (!s.isEmpty()) {
-            int pageId = s.pop();
-            ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
-            incrementPins();
-            node.acquireReadLatch();
-            incrementReadLatchesAcquired();
-
-            try {
-
-                ctx.interiorFrame.setPage(node);
-                boolean isLeaf = ctx.interiorFrame.isLeaf();
-                int tupleCount = ctx.interiorFrame.getTupleCount();
-
-                if (!isLeaf) {
-                    for (int i = 0; i < tupleCount; i++) {
-                        // check intersection, if intersect, call search
-                        int childPageId = ctx.interiorFrame.getChildPageIdIfIntersect(ctx.tuple, i, interiorCmp);
-                        if (childPageId != -1) {
-                            s.push(childPageId);
-                        }
-                    }
-
-                } else {
-                    for (int i = 0; i < tupleCount; i++) {
-                        ctx.leafFrame.setPage(node);
-
-                        // check intersection, if intersect, add the tuple to
-                        // the
-                        // result set
-                        Rectangle rec = ctx.leafFrame.checkIntersect(ctx.tuple, i, leafCmp);
-                        if (rec != null) {
-                            // add the tuple to the result set
-                            results.add(rec);
-                        }
-                    }
-
-                }
-
-            } finally {
-                node.releaseReadLatch();
-                incrementReadLatchesReleased();
-                bufferCache.unpin(node);
-                incrementUnpins();
-            }
-        }
-    }
-
     public ITreeIndexFrameFactory getInteriorFrameFactory() {
         return interiorFrameFactory;
     }
@@ -901,12 +831,8 @@
         return leafFrameFactory;
     }
 
-    public MultiComparator getInteriorCmp() {
-        return interiorCmp;
-    }
-
-    public MultiComparator getLeafCmp() {
-        return leafCmp;
+    public MultiComparator getCmp() {
+        return cmp;
     }
 
     public IFreePageManager getFreePageManager() {
@@ -918,35 +844,60 @@
         throw new Exception("RTree Update not implemented.");
     }
 
+    public final class BulkLoadContext implements IIndexBulkLoadContext {
+
+        public RTreeOpContext insertOpCtx;
+
+        public BulkLoadContext(float fillFactor, IRTreeFrame leafFrame, IRTreeFrame interiorFrame,
+                ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
+
+            insertOpCtx = createOpContext(IndexOp.INSERT, leafFrame, interiorFrame, metaFrame);
+        }
+    }
+
     @Override
     public IIndexBulkLoadContext beginBulkLoad(float fillFactor, ITreeIndexFrame leafFrame,
             ITreeIndexFrame interiorFrame, ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
-        throw new HyracksDataException("RTree Bulkload not implemented.");
+        // throw new HyracksDataException("RTree Bulkload not implemented.");
+
+        if (loaded)
+            throw new HyracksDataException("Trying to bulk-load RTree but has RTree already been loaded.");
+
+        BulkLoadContext ctx = new BulkLoadContext(fillFactor, (IRTreeFrame) leafFrame, (IRTreeFrame) interiorFrame,
+                metaFrame);
+        return ctx;
     }
 
     @Override
     public void bulkLoadAddTuple(IIndexBulkLoadContext ictx, ITupleReference tuple) throws HyracksDataException {
-        throw new HyracksDataException("RTree Bulkload not implemented.");
+        // throw new HyracksDataException("RTree Bulkload not implemented.");
+
+        try {
+            insert(tuple, ((BulkLoadContext) ictx).insertOpCtx);
+        } catch (Exception e) {
+            // TODO Auto-generated catch block
+            e.printStackTrace();
+        }
     }
 
     @Override
     public void endBulkLoad(IIndexBulkLoadContext ictx) throws HyracksDataException {
-        throw new HyracksDataException("RTree Bulkload not implemented.");
+        // throw new HyracksDataException("RTree Bulkload not implemented.");
+
+        loaded = true;
     }
 
     @Override
-    public void diskOrderScan(ITreeIndexCursor icursor,
-            ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame, IndexOpContext ictx)
-            throws HyracksDataException {
-        RTreeDiskOrderScanCursor cursor = (RTreeDiskOrderScanCursor)icursor;
+    public void diskOrderScan(ITreeIndexCursor icursor, ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame,
+            IndexOpContext ictx) throws HyracksDataException {
+        RTreeDiskOrderScanCursor cursor = (RTreeDiskOrderScanCursor) icursor;
         RTreeOpContext ctx = (RTreeOpContext) ictx;
         ctx.reset();
-        
+
         int currentPageId = rootPage + 1;
         int maxPageId = freePageManager.getMaxPage(metaFrame);
 
-        ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(
-                fileId, currentPageId), false);
+        ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, currentPageId), false);
         page.acquireReadLatch();
         cursor.setBufferCache(bufferCache);
         cursor.setFileId(fileId);
@@ -956,7 +907,6 @@
         cursor.open(ctx.cursorInitialState, diskOrderScanPredicate);
     }
 
-
     @Override
     public int getRootPageId() {
         return rootPage;
@@ -964,7 +914,7 @@
 
     @Override
     public int getFieldCount() {
-        return leafCmp.getFieldCount();
+        return cmp.getFieldCount();
     }
 
     @Override
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeDiskOrderScanCursor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeDiskOrderScanCursor.java
index de66e77..f852905 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeDiskOrderScanCursor.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeDiskOrderScanCursor.java
@@ -118,8 +118,8 @@
         tupleIndex = 0;
         frame.setPage(page);
         SearchPredicate pred = (SearchPredicate) searchPred;
-        MultiComparator leafCmp = pred.getLeafCmp();
-        frameTuple.setFieldCount(leafCmp.getFieldCount());
+        MultiComparator cmp = pred.getCmp();
+        frameTuple.setFieldCount(cmp.getFieldCount());
         boolean leafExists = positionToNextLeaf(false);
         if (!leafExists) {
             throw new HyracksDataException(
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 f377bba..5ad9965 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
@@ -5,12 +5,13 @@
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
-import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
 
 public final class RTreeOpContext implements IndexOpContext {
     public final IndexOp op;
-    public final IRTreeFrame interiorFrame;
-    public final IRTreeFrame leafFrame;
+    public final IRTreeInteriorFrame interiorFrame;
+    public final IRTreeLeafFrame leafFrame;
     public ITreeIndexCursor cursor;
     public CursorInitialState cursorInitialState;
     public final ITreeIndexMetaDataFrame metaFrame;
@@ -20,7 +21,7 @@
                                     // of the visited pages
     public final TraverseList traverseList; // used for traversing the tree
 
-    public RTreeOpContext(IndexOp op, IRTreeFrame leafFrame, IRTreeFrame interiorFrame,
+    public RTreeOpContext(IndexOp op, IRTreeLeafFrame leafFrame, IRTreeInteriorFrame interiorFrame,
             ITreeIndexMetaDataFrame metaFrame, int treeHeightHint) {
         this.op = op;
         this.interiorFrame = interiorFrame;
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
index 478acb2..481c034 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
@@ -2,12 +2,14 @@
 
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
 import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
 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;
@@ -16,8 +18,8 @@
 
     private int fileId = -1;
     private ICachedPage page = null;
-    private IRTreeFrame interiorFrame = null;
-    private IRTreeFrame leafFrame = null;
+    private IRTreeInteriorFrame interiorFrame = null;
+    private IRTreeLeafFrame leafFrame = null;
     private IBufferCache bufferCache = null;
 
     private SearchPredicate pred;
@@ -28,15 +30,14 @@
     private int tupleIndex = 0;
     private int tupleIndexInc = 0;
 
-    private MultiComparator leafCmp;
-    private MultiComparator interiorCmp;
+    private MultiComparator cmp;
 
     private ITreeIndexTupleReference frameTuple;
 
     private int pin = 0;
     private int unpin = 0;
 
-    public RTreeSearchCursor(IRTreeFrame interiorFrame, IRTreeFrame leafFrame) {
+    public RTreeSearchCursor(IRTreeInteriorFrame interiorFrame, IRTreeLeafFrame leafFrame) {
         this.interiorFrame = interiorFrame;
         this.leafFrame = leafFrame;
         this.frameTuple = leafFrame.createTupleReference();
@@ -51,7 +52,7 @@
         tupleIndex = 0;
         tupleIndexInc = 0;
         page = null;
-        pathList.clear();
+        pathList = null;
     }
 
     public ITupleReference getTuple() {
@@ -85,7 +86,7 @@
 
             if (!isLeaf) {
                 for (int i = 0; i < interiorFrame.getTupleCount(); i++) {
-                    int childPageId = interiorFrame.getChildPageIdIfIntersect(searchKey, i, interiorCmp);
+                    int childPageId = interiorFrame.getChildPageIdIfIntersect(searchKey, i, cmp);
                     if (childPageId != -1) {
                         pathList.add(childPageId, pageLsn, -1);
                     }
@@ -110,6 +111,10 @@
 
     @Override
     public boolean hasNext() throws Exception {
+        if (page == null) {
+            return false;
+        }
+            
         if (tupleIndex == leafFrame.getTupleCount()) {
             if (!fetchNextLeafPage()) {
                 return false;
@@ -118,7 +123,7 @@
 
         do {
             for (int i = tupleIndex; i < leafFrame.getTupleCount(); i++) {
-                if (leafFrame.intersect(searchKey, i, leafCmp)) {
+                if (leafFrame.intersect(searchKey, i, cmp)) {
                     frameTuple.resetByTupleIndex(leafFrame, i);
                     tupleIndexInc = i + 1;
                     return true;
@@ -146,12 +151,11 @@
         rootPage = ((CursorInitialState) initialState).getRootPage();
 
         pred = (SearchPredicate) searchPred;
-        interiorCmp = pred.getInteriorCmp();
-        leafCmp = pred.getLeafCmp();
+        cmp = pred.getCmp();
         searchKey = pred.getSearchKey();
-
+        
         pathList.add(this.rootPage, -1, -1);
-        frameTuple.setFieldCount(leafCmp.getFieldCount());
+        frameTuple.setFieldCount(cmp.getFieldCount());
         tupleIndex = 0;
         fetchNextLeafPage();
     }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchPredicate.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchPredicate.java
index c83f0e2..4ad6223 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchPredicate.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchPredicate.java
@@ -9,13 +9,11 @@
     private static final long serialVersionUID = 1L;
 
     protected ITupleReference searchKey;
-    protected MultiComparator interiorCmp;
-    protected MultiComparator leafCmp;
+    protected MultiComparator cmp;
 
-    public SearchPredicate(ITupleReference searchKey, MultiComparator interiorCmp, MultiComparator leafCmp) {
+    public SearchPredicate(ITupleReference searchKey, MultiComparator cmp) {
         this.searchKey = searchKey;
-        this.interiorCmp = interiorCmp;
-        this.leafCmp = leafCmp;
+        this.cmp = cmp;
     }
 
     public ITupleReference getSearchKey() {
@@ -26,11 +24,7 @@
         this.searchKey = searchKey;
     }
 
-    public MultiComparator getInteriorCmp() {
-        return interiorCmp;
-    }
-
-    public MultiComparator getLeafCmp() {
-        return leafCmp;
+    public MultiComparator getCmp() {
+        return cmp;
     }
 }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/TraverseList.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/TraverseList.java
index c09971d..6a4d45c 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/TraverseList.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/TraverseList.java
@@ -15,6 +15,8 @@
 
 package edu.uci.ics.hyracks.storage.am.rtree.impls;
 
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
+
 public class TraverseList {
     private IntArrayList pageIds;
     private IntArrayList pageLsns;
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 e90cc0d..8cffd4d 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
@@ -1,13 +1,9 @@
 package edu.uci.ics.hyracks.storage.am.rtree;
 
-import java.io.BufferedReader;
 import java.io.DataOutput;
 import java.io.File;
-import java.io.FileReader;
 import java.nio.ByteBuffer;
-import java.util.ArrayList;
 import java.util.Random;
-import java.util.Stack;
 
 import org.junit.Test;
 
@@ -27,7 +23,6 @@
 import edu.uci.ics.hyracks.dataflow.common.data.comparators.DoubleBinaryComparatorFactory;
 import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
 import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
@@ -37,13 +32,14 @@
 import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.utility.TreeIndexStats;
+import edu.uci.ics.hyracks.storage.am.common.utility.TreeIndexStatsGatherer;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
-import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMFrameFactory;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.InteriorFrameSchema;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMLeafFrameFactory;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeDiskOrderScanCursor;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.Rectangle;
 import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriterFactory;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
@@ -52,9 +48,9 @@
 
 public class RTreeTest extends AbstractRTreeTest {
 
-    private static final int PAGE_SIZE = 1024;
-    private static final int NUM_PAGES = 10000;
-    private static final int MAX_OPEN_FILES = 10;
+    private static final int PAGE_SIZE = 8192;
+    private static final int NUM_PAGES = 20;
+    private static final int MAX_OPEN_FILES = 20;
     private static final int HYRACKS_FRAME_SIZE = 128;
     private IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
 
@@ -77,26 +73,23 @@
         cmps[2] = cmps[0];
         cmps[3] = cmps[0];
 
-        // declare leaf-frame-tuple fields
-        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(8);
-        leafTypeTraits[5] = new TypeTrait(4);
-        leafTypeTraits[6] = new TypeTrait(8);
+        // declare tuple fields
+        int fieldCount = 7;
+        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(8);
+        typeTraits[5] = new TypeTrait(4);
+        typeTraits[6] = new TypeTrait(8);
 
-        MultiComparator leafCmp = new MultiComparator(leafTypeTraits, cmps);
-        InteriorFrameSchema interiorFrameSchema = new InteriorFrameSchema(leafCmp);
+        MultiComparator cmp = new MultiComparator(typeTraits, cmps);
 
-        RTreeTypeAwareTupleWriterFactory interiorTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(
-                interiorFrameSchema.getInteriorCmp().getTypeTraits());
-        RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
+        RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
 
-        ITreeIndexFrameFactory interiorFrameFactory = new NSMFrameFactory(interiorTupleWriterFactory, keyFieldCount);
-        ITreeIndexFrameFactory leafFrameFactory = new NSMFrameFactory(leafTupleWriterFactory, keyFieldCount);
+        ITreeIndexFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(tupleWriterFactory, keyFieldCount);
+        ITreeIndexFrameFactory leafFrameFactory = new NSMLeafFrameFactory(tupleWriterFactory, keyFieldCount);
         ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
         ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
 
@@ -104,14 +97,13 @@
         IRTreeFrame leafFrame = (IRTreeFrame) leafFrameFactory.createFrame();
         IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
 
-        RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory,
-                interiorFrameSchema.getInteriorCmp(), leafCmp);
+        RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, cmp);
         rtree.create(fileId, leafFrame, metaFrame);
         rtree.open(fileId);
 
         ByteBuffer hyracksFrame = ctx.allocateFrame();
         FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
-        ArrayTupleBuilder tb = new ArrayTupleBuilder(leafCmp.getFieldCount());
+        ArrayTupleBuilder tb = new ArrayTupleBuilder(cmp.getFieldCount());
         DataOutput dos = tb.getDataOutput();
 
         @SuppressWarnings("rawtypes")
@@ -131,7 +123,6 @@
 
         Random rnd2 = new Random();
         rnd2.setSeed(50);
-        Stack<Integer> s = new Stack<Integer>();
         for (int i = 0; i < 10000; i++) {
 
             double p1x = rnd.nextDouble();
@@ -164,7 +155,6 @@
 
             tuple.reset(accessor, 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");
 
@@ -179,34 +169,19 @@
         // rtree.printTree(leafFrame, interiorFrame, recDescSers);
         // System.out.println();
 
-        RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame);
-        ArrayList<Rectangle> results = new ArrayList<Rectangle>();
-        rtree.search(s, tuple, searchOpCtx, results);
+        String rtreeStats = rtree.printStats();
+        print(rtreeStats);
 
-        // for (int i = 0; i < results.size(); i++) {
-        // for (int j = 0; j < dim; j++) {
-        // System.out.print(results.get(i).getLow(j) + " " +
-        // results.get(i).getHigh(j));
-        // }
-        // System.out.println();
-        // }
-        System.out.println("Number of Results: " + results.size());
-
-        String stats = rtree.printStats();
-        print(stats);
-
-        
         // disk-order scan
         print("DISK-ORDER SCAN:\n");
         RTreeDiskOrderScanCursor diskOrderCursor = new RTreeDiskOrderScanCursor(leafFrame);
-        RTreeOpContext diskOrderScanOpCtx = rtree.createOpContext(IndexOp.DISKORDERSCAN,
-                leafFrame, null, null);
+        RTreeOpContext diskOrderScanOpCtx = rtree.createOpContext(IndexOp.DISKORDERSCAN, leafFrame, null, null);
         rtree.diskOrderScan(diskOrderCursor, leafFrame, metaFrame, diskOrderScanOpCtx);
         try {
             while (diskOrderCursor.hasNext()) {
                 diskOrderCursor.next();
                 ITupleReference frameTuple = diskOrderCursor.getTuple();
-                String rec = leafCmp.printTuple(frameTuple, recDescSers);
+                String rec = cmp.printTuple(frameTuple, recDescSers);
                 print(rec + "\n");
             }
         } catch (Exception e) {
@@ -214,356 +189,12 @@
         } finally {
             diskOrderCursor.close();
         }
-        
-        // TreeIndexStatsGatherer statsGatherer = new
-        // TreeIndexStatsGatherer(bufferCache, freePageManager, fileId, rtree.getRootPageId());
-        // TreeIndexStats stats = statsGatherer.gatherStats(leafFrame,
-        // interiorFrame, metaFrame);
-        // String string = stats.toString();
-        // System.out.println(string);
 
-        rtree.close();
-        bufferCache.closeFile(fileId);
-        bufferCache.close();
-
-    }
-
-    // @Test
-    public void test02() throws Exception {
-
-        TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
-        IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
-        IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
-        FileReference file = new FileReference(new File(fileName));
-        bufferCache.createFile(file);
-        int fileId = fmp.lookupFileId(file);
-        bufferCache.openFile(fileId);
-
-        // declare interior-frame-tuple fields
-        int interiorFieldCount = 5;
-        ITypeTrait[] interiorTypeTraits = new ITypeTrait[interiorFieldCount];
-        interiorTypeTraits[0] = new TypeTrait(8);
-        interiorTypeTraits[1] = new TypeTrait(8);
-        interiorTypeTraits[2] = new TypeTrait(8);
-        interiorTypeTraits[3] = new TypeTrait(8);
-        interiorTypeTraits[4] = new TypeTrait(4);
-
-        // declare keys
-        int keyFieldCount = 4;
-        IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
-        cmps[0] = DoubleBinaryComparatorFactory.INSTANCE.createBinaryComparator();
-        cmps[1] = cmps[0];
-        cmps[2] = cmps[0];
-        cmps[3] = cmps[0];
-
-        // declare leaf-frame-tuple fields
-        int leafFieldCount = 5;
-        ITypeTrait[] leafTypeTraits = new ITypeTrait[leafFieldCount];
-        leafTypeTraits[0] = new TypeTrait(8);
-        leafTypeTraits[1] = new TypeTrait(8);
-        leafTypeTraits[2] = new TypeTrait(8);
-        leafTypeTraits[3] = new TypeTrait(8);
-        leafTypeTraits[4] = new TypeTrait(4);
-
-        MultiComparator interiorCmp = new MultiComparator(interiorTypeTraits, cmps);
-        MultiComparator leafCmp = new MultiComparator(leafTypeTraits, cmps);
-
-        RTreeTypeAwareTupleWriterFactory interiorTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(
-                interiorTypeTraits);
-        RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
-
-        ITreeIndexFrameFactory interiorFrameFactory = new NSMFrameFactory(interiorTupleWriterFactory, keyFieldCount);
-        ITreeIndexFrameFactory leafFrameFactory = new NSMFrameFactory(leafTupleWriterFactory, keyFieldCount);
-        ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
-        ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
-
-        IRTreeFrame interiorFrame = (IRTreeFrame) interiorFrameFactory.createFrame();
-        IRTreeFrame leafFrame = (IRTreeFrame) leafFrameFactory.createFrame();
-        IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
-
-        RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, interiorCmp,
-                leafCmp);
-        rtree.create(fileId, leafFrame, metaFrame);
-        rtree.open(fileId);
-
-        ByteBuffer hyracksFrame = ctx.allocateFrame();
-        FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
-        ArrayTupleBuilder tb = new ArrayTupleBuilder(leafCmp.getFieldCount());
-        DataOutput dos = tb.getDataOutput();
-
-        @SuppressWarnings("rawtypes")
-        ISerializerDeserializer[] recDescSers = { DoubleSerializerDeserializer.INSTANCE,
-                DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
-                DoubleSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
-        RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
-        IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
-        accessor.reset(hyracksFrame);
-        FrameTupleReference tuple = new FrameTupleReference();
-
-        RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, leafFrame, interiorFrame, metaFrame);
-
-        File datasetFile = new File("/home/salsubaiee/dataset.txt");
-        BufferedReader reader = new BufferedReader(new FileReader(datasetFile));
-
-        Random rnd = new Random();
-        rnd.setSeed(50);
-        String inputLine = reader.readLine();
-        int index = 0;
-
-        while (inputLine != null) {
-
-            String[] splittedLine1 = inputLine.split(",");
-            String[] splittedLine2 = splittedLine1[0].split("\\s");
-
-            double p1x = 0;
-            double p1y = 0;
-
-            try {
-                p1x = Double.valueOf(splittedLine2[1].trim()).doubleValue();
-                p1y = Double.valueOf(splittedLine2[2].trim()).doubleValue();
-            } catch (Exception e) {
-                inputLine = reader.readLine();
-                continue;
-            }
-            double p2x = p1x;
-            double p2y = p1y;
-
-            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);
-
-            long end = System.currentTimeMillis();
-            print("INSERTING " + index + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " " + Math.max(p1x, p2x)
-                    + " " + Math.max(p1y, p2y) + "\n");
-
-            try {
-                rtree.insert(tuple, insertOpCtx);
-            } catch (TreeIndexException e) {
-            } catch (Exception e) {
-                e.printStackTrace();
-            }
-
-            if (index == 1000) {
-                break;
-            }
-            inputLine = reader.readLine();
-            index++;
-
-            // rtree.printTree(leafFrame, interiorFrame, recDescSers);
-            // System.out.println();
-        }
-
-        // rtree.printTree(leafFrame, interiorFrame, recDescSers);
-        // System.out.println();
-
-        RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame);
-
-        File querysetFile = new File("/home/salsubaiee/queryset.txt");
-        BufferedReader reader2 = new BufferedReader(new FileReader(querysetFile));
-
-        inputLine = reader2.readLine();
-        int totalResults = 0;
-        index = 0;
-        Stack<Integer> s = new Stack<Integer>();
-        while (inputLine != null) {
-
-            String[] splittedLine1 = inputLine.split(",");
-            String[] splittedLine2 = splittedLine1[0].split("\\s");
-
-            double p1x;
-            double p1y;
-            double p2x;
-            double p2y;
-
-            try {
-                p1x = Double.valueOf(splittedLine2[1].trim()).doubleValue();
-                p1y = Double.valueOf(splittedLine2[2].trim()).doubleValue();
-                p2x = Double.valueOf(splittedLine2[3].trim()).doubleValue();
-                p2y = Double.valueOf(splittedLine2[4].trim()).doubleValue();
-            } catch (Exception e) {
-                inputLine = reader2.readLine();
-                continue;
-            }
-
-            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);
-
-            long end = System.currentTimeMillis();
-            print("SEARCHING " + index + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " " + Math.max(p1x, p2x)
-                    + " " + Math.max(p1y, p2y) + "\n");
-
-            try {
-                ArrayList<Rectangle> results = new ArrayList<Rectangle>();
-                rtree.search(s, tuple, searchOpCtx, results);
-                totalResults += results.size();
-            } catch (TreeIndexException e) {
-            } catch (Exception e) {
-                e.printStackTrace();
-            }
-
-            inputLine = reader2.readLine();
-            index++;
-
-        }
-
-        System.out.println("Number of Results: " + totalResults);
-
-        // String stats = rtree.printStats();
-        // print(stats);
-
-        RTreeOpContext deleteOpCtx = rtree.createOpContext(IndexOp.DELETE, leafFrame, interiorFrame, metaFrame);
-
-        BufferedReader reader3 = new BufferedReader(new FileReader(datasetFile));
-        inputLine = reader3.readLine();
-        index = 0;
-        rnd.setSeed(50);
-        while (inputLine != null) {
-
-            String[] splittedLine1 = inputLine.split(",");
-            String[] splittedLine2 = splittedLine1[0].split("\\s");
-
-            double p1x = 0;
-            double p1y = 0;
-
-            try {
-                p1x = Double.valueOf(splittedLine2[1].trim()).doubleValue();
-                p1y = Double.valueOf(splittedLine2[2].trim()).doubleValue();
-            } catch (Exception e) {
-                inputLine = reader3.readLine();
-                continue;
-            }
-            double p2x = p1x;
-            double p2y = p1y;
-
-            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);
-
-            print("Deleteing " + index + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " " + Math.max(p1x, p2x)
-                    + " " + Math.max(p1y, p2y) + "\n");
-
-            try {
-                rtree.delete(tuple, deleteOpCtx);
-            } catch (TreeIndexException e) {
-            } catch (Exception e) {
-                e.printStackTrace();
-            }
-
-            if (index == 1000) {
-                break;
-            }
-            inputLine = reader3.readLine();
-            index++;
-
-            // rtree.printTree(leafFrame, interiorFrame, recDescSers);
-            // System.out.println();
-        }
-
-        BufferedReader reader4 = new BufferedReader(new FileReader(querysetFile));
-
-        inputLine = reader4.readLine();
-        totalResults = 0;
-        index = 0;
-        Stack<Integer> s2 = new Stack<Integer>();
-        while (inputLine != null) {
-
-            String[] splittedLine1 = inputLine.split(",");
-            String[] splittedLine2 = splittedLine1[0].split("\\s");
-
-            double p1x = Double.valueOf(splittedLine2[1].trim()).doubleValue();
-            double p1y = Double.valueOf(splittedLine2[2].trim()).doubleValue();
-            double p2x = Double.valueOf(splittedLine2[3].trim()).doubleValue();
-            double p2y = Double.valueOf(splittedLine2[4].trim()).doubleValue();
-
-            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);
-
-            print("SEARCHING " + index + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " " + Math.max(p1x, p2x)
-                    + " " + Math.max(p1y, p2y) + "\n");
-
-            try {
-                ArrayList<Rectangle> results = new ArrayList<Rectangle>();
-                rtree.search(s2, tuple, searchOpCtx, results);
-                totalResults += results.size();
-            } catch (TreeIndexException e) {
-            } catch (Exception e) {
-                e.printStackTrace();
-            }
-
-            inputLine = reader4.readLine();
-            index++;
-
-        }
-
-        System.out.println("Number of Results: " + totalResults);
-
-        // stats = rtree.printStats();
-        // print(stats);
-
-        rtree.printTree(leafFrame, interiorFrame, recDescSers);
-        System.out.println();
+        TreeIndexStatsGatherer statsGatherer = new TreeIndexStatsGatherer(bufferCache, freePageManager, fileId,
+                rtree.getRootPageId());
+        TreeIndexStats stats = statsGatherer.gatherStats(leafFrame, interiorFrame, metaFrame);
+        String string = stats.toString();
+        System.out.println(string);
 
         rtree.close();
         bufferCache.closeFile(fileId);
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 f750edc..f8d0383 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
@@ -37,9 +37,10 @@
 import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
-import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMFrameFactory;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.InteriorFrameSchema;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMLeafFrameFactory;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSearchCursor;
@@ -76,39 +77,35 @@
         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);
+        // declare tuple 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);
 
-        MultiComparator leafCmp = new MultiComparator(leafTypeTraits, cmps);
-        InteriorFrameSchema interiorFrameSchema = new InteriorFrameSchema(leafCmp);
+        MultiComparator cmp = new MultiComparator(typeTraits, cmps);
 
-        RTreeTypeAwareTupleWriterFactory interiorTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(
-                interiorFrameSchema.getInteriorCmp().getTypeTraits());
-        RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
+        RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
 
-        ITreeIndexFrameFactory interiorFrameFactory = new NSMFrameFactory(interiorTupleWriterFactory, keyFieldCount);
-        ITreeIndexFrameFactory leafFrameFactory = new NSMFrameFactory(leafTupleWriterFactory, keyFieldCount);
+        ITreeIndexFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(tupleWriterFactory, keyFieldCount);
+        ITreeIndexFrameFactory leafFrameFactory = new NSMLeafFrameFactory(tupleWriterFactory, keyFieldCount);
         ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
         ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
 
-        IRTreeFrame interiorFrame = (IRTreeFrame) interiorFrameFactory.createFrame();
-        IRTreeFrame leafFrame = (IRTreeFrame) leafFrameFactory.createFrame();
+        IRTreeInteriorFrame interiorFrame = (IRTreeInteriorFrame) interiorFrameFactory.createFrame();
+        IRTreeLeafFrame leafFrame = (IRTreeLeafFrame) leafFrameFactory.createFrame();
         IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
 
-        RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory,
-                interiorFrameSchema.getInteriorCmp(), leafCmp);
+        RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, cmp);
         rtree.create(fileId, leafFrame, metaFrame);
         rtree.open(fileId);
 
         ByteBuffer hyracksFrame = ctx.allocateFrame();
         FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
-        ArrayTupleBuilder tb = new ArrayTupleBuilder(leafCmp.getFieldCount());
+        ArrayTupleBuilder tb = new ArrayTupleBuilder(cmp.getFieldCount());
         DataOutput dos = tb.getDataOutput();
 
         @SuppressWarnings("rawtypes")
@@ -163,8 +160,7 @@
         }
 
         ITreeIndexCursor searchCursor = new RTreeSearchCursor(interiorFrame, leafFrame);
-        SearchPredicate searchPredicate = new SearchPredicate(tuple, interiorFrameSchema.getInteriorCmp(), leafCmp);
-        
+        SearchPredicate searchPredicate = new SearchPredicate(tuple, cmp);
 
         RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame);
         rtree.search(searchCursor, searchPredicate, searchOpCtx);