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 d414073..9107b23 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,6 +105,12 @@
     }
 
     @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 {
 
@@ -603,19 +609,28 @@
         for (int i = 0; i < getTupleCount(); i++) {
             frameTuple.resetByTupleIndex(this, i);
 
+            boolean foundTuple = true;
             for (int j = 0; j < maxFieldPos; j++) {
                 int k = maxFieldPos + j;
                 int c1 = cmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
                         frameTuple.getFieldLength(j), tuple.getFieldData(j), tuple.getFieldStart(j),
                         tuple.getFieldLength(j));
 
+                if (c1 != 0) {
+                    foundTuple = false;
+                    break;
+                }
                 int c2 = cmp.getComparators()[k].compare(frameTuple.getFieldData(k), frameTuple.getFieldStart(k),
                         frameTuple.getFieldLength(k), tuple.getFieldData(k), tuple.getFieldStart(k),
                         tuple.getFieldLength(k));
-                if (c1 == 0 && c2 == 0) {
-                    return i;
+                if (c2 != 0) {
+                    foundTuple = false;
+                    break;
                 }
             }
+            if (foundTuple) {
+                return i;
+            }
         }
         return -1;
     }
@@ -638,21 +653,21 @@
         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()));
+                    frameTuple.getFieldStart(cmp.getKeyFieldCount()));
             if (id == pageId) {
                 return i;
             }
         }
         return -1;
     }
-    
+
     @Override
     public int findTupleByPointer(ITupleReference tuple, MultiComparator cmp) {
         frameTuple.setFieldCount(cmp.getFieldCount());
@@ -777,7 +792,7 @@
         RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
         RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
         frameTuple.setFieldCount(cmp.getFieldCount());
-        
+
         int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
         frameTuple.resetByTupleOffset(buf, tupleOff);
         int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
@@ -787,12 +802,12 @@
         rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
         rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(), 0);
     }
-    
+
     @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;
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 2815e48..8a22317 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
@@ -638,14 +638,13 @@
                 tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), interiorCmp);
             }
             boolean recomputeMBR = ctx.interiorFrame.recomputeMBR(ctx.splitKey.getLeftTuple(), tupleIndex, interiorCmp);
-            
-            
+
             if (recomputeMBR) {
                 ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), tupleIndex, interiorCmp);
                 ctx.pathList.removeLast();
-                
+
                 ctx.splitKey.reset();
-                if (!ctx.pathList.isEmpty()) {                   
+                if (!ctx.pathList.isEmpty()) {
                     ctx.interiorFrame.computeMBR(ctx.splitKey, interiorCmp);
                     ctx.splitKey.setLeftPage(parentId);
                 }
@@ -669,7 +668,7 @@
         findPath(ctx);
         updateParentForDelete(ctx);
     }
-    
+
     public int findTupleToDelete(RTreeOpContext ctx) throws Exception {
 
         ctx.traverseList.add(rootPage, -1, -1);
@@ -747,16 +746,13 @@
     }
 
     public void deleteTuple(int pageId, int tupleIndex, RTreeOpContext ctx) throws Exception {
-
-         if (ctx.leafFrame.getTupleCount() == 1) {
-        
-         } else {
-
         ctx.leafFrame.delete(tupleIndex, leafCmp);
-        ctx.leafFrame.computeMBR(ctx.splitKey, leafCmp);
-        ctx.splitKey.setLeftPage(pageId);
-
-         }
+        if (ctx.leafFrame.getTupleCount() == 0) {
+            ctx.leafFrame.setSmFlag(true);
+        } else {
+            ctx.leafFrame.computeMBR(ctx.splitKey, leafCmp);
+            ctx.splitKey.setLeftPage(pageId);
+        }
     }
 
     public void search(Stack<Integer> s, ITupleReference tuple, RTreeOpContext ctx, ArrayList<Rectangle> results)