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 675bee3..d102612 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
@@ -18,7 +18,7 @@
 import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
 
-public interface IBTreeInteriorFrame extends IBTreeFrame {
+public interface IBTreeInteriorFrame extends ITreeIndexFrame {
     public int getChildPageId(RangePredicate pred, MultiComparator srcCmp);
 
     public int getLeftmostChildPageId(MultiComparator cmp);
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 9eb449c..21cb6b6 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
@@ -20,7 +20,7 @@
 import edu.uci.ics.hyracks.storage.am.btree.impls.FindTupleNoExactMatchPolicy;
 import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
 
-public interface IBTreeLeafFrame extends IBTreeFrame {
+public interface IBTreeLeafFrame extends ITreeIndexFrame {
     public void setNextLeaf(int nextPage);
 
     public int getNextLeaf();
@@ -29,8 +29,8 @@
 
     public int getPrevLeaf();
 
-    public IBTreeTupleReference createTupleReference();
+    public ITreeIndexTupleReference createTupleReference();
 
-    public int findTupleIndex(ITupleReference searchKey, IBTreeTupleReference pageTuple, MultiComparator cmp,
+    public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference pageTuple, MultiComparator cmp,
             FindTupleMode ftm, FindTupleNoExactMatchPolicy ftp);
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IPrefixSlotManager.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IPrefixSlotManager.java
index f45406f..97412e5 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IPrefixSlotManager.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IPrefixSlotManager.java
@@ -50,14 +50,14 @@
 
     public int encodeSlotFields(int firstField, int secondField);
 
-    public int findSlot(ITupleReference searchKey, IBTreeTupleReference frameTuple,
-            IBTreeTupleReference framePrefixTuple, MultiComparator multiCmp, FindTupleMode mode,
+    public int findSlot(ITupleReference searchKey, ITreeIndexTupleReference frameTuple,
+            ITreeIndexTupleReference framePrefixTuple, MultiComparator multiCmp, FindTupleMode mode,
             FindTupleNoExactMatchPolicy matchPolicy);
 
     public int insertSlot(int slot, int tupleOff);
 
     // returns prefix slot number, returns TUPLE_UNCOMPRESSED if none found
-    public int findPrefix(ITupleReference tuple, IBTreeTupleReference framePrefixTuple, MultiComparator multiCmp);
+    public int findPrefix(ITupleReference tuple, ITreeIndexTupleReference framePrefixTuple, MultiComparator multiCmp);
 
     public int getTupleSlotStartOff();
 
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ISlotManager.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ISlotManager.java
index c1d4e0a..a7e840e 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ISlotManager.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ISlotManager.java
@@ -21,9 +21,9 @@
 import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
 
 public interface ISlotManager {
-    public void setFrame(IBTreeFrame frame);
+    public void setFrame(ITreeIndexFrame frame);
 
-    public int findTupleIndex(ITupleReference searchKey, IBTreeTupleReference frameTuple, MultiComparator multiCmp,
+    public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, MultiComparator multiCmp,
             FindTupleMode mode, FindTupleNoExactMatchPolicy matchPolicy);
 
     public int insertSlot(int tupleIndex, int tupleOff);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ISplitKey.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ISplitKey.java
new file mode 100644
index 0000000..84526b8
--- /dev/null
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ISplitKey.java
@@ -0,0 +1,16 @@
+package edu.uci.ics.hyracks.storage.am.btree.api;
+
+import java.nio.ByteBuffer;
+
+public interface ISplitKey {
+	public void initData(int keySize);	
+	public void reset();
+	public ByteBuffer getBuffer();	        
+	public ITreeIndexTupleReference getTuple();
+	public int getLeftPage();
+	public int getRightPage();
+	public void setLeftPage(int leftPage);
+	public void setRightPage(int rightPage);
+	public void setPages(int leftPage, int rightPage);
+	public ISplitKey duplicate(ITreeIndexTupleReference copyTuple);
+}
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/ITreeIndexFrame.java
similarity index 84%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeFrame.java
rename to hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ITreeIndexFrame.java
index 0e15903..f5687a9 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/ITreeIndexFrame.java
@@ -21,11 +21,11 @@
 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.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.btree.impls.SpaceStatus;
-import edu.uci.ics.hyracks.storage.am.btree.impls.SplitKey;
+import edu.uci.ics.hyracks.storage.am.btree.impls.FrameOpSpaceStatus;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeSplitKey;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
 
-public interface IBTreeFrame {
+public interface ITreeIndexFrame {
     public void setPage(ICachedPage page);
 
     public ICachedPage getPage();
@@ -47,9 +47,9 @@
     public int getTupleCount();
 
     // assumption: page must be write-latched at this point
-    public SpaceStatus hasSpaceInsert(ITupleReference tuple, MultiComparator cmp);
+    public FrameOpSpaceStatus hasSpaceInsert(ITupleReference tuple, MultiComparator cmp);
 
-    public SpaceStatus hasSpaceUpdate(int rid, ITupleReference tuple, MultiComparator cmp);
+    public FrameOpSpaceStatus hasSpaceUpdate(int rid, ITupleReference tuple, MultiComparator cmp);
 
     public int getTupleOffset(int slotNum);
 
@@ -65,10 +65,9 @@
     public String printKeys(MultiComparator cmp, ISerializerDeserializer[] fields) throws HyracksDataException;
 
     // TODO; what if tuples more than half-page size?
-    public int split(IBTreeFrame rightFrame, ITupleReference tuple, MultiComparator cmp, SplitKey splitKey)
+    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, BTreeSplitKey splitKey)
             throws Exception;
-
-    // TODO: check if we do something nicer than returning object
+    
     public ISlotManager getSlotManager();
 
     // ATTENTION: in b-tree operations it may not always be possible to
@@ -97,6 +96,6 @@
 
     public void setFreeSpaceOff(int freeSpace);
 
-    public IBTreeTupleWriter getTupleWriter();
+    public ITreeIndexTupleWriter getTupleWriter();
 
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeTupleReference.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ITreeIndexTupleReference.java
similarity index 87%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeTupleReference.java
rename to hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ITreeIndexTupleReference.java
index 38d6217..67c946c 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeTupleReference.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ITreeIndexTupleReference.java
@@ -19,12 +19,12 @@
 
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 
-public interface IBTreeTupleReference extends ITupleReference {
+public interface ITreeIndexTupleReference extends ITupleReference {
     public void setFieldCount(int fieldCount);
 
     public void setFieldCount(int fieldStartIndex, int fieldCount);
 
     public void resetByOffset(ByteBuffer buf, int tupleStartOffset);
 
-    public void resetByTupleIndex(IBTreeFrame frame, int tupleIndex);
+    public void resetByTupleIndex(ITreeIndexFrame frame, int tupleIndex);
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeTupleWriter.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ITreeIndexTupleWriter.java
similarity index 93%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeTupleWriter.java
rename to hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ITreeIndexTupleWriter.java
index d8cb9af..2531290 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeTupleWriter.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ITreeIndexTupleWriter.java
@@ -19,7 +19,7 @@
 
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 
-public interface IBTreeTupleWriter {
+public interface ITreeIndexTupleWriter {
     public int writeTuple(ITupleReference tuple, ByteBuffer targetBuf, int targetOff);
 
     public int bytesRequired(ITupleReference tuple);
@@ -33,5 +33,5 @@
     // writer
     // the main idea is that the format of the written tuple may not be the same
     // as the format written by this writer
-    public IBTreeTupleReference createTupleReference();
+    public ITreeIndexTupleReference createTupleReference();
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeTupleWriterFactory.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ITreeIndexTupleWriterFactory.java
similarity index 85%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeTupleWriterFactory.java
rename to hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ITreeIndexTupleWriterFactory.java
index 645c430..4eed9c3 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeTupleWriterFactory.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ITreeIndexTupleWriterFactory.java
@@ -17,6 +17,6 @@
 
 import java.io.Serializable;
 
-public interface IBTreeTupleWriterFactory extends Serializable {
-    public IBTreeTupleWriter createTupleWriter();
+public interface ITreeIndexTupleWriterFactory extends Serializable {
+    public ITreeIndexTupleWriter createTupleWriter();
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorDescriptor.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorDescriptor.java
index 7d50fff..b7a88ed 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorDescriptor.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorDescriptor.java
@@ -26,7 +26,7 @@
 import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrameFactory;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrameFactory;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOp;
+import edu.uci.ics.hyracks.storage.am.btree.impls.TreeIndexOp;
 import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
 
 public class BTreeInsertUpdateDeleteOperatorDescriptor extends AbstractBTreeOperatorDescriptor {
@@ -35,13 +35,13 @@
 
     private final int[] fieldPermutation;
 
-    private BTreeOp op;
+    private TreeIndexOp op;
 
     public BTreeInsertUpdateDeleteOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc,
             IStorageManagerInterface storageManager, IBTreeRegistryProvider btreeRegistryProvider,
             IFileSplitProvider fileSplitProvider, IBTreeInteriorFrameFactory interiorFactory,
             IBTreeLeafFrameFactory leafFactory, ITypeTrait[] typeTraits,
-            IBinaryComparatorFactory[] comparatorFactories, int[] fieldPermutation, BTreeOp op) {
+            IBinaryComparatorFactory[] comparatorFactories, int[] fieldPermutation, TreeIndexOp op) {
         super(spec, 1, 1, recDesc, storageManager, btreeRegistryProvider, fileSplitProvider, interiorFactory,
                 leafFactory, typeTraits, comparatorFactories);
         this.fieldPermutation = fieldPermutation;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorNodePushable.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorNodePushable.java
index 733cb88..681c86b 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorNodePushable.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorNodePushable.java
@@ -24,7 +24,7 @@
 import edu.uci.ics.hyracks.dataflow.common.comm.util.FrameUtils;
 import edu.uci.ics.hyracks.dataflow.std.base.AbstractUnaryInputUnaryOutputOperatorNodePushable;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOp;
+import edu.uci.ics.hyracks.storage.am.btree.impls.TreeIndexOp;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrame;
 
@@ -32,14 +32,14 @@
     private final BTreeOpHelper btreeOpHelper;
     private FrameTupleAccessor accessor;
     private final IRecordDescriptorProvider recordDescProvider;
-    private final BTreeOp op;
+    private final TreeIndexOp op;
     private final PermutingFrameTupleReference tuple = new PermutingFrameTupleReference();
     private ByteBuffer writeBuffer;
     private BTreeOpContext opCtx;
 
     public BTreeInsertUpdateDeleteOperatorNodePushable(AbstractBTreeOperatorDescriptor opDesc,
             IHyracksStageletContext ctx, int partition, int[] fieldPermutation,
-            IRecordDescriptorProvider recordDescProvider, BTreeOp op) {
+            IRecordDescriptorProvider recordDescProvider, TreeIndexOp op) {
         btreeOpHelper = new BTreeOpHelper(opDesc, ctx, partition, BTreeOpHelper.BTreeMode.OPEN_BTREE);
         this.recordDescProvider = recordDescProvider;
         this.op = op;
@@ -75,12 +75,12 @@
             try {
                 switch (op) {
 
-                    case BTO_INSERT: {
+                    case TI_INSERT: {
                         btree.insert(tuple, opCtx);
                     }
                         break;
 
-                    case BTO_DELETE: {
+                    case TI_DELETE: {
                         btree.delete(tuple, opCtx);
                     }
                         break;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorNodePushable.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorNodePushable.java
index 415f169..e68ea40 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorNodePushable.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorNodePushable.java
@@ -31,7 +31,7 @@
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeCursor;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOp;
+import edu.uci.ics.hyracks.storage.am.btree.impls.TreeIndexOp;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
@@ -149,7 +149,7 @@
 					.getHyracksStageletContext().getFrameSize());
 			appender.reset(writeBuffer, true);
 
-			opCtx = btree.createOpContext(BTreeOp.BTO_SEARCH, btreeOpHelper
+			opCtx = btree.createOpContext(TreeIndexOp.TI_SEARCH, btreeOpHelper
 					.getLeafFrame(), btreeOpHelper.getInteriorFrame(), null);
 
 		} catch (Exception e) {
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/FieldPrefixNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/FieldPrefixNSMLeafFrame.java
index 6eeb5e1..7cabe16 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/FieldPrefixNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/FieldPrefixNSMLeafFrame.java
@@ -26,10 +26,10 @@
 import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
 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.api.IBTreeFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriter;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriter;
 import edu.uci.ics.hyracks.storage.am.btree.api.IFrameCompressor;
 import edu.uci.ics.hyracks.storage.am.btree.api.IPrefixSlotManager;
 import edu.uci.ics.hyracks.storage.am.btree.api.ISlotManager;
@@ -42,8 +42,8 @@
 import edu.uci.ics.hyracks.storage.am.btree.impls.FindTupleNoExactMatchPolicy;
 import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.btree.impls.SlotOffTupleOff;
-import edu.uci.ics.hyracks.storage.am.btree.impls.SpaceStatus;
-import edu.uci.ics.hyracks.storage.am.btree.impls.SplitKey;
+import edu.uci.ics.hyracks.storage.am.btree.impls.FrameOpSpaceStatus;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeSplitKey;
 import edu.uci.ics.hyracks.storage.am.btree.tuples.TypeAwareTupleWriter;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
 
@@ -69,12 +69,12 @@
     public IPrefixSlotManager slotManager; // TODO: should be protected, but
     // will trigger some refactoring
 
-    private IBTreeTupleWriter tupleWriter;
+    private ITreeIndexTupleWriter tupleWriter;
 
     private FieldPrefixTupleReference frameTuple;
     private FieldPrefixPrefixTupleReference framePrefixTuple;
 
-    public FieldPrefixNSMLeafFrame(IBTreeTupleWriter tupleWriter) {
+    public FieldPrefixNSMLeafFrame(ITreeIndexTupleWriter tupleWriter) {
         this.tupleWriter = tupleWriter;
         this.frameTuple = new FieldPrefixTupleReference(tupleWriter.createTupleReference());
         ITypeTrait[] typeTraits = ((TypeAwareTupleWriter) tupleWriter).getTypeTraits();
@@ -225,7 +225,7 @@
     }
 
     @Override
-    public SpaceStatus hasSpaceInsert(ITupleReference tuple, MultiComparator cmp) {
+    public FrameOpSpaceStatus hasSpaceInsert(ITupleReference tuple, MultiComparator cmp) {
         int freeContiguous = buf.capacity() - buf.getInt(freeSpaceOff)
                 - ((buf.getInt(tupleCountOff) + buf.getInt(prefixTupleCountOff)) * slotManager.getSlotSize());
 
@@ -233,11 +233,11 @@
 
         // see if the tuple would fit uncompressed
         if (bytesRequired + slotManager.getSlotSize() <= freeContiguous)
-            return SpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
+            return FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
 
         // see if tuple would fit into remaining space after compaction
         if (bytesRequired + slotManager.getSlotSize() <= buf.getInt(totalFreeSpaceOff))
-            return SpaceStatus.SUFFICIENT_SPACE;
+            return FrameOpSpaceStatus.SUFFICIENT_SPACE;
 
         // see if the tuple matches a prefix and will fit after truncating the
         // prefix
@@ -250,16 +250,16 @@
             int compressedSize = tupleWriter.bytesRequired(tuple, numPrefixFields, tuple.getFieldCount()
                     - numPrefixFields);
             if (compressedSize + slotManager.getSlotSize() <= freeContiguous)
-                return SpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
+                return FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
         }
 
-        return SpaceStatus.INSUFFICIENT_SPACE;
+        return FrameOpSpaceStatus.INSUFFICIENT_SPACE;
     }
 
     @Override
-    public SpaceStatus hasSpaceUpdate(int rid, ITupleReference tuple, MultiComparator cmp) {
+    public FrameOpSpaceStatus hasSpaceUpdate(int rid, ITupleReference tuple, MultiComparator cmp) {
         // TODO Auto-generated method stub
-        return SpaceStatus.INSUFFICIENT_SPACE;
+        return FrameOpSpaceStatus.INSUFFICIENT_SPACE;
     }
 
     protected void resetSpaceParams() {
@@ -446,7 +446,7 @@
     }
 
     @Override
-    public int split(IBTreeFrame rightFrame, ITupleReference tuple, MultiComparator cmp, SplitKey splitKey)
+    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, BTreeSplitKey splitKey)
             throws Exception {
 
         FieldPrefixNSMLeafFrame rf = (FieldPrefixNSMLeafFrame) rightFrame;
@@ -470,7 +470,7 @@
 
         int tuplesToLeft;
         int midSlotNum = tupleCount / 2;
-        IBTreeFrame targetFrame = null;
+        ITreeIndexFrame targetFrame = null;
         frameTuple.resetByTupleIndex(this, midSlotNum);
         int comparison = cmp.compare(tuple, frameTuple);
         if (comparison >= 0) {
@@ -638,17 +638,17 @@
         frameTuple.setFieldCount(fieldCount);
     }
 
-    public IBTreeTupleWriter getTupleWriter() {
+    public ITreeIndexTupleWriter getTupleWriter() {
         return tupleWriter;
     }
 
     @Override
-    public IBTreeTupleReference createTupleReference() {
+    public ITreeIndexTupleReference createTupleReference() {
         return new FieldPrefixTupleReference(tupleWriter.createTupleReference());
     }
 
     @Override
-    public int findTupleIndex(ITupleReference searchKey, IBTreeTupleReference pageTuple, MultiComparator cmp,
+    public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference pageTuple, MultiComparator cmp,
             FindTupleMode ftm, FindTupleNoExactMatchPolicy ftp) {
         int slot = slotManager.findSlot(searchKey, pageTuple, framePrefixTuple, cmp, ftm, ftp);
         int tupleIndex = slotManager.decodeSecondSlotField(slot);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/FieldPrefixNSMLeafFrameFactory.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/FieldPrefixNSMLeafFrameFactory.java
index a3084ab..acac44e 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/FieldPrefixNSMLeafFrameFactory.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/FieldPrefixNSMLeafFrameFactory.java
@@ -17,14 +17,14 @@
 
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrameFactory;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriterFactory;
 
 public class FieldPrefixNSMLeafFrameFactory implements IBTreeLeafFrameFactory {
 
     private static final long serialVersionUID = 1L;
-    private IBTreeTupleWriterFactory tupleWriterFactory;
+    private ITreeIndexTupleWriterFactory tupleWriterFactory;
 
-    public FieldPrefixNSMLeafFrameFactory(IBTreeTupleWriterFactory tupleWriterFactory) {
+    public FieldPrefixNSMLeafFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory) {
         this.tupleWriterFactory = tupleWriterFactory;
     }
 
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrame.java
index 90d400d..1df55f8 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrame.java
@@ -25,29 +25,29 @@
 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.storage.am.btree.api.IBTreeFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriter;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriter;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeException;
 import edu.uci.ics.hyracks.storage.am.btree.impls.FindTupleMode;
 import edu.uci.ics.hyracks.storage.am.btree.impls.FindTupleNoExactMatchPolicy;
 import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
 import edu.uci.ics.hyracks.storage.am.btree.impls.SlotOffTupleOff;
-import edu.uci.ics.hyracks.storage.am.btree.impls.SpaceStatus;
-import edu.uci.ics.hyracks.storage.am.btree.impls.SplitKey;
+import edu.uci.ics.hyracks.storage.am.btree.impls.FrameOpSpaceStatus;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeSplitKey;
 
-public class NSMInteriorFrame extends NSMFrame implements IBTreeInteriorFrame {
+public class NSMInteriorFrame extends TreeIndexNSMFrame implements IBTreeInteriorFrame {
 
     private static final int rightLeafOff = smFlagOff + 1;
 
     private static final int childPtrSize = 4;
 
     // private SimpleTupleReference cmpFrameTuple = new SimpleTupleReference();
-    private IBTreeTupleReference cmpFrameTuple;
+    private ITreeIndexTupleReference cmpFrameTuple;
 
-    public NSMInteriorFrame(IBTreeTupleWriter tupleWriter) {
+    public NSMInteriorFrame(ITreeIndexTupleWriter tupleWriter) {
         super(tupleWriter);
         cmpFrameTuple = tupleWriter.createTupleReference();
 
@@ -64,16 +64,16 @@
     }
 
     @Override
-    public SpaceStatus hasSpaceInsert(ITupleReference tuple, MultiComparator cmp) {
+    public FrameOpSpaceStatus hasSpaceInsert(ITupleReference tuple, MultiComparator cmp) {
         int bytesRequired = tupleWriter.bytesRequired(tuple) + 8; // for the two
         // childpointers
         if (bytesRequired + slotManager.getSlotSize() <= buf.capacity() - buf.getInt(freeSpaceOff)
                 - (buf.getInt(tupleCountOff) * slotManager.getSlotSize()))
-            return SpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
+            return FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
         else if (bytesRequired + slotManager.getSlotSize() <= buf.getInt(totalFreeSpaceOff))
-            return SpaceStatus.SUFFICIENT_SPACE;
+            return FrameOpSpaceStatus.SUFFICIENT_SPACE;
         else
-            return SpaceStatus.INSUFFICIENT_SPACE;
+            return FrameOpSpaceStatus.INSUFFICIENT_SPACE;
     }
 
     @Override
@@ -144,7 +144,7 @@
     }
 
     @Override
-    public int split(IBTreeFrame rightFrame, ITupleReference tuple, MultiComparator cmp, SplitKey splitKey)
+    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, BTreeSplitKey splitKey)
             throws Exception {
         // before doing anything check if key already exists
         frameTuple.setFieldCount(cmp.getKeyFieldCount());
@@ -162,7 +162,7 @@
         int tupleCount = buf.getInt(tupleCountOff);
 
         int tuplesToLeft = (tupleCount / 2) + (tupleCount % 2);
-        IBTreeFrame targetFrame = null;
+        ITreeIndexFrame targetFrame = null;
         frameTuple.resetByOffset(buf, getTupleOffset(tuplesToLeft - 1));
         if (cmp.compare(tuple, frameTuple) <= 0) {
             targetFrame = this;
@@ -189,7 +189,7 @@
         // 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())
-        SplitKey savedSplitKey = splitKey.duplicate(tupleWriter.createTupleReference());
+        BTreeSplitKey savedSplitKey = splitKey.duplicate(tupleWriter.createTupleReference());
 
         // set split key to be highest value in left page
         int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrameFactory.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrameFactory.java
index 86fa94f..3e451f9 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrameFactory.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrameFactory.java
@@ -17,14 +17,14 @@
 
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrameFactory;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriterFactory;
 
 public class NSMInteriorFrameFactory implements IBTreeInteriorFrameFactory {
 
     private static final long serialVersionUID = 1L;
-    private IBTreeTupleWriterFactory tupleWriterFactory;
+    private ITreeIndexTupleWriterFactory tupleWriterFactory;
 
-    public NSMInteriorFrameFactory(IBTreeTupleWriterFactory tupleWriterFactory) {
+    public NSMInteriorFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory) {
         this.tupleWriterFactory = tupleWriterFactory;
     }
 
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrame.java
index fd8f826..e22b825 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrame.java
@@ -19,21 +19,21 @@
 
 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.api.IBTreeFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriter;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriter;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeException;
 import edu.uci.ics.hyracks.storage.am.btree.impls.FindTupleMode;
 import edu.uci.ics.hyracks.storage.am.btree.impls.FindTupleNoExactMatchPolicy;
 import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.btree.impls.SplitKey;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeSplitKey;
 
-public class NSMLeafFrame extends NSMFrame implements IBTreeLeafFrame {
+public class NSMLeafFrame extends TreeIndexNSMFrame implements IBTreeLeafFrame {
     protected static final int prevLeafOff = smFlagOff + 1;
     protected static final int nextLeafOff = prevLeafOff + 4;
 
-    public NSMLeafFrame(IBTreeTupleWriter tupleWriter) {
+    public NSMLeafFrame(ITreeIndexTupleWriter tupleWriter) {
         super(tupleWriter);
     }
 
@@ -105,7 +105,7 @@
     }
 
     @Override
-    public int split(IBTreeFrame rightFrame, ITupleReference tuple, MultiComparator cmp, SplitKey splitKey)
+    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, BTreeSplitKey splitKey)
             throws Exception {
 
         frameTuple.setFieldCount(cmp.getFieldCount());
@@ -125,7 +125,7 @@
 
         int tuplesToLeft;
         int mid = tupleCount / 2;
-        IBTreeFrame targetFrame = null;
+        ITreeIndexFrame targetFrame = null;
         int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff() + slotManager.getSlotSize() * mid);
         frameTuple.resetByOffset(buf, tupleOff);
         if (cmp.compare(tuple, frameTuple) >= 0) {
@@ -177,12 +177,12 @@
     }
 
     @Override
-    public IBTreeTupleReference createTupleReference() {
+    public ITreeIndexTupleReference createTupleReference() {
         return tupleWriter.createTupleReference();
     }
 
     @Override
-    public int findTupleIndex(ITupleReference searchKey, IBTreeTupleReference pageTuple, MultiComparator cmp,
+    public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference pageTuple, MultiComparator cmp,
             FindTupleMode ftm, FindTupleNoExactMatchPolicy ftp) {
         return slotManager.findTupleIndex(searchKey, pageTuple, cmp, ftm, ftp);
     }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrameFactory.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrameFactory.java
index 202f31a..e774f39 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrameFactory.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrameFactory.java
@@ -17,14 +17,14 @@
 
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrameFactory;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriterFactory;
 
 public class NSMLeafFrameFactory implements IBTreeLeafFrameFactory {
 
     private static final long serialVersionUID = 1L;
-    private IBTreeTupleWriterFactory tupleWriterFactory;
+    private ITreeIndexTupleWriterFactory tupleWriterFactory;
 
-    public NSMLeafFrameFactory(IBTreeTupleWriterFactory tupleWriterFactory) {
+    public NSMLeafFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory) {
         this.tupleWriterFactory = tupleWriterFactory;
     }
 
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/TreeIndexNSMFrame.java
similarity index 91%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMFrame.java
rename to hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/TreeIndexNSMFrame.java
index 2324eab..d47ece4 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/TreeIndexNSMFrame.java
@@ -25,9 +25,9 @@
 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.storage.am.btree.api.IBTreeFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriter;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriter;
 import edu.uci.ics.hyracks.storage.am.btree.api.ISlotManager;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeException;
 import edu.uci.ics.hyracks.storage.am.btree.impls.FindTupleMode;
@@ -35,10 +35,10 @@
 import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.btree.impls.OrderedSlotManager;
 import edu.uci.ics.hyracks.storage.am.btree.impls.SlotOffTupleOff;
-import edu.uci.ics.hyracks.storage.am.btree.impls.SpaceStatus;
+import edu.uci.ics.hyracks.storage.am.btree.impls.FrameOpSpaceStatus;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
 
-public abstract class NSMFrame implements IBTreeFrame {
+public abstract class TreeIndexNSMFrame implements ITreeIndexFrame {
 
     protected static final int pageLsnOff = 0; // 0
     protected static final int tupleCountOff = pageLsnOff + 4; // 4
@@ -51,10 +51,10 @@
     protected ByteBuffer buf = null;
     protected ISlotManager slotManager;
 
-    protected IBTreeTupleWriter tupleWriter;
-    protected IBTreeTupleReference frameTuple;
+    protected ITreeIndexTupleWriter tupleWriter;
+    protected ITreeIndexTupleReference frameTuple;
 
-    public NSMFrame(IBTreeTupleWriter tupleWriter) {
+    public TreeIndexNSMFrame(ITreeIndexTupleWriter tupleWriter) {
         this.tupleWriter = tupleWriter;
         this.frameTuple = tupleWriter.createTupleReference();
         this.slotManager = new OrderedSlotManager();
@@ -198,21 +198,21 @@
     }
 
     @Override
-    public SpaceStatus hasSpaceInsert(ITupleReference tuple, MultiComparator cmp) {
+    public FrameOpSpaceStatus hasSpaceInsert(ITupleReference tuple, MultiComparator cmp) {
         int bytesRequired = tupleWriter.bytesRequired(tuple);
         if (bytesRequired + slotManager.getSlotSize() <= buf.capacity() - buf.getInt(freeSpaceOff)
                 - (buf.getInt(tupleCountOff) * slotManager.getSlotSize()))
-            return SpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
+            return FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
         else if (bytesRequired + slotManager.getSlotSize() <= buf.getInt(totalFreeSpaceOff))
-            return SpaceStatus.SUFFICIENT_SPACE;
+            return FrameOpSpaceStatus.SUFFICIENT_SPACE;
         else
-            return SpaceStatus.INSUFFICIENT_SPACE;
+            return FrameOpSpaceStatus.INSUFFICIENT_SPACE;
     }
 
     @Override
-    public SpaceStatus hasSpaceUpdate(int rid, ITupleReference tuple, MultiComparator cmp) {
+    public FrameOpSpaceStatus hasSpaceUpdate(int rid, ITupleReference tuple, MultiComparator cmp) {
         // TODO Auto-generated method stub
-        return SpaceStatus.INSUFFICIENT_SPACE;
+        return FrameOpSpaceStatus.INSUFFICIENT_SPACE;
     }
 
     protected void resetSpaceParams() {
@@ -309,7 +309,7 @@
         frameTuple.setFieldCount(fieldCount);
     }
 
-    public IBTreeTupleWriter getTupleWriter() {
+    public ITreeIndexTupleWriter getTupleWriter() {
         return tupleWriter;
     }
 }
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 1902572..6a610e7 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
@@ -23,12 +23,12 @@
 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.api.IBTreeCursor;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrameFactory;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrameFactory;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriter;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriter;
 import edu.uci.ics.hyracks.storage.am.btree.frames.NSMInteriorFrame;
 import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
@@ -395,7 +395,7 @@
     private void insertLeaf(ICachedPage node, int pageId, ITupleReference tuple, BTreeOpContext ctx) throws Exception {
         ctx.leafFrame.setPage(node);
         ctx.leafFrame.setPageTupleFieldCount(cmp.getFieldCount());
-        SpaceStatus spaceStatus = ctx.leafFrame.hasSpaceInsert(tuple, cmp);
+        FrameOpSpaceStatus spaceStatus = ctx.leafFrame.hasSpaceInsert(tuple, cmp);
         switch (spaceStatus) {
 
             case SUFFICIENT_CONTIGUOUS_SPACE: {
@@ -424,7 +424,7 @@
                 if (reCompressed)
                     spaceStatus = ctx.leafFrame.hasSpaceInsert(tuple, cmp);
 
-                if (spaceStatus == SpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE) {
+                if (spaceStatus == FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE) {
                     ctx.leafFrame.insert(tuple, cmp);
                     ctx.splitKey.reset();
 
@@ -533,7 +533,7 @@
             throws Exception {
         ctx.interiorFrame.setPage(node);
         ctx.interiorFrame.setPageTupleFieldCount(cmp.getKeyFieldCount());
-        SpaceStatus spaceStatus = ctx.interiorFrame.hasSpaceInsert(tuple, cmp);
+        FrameOpSpaceStatus spaceStatus = ctx.interiorFrame.hasSpaceInsert(tuple, cmp);
         switch (spaceStatus) {
             case INSUFFICIENT_SPACE: {
                 splitsByLevel[ctx.interiorFrame.getLevel()]++; // debug
@@ -543,7 +543,7 @@
                 rightNode.acquireWriteLatch();
                 writeLatchesAcquired++;
                 try {
-                    IBTreeFrame rightFrame = interiorFrameFactory.getFrame();
+                    ITreeIndexFrame rightFrame = interiorFrameFactory.getFrame();
                     rightFrame.setPage(rightNode);
                     rightFrame.initBuffer((byte) ctx.interiorFrame.getLevel());
                     rightFrame.setPageTupleFieldCount(cmp.getKeyFieldCount());
@@ -784,8 +784,8 @@
         }
     }
 
-    private final void acquireLatch(ICachedPage node, BTreeOp op, boolean isLeaf) {
-        if (isLeaf && (op.equals(BTreeOp.BTO_INSERT) || op.equals(BTreeOp.BTO_DELETE))) {
+    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 {
@@ -794,8 +794,8 @@
         }
     }
 
-    private final void releaseLatch(ICachedPage node, BTreeOp op, boolean isLeaf) {
-        if (isLeaf && (op.equals(BTreeOp.BTO_INSERT) || op.equals(BTreeOp.BTO_DELETE))) {
+    private final void releaseLatch(ICachedPage node, TreeIndexOp op, boolean isLeaf) {
+        if (isLeaf && (op.equals(TreeIndexOp.TI_INSERT) || op.equals(TreeIndexOp.TI_DELETE))) {
             node.releaseWriteLatch();
             writeLatchesReleased++;
         } else {
@@ -882,7 +882,7 @@
 
                         switch (ctx.op) {
 
-                            case BTO_INSERT: {
+                            case TI_INSERT: {
                                 if (ctx.splitKey.getBuffer() != null) {
                                     node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
                                     pins++;
@@ -902,7 +902,7 @@
                             }
                                 break;
 
-                            case BTO_DELETE: {
+                            case TI_DELETE: {
                                 if (ctx.splitKey.getBuffer() != null) {
                                     node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
                                     pins++;
@@ -922,7 +922,7 @@
                             }
                                 break;
 
-                            case BTO_SEARCH: {
+                            case TI_SEARCH: {
                                 // do nothing
                             }
                                 break;
@@ -957,17 +957,17 @@
                 }
             } else { // isLeaf and !smFlag
                 switch (ctx.op) {
-                    case BTO_INSERT: {
+                    case TI_INSERT: {
                         insertLeaf(node, pageId, ctx.pred.getLowKey(), ctx);
                     }
                         break;
 
-                    case BTO_DELETE: {
+                    case TI_DELETE: {
                         deleteLeaf(node, pageId, ctx.pred.getLowKey(), ctx);
                     }
                         break;
 
-                    case BTO_SEARCH: {
+                    case TI_SEARCH: {
                         ctx.cursor.open(node, ctx.pred);
                     }
                         break;
@@ -1006,19 +1006,19 @@
         public final int slotSize;
         public final int leafMaxBytes;
         public final int interiorMaxBytes;
-        public final SplitKey splitKey;
+        public final BTreeSplitKey splitKey;
         // we maintain a frontier of nodes for each level
         private final ArrayList<NodeFrontier> nodeFrontiers = new ArrayList<NodeFrontier>();
         private final IBTreeLeafFrame leafFrame;
         private final IBTreeInteriorFrame interiorFrame;
         private final ITreeIndexMetaDataFrame metaFrame;
 
-        private final IBTreeTupleWriter tupleWriter;
+        private final ITreeIndexTupleWriter tupleWriter;
 
         public BulkLoadContext(float fillFactor, IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
                 ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
 
-            splitKey = new SplitKey(leafFrame.getTupleWriter().createTupleReference());
+            splitKey = new BTreeSplitKey(leafFrame.getTupleWriter().createTupleReference());
             tupleWriter = leafFrame.getTupleWriter();
 
             NodeFrontier leafFrontier = new NodeFrontier(leafFrame.createTupleReference());
@@ -1071,7 +1071,7 @@
         int spaceUsed = ctx.interiorFrame.getBuffer().capacity() - ctx.interiorFrame.getTotalFreeSpace();
         if (spaceUsed + spaceNeeded > ctx.interiorMaxBytes) {
 
-            SplitKey copyKey = ctx.splitKey.duplicate(ctx.leafFrame.getTupleWriter().createTupleReference());
+            BTreeSplitKey copyKey = ctx.splitKey.duplicate(ctx.leafFrame.getTupleWriter().createTupleReference());
             tuple = copyKey.getTuple();
 
             frontier.lastTuple.resetByOffset(frontier.page.getBuffer(), ctx.interiorFrame
@@ -1193,7 +1193,7 @@
         loaded = true;
     }
 
-    public BTreeOpContext createOpContext(BTreeOp op, IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
+    public BTreeOpContext createOpContext(TreeIndexOp op, IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
             ITreeIndexMetaDataFrame metaFrame) {
         // TODO: figure out better tree-height hint
         return new BTreeOpContext(op, leafFrame, interiorFrame, metaFrame, 6);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
index fb59d07..92ad0a2 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
@@ -21,19 +21,19 @@
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
 
 public final class BTreeOpContext {
-    public final BTreeOp op;
+    public final TreeIndexOp op;
     public final IBTreeLeafFrame leafFrame;
     public final IBTreeInteriorFrame interiorFrame;
     public final ITreeIndexMetaDataFrame metaFrame;
     public IBTreeCursor cursor;
     public RangePredicate pred;
-    public final SplitKey splitKey;
+    public final BTreeSplitKey splitKey;
     public int opRestarts = 0;
     public final IntArrayList pageLsns; // used like a stack
     public final IntArrayList smPages;
     public final IntArrayList freePages;
 
-    public BTreeOpContext(BTreeOp op, IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
+    public BTreeOpContext(TreeIndexOp op, IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
     		ITreeIndexMetaDataFrame metaFrame, int treeHeightHint) {
         this.op = op;
         this.leafFrame = leafFrame;
@@ -41,11 +41,11 @@
         this.metaFrame = metaFrame;
 
         pageLsns = new IntArrayList(treeHeightHint, treeHeightHint);
-        if (op != BTreeOp.BTO_SEARCH) {
+        if (op != TreeIndexOp.TI_SEARCH) {
             smPages = new IntArrayList(treeHeightHint, treeHeightHint);
             freePages = new IntArrayList(treeHeightHint, treeHeightHint);
             pred = new RangePredicate(true, null, null, true, true, null, null);
-            splitKey = new SplitKey(leafFrame.getTupleWriter().createTupleReference());
+            splitKey = new BTreeSplitKey(leafFrame.getTupleWriter().createTupleReference());
         } else {
             smPages = null;
             freePages = null;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/SplitKey.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeSplitKey.java
similarity index 82%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/SplitKey.java
rename to hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeSplitKey.java
index cf2fd74..1c02d71 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/SplitKey.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeSplitKey.java
@@ -17,18 +17,19 @@
 
 import java.nio.ByteBuffer;
 
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ISplitKey;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
 
-public class SplitKey {
+public class BTreeSplitKey implements ISplitKey {
     public byte[] data = null;
     public ByteBuffer buf = null;
-    public IBTreeTupleReference tuple;
+    public ITreeIndexTupleReference tuple;
     public int keySize = 0;
 
-    public SplitKey(IBTreeTupleReference tuple) {
+    public BTreeSplitKey(ITreeIndexTupleReference tuple) {
         this.tuple = tuple;
     }
-
+    
     public void initData(int keySize) {
         // try to reuse existing memory from a lower-level split if possible
         this.keySize = keySize;
@@ -54,7 +55,7 @@
         return buf;
     }
 
-    public IBTreeTupleReference getTuple() {
+    public ITreeIndexTupleReference getTuple() {
         return tuple;
     }
 
@@ -79,8 +80,8 @@
         buf.putInt(keySize + 4, rightPage);
     }
 
-    public SplitKey duplicate(IBTreeTupleReference copyTuple) {
-        SplitKey copy = new SplitKey(copyTuple);
+    public BTreeSplitKey duplicate(ITreeIndexTupleReference copyTuple) {
+        BTreeSplitKey copy = new BTreeSplitKey(copyTuple);
         copy.data = data.clone();
         copy.buf = ByteBuffer.wrap(copy.data);
         copy.tuple.setFieldCount(tuple.getFieldCount());
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/DiskOrderScanCursor.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/DiskOrderScanCursor.java
index 29086ba..0aab609 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/DiskOrderScanCursor.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/DiskOrderScanCursor.java
@@ -18,7 +18,7 @@
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeCursor;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
 import edu.uci.ics.hyracks.storage.am.btree.api.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
@@ -38,7 +38,7 @@
     private IBTreeLeafFrame frame = null;
     private IBufferCache bufferCache = null;
 
-    private IBTreeTupleReference frameTuple;
+    private ITreeIndexTupleReference frameTuple;
 
     public DiskOrderScanCursor(IBTreeLeafFrame frame) {
         this.frame = frame;
@@ -53,7 +53,7 @@
     }
 
     @Override
-    public IBTreeTupleReference getTuple() {
+    public ITreeIndexTupleReference getTuple() {
         return frameTuple;
     }
 
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixPrefixTupleReference.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixPrefixTupleReference.java
index 8711a17..d3f28f9 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixPrefixTupleReference.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixPrefixTupleReference.java
@@ -16,7 +16,7 @@
 package edu.uci.ics.hyracks.storage.am.btree.impls;
 
 import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexFrame;
 import edu.uci.ics.hyracks.storage.am.btree.frames.FieldPrefixNSMLeafFrame;
 import edu.uci.ics.hyracks.storage.am.btree.tuples.TypeAwareTupleReference;
 
@@ -28,7 +28,7 @@
 
     // assumes tuple index refers to prefix tuples
     @Override
-    public void resetByTupleIndex(IBTreeFrame frame, int tupleIndex) {
+    public void resetByTupleIndex(ITreeIndexFrame frame, int tupleIndex) {
         FieldPrefixNSMLeafFrame concreteFrame = (FieldPrefixNSMLeafFrame) frame;
         int prefixSlotOff = concreteFrame.slotManager.getPrefixSlotOff(tupleIndex);
         int prefixSlot = concreteFrame.getBuffer().getInt(prefixSlotOff);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixSlotManager.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixSlotManager.java
index 83a2d92..112e186 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixSlotManager.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixSlotManager.java
@@ -18,7 +18,7 @@
 import java.nio.ByteBuffer;
 
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
 import edu.uci.ics.hyracks.storage.am.btree.api.IPrefixSlotManager;
 import edu.uci.ics.hyracks.storage.am.btree.frames.FieldPrefixNSMLeafFrame;
 
@@ -45,7 +45,7 @@
     }
 
     // returns prefix slot number, or TUPLE_UNCOMPRESSED of no match was found
-    public int findPrefix(ITupleReference tuple, IBTreeTupleReference framePrefixTuple, MultiComparator multiCmp) {
+    public int findPrefix(ITupleReference tuple, ITreeIndexTupleReference framePrefixTuple, MultiComparator multiCmp) {
         int prefixMid;
         int prefixBegin = 0;
         int prefixEnd = frame.getPrefixTupleCount() - 1;
@@ -68,8 +68,8 @@
     }
 
     @Override
-    public int findSlot(ITupleReference searchKey, IBTreeTupleReference frameTuple,
-            IBTreeTupleReference framePrefixTuple, MultiComparator multiCmp, FindTupleMode mode,
+    public int findSlot(ITupleReference searchKey, ITreeIndexTupleReference frameTuple,
+            ITreeIndexTupleReference framePrefixTuple, MultiComparator multiCmp, FindTupleMode mode,
             FindTupleNoExactMatchPolicy matchPolicy) {
         if (frame.getTupleCount() <= 0)
             encodeSlotFields(TUPLE_UNCOMPRESSED, GREATEST_SLOT);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixTupleReference.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixTupleReference.java
index c131e3f..d3fb098 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixTupleReference.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixTupleReference.java
@@ -2,25 +2,25 @@
 
 import java.nio.ByteBuffer;
 
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
 import edu.uci.ics.hyracks.storage.am.btree.frames.FieldPrefixNSMLeafFrame;
 
-public class FieldPrefixTupleReference implements IBTreeTupleReference {
+public class FieldPrefixTupleReference implements ITreeIndexTupleReference {
 
     private FieldPrefixNSMLeafFrame frame;
     private int prefixTupleStartOff;
     private int suffixTupleStartOff;
     private int numPrefixFields;
     private int fieldCount;
-    private IBTreeTupleReference helperTuple;
+    private ITreeIndexTupleReference helperTuple;
 
-    public FieldPrefixTupleReference(IBTreeTupleReference helperTuple) {
+    public FieldPrefixTupleReference(ITreeIndexTupleReference helperTuple) {
         this.helperTuple = helperTuple;
     }
 
     @Override
-    public void resetByTupleIndex(IBTreeFrame frame, int tupleIndex) {
+    public void resetByTupleIndex(ITreeIndexFrame frame, int tupleIndex) {
         this.frame = (FieldPrefixNSMLeafFrame) frame;
 
         int tupleSlotOff = this.frame.slotManager.getTupleSlotOff(tupleIndex);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/SpaceStatus.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FrameOpSpaceStatus.java
similarity index 95%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/SpaceStatus.java
rename to hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FrameOpSpaceStatus.java
index 9ad15ee..0568057 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/SpaceStatus.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FrameOpSpaceStatus.java
@@ -15,6 +15,6 @@
 
 package edu.uci.ics.hyracks.storage.am.btree.impls;
 
-public enum SpaceStatus {
+public enum FrameOpSpaceStatus {
     INSUFFICIENT_SPACE, SUFFICIENT_CONTIGUOUS_SPACE, SUFFICIENT_SPACE
 }
\ No newline at end of file
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/NodeFrontier.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/NodeFrontier.java
index 83baa92..7501c5a 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/NodeFrontier.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/NodeFrontier.java
@@ -15,15 +15,15 @@
 
 package edu.uci.ics.hyracks.storage.am.btree.impls;
 
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
 
 public class NodeFrontier {
     public ICachedPage page;
     public int pageId;
-    public IBTreeTupleReference lastTuple;
+    public ITreeIndexTupleReference lastTuple;
 
-    public NodeFrontier(IBTreeTupleReference lastTuple) {
+    public NodeFrontier(ITreeIndexTupleReference lastTuple) {
         this.lastTuple = lastTuple;
     }
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/OrderedSlotManager.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/OrderedSlotManager.java
index 258161b..a106d5c 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/OrderedSlotManager.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/OrderedSlotManager.java
@@ -16,17 +16,17 @@
 package edu.uci.ics.hyracks.storage.am.btree.impls;
 
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
 import edu.uci.ics.hyracks.storage.am.btree.api.ISlotManager;
 
 public class OrderedSlotManager implements ISlotManager {
 
     private static final int slotSize = 4;
-    private IBTreeFrame frame;
+    private ITreeIndexFrame frame;
 
     @Override
-    public int findTupleIndex(ITupleReference searchKey, IBTreeTupleReference frameTuple, MultiComparator multiCmp,
+    public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, MultiComparator multiCmp,
             FindTupleMode mode, FindTupleNoExactMatchPolicy matchPolicy) {
         if (frame.getTupleCount() <= 0)
             return -1;
@@ -121,7 +121,7 @@
     }
 
     @Override
-    public void setFrame(IBTreeFrame frame) {
+    public void setFrame(ITreeIndexFrame frame) {
         this.frame = frame;
     }
 
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangeSearchCursor.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangeSearchCursor.java
index 2ef1905..a912ae6 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangeSearchCursor.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangeSearchCursor.java
@@ -19,7 +19,7 @@
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeCursor;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
 import edu.uci.ics.hyracks.storage.am.btree.api.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
@@ -42,7 +42,7 @@
     private FindTupleNoExactMatchPolicy lowKeyFtp;
     private FindTupleNoExactMatchPolicy highKeyFtp;
 
-    private IBTreeTupleReference frameTuple;
+    private ITreeIndexTupleReference frameTuple;
 
     private RangePredicate pred;
     private MultiComparator lowKeyCmp;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOp.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/TreeIndexOp.java
similarity index 90%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOp.java
rename to hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/TreeIndexOp.java
index d698c8a..f4c58cf 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOp.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/TreeIndexOp.java
@@ -15,6 +15,6 @@
 
 package edu.uci.ics.hyracks.storage.am.btree.impls;
 
-public enum BTreeOp {
-    BTO_INSERT, BTO_DELETE, BTO_UPDATE, BTO_SEARCH
+public enum TreeIndexOp {
+    TI_INSERT, TI_DELETE, TI_UPDATE, TI_SEARCH
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/SimpleTupleReference.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/SimpleTupleReference.java
index eb9fe2e..93497c1 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/SimpleTupleReference.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/SimpleTupleReference.java
@@ -17,10 +17,10 @@
 
 import java.nio.ByteBuffer;
 
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
 
-public class SimpleTupleReference implements IBTreeTupleReference {
+public class SimpleTupleReference implements ITreeIndexTupleReference {
 
     protected ByteBuffer buf;
     protected int fieldStartIndex;
@@ -36,7 +36,7 @@
     }
 
     @Override
-    public void resetByTupleIndex(IBTreeFrame frame, int tupleIndex) {
+    public void resetByTupleIndex(ITreeIndexFrame frame, int tupleIndex) {
         resetByOffset(frame.getBuffer(), frame.getTupleOffset(tupleIndex));
     }
 
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/SimpleTupleWriter.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/SimpleTupleWriter.java
index e2966ee..8a72fa9 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/SimpleTupleWriter.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/SimpleTupleWriter.java
@@ -18,10 +18,10 @@
 import java.nio.ByteBuffer;
 
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriter;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriter;
 
-public class SimpleTupleWriter implements IBTreeTupleWriter {
+public class SimpleTupleWriter implements ITreeIndexTupleWriter {
 
     @Override
     public int bytesRequired(ITupleReference tuple) {
@@ -42,7 +42,7 @@
     }
 
     @Override
-    public IBTreeTupleReference createTupleReference() {
+    public ITreeIndexTupleReference createTupleReference() {
         return new SimpleTupleReference();
     }
 
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/SimpleTupleWriterFactory.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/SimpleTupleWriterFactory.java
index 3b06153..3229dd8 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/SimpleTupleWriterFactory.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/SimpleTupleWriterFactory.java
@@ -15,15 +15,15 @@
 
 package edu.uci.ics.hyracks.storage.am.btree.tuples;
 
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriter;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriterFactory;
 
-public class SimpleTupleWriterFactory implements IBTreeTupleWriterFactory {
+public class SimpleTupleWriterFactory implements ITreeIndexTupleWriterFactory {
 
     private static final long serialVersionUID = 1L;
 
     @Override
-    public IBTreeTupleWriter createTupleWriter() {
+    public ITreeIndexTupleWriter createTupleWriter() {
         return new SimpleTupleWriter();
     }
 
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/TypeAwareTupleReference.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/TypeAwareTupleReference.java
index b82adb8..2ff7a8a 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/TypeAwareTupleReference.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/TypeAwareTupleReference.java
@@ -18,10 +18,10 @@
 import java.nio.ByteBuffer;
 
 import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
 
-public class TypeAwareTupleReference implements IBTreeTupleReference {
+public class TypeAwareTupleReference implements ITreeIndexTupleReference {
     protected ByteBuffer buf;
     protected int fieldStartIndex;
     protected int fieldCount;
@@ -62,7 +62,7 @@
     }
 
     @Override
-    public void resetByTupleIndex(IBTreeFrame frame, int tupleIndex) {
+    public void resetByTupleIndex(ITreeIndexFrame frame, int tupleIndex) {
         resetByOffset(frame.getBuffer(), frame.getTupleOffset(tupleIndex));
     }
 
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/TypeAwareTupleWriter.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/TypeAwareTupleWriter.java
index c975dae..b06ed83 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/TypeAwareTupleWriter.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/TypeAwareTupleWriter.java
@@ -19,10 +19,10 @@
 
 import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriter;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriter;
 
-public class TypeAwareTupleWriter implements IBTreeTupleWriter {
+public class TypeAwareTupleWriter implements ITreeIndexTupleWriter {
 
     private ITypeTrait[] typeTraits;
     private VarLenIntEncoderDecoder encDec = new VarLenIntEncoderDecoder();
@@ -42,7 +42,7 @@
 
     @Override
     public int bytesRequired(ITupleReference tuple, int startField, int numFields) {
-        int bytes = getNullFlagsBytes(tuple, startField, numFields) + getFieldSlotsBytes(tuple, startField, numFields);
+        int bytes = getNullFlagsBytes(numFields) + getFieldSlotsBytes(tuple, startField, numFields);
         for (int i = startField; i < startField + numFields; i++) {
             bytes += tuple.getFieldLength(i);
         }
@@ -50,7 +50,7 @@
     }
 
     @Override
-    public IBTreeTupleReference createTupleReference() {
+    public ITreeIndexTupleReference createTupleReference() {
         return new TypeAwareTupleReference(typeTraits);
     }
 
@@ -86,7 +86,7 @@
     public int writeTupleFields(ITupleReference tuple, int startField, int numFields, ByteBuffer targetBuf,
             int targetOff) {
         int runner = targetOff;
-        int nullFlagsBytes = getNullFlagsBytes(tuple, startField, numFields);
+        int nullFlagsBytes = getNullFlagsBytes(numFields);
         // write null indicator bits
         for (int i = 0; i < nullFlagsBytes; i++) {
             targetBuf.put(runner++, (byte) 0);
@@ -124,7 +124,7 @@
         return fieldSlotBytes;
     }
 
-    private int getNullFlagsBytes(ITupleReference tuple, int startField, int numFields) {
+    private int getNullFlagsBytes(int numFields) {
         return (int) Math.ceil((double) numFields / 8.0);
     }
 
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/TypeAwareTupleWriterFactory.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/TypeAwareTupleWriterFactory.java
index bfaa120..8ece6a2 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/TypeAwareTupleWriterFactory.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/tuples/TypeAwareTupleWriterFactory.java
@@ -16,10 +16,10 @@
 package edu.uci.ics.hyracks.storage.am.btree.tuples;
 
 import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriter;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriterFactory;
 
-public class TypeAwareTupleWriterFactory implements IBTreeTupleWriterFactory {
+public class TypeAwareTupleWriterFactory implements ITreeIndexTupleWriterFactory {
 
     private static final long serialVersionUID = 1L;
     private ITypeTrait[] typeTraits;
@@ -29,7 +29,7 @@
     }
 
     @Override
-    public IBTreeTupleWriter createTupleWriter() {
+    public ITreeIndexTupleWriter createTupleWriter() {
         return new TypeAwareTupleWriter(typeTraits);
     }
 
diff --git a/hyracks-storage-am-common/pom.xml b/hyracks-storage-am-common/pom.xml
index 5271eae..eb897d5 100644
--- a/hyracks-storage-am-common/pom.xml
+++ b/hyracks-storage-am-common/pom.xml
@@ -38,5 +38,12 @@
   		<type>jar</type>
   		<scope>compile</scope>
   	</dependency>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-dataflow-common</artifactId>
+  		<version>0.1.4</version>
+  		<type>jar</type>
+  		<scope>compile</scope>
+  	</dependency>
   </dependencies>
 </project>
diff --git a/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/SimpleConjunctiveSearcher.java b/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/SimpleConjunctiveSearcher.java
index 6ad5a9c..eb0487f 100644
--- a/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/SimpleConjunctiveSearcher.java
+++ b/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/SimpleConjunctiveSearcher.java
@@ -36,7 +36,7 @@
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOp;
+import edu.uci.ics.hyracks.storage.am.btree.impls.TreeIndexOp;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
@@ -152,7 +152,7 @@
 
         maxResultBufIdx = 0;
 
-        BTreeOpContext opCtx = btree.createOpContext(BTreeOp.BTO_SEARCH, leafFrame, interiorFrame, null);
+        BTreeOpContext opCtx = btree.createOpContext(TreeIndexOp.TI_SEARCH, leafFrame, interiorFrame, null);
 
         resultTupleAppender.reset(newResultBuffers.get(0), true);
         try {
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java
index e856296..06463fc 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java
@@ -39,7 +39,7 @@
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.dataflow.common.data.comparators.IntegerBinaryComparatorFactory;
 import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriter;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITreeIndexTupleWriter;
 import edu.uci.ics.hyracks.storage.am.btree.api.IPrefixSlotManager;
 import edu.uci.ics.hyracks.storage.am.btree.frames.FieldPrefixNSMLeafFrame;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeException;
@@ -154,7 +154,7 @@
 		try {
 
 			IPrefixSlotManager slotManager = new FieldPrefixSlotManager();
-			IBTreeTupleWriter tupleWriter = new TypeAwareTupleWriter(typeTraits);
+			ITreeIndexTupleWriter tupleWriter = new TypeAwareTupleWriter(typeTraits);
 			FieldPrefixNSMLeafFrame frame = new FieldPrefixNSMLeafFrame(
 					tupleWriter);
 			frame.setPage(page);
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
index e12b5b7..98aefb6 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
@@ -48,7 +48,7 @@
 import edu.uci.ics.hyracks.storage.am.btree.frames.NSMLeafFrameFactory;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeException;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOp;
+import edu.uci.ics.hyracks.storage.am.btree.impls.TreeIndexOp;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.btree.impls.DiskOrderScanCursor;
 import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
@@ -162,7 +162,7 @@
 		accessor.reset(frame);
 		FrameTupleReference tuple = new FrameTupleReference();
 
-		BTreeOpContext insertOpCtx = btree.createOpContext(BTreeOp.BTO_INSERT,
+		BTreeOpContext insertOpCtx = btree.createOpContext(TreeIndexOp.TI_INSERT,
 				leafFrame, interiorFrame, metaFrame);
 
 		// 10000
@@ -221,7 +221,7 @@
 		IBTreeCursor scanCursor = new RangeSearchCursor(leafFrame);
 		RangePredicate nullPred = new RangePredicate(true, null, null, true,
 				true, null, null);
-		BTreeOpContext searchOpCtx = btree.createOpContext(BTreeOp.BTO_SEARCH,
+		BTreeOpContext searchOpCtx = btree.createOpContext(TreeIndexOp.TI_SEARCH,
 				leafFrame, interiorFrame, null);
 		btree.search(scanCursor, nullPred, searchOpCtx);
 		try {
@@ -401,7 +401,7 @@
 		accessor.reset(frame);
 		FrameTupleReference tuple = new FrameTupleReference();
 
-		BTreeOpContext insertOpCtx = btree.createOpContext(BTreeOp.BTO_INSERT,
+		BTreeOpContext insertOpCtx = btree.createOpContext(TreeIndexOp.TI_INSERT,
 				leafFrame, interiorFrame, metaFrame);
 
 		for (int i = 0; i < 10000; i++) {
@@ -443,7 +443,7 @@
 		IBTreeCursor scanCursor = new RangeSearchCursor(leafFrame);
 		RangePredicate nullPred = new RangePredicate(true, null, null, true,
 				true, null, null);
-		BTreeOpContext searchOpCtx = btree.createOpContext(BTreeOp.BTO_SEARCH,
+		BTreeOpContext searchOpCtx = btree.createOpContext(TreeIndexOp.TI_SEARCH,
 				leafFrame, interiorFrame, null);
 		btree.search(scanCursor, nullPred, searchOpCtx);
 
@@ -603,7 +603,7 @@
 		accessor.reset(frame);
 		FrameTupleReference tuple = new FrameTupleReference();
 
-		BTreeOpContext insertOpCtx = btree.createOpContext(BTreeOp.BTO_INSERT,
+		BTreeOpContext insertOpCtx = btree.createOpContext(TreeIndexOp.TI_INSERT,
 				leafFrame, interiorFrame, metaFrame);
 		int maxLength = 10; // max string length to be generated
 		for (int i = 0; i < 10000; i++) {
@@ -646,7 +646,7 @@
 		IBTreeCursor scanCursor = new RangeSearchCursor(leafFrame);
 		RangePredicate nullPred = new RangePredicate(true, null, null, true,
 				true, null, null);
-		BTreeOpContext searchOpCtx = btree.createOpContext(BTreeOp.BTO_SEARCH,
+		BTreeOpContext searchOpCtx = btree.createOpContext(TreeIndexOp.TI_SEARCH,
 				leafFrame, interiorFrame, null);
 		btree.search(scanCursor, nullPred, searchOpCtx);
 
@@ -803,9 +803,9 @@
 		accessor.reset(frame);
 		FrameTupleReference tuple = new FrameTupleReference();
 
-		BTreeOpContext insertOpCtx = btree.createOpContext(BTreeOp.BTO_INSERT,
+		BTreeOpContext insertOpCtx = btree.createOpContext(TreeIndexOp.TI_INSERT,
 				leafFrame, interiorFrame, metaFrame);
-		BTreeOpContext deleteOpCtx = btree.createOpContext(BTreeOp.BTO_DELETE,
+		BTreeOpContext deleteOpCtx = btree.createOpContext(TreeIndexOp.TI_DELETE,
 				leafFrame, interiorFrame, metaFrame);
 
 		int runs = 3;
@@ -1070,7 +1070,7 @@
 		// TODO: check when searching backwards
 		RangePredicate rangePred = new RangePredicate(true, lowKey, highKey,
 				true, true, searchCmp, searchCmp);
-		BTreeOpContext searchOpCtx = btree.createOpContext(BTreeOp.BTO_SEARCH,
+		BTreeOpContext searchOpCtx = btree.createOpContext(TreeIndexOp.TI_SEARCH,
 				leafFrame, interiorFrame, null);
 		btree.search(rangeCursor, rangePred, searchOpCtx);
 
@@ -1202,7 +1202,7 @@
 		intervals[9][0] = 20;
 		intervals[9][1] = 35;
 
-		BTreeOpContext insertOpCtx = btree.createOpContext(BTreeOp.BTO_INSERT,
+		BTreeOpContext insertOpCtx = btree.createOpContext(TreeIndexOp.TI_INSERT,
 				leafFrame, interiorFrame, metaFrame);
 
 		// int exceptionCount = 0;
@@ -1247,7 +1247,7 @@
 		IBTreeCursor scanCursor = new RangeSearchCursor(leafFrame);
 		RangePredicate nullPred = new RangePredicate(true, null, null, true,
 				true, null, null);
-		BTreeOpContext searchOpCtx = btree.createOpContext(BTreeOp.BTO_SEARCH,
+		BTreeOpContext searchOpCtx = btree.createOpContext(TreeIndexOp.TI_SEARCH,
 				leafFrame, interiorFrame, null);
 		btree.search(scanCursor, nullPred, searchOpCtx);
 
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java
index d9736ce..3cc5235 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java
@@ -55,7 +55,7 @@
 import edu.uci.ics.hyracks.storage.am.btree.frames.NSMLeafFrameFactory;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeException;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOp;
+import edu.uci.ics.hyracks.storage.am.btree.impls.TreeIndexOp;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
@@ -158,7 +158,7 @@
 		ArrayTupleBuilder tb = new ArrayTupleBuilder(cmp.getFieldCount());
 		DataOutput dos = tb.getDataOutput();
 
-		BTreeOpContext insertOpCtx = btree.createOpContext(BTreeOp.BTO_INSERT,
+		BTreeOpContext insertOpCtx = btree.createOpContext(TreeIndexOp.TI_INSERT,
 				leafFrame, interiorFrame, metaFrame);
 
 		// generate keys
@@ -265,7 +265,7 @@
 		ArrayTupleBuilder tb = new ArrayTupleBuilder(cmp.getFieldCount());
 		DataOutput dos = tb.getDataOutput();
 
-		BTreeOpContext insertOpCtx = btree.createOpContext(BTreeOp.BTO_INSERT,
+		BTreeOpContext insertOpCtx = btree.createOpContext(TreeIndexOp.TI_INSERT,
 				leafFrame, interiorFrame, metaFrame);
 
 		// generate keys
@@ -374,7 +374,7 @@
 		ArrayTupleBuilder tb = new ArrayTupleBuilder(cmp.getFieldCount());
 		DataOutput dos = tb.getDataOutput();
 
-		BTreeOpContext insertOpCtx = btree.createOpContext(BTreeOp.BTO_INSERT,
+		BTreeOpContext insertOpCtx = btree.createOpContext(TreeIndexOp.TI_INSERT,
 				leafFrame, interiorFrame, metaFrame);
 
 		// generate keys
@@ -556,7 +556,7 @@
 						btree.getMultiComparator(), btree.getMultiComparator()
 								.getTypeTraits());
 				BTreeOpContext searchOpCtx = btree.createOpContext(
-						BTreeOp.BTO_SEARCH, leafFrame, interiorFrame, null);
+						TreeIndexOp.TI_SEARCH, leafFrame, interiorFrame, null);
 				btree.search(rangeCursor, rangePred, searchOpCtx);
 
 				try {
diff --git a/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/searchers/SimpleConjunctiveSearcherTest.java b/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/searchers/SimpleConjunctiveSearcherTest.java
index f70092c..9185735 100644
--- a/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/searchers/SimpleConjunctiveSearcherTest.java
+++ b/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/searchers/SimpleConjunctiveSearcherTest.java
@@ -50,7 +50,7 @@
 import edu.uci.ics.hyracks.storage.am.btree.frames.NSMInteriorFrameFactory;
 import edu.uci.ics.hyracks.storage.am.btree.frames.NSMLeafFrameFactory;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOp;
+import edu.uci.ics.hyracks.storage.am.btree.impls.TreeIndexOp;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.btree.tuples.TypeAwareTupleWriterFactory;
@@ -165,7 +165,7 @@
         int addProb = 0;
         int addProbStep = 2;
 
-        BTreeOpContext opCtx = btree.createOpContext(BTreeOp.BTO_INSERT, leafFrame, interiorFrame, metaFrame);
+        BTreeOpContext opCtx = btree.createOpContext(TreeIndexOp.TI_INSERT, leafFrame, interiorFrame, metaFrame);
 
         for (int i = 0; i < tokens.size(); i++) {