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 9d60464..5e766c5 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
@@ -5,14 +5,24 @@
 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.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.FindPathList;
 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 boolean recomputeMBR(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
 
-    public int findTuple(ITupleReference tuple, FindPathList findPathList, int parentId, MultiComparator cmp);
+    public void computeMBR(ISplitKey splitKey, MultiComparator cmp);
+    
+    public void delete(int tupleIndex, MultiComparator cmp) throws Exception;
+    
+    public int findTupleByPointer(int pageId, MultiComparator cmp);
+    
+    public int findTupleByPointer(ITupleReference tuple, TraverseList traverseList, int parentId, MultiComparator cmp);
 
+    public int findTupleByPointer(ITupleReference tuple, MultiComparator cmp);
+    
     public int findTuple(ITupleReference tuple, MultiComparator cmp);
 
     public int getPageNsn();
@@ -25,19 +35,15 @@
 
     public int getBestChildPageId(MultiComparator cmp);
 
-    public boolean checkEnlargement(ITupleReference tuple, TupleEntryArrayList entries,
-            ITreeIndexTupleReference[] nodesMBRs, MultiComparator cmp);
+    public boolean findBestChild(ITupleReference tuple, TupleEntryArrayList entries, MultiComparator cmp);
 
-    public void adjustNodeMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp);
+    public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp);
 
-    public void adjustKey(ITupleReference tuple, MultiComparator cmp);
+    public void adjustKey(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
 
     public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey,
             TupleEntryArrayList entries1, TupleEntryArrayList entries2, Rectangle[] rec) throws Exception;
 
-    public void reinsert(ITupleReference tuple, ITreeIndexTupleReference nodeMBR, TupleEntryArrayList entries,
-            ISplitKey splitKey, MultiComparator cmp) throws Exception;
-
     public Rectangle intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
 
     public int getChildPageIdIfIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
index 7d0e886..d414073 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
@@ -10,13 +10,16 @@
 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.api.TreeIndexException;
 import edu.uci.ics.hyracks.storage.am.common.frames.TreeIndexNSMFrame;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleMode;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleNoExactMatchPolicy;
 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.FindPathList;
 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.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;
@@ -29,7 +32,6 @@
 
     private ITreeIndexTupleReference cmpFrameTuple;
 
-    private static final double reinsertFactor = 0.3;
     private static final double splitFactor = 0.4;
     private static final int nearMinimumOverlapFactor = 32;
 
@@ -102,82 +104,6 @@
         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());
-    // frameTuple.setFieldCount(cmp.getFieldCount());
-    // rightFrame.setPageTupleFieldCount(cmp.getFieldCount());
-    //
-    // ByteBuffer right = rightFrame.getBuffer();
-    // int tupleCount = getTupleCount();
-    //
-    // int tuplesToLeft;
-    // int mid = tupleCount / 2;
-    // ITreeIndexFrame targetFrame = null;
-    // int tupleOff = slotManager.getTupleOff(slotManager.getSlotOff(mid));
-    // frameTuple.resetByTupleOffset(buf, tupleOff);
-    // if (cmp.compare(tuple, frameTuple) >= 0) {
-    // tuplesToLeft = mid + (tupleCount % 2);
-    // targetFrame = rightFrame;
-    // } else {
-    // tuplesToLeft = mid;
-    // targetFrame = this;
-    // }
-    // int tuplesToRight = tupleCount - tuplesToLeft;
-    //
-    // // copy entire page
-    // System.arraycopy(buf.array(), 0, right.array(), 0, buf.capacity());
-    //
-    // // on right page we need to copy rightmost slots to left
-    // int src = rightFrame.getSlotManager().getSlotEndOff();
-    // int dest = rightFrame.getSlotManager().getSlotEndOff() + tuplesToLeft
-    // * rightFrame.getSlotManager().getSlotSize();
-    // int length = rightFrame.getSlotManager().getSlotSize() * tuplesToRight;
-    // System.arraycopy(right.array(), src, right.array(), dest, length);
-    // right.putInt(tupleCountOff, tuplesToRight);
-    //
-    // // on left page only change the tupleCount indicator
-    // buf.putInt(tupleCountOff, tuplesToLeft);
-    //
-    // // compact both pages
-    // rightFrame.compact(cmp);
-    // compact(cmp);
-    //
-    // // insert last key
-    // targetFrame.insert(tuple, cmp);
-    //
-    // // set split key to be highest value in left page
-    // // TODO: find a better way to find the key size
-    // tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
-    // frameTuple.resetByTupleOffset(buf, tupleOff);
-    //
-    // int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0,
-    // cmp.getKeyFieldCount());
-    // splitKey.initData(splitKeySize);
-    // this.adjustNodeMBR(tuples, cmp);
-    // rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0,
-    // rTreeSplitKey.getLeftPageBuffer(), 0);
-    // rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(),
-    // 0);
-    //
-    // ((IRTreeFrame) rightFrame).adjustNodeMBR(((NSMRTreeFrame)
-    // rightFrame).getTuples(), cmp);
-    // rTreeTupleWriterRightFrame.writeTupleFields(((NSMRTreeFrame)
-    // rightFrame).getTuples(), 0,
-    // rTreeSplitKey.getRightPageBuffer(), 0);
-    // rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(),
-    // 0);
-    //
-    // return 0;
-    // }
-
     @Override
     public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey,
             TupleEntryArrayList entries1, TupleEntryArrayList entries2, Rectangle[] rec) throws Exception {
@@ -237,13 +163,13 @@
         // int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0,
         // cmp.getKeyFieldCount());
         // splitKey.initData(splitKeySize);
-        // this.adjustNodeMBR(tuples, cmp);
+        // this.adjustMBR(tuples, cmp);
         // rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0,
         // rTreeSplitKey.getLeftPageBuffer(), 0);
         // rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(),
         // 0);
         //
-        // ((IRTreeFrame) rightFrame).adjustNodeMBR(((NSMRTreeFrame)
+        // ((IRTreeFrame) rightFrame).adjustMBR(((NSMRTreeFrame)
         // rightFrame).getTuples(), cmp);
         // rTreeTupleWriterRightFrame.writeTupleFields(((NSMRTreeFrame)
         // rightFrame).getTuples(), 0,
@@ -258,7 +184,6 @@
         RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame = ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
         rightFrame.setPageTupleFieldCount(cmp.getFieldCount());
         frameTuple.setFieldCount(cmp.getFieldCount());
-        cmpFrameTuple.setFieldCount(cmp.getFieldCount());
 
         // calculations are based on the R*-tree paper
         int m = (int) Math.floor((getTupleCount() + 1) * splitFactor);
@@ -397,11 +322,11 @@
         int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
 
         splitKey.initData(splitKeySize);
-        this.adjustNodeMBR(tuples, cmp);
+        this.adjustMBR(tuples, cmp);
         rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
         rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(), 0);
 
-        ((IRTreeFrame) rightFrame).adjustNodeMBR(((NSMRTreeFrame) rightFrame).getTuples(), cmp);
+        ((IRTreeFrame) rightFrame).adjustMBR(((NSMRTreeFrame) rightFrame).getTuples(), cmp);
         rTreeTupleWriterRightFrame.writeTupleFields(((NSMRTreeFrame) rightFrame).getTuples(), 0,
                 rTreeSplitKey.getRightPageBuffer(), 0);
         rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(), 0);
@@ -444,9 +369,7 @@
     }
 
     @Override
-    public boolean checkEnlargement(ITupleReference tuple, TupleEntryArrayList entries,
-            ITreeIndexTupleReference[] nodesMBRs, MultiComparator cmp) {
-
+    public boolean findBestChild(ITupleReference tuple, TupleEntryArrayList entries, MultiComparator cmp) {
         cmpFrameTuple.setFieldCount(cmp.getFieldCount());
         frameTuple.setFieldCount(cmp.getFieldCount());
 
@@ -544,195 +467,9 @@
         frameTuple.resetByTupleIndex(this, bestChild);
         if (minEnlargedArea > 0.0) {
             return true;
-            // enlarge(frameTuple, tuple, cmp);
         } else {
             return false;
         }
-
-        // nodesMBRs[(int) getLevel() - 1].resetByTupleIndex(this, bestChild);
-
-        // return the page id of the bestChild tuple
-        // return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
-    }
-
-    // @Override
-    // public int getChildPageId(ITupleReference tuple, TupleEntryArrayList
-    // entries, ITreeIndexTupleReference[] nodesMBRs,
-    // 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);
-    // entries.add(i, enlargedArea);
-    // if (enlargedArea < minEnlargedArea) {
-    // minEnlargedArea = enlargedArea;
-    // bestChild = i;
-    // }
-    // }
-    // if (minEnlargedArea < entries.getDoubleEpsilon() || minEnlargedArea >
-    // entries.getDoubleEpsilon()) {
-    // minEnlargedArea = Double.MAX_VALUE;
-    // int k;
-    // if (getTupleCount() > nearMinimumOverlapFactor) {
-    // // sort the entries based on their area enlargement needed
-    // // to include the object
-    // entries.sort(EntriesOrder.ASCENDING, getTupleCount());
-    // 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, entries.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;
-    // }
-    // }
-    // }
-    // }
-    // frameTuple.resetByTupleIndex(this, bestChild);
-    // nodesMBRs[(int) getLevel() - 1].resetByTupleIndex(this, bestChild);
-    //
-    // entries.clear();
-    //
-    // // return the page id of the bestChild tuple
-    // return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
-    // }
-
-    @Override
-    public void reinsert(ITupleReference tuple, ITreeIndexTupleReference nodeMBR, TupleEntryArrayList entries,
-            ISplitKey splitKey, MultiComparator cmp) throws Exception {
-
-        nodeMBR.setFieldCount(cmp.getFieldCount());
-        int maxFieldPos = cmp.getKeyFieldCount() / 2;
-        for (int i = 0; i < getTupleCount() + 1; ++i) {
-            if (i < getTupleCount()) {
-                frameTuple.resetByTupleIndex(this, i);
-            }
-            double centerDistance = 0.0;
-            for (int j = 0; j < maxFieldPos; j++) {
-                int k = maxFieldPos + j;
-
-                // TODO: an optimization can be done here, compute nodeCenter
-                // only once and reuse it
-                double nodeCenter = (DoubleSerializerDeserializer.getDouble(nodeMBR.getFieldData(j),
-                        nodeMBR.getFieldStart(j)) + DoubleSerializerDeserializer.getDouble(nodeMBR.getFieldData(k),
-                        nodeMBR.getFieldStart(k))) / 2.0;
-
-                double childCenter;
-                if (i < getTupleCount()) {
-                    childCenter = (DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(j),
-                            frameTuple.getFieldStart(j)) + DoubleSerializerDeserializer.getDouble(
-                            frameTuple.getFieldData(k), frameTuple.getFieldStart(k))) / 2.0;
-                } else { // special case to deal with the new tuple to be
-                         // inserted
-                    childCenter = (DoubleSerializerDeserializer
-                            .getDouble(tuple.getFieldData(j), tuple.getFieldStart(j)) + DoubleSerializerDeserializer
-                            .getDouble(tuple.getFieldData(k), tuple.getFieldStart(k))) / 2.0;
-                }
-
-                double d = childCenter - nodeCenter;
-                centerDistance += d * d;
-            }
-            if (i < getTupleCount()) {
-                entries.add(i, centerDistance);
-            } else { // special case to deal with the new tuple to be inserted
-                entries.add(-1, centerDistance);
-            }
-
-        }
-        entries.sort(EntriesOrder.DESCENDING, getTupleCount() + 1);
-
-        int j = (int) Math.floor((getTupleCount() + 1) * reinsertFactor);
-        for (int i = 0; i < j; i++) {
-            if (entries.get(i).getTupleIndex() != -1) {
-                frameTuple.resetByTupleIndex(this, i);
-                delete(frameTuple, cmp, false);
-            } else {
-                delete(tuple, cmp, false);
-            }
-
-        }
-
-        // rebuild the node's MBR
-        RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
-        RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
-        this.adjustNodeMBR(tuples, cmp);
-
-        int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
-        frameTuple.resetByTupleOffset(buf, tupleOff);
-        int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
-        rTreeSplitKey.initData(splitKeySize);
-
-        rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
-
-        entries.clear();
     }
 
     private double area(ITupleReference tuple, MultiComparator cmp) {
@@ -849,9 +586,11 @@
     }
 
     @Override
-    public void adjustKey(ITupleReference tuple, MultiComparator cmp) {
+    public void adjustKey(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
         frameTuple.setFieldCount(cmp.getFieldCount());
-        int tupleIndex = findTuple(tuple, cmp);
+        if (tupleIndex == -1) {
+            tupleIndex = findTupleByPointer(tuple, cmp);
+        }
         if (tupleIndex != -1) {
             tupleWriter.writeTuple(tuple, buf, getTupleOffset(tupleIndex));
         }
@@ -860,6 +599,63 @@
     @Override
     public int findTuple(ITupleReference tuple, MultiComparator cmp) {
         frameTuple.setFieldCount(cmp.getFieldCount());
+        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        for (int i = 0; i < getTupleCount(); i++) {
+            frameTuple.resetByTupleIndex(this, i);
+
+            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));
+
+                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;
+                }
+            }
+        }
+        return -1;
+    }
+
+    @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()),
@@ -874,7 +670,7 @@
     }
 
     @Override
-    public int findTuple(ITupleReference tuple, FindPathList findPathList, int parentIndex, MultiComparator cmp) {
+    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);
@@ -887,14 +683,14 @@
             } else {
                 int pageId = IntegerSerializerDeserializer.getInt(frameTuple.getFieldData(cmp.getKeyFieldCount()),
                         frameTuple.getFieldStart(cmp.getKeyFieldCount()));
-                findPathList.add(pageId, parentIndex);
+                traverseList.add(pageId, -1, parentIndex);
             }
         }
         return -1;
     }
 
     @Override
-    public void adjustNodeMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
+    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);
@@ -975,4 +771,45 @@
         // TODO Auto-generated method stub
         return 0;
     }
+
+    @Override
+    public void computeMBR(ISplitKey splitKey, MultiComparator cmp) {
+        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());
+
+        splitKey.initData(splitKeySize);
+        this.adjustMBR(tuples, cmp);
+        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;
+            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;
+    }
 }
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
index 2522e17..83289e4 100644
--- 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
@@ -36,7 +36,7 @@
         return size;
     }
 
-    public void add(int pageId, int parentId) {
+    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);
@@ -52,7 +52,7 @@
         }
 
         pageIds[size] = pageId;
-        parentIndexes[size] = parentId;
+        parentIndexes[size] = parentIndex;
         size++;
     }
 
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/IntArrayList.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/IntArrayList.java
index 1cc95d1..4be3b38 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/IntArrayList.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/IntArrayList.java
@@ -18,17 +18,23 @@
 public class IntArrayList {
     private int[] data;
     private int size;
+    private int first;
     private final int growth;
 
     public IntArrayList(int initialCapacity, int growth) {
         data = new int[initialCapacity];
         size = 0;
+        first = 0;
         this.growth = growth;
     }
 
     public int size() {
         return size;
     }
+    
+    public int first() {
+        return first;
+    }
 
     public void add(int i) {
         if (size == data.length) {
@@ -54,10 +60,29 @@
         return data[i];
     }
 
-    public void clear() {
-        size = 0;
+    // WARNING: caller is responsible for checking i < size
+    public void set(int i, int value) {
+        data[i] = value;
+
     }
 
+    public int getFirst() {
+        return data[first];
+    }
+    
+    public void moveFirst() {
+        first++;
+    }
+    
+    public void clear() {
+        size = 0;
+        first = 0;
+    }
+
+    public boolean isLast() {
+        return size == first;
+    }
+    
     public boolean isEmpty() {
         return size == 0;
     }
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
new file mode 100644
index 0000000..093bc8c
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/PathList.java
@@ -0,0 +1,78 @@
+/*
+ * 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 PathList {
+    private IntArrayList pageIds;
+    private IntArrayList pageLsns;
+    private IntArrayList pageIndexes;
+    
+    public PathList(int initialCapacity, int growth) {
+        pageIds = new IntArrayList(initialCapacity, growth);
+        pageLsns = new IntArrayList(initialCapacity, growth);
+        pageIndexes = new IntArrayList(initialCapacity, growth);
+    }
+
+    public int size() {
+        return pageIds.size();
+    }
+
+    public void add(int pageId, int pageLsn, int pageIndex) {
+        pageIds.add(pageId);
+        pageLsns.add(pageLsn);
+        pageIndexes.add(pageIndex);
+    }
+
+    public int getLastPageId() {
+        return pageIds.getLast();
+    }
+    
+    public int getLastPageLsn() {
+        return pageLsns.getLast();
+    }
+    
+    public int getLastPageIndex() {
+        return pageIndexes.getLast();
+    }
+
+    public int getPageId(int i) {
+        return pageIds.get(i);
+    }
+    
+    public int getPageLsn(int i) {
+        return pageLsns.get(i);
+    }
+    
+    public int getPageIndex(int i) {
+        return pageIndexes.get(i);
+    }
+    
+    public void removeLast() {
+        pageIds.removeLast();
+        pageLsns.removeLast();
+        pageIndexes.removeLast();
+    }
+    
+    public void clear() {
+        pageIds.clear();
+        pageLsns.clear();
+        pageIndexes.clear();
+    }
+
+    public boolean isEmpty() {
+        return pageIds.isEmpty();
+    }
+}
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 534ca50..2815e48 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
@@ -3,6 +3,8 @@
 import java.util.ArrayList;
 import java.util.Stack;
 import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
 
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
@@ -25,6 +27,7 @@
 
     private final AtomicInteger globalNsn; // Global node sequence number
     private int numOfPages = 1;
+    private final ReadWriteLock treeLatch;
 
     private final IFreePageManager freePageManager;
     private final IBufferCache bufferCache;
@@ -57,6 +60,7 @@
         this.leafCmp = leafCmp;
         this.dim = dim;
         globalNsn = new AtomicInteger();
+        this.treeLatch = new ReentrantReadWriteLock(true);
     }
 
     public synchronized void incrementGlobalNsn() {
@@ -150,30 +154,35 @@
         if (created)
             return;
 
-        // check if another thread beat us to it
-        if (created)
-            return;
-
-        freePageManager.init(metaFrame, rootPage);
-
-        // initialize root page
-        ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), true);
-        pins++;
-
-        rootNode.acquireWriteLatch();
-        writeLatchesAcquired++;
+        treeLatch.writeLock().lock();
         try {
-            leafFrame.setPage(rootNode);
-            leafFrame.initBuffer((byte) 0);
-        } finally {
-            rootNode.releaseWriteLatch();
-            writeLatchesReleased++;
-            bufferCache.unpin(rootNode);
-            unpins++;
-        }
-        currentLevel = 0;
+            // check if another thread beat us to it
+            if (created)
+                return;
 
-        created = true;
+            freePageManager.init(metaFrame, rootPage);
+
+            // initialize root page
+            ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), true);
+            pins++;
+
+            rootNode.acquireWriteLatch();
+            writeLatchesAcquired++;
+            try {
+                leafFrame.setPage(rootNode);
+                leafFrame.initBuffer((byte) 0);
+            } finally {
+                rootNode.releaseWriteLatch();
+                writeLatchesReleased++;
+                bufferCache.unpin(rootNode);
+                unpins++;
+            }
+            currentLevel = 0;
+
+            created = true;
+        } finally {
+            treeLatch.writeLock().unlock();
+        }
     }
 
     public void open(int fileId) {
@@ -190,150 +199,6 @@
         return new RTreeOpContext(op, interiorFrame, leafFrame, metaFrame, 8, dim);
     }
 
-    private void createNewRoot(RTreeOpContext ctx) throws Exception {
-        rootSplits++; // debug
-        splitsByLevel[currentLevel]++;
-        currentLevel++;
-
-        // make sure the root is always at the same level
-        ICachedPage leftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, ctx.splitKey.getLeftPage()),
-                false);
-        pins++;
-        leftNode.acquireWriteLatch(); // TODO: think about whether latching is
-                                      // really required
-        writeLatchesAcquired++;
-        try {
-            ICachedPage rightNode = bufferCache.pin(
-                    BufferedFileHandle.getDiskPageId(fileId, ctx.splitKey.getRightPage()), false);
-            pins++;
-            rightNode.acquireWriteLatch(); // TODO: think about whether latching
-                                           // is really required
-            writeLatchesAcquired++;
-            try {
-                int newLeftId = freePageManager.getFreePage(ctx.metaFrame);
-                ICachedPage newLeftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, newLeftId), true);
-                pins++;
-                newLeftNode.acquireWriteLatch(); // TODO: think about whether
-                                                 // latching is really required
-                writeLatchesAcquired++;
-                try {
-                    // copy left child to new left child
-                    System.arraycopy(leftNode.getBuffer().array(), 0, newLeftNode.getBuffer().array(), 0, newLeftNode
-                            .getBuffer().capacity());
-
-                    // initialize new root (leftNode becomes new root)
-                    ctx.interiorFrame.setPage(leftNode);
-                    ctx.interiorFrame.initBuffer((byte) (ctx.interiorFrame.getLevel() + 1));
-
-                    ctx.splitKey.setLeftPage(newLeftId);
-
-                    ctx.interiorFrame.insert(ctx.splitKey.getLeftTuple(), interiorCmp);
-                    ctx.interiorFrame.insert(ctx.splitKey.getRightTuple(), interiorCmp);
-                } finally {
-                    newLeftNode.releaseWriteLatch();
-                    writeLatchesReleased++;
-                    bufferCache.unpin(newLeftNode);
-                    unpins++;
-                }
-            } finally {
-                rightNode.releaseWriteLatch();
-                writeLatchesReleased++;
-                bufferCache.unpin(rightNode);
-                unpins++;
-            }
-        } finally {
-            leftNode.releaseWriteLatch();
-            writeLatchesReleased++;
-            bufferCache.unpin(leftNode);
-            unpins++;
-        }
-    }
-
-    private final void acquireLatch(ICachedPage node, TreeIndexOp op, boolean isLeaf) {
-        if (isLeaf && (op.equals(TreeIndexOp.TI_INSERT) || op.equals(TreeIndexOp.TI_DELETE))) {
-            node.acquireWriteLatch();
-            writeLatchesAcquired++;
-        } else {
-            node.acquireReadLatch();
-            readLatchesAcquired++;
-        }
-    }
-
-    // public void insert(ITupleReference tuple, RTreeOpContext ctx) throws
-    // Exception {
-    // 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());
-    // for (int i = 0; i < currentLevel; i++) {
-    // ctx.overflowArray.add((byte) 0);
-    // }
-    // insertImpl(rootPage, null, (byte) 0, ctx);
-    //
-    // // we split the root, here is the key for a new root
-    // if (ctx.splitKey.getLeftPageBuffer() != null) {
-    // createNewRoot(ctx);
-    // }
-    // }
-
-    // public void insertImpl(int pageId, ICachedPage parent, byte desiredLevel,
-    // RTreeOpContext ctx) throws Exception {
-    // ICachedPage node =
-    // bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
-    // pins++;
-    // ctx.interiorFrame.setPage(node);
-    // boolean isLeaf = ctx.interiorFrame.isLeaf();
-    // acquireLatch(node, ctx.op, isLeaf);
-    //
-    // // latch coupling TODO: check the correctness of this
-    // if (parent != null) {
-    // parent.releaseReadLatch();
-    // readLatchesReleased++;
-    // bufferCache.unpin(parent);
-    // unpins++;
-    // }
-    //
-    // if (ctx.interiorFrame.getLevel() > desiredLevel) {
-    // int childPageId = ctx.interiorFrame.checkEnlargement(ctx.getTuple(),
-    // ctx.tupleEntries1, ctx.nodesMBRs,
-    // interiorCmp);
-    //
-    // insertImpl(childPageId, node, desiredLevel, ctx);
-    // if (ctx.splitKey.getLeftPageBuffer() != null) {
-    // node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId),
-    // false);
-    // pins++;
-    // node.acquireWriteLatch();
-    // writeLatchesAcquired++;
-    // try {
-    // ctx.interiorFrame.setPage(node);
-    // ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), interiorCmp);
-    // insertTuple(pageId, ctx.splitKey.getRightTuple(), ctx, isLeaf);
-    // } finally {
-    // node.releaseWriteLatch();
-    // writeLatchesReleased++;
-    // bufferCache.unpin(node);
-    // unpins++;
-    // }
-    // }
-    // } else {
-    // try {
-    // if (isLeaf) {
-    // ctx.leafFrame.setPage(node);
-    // ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
-    // }
-    // insertTuple(pageId, ctx.getTuple(), ctx, isLeaf);
-    // } finally {
-    // node.releaseWriteLatch();
-    // writeLatchesReleased++;
-    // bufferCache.unpin(node);
-    // unpins++;
-    // }
-    // }
-    // }
-
     public void insert(ITupleReference tuple, RTreeOpContext ctx) throws Exception {
         ctx.reset();
         ctx.setTuple(tuple);
@@ -341,20 +206,17 @@
         ctx.splitKey.getLeftTuple().setFieldCount(interiorCmp.getFieldCount());
         ctx.splitKey.getRightTuple().setFieldCount(interiorCmp.getFieldCount());
         ctx.interiorFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
-        for (int i = 0; i < currentLevel; i++) {
-            ctx.overflowArray.add((byte) 0);
-        }
+        ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
 
         ICachedPage leafNode = findLeaf(ctx);
 
-        int pageId = ctx.path.getLast();
-        ctx.path.removeLast();
-        ctx.pageLsns.removeLast();
-        insertTuple(leafNode, pageId, ctx.getTuple(), ctx, ctx.leafFrame.isLeaf());
+        int pageId = ctx.pathList.getLastPageId();
+        ctx.pathList.removeLast();
+        insertTuple(leafNode, pageId, ctx.getTuple(), ctx, true);
 
         while (true) {
             if (ctx.splitKey.getLeftPageBuffer() != null) {
-                updateParent(ctx);
+                updateParentForInsert(ctx);
             } else {
                 break;
             }
@@ -366,113 +228,6 @@
         unpins++;
     }
 
-    public void updateParent(RTreeOpContext ctx) throws Exception {
-        int parentId = ctx.path.getLast();
-        ICachedPage parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
-        pins++;
-        parentNode.acquireWriteLatch();
-        writeLatchesAcquired++;
-        ctx.interiorFrame.setPage(parentNode);
-        boolean foundParent = true;
-
-        if (ctx.interiorFrame.getPageLsn() != ctx.pageLsns.getLast()) {
-            foundParent = false;
-            while (true) {
-                if (ctx.interiorFrame.findTuple(ctx.splitKey.getLeftTuple(), interiorCmp) != -1) {
-                    // found the parent
-                    foundParent = true;
-                    break;
-                }
-                int rightPage = ctx.interiorFrame.getRightPage();
-                parentNode.releaseWriteLatch();
-                writeLatchesReleased++;
-                bufferCache.unpin(parentNode);
-                unpins++;
-
-                if (rightPage == -1) {
-                    break;
-                }
-
-                parentId = rightPage;
-                parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
-                pins++;
-                parentNode.acquireWriteLatch();
-                writeLatchesAcquired++;
-                ctx.interiorFrame.setPage(parentNode);
-            }
-        } 
-        if (foundParent) {
-            ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), interiorCmp);
-            insertTuple(parentNode, parentId, ctx.splitKey.getRightTuple(), ctx, ctx.interiorFrame.isLeaf());
-            ctx.path.removeLast();
-            ctx.pageLsns.removeLast();
-
-            parentNode.releaseWriteLatch();
-            writeLatchesReleased++;
-            bufferCache.unpin(parentNode);
-            unpins++;
-            return;
-        }
-
-        // very rare situation when the there is a root split, do an exhaustive
-        // breadth-first traversal looking for the parent tuple
-
-        ctx.path.clear();
-        ctx.pageLsns.clear();
-        ctx.findPathList.clear();
-        findPath(ctx);
-        updateParent(ctx);
-    }
-
-    public void findPath(RTreeOpContext ctx) throws Exception {
-        int pageId = rootPage;
-        int parentIndex = -1;
-        int parentLsn = 0;
-        int pageLsn, pageIndex;
-        ctx.findPathList.add(pageId, parentIndex);
-
-        while (!ctx.findPathList.isLast()) {
-            pageId = ctx.findPathList.getFirstPageId();
-            parentIndex = ctx.findPathList.getFirstParentIndex();
-            ctx.findPathList.moveFirst();
-            ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
-            pins++;
-            node.acquireReadLatch();
-            readLatchesAcquired++;
-            ctx.interiorFrame.setPage(node);
-            pageLsn = ctx.interiorFrame.getPageLsn();
-            pageIndex = ctx.findPathList.size() - 1;
-            ctx.findPathList.setPageLsn(pageIndex, pageLsn);
-
-            if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
-                ctx.findPathList.add(ctx.interiorFrame.getRightPage(), parentIndex);
-            }
-            parentLsn = pageLsn;
-            
-            if (ctx.interiorFrame.findTuple(ctx.splitKey.getLeftTuple(), ctx.findPathList, pageIndex, interiorCmp) != -1) {
-                fillPath(ctx, pageIndex);
-
-                node.releaseReadLatch();
-                readLatchesReleased++;
-                bufferCache.unpin(node);
-                unpins++;
-                return;
-            }
-            node.releaseReadLatch();
-            readLatchesReleased++;
-            bufferCache.unpin(node);
-            unpins++;
-        } 
-    }
-
-    public void fillPath(RTreeOpContext ctx, int pageIndex) throws Exception {
-        if (pageIndex != -1) {
-            fillPath(ctx, ctx.findPathList.getParentIndex(pageIndex));
-            ctx.path.add(ctx.findPathList.getPageId(pageIndex));
-            ctx.pageLsns.add(ctx.findPathList.getPageLsn(pageIndex));
-        }
-    }
-    
     public ICachedPage findLeaf(RTreeOpContext ctx) throws Exception {
         int pageId = rootPage;
         boolean writeLatched = false;
@@ -498,9 +253,8 @@
                     readLatchesAcquired++;
                 }
             }
-            ctx.path.add(pageId);
             pageLsn = ctx.interiorFrame.getPageLsn();
-            ctx.pageLsns.add(pageLsn);
+            ctx.pathList.add(pageId, pageLsn, -1);
 
             if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
                 // Concurrent split detected, go back to parent and re-choose
@@ -517,17 +271,21 @@
                     unpins++;
                 }
 
-                ctx.path.removeLast();
-                ctx.pageLsns.removeLast();
+                ctx.pathList.removeLast();
+
+                pageId = ctx.pathList.getLastPageId();
+                if (pageId != rootPage) {
+                    parentLsn = ctx.pathList.getPageLsn(ctx.pathList.size() - 2);
+                }
+
                 writeLatched = false;
                 continue;
             }
-            parentLsn = pageLsn;
 
             if (!isLeaf) {
                 // checkEnlargement must be called *before* getBestChildPageId
-                boolean needsEnlargement = ctx.interiorFrame.checkEnlargement(ctx.getTuple(), ctx.tupleEntries1,
-                        ctx.nodesMBRs, interiorCmp);
+                boolean needsEnlargement = ctx.interiorFrame.findBestChild(ctx.getTuple(), ctx.tupleEntries1,
+                        interiorCmp);
                 int childPageId = ctx.interiorFrame.getBestChildPageId(interiorCmp);
 
                 if (needsEnlargement) {
@@ -547,7 +305,8 @@
 
                         if (ctx.interiorFrame.getPageLsn() != pageLsn) {
                             // The page was changed while we unlocked it; thus,
-                            // retry
+                            // retry (re-choose best child)
+                            ctx.pathList.removeLast();
                             continue;
                         }
                     }
@@ -568,16 +327,15 @@
                     unpins++;
                 }
                 pageId = childPageId;
+                parentLsn = pageLsn;
             } else {
                 ctx.leafFrame.setPage(node);
-                ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
                 return node;
             }
         }
-
     }
 
-    private void insertTuple(ICachedPage leafNode, int pageId, ITupleReference tuple, RTreeOpContext ctx, boolean isLeaf)
+    private void insertTuple(ICachedPage node, int pageId, ITupleReference tuple, RTreeOpContext ctx, boolean isLeaf)
             throws Exception {
         FrameOpSpaceStatus spaceStatus;
         if (!isLeaf) {
@@ -618,21 +376,6 @@
                 writeLatchesAcquired++;
 
                 try {
-                    // if the level is not the root level and this is the
-                    // first overflow treatment in the given level during the
-                    // insertion of one data rectangle
-                    /*
-                     * if (ctx.overflowArray.get((int)
-                     * ctx.interiorFrame.getLevel()) == 0 && pageId != rootPage)
-                     * { if (!isLeaf) { ctx.overflowArray.set((int)
-                     * ctx.interiorFrame.getLevel(), (byte) 1);
-                     * ctx.interiorFrame.reinsert(tuple,
-                     * ctx.nodesMBRs[ctx.interiorFrame.getLevel()], ctx.entries,
-                     * ctx.splitKey, interiorCmp); } else {
-                     * ctx.overflowArray.set(0, (byte) 1);
-                     * ctx.leafFrame.reinsert(tuple, ctx.nodesMBRs[0],
-                     * ctx.entries, ctx.splitKey, leafCmp); } } else {
-                     */
                     IRTreeFrame rightFrame;
                     int ret;
                     numOfPages++; // debug
@@ -681,11 +424,11 @@
                         writeLatchesAcquired++;
                         try {
                             // copy left child to new left child
-                            System.arraycopy(leafNode.getBuffer().array(), 0, newLeftNode.getBuffer().array(), 0,
+                            System.arraycopy(node.getBuffer().array(), 0, newLeftNode.getBuffer().array(), 0,
                                     newLeftNode.getBuffer().capacity());
 
                             // initialize new root (leftNode becomes new root)
-                            ctx.interiorFrame.setPage(leafNode);
+                            ctx.interiorFrame.setPage(node);
                             ctx.interiorFrame.initBuffer((byte) (ctx.interiorFrame.getLevel() + 1));
 
                             ctx.splitKey.setLeftPage(newLeftId);
@@ -714,6 +457,308 @@
         }
     }
 
+    public void updateParentForInsert(RTreeOpContext ctx) throws Exception {
+        int parentId = ctx.pathList.getLastPageId();
+        ICachedPage parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
+        pins++;
+        parentNode.acquireWriteLatch();
+        writeLatchesAcquired++;
+        ctx.interiorFrame.setPage(parentNode);
+        boolean foundParent = true;
+
+        if (ctx.interiorFrame.getPageLsn() != ctx.pathList.getLastPageLsn()) {
+            foundParent = false;
+            while (true) {
+                if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), interiorCmp) != -1) {
+                    // found the parent
+                    foundParent = true;
+                    break;
+                }
+                int rightPage = ctx.interiorFrame.getRightPage();
+                parentNode.releaseWriteLatch();
+                writeLatchesReleased++;
+                bufferCache.unpin(parentNode);
+                unpins++;
+
+                if (rightPage == -1) {
+                    break;
+                }
+
+                parentId = rightPage;
+                parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
+                pins++;
+                parentNode.acquireWriteLatch();
+                writeLatchesAcquired++;
+                ctx.interiorFrame.setPage(parentNode);
+            }
+        }
+        if (foundParent) {
+            ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), -1, interiorCmp);
+            insertTuple(parentNode, parentId, ctx.splitKey.getRightTuple(), ctx, ctx.interiorFrame.isLeaf());
+            ctx.pathList.removeLast();
+
+            parentNode.releaseWriteLatch();
+            writeLatchesReleased++;
+            bufferCache.unpin(parentNode);
+            unpins++;
+            return;
+        }
+
+        // very rare situation when the there is a root split, do an exhaustive
+        // breadth-first traversal looking for the parent tuple
+
+        ctx.pathList.clear();
+        ctx.traverseList.clear();
+        findPath(ctx);
+        updateParentForInsert(ctx);
+    }
+
+    public void findPath(RTreeOpContext ctx) throws Exception {
+        int pageId = rootPage;
+        int parentIndex = -1;
+        int parentLsn = 0;
+        int pageLsn, pageIndex;
+        ctx.traverseList.add(pageId, -1, parentIndex);
+        while (!ctx.traverseList.isLast()) {
+            pageId = ctx.traverseList.getFirstPageId();
+            parentIndex = ctx.traverseList.getFirstParentIndex();
+
+            ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+            pins++;
+            node.acquireReadLatch();
+            readLatchesAcquired++;
+            ctx.interiorFrame.setPage(node);
+            pageLsn = ctx.interiorFrame.getPageLsn();
+            pageIndex = ctx.traverseList.first();
+            ctx.traverseList.setPageLsn(pageIndex, pageLsn);
+
+            ctx.traverseList.moveFirst();
+
+            if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
+                int rightPage = ctx.interiorFrame.getRightPage();
+                if (rightPage != -1) {
+                    ctx.traverseList.add(rightPage, -1, parentIndex);
+                }
+            }
+            parentLsn = pageLsn;
+
+            if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), ctx.traverseList, pageIndex,
+                    interiorCmp) != -1) {
+                fillPath(ctx, pageIndex);
+
+                node.releaseReadLatch();
+                readLatchesReleased++;
+                bufferCache.unpin(node);
+                unpins++;
+                return;
+            }
+            node.releaseReadLatch();
+            readLatchesReleased++;
+            bufferCache.unpin(node);
+            unpins++;
+        }
+    }
+
+    public void fillPath(RTreeOpContext ctx, int pageIndex) throws Exception {
+        if (pageIndex != -1) {
+            fillPath(ctx, ctx.traverseList.getParentIndex(pageIndex));
+            ctx.pathList.add(ctx.traverseList.getPageId(pageIndex), ctx.traverseList.getPageLsn(pageIndex), -1);
+        }
+    }
+
+    public void delete(ITupleReference tuple, RTreeOpContext ctx) throws Exception {
+        ctx.reset();
+        ctx.setTuple(tuple);
+        ctx.splitKey.reset();
+        ctx.splitKey.getLeftTuple().setFieldCount(interiorCmp.getFieldCount());
+        ctx.interiorFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
+        ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
+
+        int tupleIndex = findTupleToDelete(ctx);
+
+        if (tupleIndex != -1) {
+            int pageId = ctx.pathList.getLastPageId();
+            ctx.pathList.removeLast();
+            deleteTuple(pageId, tupleIndex, ctx);
+
+            while (true) {
+                if (ctx.splitKey.getLeftPageBuffer() != null) {
+                    updateParentForDelete(ctx);
+                } else {
+                    break;
+                }
+            }
+
+            ctx.leafFrame.getPage().releaseWriteLatch();
+            writeLatchesReleased++;
+            bufferCache.unpin(ctx.leafFrame.getPage());
+            unpins++;
+        }
+    }
+
+    public void updateParentForDelete(RTreeOpContext ctx) throws Exception {
+        int parentId = ctx.pathList.getLastPageId();
+        ICachedPage parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
+        pins++;
+        parentNode.acquireWriteLatch();
+        writeLatchesAcquired++;
+        ctx.interiorFrame.setPage(parentNode);
+        boolean foundParent = true;
+        int tupleIndex = -1;
+
+        if (ctx.interiorFrame.getPageLsn() != ctx.pathList.getLastPageLsn()) {
+            foundParent = false;
+            while (true) {
+                tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), interiorCmp);
+                if (tupleIndex != -1) {
+                    // found the parent
+                    foundParent = true;
+                    break;
+                }
+                int rightPage = ctx.interiorFrame.getRightPage();
+                parentNode.releaseWriteLatch();
+                writeLatchesReleased++;
+                bufferCache.unpin(parentNode);
+                unpins++;
+
+                if (rightPage == -1) {
+                    break;
+                }
+
+                parentId = rightPage;
+                parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
+                pins++;
+                parentNode.acquireWriteLatch();
+                writeLatchesAcquired++;
+                ctx.interiorFrame.setPage(parentNode);
+            }
+        }
+        if (foundParent) {
+            if (tupleIndex == -1) {
+                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()) {                   
+                    ctx.interiorFrame.computeMBR(ctx.splitKey, interiorCmp);
+                    ctx.splitKey.setLeftPage(parentId);
+                }
+            } else {
+                ctx.pathList.removeLast();
+                ctx.splitKey.reset();
+            }
+
+            parentNode.releaseWriteLatch();
+            writeLatchesReleased++;
+            bufferCache.unpin(parentNode);
+            unpins++;
+            return;
+        }
+
+        // very rare situation when the there is a root split, do an exhaustive
+        // breadth-first traversal looking for the parent tuple
+
+        ctx.pathList.clear();
+        ctx.traverseList.clear();
+        findPath(ctx);
+        updateParentForDelete(ctx);
+    }
+    
+    public int findTupleToDelete(RTreeOpContext ctx) throws Exception {
+
+        ctx.traverseList.add(rootPage, -1, -1);
+        ctx.pathList.add(rootPage, -1, ctx.traverseList.size() - 1);
+
+        while (!ctx.pathList.isEmpty()) {
+            int pageId = ctx.pathList.getLastPageId();
+            int parentLsn = ctx.pathList.getLastPageLsn();
+            int pageIndex = ctx.pathList.getLastPageIndex();
+            ctx.pathList.removeLast();
+            ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+            pins++;
+            node.acquireReadLatch();
+            readLatchesAcquired++;
+            ctx.interiorFrame.setPage(node);
+            boolean isLeaf = ctx.interiorFrame.isLeaf();
+            int pageLsn = ctx.interiorFrame.getPageLsn();
+            int parentIndex = ctx.traverseList.getParentIndex(pageIndex);
+
+            if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
+                // Concurrent split detected, we need to visit the right page
+                int rightPage = ctx.interiorFrame.getRightPage();
+                if (rightPage != -1) {
+                    ctx.traverseList.add(rightPage, parentLsn, parentIndex);
+                    ctx.pathList.add(rightPage, parentLsn, ctx.traverseList.size() - 1);
+                }
+            }
+
+            if (!isLeaf) {
+                parentLsn = pageLsn;
+                for (int i = 0; i < ctx.interiorFrame.getTupleCount(); i++) {
+                    int childPageId = ctx.interiorFrame.getChildPageIdIfIntersect(ctx.tuple, i, interiorCmp);
+                    if (childPageId != -1) {
+                        ctx.traverseList.add(childPageId, parentLsn, pageIndex);
+                        ctx.pathList.add(childPageId, parentLsn, ctx.traverseList.size() - 1);
+                    }
+                }
+            } else {
+                ctx.leafFrame.setPage(node);
+                int tupleIndex = ctx.leafFrame.findTuple(ctx.tuple, leafCmp);
+                if (tupleIndex != -1) {
+
+                    node.releaseReadLatch();
+                    readLatchesReleased++;
+                    bufferCache.unpin(node);
+                    unpins++;
+
+                    node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+                    pins++;
+                    node.acquireWriteLatch();
+                    writeLatchesAcquired++;
+                    ctx.leafFrame.setPage(node);
+
+                    if (ctx.leafFrame.getPageLsn() != pageLsn) {
+                        // The page was changed while we unlocked it
+
+                        tupleIndex = ctx.leafFrame.findTuple(ctx.tuple, leafCmp);
+                        if (tupleIndex == -1) {
+                            ctx.traverseList.add(pageId, parentLsn, parentIndex);
+                            ctx.pathList.add(pageId, parentLsn, ctx.traverseList.size() - 1);
+                        }
+                    } else {
+                        ctx.pathList.clear();
+                        fillPath(ctx, pageIndex);
+                        return tupleIndex;
+                    }
+                }
+            }
+            node.releaseReadLatch();
+            readLatchesReleased++;
+            bufferCache.unpin(node);
+            unpins++;
+        }
+        return -1;
+    }
+
+    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);
+
+         }
+    }
+
     public void search(Stack<Integer> s, ITupleReference tuple, RTreeOpContext ctx, ArrayList<Rectangle> results)
             throws Exception {
         ctx.reset();
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 6a07c93..4c8f198 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
@@ -2,7 +2,6 @@
 
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.TreeIndexOp;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
 
@@ -11,16 +10,13 @@
     public final IRTreeFrame interiorFrame;
     public final IRTreeFrame leafFrame;
     public final ITreeIndexMetaDataFrame metaFrame;
-    public final ByteArrayList overflowArray;
     public final RTreeSplitKey splitKey;
     public final SpatialUtils spatialUtils;
     public ITupleReference tuple;
-    public TupleEntryArrayList tupleEntries1;
-    public TupleEntryArrayList tupleEntries2;
-    public ITreeIndexTupleReference[] nodesMBRs;
-    public final IntArrayList path;
-    public final IntArrayList pageLsns;
-    public final FindPathList findPathList; // works as a queue
+    public TupleEntryArrayList tupleEntries1; // used for split and checking enlargement
+    public TupleEntryArrayList tupleEntries2; // used for split
+    public final PathList pathList; // used to record the pageIds and pageLsns of the visited pages 
+    public final TraverseList traverseList; // used for traversing the tree
     public Rectangle[] rec;
 
     public RTreeOpContext(TreeIndexOp op, IRTreeFrame interiorFrame, IRTreeFrame leafFrame,
@@ -31,19 +27,12 @@
         this.metaFrame = metaFrame;
         splitKey = new RTreeSplitKey(interiorFrame.getTupleWriter().createTupleReference(), interiorFrame
                 .getTupleWriter().createTupleReference());
-        overflowArray = new ByteArrayList(treeHeightHint, treeHeightHint);
         spatialUtils = new SpatialUtils();
         // TODO: find a better way to know number of entries per node
         tupleEntries1 = new TupleEntryArrayList(100, 100, spatialUtils);
         tupleEntries2 = new TupleEntryArrayList(100, 100, spatialUtils);
-        nodesMBRs = new ITreeIndexTupleReference[treeHeightHint];
-        path = new IntArrayList(treeHeightHint, treeHeightHint);
-        pageLsns = new IntArrayList(treeHeightHint, treeHeightHint);
-        findPathList = new FindPathList(100, 100);
-        for (int i = 0; i < treeHeightHint; i++) {
-            nodesMBRs[i] = interiorFrame.getTupleWriter().createTupleReference();
-            nodesMBRs[i].setFieldCount(nodesMBRs[i].getFieldCount());
-        }
+        pathList = new PathList(treeHeightHint, treeHeightHint);
+        traverseList = new TraverseList(100, 100);
         rec = new Rectangle[4];
         for (int i = 0; i < 4; i++) {
             rec[i] = new Rectangle(dim);
@@ -59,23 +48,17 @@
     }
 
     public void reset() {
-        if (overflowArray != null) {
-            overflowArray.clear();
-        }
         if (tupleEntries1 != null) {
             tupleEntries1.clear();
         }
         if (tupleEntries2 != null) {
             tupleEntries2.clear();
         }
-        if (path != null) {
-            path.clear();
+        if (pathList != null) {
+            pathList.clear();
         }
-        if (pageLsns != null) {
-            pageLsns.clear();
-        }
-        if (findPathList != null) {
-            pageLsns.clear();
+        if (traverseList != null) {
+            traverseList.clear();
         }
     }
 }
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
new file mode 100644
index 0000000..c09971d
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/TraverseList.java
@@ -0,0 +1,108 @@
+/*
+ * 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 TraverseList {
+    private IntArrayList pageIds;
+    private IntArrayList pageLsns;
+    private IntArrayList parentIndexes;
+    
+    public TraverseList(int initialCapacity, int growth) {
+        pageIds = new IntArrayList(initialCapacity, growth);
+        pageLsns = new IntArrayList(initialCapacity, growth);
+        parentIndexes = new IntArrayList(initialCapacity, growth);
+    }
+
+    public int size() {
+        return pageIds.size();
+    }
+    
+    public int first() {
+        return pageIds.first();
+    }
+
+    public void add(int pageId, int pageLsn, int parentIndex) {
+        pageIds.add(pageId);
+        pageLsns.add(pageLsn);
+        parentIndexes.add(parentIndex);
+    }
+
+    public int getFirstPageId() {
+        return pageIds.getFirst();
+    }
+    
+    public int getFirstPageLsn() {
+        return pageLsns.getFirst();
+    }
+
+    public int getFirstParentIndex() {
+        return parentIndexes.getFirst();
+    }
+    
+    public int getLastPageId() {
+        return pageIds.getLast();
+    }
+    
+    public int getLastPageLsn() {
+        return pageLsns.getLast();
+    }
+
+    public int getLastParentIndex() {
+        return parentIndexes.getLast();
+    }
+
+    public int getPageId(int i) {
+        return pageIds.get(i);
+    }
+    
+    public int getPageLsn(int i) {
+        return pageLsns.get(i);
+    }
+
+    public int getParentIndex(int i) {
+        return parentIndexes.get(i);
+    }
+    
+    public void setPageLsn(int i, int pageLsn) {
+        pageLsns.set(i, pageLsn);
+    }
+    
+    public void moveFirst() {
+        pageIds.moveFirst();
+        pageLsns.moveFirst();
+        parentIndexes.moveFirst();
+    }
+    
+    public void moveLast() {
+        pageIds.removeLast();
+        pageLsns.removeLast();
+        parentIndexes.removeLast();
+    }
+    
+    public boolean isLast() {
+        return pageIds.isLast();
+    }
+
+    public void clear() {
+        pageIds.clear();
+        pageLsns.clear();
+        parentIndexes.clear();
+    }
+
+    public boolean isEmpty() {
+        return pageIds.isEmpty();
+    }
+}