diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
index 3572285..36f384d 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
@@ -105,12 +105,6 @@
     }
 
     @Override
-    public void insert(ITupleReference tuple, MultiComparator cmp) throws Exception {
-        super.insert(tuple, cmp);
-        setSmFlag(false);
-    }
-
-    @Override
     public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey,
             TupleEntryArrayList entries1, TupleEntryArrayList entries2, Rectangle[] rec) throws Exception {
 
@@ -609,6 +603,17 @@
     }
     
     @Override
+    public void insert(ITupleReference tuple, MultiComparator cmp) 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);
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/FindPathList.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/FindPathList.java
deleted file mode 100644
index 83289e4..0000000
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/FindPathList.java
+++ /dev/null
@@ -1,103 +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.rtree.impls;
-
-public class FindPathList {
-    private int[] pageIds;
-    private int[] pageLsns;
-    private int[] parentIndexes;
-    private int size;
-    private final int growth;
-    private int first;
-
-    public FindPathList(int initialCapacity, int growth) {
-        pageIds = new int[initialCapacity];
-        pageLsns = new int[initialCapacity];
-        parentIndexes = new int[initialCapacity];
-        size = 0;
-        this.growth = growth;
-        first = 0;
-    }
-
-    public int size() {
-        return size;
-    }
-
-    public void add(int pageId, int parentIndex) {
-        if (size == pageIds.length) {
-            int[] newPageIds = new int[pageIds.length + growth];
-            System.arraycopy(pageIds, 0, newPageIds, 0, pageIds.length);
-            pageIds = newPageIds;
-
-            int[] newPageLsns = new int[pageLsns.length + growth];
-            System.arraycopy(pageLsns, 0, newPageLsns, 0, pageLsns.length);
-            pageLsns = newPageLsns;
-            
-            int[] newParentIds = new int[parentIndexes.length + growth];
-            System.arraycopy(parentIndexes, 0, newParentIds, 0, parentIndexes.length);
-            parentIndexes = newParentIds;
-        }
-
-        pageIds[size] = pageId;
-        parentIndexes[size] = parentIndex;
-        size++;
-    }
-
-    public void moveFirst() {
-        first++;
-    }
-
-    public int getFirstPageId() {
-        return pageIds[first];
-    }
-    
-    public int getFirstPageLsn() {
-        return pageLsns[first];
-    }
-
-    public int getFirstParentIndex() {
-        return parentIndexes[first];
-    }
-
-    public int getPageId(int i) {
-        return pageIds[i];
-    }
-    
-    public int getPageLsn(int i) {
-        return pageLsns[i];
-    }
-    
-    public void setPageLsn(int i, int pageLsn) {
-        pageLsns[i] = pageLsn;
-    }
-
-    public int getParentIndex(int i) {
-        return parentIndexes[i];
-    }
-    
-    public boolean isLast() {
-        return size == first;
-    }
-
-    public void clear() {
-        size = 0;
-        first = 0;
-    }
-
-    public boolean isEmpty() {
-        return size == 0;
-    }
-}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
index 8a23c44..41f74f0 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
@@ -747,9 +747,9 @@
 
     public void deleteTuple(int pageId, int tupleIndex, RTreeOpContext ctx) throws Exception {
         ctx.leafFrame.delete(tupleIndex, leafCmp);
-        if (ctx.leafFrame.getTupleCount() == 0) {
-            ctx.leafFrame.setSmFlag(true);
-        } else {
+        
+        // if the page is empty, just leave it there for future inserts
+        if (ctx.leafFrame.getTupleCount() > 0) {
             ctx.leafFrame.computeMBR(ctx.splitKey, leafCmp);
             ctx.splitKey.setLeftPage(pageId);
         }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
index 998a984..34155d4 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
@@ -12,7 +12,7 @@
     @Override
     public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, MultiComparator multiCmp,
             FindTupleMode mode, FindTupleNoExactMatchPolicy matchPolicy) {
-        
+
         int maxFieldPos = multiCmp.getKeyFieldCount() / 2;
         for (int i = 0; i < frame.getTupleCount(); i++) {
             frameTuple.resetByTupleIndex(frame, i);
@@ -36,6 +36,13 @@
                     break;
                 }
             }
+            int remainingFieldCount = multiCmp.getFieldCount() - multiCmp.getKeyFieldCount();
+            for (int j = multiCmp.getKeyFieldCount(); j < multiCmp.getKeyFieldCount() + remainingFieldCount; j++) {
+                if (!compareField(searchKey, frameTuple, j)) {
+                    foundTuple = false;
+                    break;
+                }
+            }
             if (foundTuple) {
                 return i;
             }
@@ -43,6 +50,23 @@
         return -1;
     }
 
+    public boolean compareField(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, int fIdx) {
+        int searchKeyFieldLength = searchKey.getFieldLength(fIdx);
+        int frameTupleFieldLength = frameTuple.getFieldLength(fIdx);
+
+        if (searchKeyFieldLength != frameTupleFieldLength) {
+            return false;
+        }
+
+        for (int i = 0; i < searchKeyFieldLength; i++) {
+            if (searchKey.getFieldData(fIdx)[i + searchKey.getFieldStart(fIdx)] != frameTuple.getFieldData(fIdx)[i
+                    + frameTuple.getFieldStart(fIdx)]) {
+                return false;
+            }
+        }
+        return true;
+    }
+
     @Override
     public int insertSlot(int tupleIndex, int tupleOff) {
         int slotOff = getSlotEndOff() - slotSize;