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 5e766c5..b07c284 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
@@ -23,7 +23,7 @@
 
     public int findTupleByPointer(ITupleReference tuple, MultiComparator cmp);
     
-    public int findTuple(ITupleReference tuple, MultiComparator cmp);
+    public int findTupleIndex(ITupleReference tuple, MultiComparator cmp);
 
     public int getPageNsn();
 
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 9107b23..3572285 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
@@ -603,38 +603,11 @@
     }
 
     @Override
-    public int findTuple(ITupleReference tuple, MultiComparator cmp) {
+    public int findTupleIndex(ITupleReference tuple, MultiComparator cmp) {
         frameTuple.setFieldCount(cmp.getFieldCount());
-        int maxFieldPos = cmp.getKeyFieldCount() / 2;
-        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 (c2 != 0) {
-                    foundTuple = false;
-                    break;
-                }
-            }
-            if (foundTuple) {
-                return i;
-            }
-        }
-        return -1;
+        return slotManager.findTupleIndex(tuple, frameTuple, cmp, null, null);
     }
-
+    
     @Override
     public void delete(int tupleIndex, MultiComparator cmp) throws Exception {
         frameTuple.setFieldCount(cmp.getFieldCount());
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 8a22317..8a23c44 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
@@ -708,7 +708,7 @@
                 }
             } else {
                 ctx.leafFrame.setPage(node);
-                int tupleIndex = ctx.leafFrame.findTuple(ctx.tuple, leafCmp);
+                int tupleIndex = ctx.leafFrame.findTupleIndex(ctx.tuple, leafCmp);
                 if (tupleIndex != -1) {
 
                     node.releaseReadLatch();
@@ -725,7 +725,7 @@
                     if (ctx.leafFrame.getPageLsn() != pageLsn) {
                         // The page was changed while we unlocked it
 
-                        tupleIndex = ctx.leafFrame.findTuple(ctx.tuple, leafCmp);
+                        tupleIndex = ctx.leafFrame.findTupleIndex(ctx.tuple, leafCmp);
                         if (tupleIndex == -1) {
                             ctx.traverseList.add(pageId, parentLsn, parentIndex);
                             ctx.pathList.add(pageId, parentLsn, ctx.traverseList.size() - 1);
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 77bddd7..998a984 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,6 +12,34 @@
     @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);
+
+            boolean foundTuple = true;
+            for (int j = 0; j < maxFieldPos; j++) {
+                int k = maxFieldPos + j;
+                int c1 = multiCmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+                        frameTuple.getFieldLength(j), searchKey.getFieldData(j), searchKey.getFieldStart(j),
+                        searchKey.getFieldLength(j));
+
+                if (c1 != 0) {
+                    foundTuple = false;
+                    break;
+                }
+                int c2 = multiCmp.getComparators()[k].compare(frameTuple.getFieldData(k), frameTuple.getFieldStart(k),
+                        frameTuple.getFieldLength(k), searchKey.getFieldData(k), searchKey.getFieldStart(k),
+                        searchKey.getFieldLength(k));
+                if (c2 != 0) {
+                    foundTuple = false;
+                    break;
+                }
+            }
+            if (foundTuple) {
+                return i;
+            }
+        }
         return -1;
     }