diff --git a/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java
index d95d8a5..093d17a 100644
--- a/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java
+++ b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java
@@ -78,7 +78,7 @@
             if (i != fields.length - 1) {
                 strBuilder.append(" ");
             }
-        }
+        }        
         return strBuilder.toString();
     }
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeFrame.java
index f6c9455..7d981cb 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeFrame.java
@@ -1,5 +1,6 @@
 package edu.uci.ics.hyracks.storage.am.btree.api;
 
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
@@ -9,6 +10,7 @@
 	public int findUpdateTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException;
 	public int findInsertTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException;
 	public int findDeleteTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException;
+	public void insertSorted(ITupleReference tuple, MultiComparator cmp) throws HyracksDataException;
     public boolean getSmFlag();
     public void setSmFlag(boolean smFlag);
     public void setMultiComparator(MultiComparator cmp);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeInteriorFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeInteriorFrame.java
index 09af783..23fdcf5 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeInteriorFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeInteriorFrame.java
@@ -15,21 +15,16 @@
 
 package edu.uci.ics.hyracks.storage.am.btree.api;
 
-import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
-import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
-import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
 
 public interface IBTreeInteriorFrame extends IBTreeFrame {
-    public void insertSorted(ITupleReference tuple, MultiComparator cmp) throws HyracksDataException;
-    
-    public int getChildPageId(RangePredicate pred, MultiComparator srcCmp);
+    public int getChildPageId(RangePredicate pred);
 
-    public int getLeftmostChildPageId(MultiComparator cmp);
+    public int getLeftmostChildPageId();
 
-    public int getRightmostChildPageId(MultiComparator cmp);
+    public int getRightmostChildPageId();
 
     public void setRightmostChildPageId(int pageId);
 
-    public void deleteGreatest(MultiComparator cmp);
+    public void deleteGreatest();
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
index 3429ba6..a079527 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
@@ -23,8 +23,6 @@
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
 
 public interface IBTreeLeafFrame extends IBTreeFrame {
-    public void insertSorted(ITupleReference tuple, MultiComparator cmp) throws HyracksDataException;
-    
     public void setNextLeaf(int nextPage);
 
     public int getNextLeaf();
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
index 09aadb8..05b9cf1 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
@@ -15,16 +15,13 @@
 
 package edu.uci.ics.hyracks.storage.am.btree.frames;
 
-import java.io.ByteArrayInputStream;
-import java.io.DataInput;
-import java.io.DataInputStream;
 import java.nio.ByteBuffer;
 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.IntegerSerializerDeserializer;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ISplitKey;
@@ -42,13 +39,13 @@
 public class BTreeNSMInteriorFrame extends TreeIndexNSMFrame implements IBTreeInteriorFrame {
 
     private static final int rightLeafOff = smFlagOff + 1;
-    private static final int childPtrSize = 4;    
-    
+    private static final int childPtrSize = 4;
+
     private final ITreeIndexTupleReference cmpFrameTuple;
     private MultiComparator cmp;
-    
-    public BTreeNSMInteriorFrame(ITreeIndexTupleWriter tupleWriter) {        
-    	super(tupleWriter, new OrderedSlotManager());
+
+    public BTreeNSMInteriorFrame(ITreeIndexTupleWriter tupleWriter) {
+        super(tupleWriter, new OrderedSlotManager());
         cmpFrameTuple = tupleWriter.createTupleReference();
     }
 
@@ -59,9 +56,15 @@
     }
 
     @Override
+    public int findInsertTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException {
+        return slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
+                FindTupleNoExactMatchPolicy.HIGHER_KEY);
+    }
+    
+    @Override
     public FrameOpSpaceStatus hasSpaceInsert(ITupleReference tuple) {
-    	// Tuple bytes + child pointer + slot.
-    	int bytesRequired = tupleWriter.bytesRequired(tuple) + childPtrSize + slotManager.getSlotSize();
+        // Tuple bytes + child pointer + slot.
+        int bytesRequired = tupleWriter.bytesRequired(tuple) + childPtrSize + slotManager.getSlotSize();
         if (bytesRequired <= getFreeContiguousSpace()) {
             return FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
         }
@@ -72,23 +75,6 @@
     }
 
     @Override
-    public int findInsertTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException {
-        return slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
-                FindTupleNoExactMatchPolicy.HIGHER_KEY);
-    }
-    
-    @Override
-    public int findDeleteTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException {
-        return slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
-                FindTupleNoExactMatchPolicy.HIGHER_KEY);
-    }
-    
-    @Override
-    public int findUpdateTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException {
-        throw new UnsupportedOperationException("Cannot update tuples in interior node.");
-    }
-
-    @Override
     public void insert(ITupleReference tuple, int tupleIndex) {
         int slotOff = slotManager.insertSlot(tupleIndex, buf.getInt(freeSpaceOff));
         int freeSpace = buf.getInt(freeSpaceOff);
@@ -96,22 +82,20 @@
         System.arraycopy(tuple.getFieldData(tuple.getFieldCount() - 1), getLeftChildPageOff(tuple), 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());
-
-        // did insert into the rightmost slot?
+        // Did we insert into the rightmost slot?
         if (slotOff == slotManager.getSlotEndOff()) {
-            System.arraycopy(tuple.getFieldData(tuple.getFieldCount() - 1), getLeftChildPageOff(tuple)
-                    + childPtrSize, buf.array(), rightLeafOff, childPtrSize);
+            System.arraycopy(tuple.getFieldData(tuple.getFieldCount() - 1), getLeftChildPageOff(tuple) + childPtrSize,
+                    buf.array(), rightLeafOff, childPtrSize);
         } else {
-            // if slotOff has a right (slot-)neighbor then update its child
-            // pointer
-            // the only time when this is NOT the case, is when this is the
-            // first tuple
-            // (or when the splitkey goes into the rightmost slot but that
-            // case was handled in the if above)
+            // If slotOff has a right (slot-)neighbor then update its child
+            // pointer.
+            // The only time when this is NOT the case, is when this is the
+            // very first tuple (or when the splitkey goes into the rightmost
+            // slot but that
+            // case is handled in the if above).
             if (buf.getInt(tupleCountOff) > 1) {
                 int rightNeighborOff = slotOff - slotManager.getSlotSize();
                 frameTuple.resetByTupleOffset(buf, slotManager.getTupleOff(rightNeighborOff));
@@ -120,191 +104,11 @@
             }
         }
     }
-
+    
     @Override
-    public void insertSorted(ITupleReference tuple, MultiComparator cmp) throws HyracksDataException {
-        int freeSpace = buf.getInt(freeSpaceOff);
-        slotManager.insertSlot(-1, freeSpace);
-        int bytesWritten = tupleWriter.writeTupleFields(tuple, 0, cmp.getKeyFieldCount(), buf, freeSpace);
-        System.arraycopy(tuple.getFieldData(cmp.getKeyFieldCount() - 1), getLeftChildPageOff(tuple), 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());
-        System.arraycopy(tuple.getFieldData(0), getLeftChildPageOff(tuple) + childPtrSize, buf.array(),
-                rightLeafOff, childPtrSize);
-    }
-
-    @Override
-    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) throws TreeIndexException {
-        ByteBuffer right = rightFrame.getBuffer();
-        int tupleCount = buf.getInt(tupleCountOff);
-
-        int tuplesToLeft = (tupleCount / 2) + (tupleCount % 2);
-        ITreeIndexFrame targetFrame = null;
-        frameTuple.resetByTupleIndex(this, tuplesToLeft - 1);
-        if (cmp.compare(tuple, frameTuple) <= 0) {
-            targetFrame = this;
-        } else {
-            targetFrame = rightFrame;
-        }
-        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, remove highest key and make its childpointer the
-        // rightmost childpointer
-        buf.putInt(tupleCountOff, tuplesToLeft);
-
-        // copy data to be inserted, we need this because creating the splitkey
-        // will overwrite the data param (data points to same memory as
-        // splitKey.getData())
-        ISplitKey savedSplitKey = splitKey.duplicate(tupleWriter.createTupleReference());
-
-        // set split key to be highest value in left page
-        int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
-        frameTuple.resetByTupleOffset(buf, tupleOff);
-        int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
-        splitKey.initData(splitKeySize);
-        tupleWriter.writeTupleFields(frameTuple, 0, cmp.getKeyFieldCount(), splitKey.getBuffer(), 0);
-        splitKey.getTuple().resetByTupleOffset(splitKey.getBuffer(), 0);
-
-        int deleteTupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
-        frameTuple.resetByTupleOffset(buf, deleteTupleOff);
-        buf.putInt(rightLeafOff, buf.getInt(getLeftChildPageOff(frameTuple)));
-        buf.putInt(tupleCountOff, tuplesToLeft - 1);
-
-        // compact both pages
-        rightFrame.compact();
-        compact();
-
-        // insert key
-        int targetTupleIndex = ((BTreeNSMInteriorFrame)targetFrame).findInsertTupleIndex(savedSplitKey.getTuple(), cmp);
-        targetFrame.insert(savedSplitKey.getTuple(), targetTupleIndex);
-
-        return 0;
-    }
-
-    @Override
-    public boolean compact() {
-        resetSpaceParams();
-
-        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 int getChildPageId(RangePredicate pred, MultiComparator srcCmp) {
-        // check for trivial case where there is only a child pointer (and no
-        // key)
-        if (buf.getInt(tupleCountOff) == 0) {
-            return buf.getInt(rightLeafOff);
-        }
-
-        cmpFrameTuple.setFieldCount(srcCmp.getKeyFieldCount());
-        frameTuple.setFieldCount(srcCmp.getKeyFieldCount());
-
-        // check for trivial cases where no low key or high key exists (e.g.
-        // during an index scan)
-        ITupleReference tuple = null;
-        FindTupleMode fsm = null;
-        MultiComparator targetCmp = null;
-        if (pred.isForward()) {
-            tuple = pred.getLowKey();
-            if (tuple == null) {
-                return getLeftmostChildPageId(srcCmp);
-            }
-            if (pred.isLowKeyInclusive())
-                fsm = FindTupleMode.INCLUSIVE;
-            else
-                fsm = FindTupleMode.EXCLUSIVE;
-            targetCmp = pred.getLowKeyComparator();
-        } else {
-            tuple = pred.getHighKey();
-            if (tuple == null) {
-                return getRightmostChildPageId(srcCmp);
-            }
-            if (pred.isHighKeyInclusive())
-                fsm = FindTupleMode.EXCLUSIVE;
-            else
-                fsm = FindTupleMode.INCLUSIVE;
-            targetCmp = pred.getHighKeyComparator();
-        }
-
-        int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, targetCmp, fsm,
+    public int findDeleteTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException {
+        return slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
                 FindTupleNoExactMatchPolicy.HIGHER_KEY);
-        int slotOff = slotManager.getSlotOff(tupleIndex);
-        if (tupleIndex == slotManager.getGreatestKeyIndicator()) {
-            return buf.getInt(rightLeafOff);
-        } else {
-            int origTupleOff = slotManager.getTupleOff(slotOff);
-            cmpFrameTuple.resetByTupleOffset(buf, origTupleOff);
-            int cmpTupleOff = origTupleOff;
-            if (pred.isForward()) {
-                int maxSlotOff = buf.capacity();
-                slotOff += slotManager.getSlotSize();
-                while (slotOff < maxSlotOff) {
-                    cmpTupleOff = slotManager.getTupleOff(slotOff);
-                    frameTuple.resetByTupleOffset(buf, cmpTupleOff);
-                    if (targetCmp.compare(cmpFrameTuple, frameTuple) != 0)
-                        break;
-                    slotOff += slotManager.getSlotSize();
-                }
-                slotOff -= slotManager.getSlotSize();
-            } else {
-                int minSlotOff = slotManager.getSlotEndOff() - slotManager.getSlotSize();
-                slotOff -= slotManager.getSlotSize();
-                while (slotOff > minSlotOff) {
-                    cmpTupleOff = slotManager.getTupleOff(slotOff);
-                    frameTuple.resetByTupleOffset(buf, cmpTupleOff);
-                    if (targetCmp.compare(cmpFrameTuple, frameTuple) != 0)
-                        break;
-                    slotOff -= slotManager.getSlotSize();
-                }
-                slotOff += slotManager.getSlotSize();
-            }
-
-            frameTuple.resetByTupleOffset(buf, slotManager.getTupleOff(slotOff));
-            int childPageOff = getLeftChildPageOff(frameTuple);
-            return buf.getInt(childPageOff);
-        }
     }
 
     @Override
@@ -316,24 +120,242 @@
             tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
             frameTuple.resetByTupleOffset(buf, tupleOff);
             keySize = tupleWriter.bytesRequired(frameTuple, 0, tuple.getFieldCount());
-
-            // copy new rightmost pointer
+            // Copy new rightmost pointer.
             System.arraycopy(buf.array(), tupleOff + keySize, buf.array(), rightLeafOff, childPtrSize);
         } else {
             tupleOff = slotManager.getTupleOff(slotOff);
             frameTuple.resetByTupleOffset(buf, tupleOff);
             keySize = tupleWriter.bytesRequired(frameTuple, 0, tuple.getFieldCount());
-            // perform deletion (we just do a memcpy to overwrite the slot)
+            // 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
+        // Maintain space information.
         buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
         buf.putInt(totalFreeSpaceOff,
                 buf.getInt(totalFreeSpaceOff) + keySize + childPtrSize + slotManager.getSlotSize());
     }
+    
+    @Override
+    public void deleteGreatest() {
+        int slotOff = slotManager.getSlotEndOff();
+        int tupleOff = slotManager.getTupleOff(slotOff);
+        frameTuple.resetByTupleOffset(buf, tupleOff);
+        int keySize = tupleWriter.bytesRequired(frameTuple);
+        System.arraycopy(buf.array(), tupleOff + keySize, buf.array(), rightLeafOff, childPtrSize);
+        // Maintain space information.
+        buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
+        buf.putInt(totalFreeSpaceOff,
+                buf.getInt(totalFreeSpaceOff) + keySize + childPtrSize + slotManager.getSlotSize());
+        int freeSpace = buf.getInt(freeSpaceOff);
+        if (freeSpace == tupleOff + keySize + childPtrSize) {
+            buf.putInt(freeSpace, freeSpace - (keySize + childPtrSize));
+        }
+    }
+    
+    @Override
+    public FrameOpSpaceStatus hasSpaceUpdate(ITupleReference tuple, int oldTupleIndex) {
+        throw new UnsupportedOperationException("Cannot update tuples in interior node.");
+    }
+    
+    @Override
+    public int findUpdateTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException {
+        throw new UnsupportedOperationException("Cannot update tuples in interior node.");
+    }
+
+    @Override
+    public void insertSorted(ITupleReference tuple, MultiComparator cmp) throws HyracksDataException {
+        int freeSpace = buf.getInt(freeSpaceOff);
+        slotManager.insertSlot(slotManager.getGreatestKeyIndicator(), freeSpace);
+        int bytesWritten = tupleWriter.writeTuple(tuple, buf, freeSpace);
+        System.arraycopy(tuple.getFieldData(tuple.getFieldCount() - 1), getLeftChildPageOff(tuple), 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());
+        System.arraycopy(tuple.getFieldData(0), getLeftChildPageOff(tuple) + childPtrSize, buf.array(), rightLeafOff,
+                childPtrSize);
+    }
+
+    @Override
+    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) throws TreeIndexException {
+        ByteBuffer right = rightFrame.getBuffer();
+        int tupleCount = getTupleCount();
+        int tuplesToLeft = (tupleCount / 2) + (tupleCount % 2);
+        ITreeIndexFrame targetFrame = null;
+        frameTuple.resetByTupleIndex(this, tuplesToLeft - 1);
+        if (cmp.compare(tuple, frameTuple) <= 0) {
+            targetFrame = this;
+        } else {
+            targetFrame = rightFrame;
+        }
+        int tuplesToRight = tupleCount - tuplesToLeft;
+
+        // Copy entire page.
+        System.arraycopy(buf.array(), 0, right.array(), 0, buf.capacity());
+
+        // On the 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 the left page, remove the highest key and make its child pointer
+        // the rightmost child pointer.
+        buf.putInt(tupleCountOff, tuplesToLeft);
+
+        // Copy the split key to be inserted.
+        // We must do so because setting the new split key will overwrite the
+        // old split key, and we cannot insert the existing split key at this point.
+        ISplitKey savedSplitKey = splitKey.duplicate(tupleWriter.createTupleReference());
+
+        // Set split key to be highest value in left page.
+        int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
+        frameTuple.resetByTupleOffset(buf, tupleOff);
+        int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
+        splitKey.initData(splitKeySize);
+        tupleWriter.writeTuple(frameTuple, splitKey.getBuffer(), 0);
+        splitKey.getTuple().resetByTupleOffset(splitKey.getBuffer(), 0);
+
+        int deleteTupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
+        frameTuple.resetByTupleOffset(buf, deleteTupleOff);
+        buf.putInt(rightLeafOff, buf.getInt(getLeftChildPageOff(frameTuple)));
+        buf.putInt(tupleCountOff, tuplesToLeft - 1);
+
+        // Compact both pages.
+        rightFrame.compact();
+        compact();
+
+        // Insert the saved split key.
+        int targetTupleIndex = ((BTreeNSMInteriorFrame) targetFrame)
+                .findInsertTupleIndex(savedSplitKey.getTuple(), cmp);
+        targetFrame.insert(savedSplitKey.getTuple(), targetTupleIndex);
+
+        return 0;
+    }
+
+    @Override
+    public boolean compact() {
+        resetSpaceParams();
+        int tupleCount = buf.getInt(tupleCountOff);
+        int freeSpace = buf.getInt(freeSpaceOff);
+        // Sort the slots by the tuple offset they point to.
+        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);
+        // Iterate over the sorted slots, and move their corresponding tuples to
+        // the left, reclaiming free space.
+        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;
+        }
+        // Update contiguous free space pointer and total free space indicator.
+        buf.putInt(freeSpaceOff, freeSpace);
+        buf.putInt(totalFreeSpaceOff, buf.capacity() - freeSpace - tupleCount * slotManager.getSlotSize());
+        return false;
+    }
+
+    @Override
+    public int getChildPageId(RangePredicate pred) {
+        // Trivial case where there is only a child pointer (and no key).
+        if (buf.getInt(tupleCountOff) == 0) {
+            return buf.getInt(rightLeafOff);
+        }
+        // Trivial cases where no low key or high key was given (e.g.
+        // during an index scan).
+        ITupleReference tuple = null;
+        FindTupleMode fsm = null;
+        // The target comparator may be on a prefix of the BTree key fields.
+        MultiComparator targetCmp = null;
+        if (pred.isForward()) {            
+            tuple = pred.getLowKey();
+            if (tuple == null) {
+                return getLeftmostChildPageId();
+            }
+            if (pred.isLowKeyInclusive()) {
+                fsm = FindTupleMode.INCLUSIVE;
+            } else {
+                fsm = FindTupleMode.EXCLUSIVE;
+            }
+            targetCmp = pred.getLowKeyComparator();
+        } else {
+            tuple = pred.getHighKey();
+            if (tuple == null) {
+                return getRightmostChildPageId();
+            }
+            if (pred.isHighKeyInclusive()) {
+                fsm = FindTupleMode.EXCLUSIVE;
+            } else {
+                fsm = FindTupleMode.INCLUSIVE;
+            }
+            targetCmp = pred.getHighKeyComparator();
+        }
+        // Search for a matching key.
+        int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, targetCmp, fsm,
+                FindTupleNoExactMatchPolicy.HIGHER_KEY);
+        int slotOff = slotManager.getSlotOff(tupleIndex);
+        // Follow the rightmost (greatest) child pointer.
+        if (tupleIndex == slotManager.getGreatestKeyIndicator()) {
+            return buf.getInt(rightLeafOff);
+        }
+        // Deal with prefix searches.
+        // slotManager.findTupleIndex() will return an arbitrary tuple matching
+        // the given field prefix (according to the target comparator).
+        // To make sure we traverse the right path, we must find the
+        // leftmost or rightmost tuple that matches the prefix.
+        int origTupleOff = slotManager.getTupleOff(slotOff);
+        cmpFrameTuple.resetByTupleOffset(buf, origTupleOff);
+        int cmpTupleOff = origTupleOff;
+        if (pred.isForward()) {
+            // The answer set begins with the lowest key matching the prefix.
+            // We must follow the child pointer of the lowest (leftmost) key
+            // matching the given prefix.
+            int maxSlotOff = buf.capacity();
+            slotOff += slotManager.getSlotSize();
+            while (slotOff < maxSlotOff) {
+                cmpTupleOff = slotManager.getTupleOff(slotOff);
+                frameTuple.resetByTupleOffset(buf, cmpTupleOff);
+                if (targetCmp.compare(cmpFrameTuple, frameTuple) != 0) {
+                    break;
+                }
+                slotOff += slotManager.getSlotSize();
+            }
+            slotOff -= slotManager.getSlotSize();
+        } else {
+            // The answer set begins with the highest key matching the prefix.
+            // We must follow the child pointer of the highest (rightmost) key
+            // matching the given prefix.
+            int minSlotOff = slotManager.getSlotEndOff() - slotManager.getSlotSize();
+            slotOff -= slotManager.getSlotSize();
+            while (slotOff > minSlotOff) {
+                cmpTupleOff = slotManager.getTupleOff(slotOff);
+                frameTuple.resetByTupleOffset(buf, cmpTupleOff);
+                if (targetCmp.compare(cmpFrameTuple, frameTuple) != 0) {
+                    break;
+                }
+                slotOff -= slotManager.getSlotSize();
+            }
+            slotOff += slotManager.getSlotSize();
+        }
+        frameTuple.resetByTupleOffset(buf, slotManager.getTupleOff(slotOff));
+        int childPageOff = getLeftChildPageOff(frameTuple);
+        return buf.getInt(childPageOff);
+    }
 
     @Override
     protected void resetSpaceParams() {
@@ -342,16 +364,15 @@
     }
 
     @Override
-    public int getLeftmostChildPageId(MultiComparator cmp) {
+    public int getLeftmostChildPageId() {
         int tupleOff = slotManager.getTupleOff(slotManager.getSlotStartOff());
-        frameTuple.setFieldCount(cmp.getKeyFieldCount());
         frameTuple.resetByTupleOffset(buf, tupleOff);
         int childPageOff = getLeftChildPageOff(frameTuple);
         return buf.getInt(childPageOff);
     }
 
     @Override
-    public int getRightmostChildPageId(MultiComparator cmp) {
+    public int getRightmostChildPageId() {
         return buf.getInt(rightLeafOff);
     }
 
@@ -360,7 +381,37 @@
         buf.putInt(rightLeafOff, pageId);
     }
 
-    // for debugging
+    @Override
+    public int getPageHeaderSize() {
+        return rightLeafOff;
+    }
+
+    private int getLeftChildPageOff(ITupleReference tuple) {
+        return tuple.getFieldStart(tuple.getFieldCount() - 1) + tuple.getFieldLength(tuple.getFieldCount() - 1);
+    }
+
+    @Override
+    public boolean getSmFlag() {
+        return buf.get(smFlagOff) != 0;
+    }
+
+    @Override
+    public void setSmFlag(boolean smFlag) {
+        if (smFlag) {
+            buf.put(smFlagOff, (byte) 1);
+        } else {
+            buf.put(smFlagOff, (byte) 0);
+        }
+    }
+
+    @Override
+    public void setMultiComparator(MultiComparator cmp) {
+        this.cmp = cmp;
+        cmpFrameTuple.setFieldCount(cmp.getKeyFieldCount());
+        frameTuple.setFieldCount(cmp.getKeyFieldCount());
+    }
+    
+    // For debugging.
     public ArrayList<Integer> getChildren(MultiComparator cmp) {
         ArrayList<Integer> ret = new ArrayList<Integer>();
         frameTuple.setFieldCount(cmp.getKeyFieldCount());
@@ -368,7 +419,7 @@
         for (int i = 0; i < tupleCount; i++) {
             int tupleOff = slotManager.getTupleOff(slotManager.getSlotOff(i));
             frameTuple.resetByTupleOffset(buf, tupleOff);
-            int intVal = getInt(
+            int intVal = IntegerSerializerDeserializer.getInt(
                     buf.array(),
                     frameTuple.getFieldStart(frameTuple.getFieldCount() - 1)
                             + frameTuple.getFieldLength(frameTuple.getFieldCount() - 1));
@@ -381,80 +432,4 @@
         }
         return ret;
     }
-
-    @Override
-    public void deleteGreatest(MultiComparator cmp) {
-        int slotOff = slotManager.getSlotEndOff();
-        int tupleOff = slotManager.getTupleOff(slotOff);
-        frameTuple.setFieldCount(cmp.getKeyFieldCount());
-        frameTuple.resetByTupleOffset(buf, tupleOff);
-        int keySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
-        System.arraycopy(buf.array(), tupleOff + keySize, buf.array(), rightLeafOff, childPtrSize);
-
-        // maintain space information
-        buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
-        buf.putInt(totalFreeSpaceOff,
-                buf.getInt(totalFreeSpaceOff) + keySize + childPtrSize + slotManager.getSlotSize());
-
-        int freeSpace = buf.getInt(freeSpaceOff);
-        if (freeSpace == tupleOff + keySize + childPtrSize) {
-            buf.putInt(freeSpace, freeSpace - (keySize + childPtrSize));
-        }
-    }
-
-    private int getInt(byte[] bytes, int offset) {
-        return ((bytes[offset] & 0xff) << 24) + ((bytes[offset + 1] & 0xff) << 16) + ((bytes[offset + 2] & 0xff) << 8)
-                + ((bytes[offset + 3] & 0xff) << 0);
-    }
-
-    @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 int getPageHeaderSize() {
-        return rightLeafOff;
-    }
-    
-    private int getLeftChildPageOff(ITupleReference tuple) {
-        return tuple.getFieldStart(tuple.getFieldCount() - 1) + tuple.getFieldLength(tuple.getFieldCount() - 1);
-    }
-    
-    // TODO: can we put these into a common AbstractFrame or something?
-    @Override
-    public boolean getSmFlag() {
-        return buf.get(smFlagOff) != 0;
-    }
-
-    // TODO: can we put these into a common AbstractFrame or something?
-    @Override
-    public void setSmFlag(boolean smFlag) {
-        if (smFlag)
-            buf.put(smFlagOff, (byte) 1);
-        else
-            buf.put(smFlagOff, (byte) 0);
-    }
-    
-	@Override
-	public void setMultiComparator(MultiComparator cmp) {
-		this.cmp = cmp;
-		cmpFrameTuple.setFieldCount(cmp.getKeyFieldCount());
-        frameTuple.setFieldCount(cmp.getKeyFieldCount());
-	}
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
index 2895686..995c447 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
@@ -706,7 +706,7 @@
                     // the descent.
                     boolean repeatOp = true;
                     while (repeatOp && ctx.opRestarts < MAX_RESTARTS) {
-                        int childPageId = ctx.interiorFrame.getChildPageId(ctx.pred, cmp);
+                        int childPageId = ctx.interiorFrame.getChildPageId(ctx.pred);
                         performOp(childPageId, node, ctx);
 
                         if (!ctx.pageLsns.isEmpty() && ctx.pageLsns.getLast() == RESTART_OP) {
@@ -908,7 +908,7 @@
             ctx.splitKey.getTuple().resetByTupleOffset(ctx.splitKey.getBuffer(), 0);
             ctx.splitKey.setLeftPage(frontier.pageId);
 
-            ctx.interiorFrame.deleteGreatest(cmp);
+            ctx.interiorFrame.deleteGreatest();
 
             frontier.page.releaseWriteLatch();
             bufferCache.unpin(frontier.page);
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorNodePushable.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorNodePushable.java
index 4b53453..82b1b38 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorNodePushable.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorNodePushable.java
@@ -20,8 +20,8 @@
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.dataflow.std.base.AbstractOperatorNodePushable;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
-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.common.util.TreeIndexStats;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexStatsGatherer;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 
 public class TreeIndexStatsOperatorNodePushable extends
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java
index 5e5360a..5f15c2f 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java
@@ -117,7 +117,7 @@
         resetSpaceParams();
         int tupleCount = buf.getInt(tupleCountOff);
         int freeSpace = buf.getInt(freeSpaceOff);
-
+		// Sort the slots by the tuple offset they point to.
         ArrayList<SlotOffTupleOff> sortedTupleOffs = new ArrayList<SlotOffTupleOff>();
         sortedTupleOffs.ensureCapacity(tupleCount);
         for (int i = 0; i < tupleCount; i++) {
@@ -126,23 +126,21 @@
             sortedTupleOffs.add(new SlotOffTupleOff(i, slotOff, tupleOff));
         }
         Collections.sort(sortedTupleOffs);
-
+        // Iterate over the sorted slots, and move their corresponding tuples to
+     	// the left, reclaiming free space.
         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;
             System.arraycopy(buf.array(), tupleOff, buf.array(), freeSpace, tupleLength);
-
             slotManager.setSlot(sortedTupleOffs.get(i).slotOff, freeSpace);
             freeSpace += tupleLength;
         }
-
+		// Update contiguous free space pointer and total free space indicator.
         buf.putInt(freeSpaceOff, freeSpace);
         buf.putInt(totalFreeSpaceOff, buf.capacity() - freeSpace - tupleCount * slotManager.getSlotSize());
-
         return false;
     }
 
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/util/TreeIndexBufferCacheWarmup.java
similarity index 97%
rename from hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java
rename to hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexBufferCacheWarmup.java
index 8179d58..65ea8de 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/util/TreeIndexBufferCacheWarmup.java
@@ -1,4 +1,4 @@
-package edu.uci.ics.hyracks.storage.am.common.utility;
+package edu.uci.ics.hyracks.storage.am.common.util;
 
 import java.util.ArrayList;
 import java.util.Random;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStats.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexStats.java
similarity index 98%
rename from hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStats.java
rename to hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexStats.java
index 2754743..d5d9b5d 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStats.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexStats.java
@@ -1,4 +1,4 @@
-package edu.uci.ics.hyracks.storage.am.common.utility;
+package edu.uci.ics.hyracks.storage.am.common.util;
 
 import java.text.DecimalFormat;
 
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStatsGatherer.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexStatsGatherer.java
similarity index 97%
rename from hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStatsGatherer.java
rename to hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexStatsGatherer.java
index 9167732..eeacccd 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStatsGatherer.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexStatsGatherer.java
@@ -1,4 +1,4 @@
-package edu.uci.ics.hyracks.storage.am.common.utility;
+package edu.uci.ics.hyracks.storage.am.common.util;
 
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexUtils.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexUtils.java
new file mode 100644
index 0000000..5c16665
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexUtils.java
@@ -0,0 +1,39 @@
+/*
+ * 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.util;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+
+@SuppressWarnings("rawtypes") 
+public class TreeIndexUtils {
+	public static String printFrameTuples(ITreeIndexFrame frame, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {		
+		StringBuilder strBuilder = new StringBuilder();
+		ITreeIndexTupleReference tuple = frame.createTupleReference();
+		for (int i = 0; i < frame.getTupleCount(); i++) {
+			tuple.resetByTupleIndex(frame, i);
+			String tupleString = TupleUtils.printTuple(tuple, fieldSerdes);
+			strBuilder.append(tupleString);
+			if (i != tuple.getFieldCount() - 1) {
+				strBuilder.append(" | ");
+			}
+		}
+		return strBuilder.toString();
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
index f696615..222a039 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
@@ -39,9 +39,9 @@
 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.tuples.TypeAwareTupleWriterFactory;
-import edu.uci.ics.hyracks.storage.am.common.utility.TreeIndexBufferCacheWarmup;
-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.common.util.TreeIndexBufferCacheWarmup;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexStats;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexStatsGatherer;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
 import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
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 0fefd3d..0a04eca 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
@@ -51,8 +51,8 @@
 import edu.uci.ics.hyracks.storage.am.common.impls.TreeDiskOrderScanCursor;
 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.common.util.TreeIndexStats;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexStatsGatherer;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
 import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrameFactory;
 import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMLeafFrameFactory;