diff --git a/hyracks/hyracks-storage-am-common/.classpath b/hyracks/hyracks-storage-am-common/.classpath
new file mode 100644
index 0000000..1f3c1ff
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/.classpath
@@ -0,0 +1,7 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<classpath>
+	<classpathentry kind="src" output="target/classes" path="src/main/java"/>
+	<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.6"/>
+	<classpathentry kind="con" path="org.maven.ide.eclipse.MAVEN2_CLASSPATH_CONTAINER"/>
+	<classpathentry kind="output" path="target/classes"/>
+</classpath>
diff --git a/hyracks/hyracks-storage-am-common/.project b/hyracks/hyracks-storage-am-common/.project
new file mode 100644
index 0000000..ec47f6b
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/.project
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+	<name>hyracks-storage-am-common</name>
+	<comment></comment>
+	<projects>
+	</projects>
+	<buildSpec>
+		<buildCommand>
+			<name>org.eclipse.jdt.core.javabuilder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+		<buildCommand>
+			<name>org.maven.ide.eclipse.maven2Builder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+	</buildSpec>
+	<natures>
+		<nature>org.eclipse.jdt.core.javanature</nature>
+		<nature>org.maven.ide.eclipse.maven2Nature</nature>
+	</natures>
+</projectDescription>
diff --git a/hyracks/hyracks-storage-am-common/.settings/org.eclipse.jdt.core.prefs b/hyracks/hyracks-storage-am-common/.settings/org.eclipse.jdt.core.prefs
new file mode 100644
index 0000000..b37b3bb
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/.settings/org.eclipse.jdt.core.prefs
@@ -0,0 +1,6 @@
+#Thu Jul 07 12:23:56 PDT 2011
+eclipse.preferences.version=1
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
+org.eclipse.jdt.core.compiler.compliance=1.6
+org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning
+org.eclipse.jdt.core.compiler.source=1.6
diff --git a/hyracks/hyracks-storage-am-common/.settings/org.maven.ide.eclipse.prefs b/hyracks/hyracks-storage-am-common/.settings/org.maven.ide.eclipse.prefs
new file mode 100644
index 0000000..7b5e618
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/.settings/org.maven.ide.eclipse.prefs
@@ -0,0 +1,8 @@
+#Thu Jul 07 12:23:53 PDT 2011
+activeProfiles=
+eclipse.preferences.version=1
+fullBuildGoals=process-test-resources
+resolveWorkspaceProjects=true
+resourceFilterGoals=process-resources resources\:testResources
+skipCompilerPlugin=true
+version=1
diff --git a/hyracks/hyracks-storage-am-common/pom.xml b/hyracks/hyracks-storage-am-common/pom.xml
new file mode 100644
index 0000000..0d20126
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/pom.xml
@@ -0,0 +1,56 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+  <modelVersion>4.0.0</modelVersion>
+  <groupId>edu.uci.ics.hyracks</groupId>
+  <artifactId>hyracks-storage-am-common</artifactId>
+  <version>0.1.7-SNAPSHOT</version>
+
+  <parent>
+    <groupId>edu.uci.ics.hyracks</groupId>
+    <artifactId>hyracks</artifactId>
+    <version>0.1.7-SNAPSHOT</version>
+  </parent>
+
+  <build>
+    <plugins>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-compiler-plugin</artifactId>
+        <version>2.0.2</version>
+        <configuration>
+          <source>1.6</source>
+          <target>1.6</target>
+        </configuration>
+      </plugin>
+    </plugins>
+  </build>
+  <dependencies>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-api</artifactId>
+  		<version>0.1.7-SNAPSHOT</version>
+  		<type>jar</type>
+  		<scope>compile</scope>
+  	</dependency>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-storage-common</artifactId>
+  		<version>0.1.7-SNAPSHOT</version>
+  		<type>jar</type>
+  		<scope>compile</scope>
+  	</dependency>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-dataflow-common</artifactId>
+  		<version>0.1.7-SNAPSHOT</version>
+  		<type>jar</type>
+  		<scope>compile</scope>
+  	</dependency>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-dataflow-std</artifactId>
+  		<version>0.1.7-SNAPSHOT</version>
+  		<type>jar</type>
+  		<scope>compile</scope>
+  	</dependency>  
+  </dependencies>
+</project>
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ICursorInitialState.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ICursorInitialState.java
new file mode 100644
index 0000000..5f7c88d
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ICursorInitialState.java
@@ -0,0 +1,24 @@
+/*
+ * 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.api;
+
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public interface ICursorInitialState {
+    public ICachedPage getPage();
+
+    public void setPage(ICachedPage page);
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IFreePageManager.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IFreePageManager.java
new file mode 100644
index 0000000..7abc0e3
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IFreePageManager.java
@@ -0,0 +1,25 @@
+package edu.uci.ics.hyracks.storage.am.common.api;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+
+public interface IFreePageManager {
+    public int getFreePage(ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException;
+
+    public void addFreePage(ITreeIndexMetaDataFrame metaFrame, int freePage) throws HyracksDataException;
+
+    public int getMaxPage(ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException;
+
+    public void init(ITreeIndexMetaDataFrame metaFrame, int currentMaxPage) throws HyracksDataException;
+
+    public ITreeIndexMetaDataFrameFactory getMetaDataFrameFactory();
+
+    // required to return negative values
+    public byte getMetaPageLevelIndicator();
+
+    public byte getFreePageLevelIndicator();
+
+    // determined by examining level indicator
+    public boolean isMetaPage(ITreeIndexMetaDataFrame metaFrame);
+
+    public boolean isFreePage(ITreeIndexMetaDataFrame metaFrame);
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IIndexBulkLoadContext.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IIndexBulkLoadContext.java
new file mode 100644
index 0000000..a896d80
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IIndexBulkLoadContext.java
@@ -0,0 +1,4 @@
+package edu.uci.ics.hyracks.storage.am.common.api;
+
+public interface IIndexBulkLoadContext {
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchPredicate.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchPredicate.java
new file mode 100644
index 0000000..f4836e0
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchPredicate.java
@@ -0,0 +1,26 @@
+/*
+ * 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.api;
+
+import java.io.Serializable;
+
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+
+public interface ISearchPredicate extends Serializable {
+    public MultiComparator getLowKeyComparator();
+
+    public MultiComparator getHighKeyComparator();
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISlotManager.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISlotManager.java
new file mode 100644
index 0000000..29646e7
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISlotManager.java
@@ -0,0 +1,42 @@
+/*
+ * 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.api;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleMode;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleNoExactMatchPolicy;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+
+public interface ISlotManager {
+    public void setFrame(ITreeIndexFrame frame);
+
+    public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, MultiComparator multiCmp,
+            FindTupleMode mode, FindTupleNoExactMatchPolicy matchPolicy);
+
+    public int insertSlot(int tupleIndex, int tupleOff);
+
+    public int getSlotStartOff();
+
+    public int getSlotEndOff();
+
+    public int getTupleOff(int slotOff);
+
+    public void setSlot(int slotOff, int value);
+
+    public int getSlotOff(int tupleIndex);
+
+    public int getSlotSize();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISplitKey.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISplitKey.java
new file mode 100644
index 0000000..246c09d
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISplitKey.java
@@ -0,0 +1,25 @@
+package edu.uci.ics.hyracks.storage.am.common.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/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndex.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndex.java
new file mode 100644
index 0000000..2d77f06
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndex.java
@@ -0,0 +1,52 @@
+package edu.uci.ics.hyracks.storage.am.common.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.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
+
+public interface ITreeIndex {
+    // init:
+
+    public void create(int indexFileId, ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame) throws Exception;
+
+    public void open(int indexFileId);
+
+    // operations:
+
+    public void insert(ITupleReference tuple, IndexOpContext ictx) throws Exception;
+
+    public void update(ITupleReference tuple, IndexOpContext ictx) throws Exception;
+
+    public void delete(ITupleReference tuple, IndexOpContext ictx) throws Exception;
+
+    public IndexOpContext createOpContext(IndexOp op, ITreeIndexFrame leafFrame, ITreeIndexFrame interiorFrame,
+            ITreeIndexMetaDataFrame metaFrame);
+
+    // bulk loading:
+
+    public IIndexBulkLoadContext beginBulkLoad(float fillFactor, ITreeIndexFrame leafFrame,
+            ITreeIndexFrame interiorFrame, ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException;
+
+    public void bulkLoadAddTuple(IIndexBulkLoadContext ictx, ITupleReference tuple) throws HyracksDataException;
+
+    public void endBulkLoad(IIndexBulkLoadContext ictx) throws HyracksDataException;
+
+    // search:
+    public void diskOrderScan(ITreeIndexCursor icursor, ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame,
+            IndexOpContext ictx) throws HyracksDataException;
+
+    // utility:
+
+    public IFreePageManager getFreePageManager();
+
+    public int getRootPageId();
+
+    public ITreeIndexFrameFactory getLeafFrameFactory();
+
+    public ITreeIndexFrameFactory getInteriorFrameFactory();
+
+    public int getFieldCount();
+
+    public IndexType getIndexType();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexCursor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexCursor.java
new file mode 100644
index 0000000..22b2b6f
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexCursor.java
@@ -0,0 +1,40 @@
+/*
+ * 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.api;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public interface ITreeIndexCursor {
+    public void reset();
+
+    public boolean hasNext() throws Exception;
+
+    public void next() throws Exception;
+
+    public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws Exception;
+
+    public ICachedPage getPage();
+
+    public void close() throws Exception;
+
+    public void setBufferCache(IBufferCache bufferCache);
+
+    public void setFileId(int fileId);
+
+    public ITupleReference getTuple();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java
new file mode 100644
index 0000000..246efe4
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java
@@ -0,0 +1,104 @@
+/*
+ * 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.api;
+
+import java.nio.ByteBuffer;
+
+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.common.frames.FrameOpSpaceStatus;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public interface ITreeIndexFrame {
+    public void setPage(ICachedPage page);
+
+    public ICachedPage getPage();
+
+    public ByteBuffer getBuffer();
+
+    public int findTupleIndex(ITupleReference tuple, MultiComparator cmp) throws Exception;
+
+    public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception;
+
+    public void update(int rid, ITupleReference tuple) throws Exception;
+
+    public void delete(ITupleReference tuple, MultiComparator cmp, boolean exactDelete) throws Exception;
+
+    // returns true if slots were modified, false otherwise
+    public boolean compact(MultiComparator cmp);
+
+    public boolean compress(MultiComparator cmp) throws HyracksDataException;
+
+    public void initBuffer(byte level);
+
+    public int getTupleCount();
+
+    // assumption: page must be write-latched at this point
+    public FrameOpSpaceStatus hasSpaceInsert(ITupleReference tuple, MultiComparator cmp);
+
+    public FrameOpSpaceStatus hasSpaceUpdate(int rid, ITupleReference tuple, MultiComparator cmp);
+
+    public int getTupleOffset(int slotNum);
+
+    public int getTotalFreeSpace();
+
+    public void setPageLsn(int pageLsn);
+
+    public int getPageLsn();
+
+    // for debugging
+    public void printHeader();
+
+    public String printKeys(MultiComparator cmp, ISerializerDeserializer[] fields) throws HyracksDataException;
+
+    // TODO; what if tuples more than half-page size?
+    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey)
+            throws Exception;
+
+    public ISlotManager getSlotManager();
+
+    // ATTENTION: in b-tree operations it may not always be possible to
+    // determine whether an ICachedPage is a leaf or interior node
+    // a compatible interior and leaf implementation MUST return identical
+    // values when given the same ByteBuffer for the functions below
+    public boolean isLeaf();
+
+    public boolean isInterior();
+
+    public byte getLevel();
+
+    public void setLevel(byte level);
+
+    public boolean getSmFlag(); // structure modification flag
+
+    public void setSmFlag(boolean smFlag);
+
+    public int getSlotSize();
+
+    // TODO: should be removed after new tuple format
+    public void setPageTupleFieldCount(int fieldCount);
+
+    // for debugging
+    public int getFreeSpaceOff();
+
+    public void setFreeSpaceOff(int freeSpace);
+
+    public ITreeIndexTupleWriter getTupleWriter();
+
+    public int getPageHeaderSize();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrameFactory.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrameFactory.java
new file mode 100644
index 0000000..83b95b6
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrameFactory.java
@@ -0,0 +1,7 @@
+package edu.uci.ics.hyracks.storage.am.common.api;
+
+import java.io.Serializable;
+
+public interface ITreeIndexFrameFactory extends Serializable {
+    public ITreeIndexFrame createFrame();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrame.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrame.java
new file mode 100644
index 0000000..bbd03d6
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrame.java
@@ -0,0 +1,44 @@
+/*
+ * 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.api;
+
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public interface ITreeIndexMetaDataFrame {
+    public void initBuffer(int level);
+
+    public void setPage(ICachedPage page);
+
+    public ICachedPage getPage();
+
+    public byte getLevel();
+
+    public void setLevel(byte level);
+
+    public int getNextPage();
+
+    public void setNextPage(int nextPage);
+
+    public int getMaxPage();
+
+    public void setMaxPage(int maxPage);
+
+    public int getFreePage();
+
+    public boolean hasSpace();
+
+    public void addFreePage(int freePage);
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrameFactory.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrameFactory.java
new file mode 100644
index 0000000..6fd88e8
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrameFactory.java
@@ -0,0 +1,20 @@
+/*
+ * 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.api;
+
+public interface ITreeIndexMetaDataFrameFactory {
+    public ITreeIndexMetaDataFrame createFrame();
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleReference.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleReference.java
new file mode 100644
index 0000000..d2c2df4
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleReference.java
@@ -0,0 +1,30 @@
+/*
+ * 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.api;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+
+public interface ITreeIndexTupleReference extends ITupleReference {
+    public void setFieldCount(int fieldCount);
+
+    public void setFieldCount(int fieldStartIndex, int fieldCount);
+
+    public void resetByTupleOffset(ByteBuffer buf, int tupleStartOffset);
+
+    public void resetByTupleIndex(ITreeIndexFrame frame, int tupleIndex);
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriter.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriter.java
new file mode 100644
index 0000000..39577ea
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriter.java
@@ -0,0 +1,37 @@
+/*
+ * 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.api;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+
+public interface ITreeIndexTupleWriter {
+    public int writeTuple(ITupleReference tuple, ByteBuffer targetBuf, int targetOff);
+
+    public int bytesRequired(ITupleReference tuple);
+
+    public int writeTupleFields(ITupleReference tuple, int startField, int numFields, ByteBuffer targetBuf,
+            int targetOff);
+
+    public int bytesRequired(ITupleReference tuple, int startField, int numFields);
+
+    // return a tuplereference instance that can read the tuple written by this
+    // 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 ITreeIndexTupleReference createTupleReference();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriterFactory.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriterFactory.java
new file mode 100644
index 0000000..bd7bfda
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriterFactory.java
@@ -0,0 +1,22 @@
+/*
+ * 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.api;
+
+import java.io.Serializable;
+
+public interface ITreeIndexTupleWriterFactory extends Serializable {
+    public ITreeIndexTupleWriter createTupleWriter();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IndexType.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IndexType.java
new file mode 100644
index 0000000..d5f9f44
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IndexType.java
@@ -0,0 +1,5 @@
+package edu.uci.ics.hyracks.storage.am.common.api;
+
+public enum IndexType {
+    BTREE, RTREE, INVERTED
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/TreeIndexException.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/TreeIndexException.java
new file mode 100644
index 0000000..ad3db58
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/TreeIndexException.java
@@ -0,0 +1,38 @@
+/*
+ * 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.api;
+
+public class TreeIndexException extends Exception {
+
+    private static final long serialVersionUID = 1L;
+    private boolean handled = false;
+
+    public TreeIndexException(Exception e) {
+        super(e);
+    }
+
+    public TreeIndexException(String message) {
+        super(message);
+    }
+
+    public void setHandled(boolean handled) {
+        this.handled = handled;
+    }
+
+    public boolean getHandled() {
+        return handled;
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/AbstractTreeIndexOperatorDescriptor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/AbstractTreeIndexOperatorDescriptor.java
new file mode 100644
index 0000000..c905eb2
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/AbstractTreeIndexOperatorDescriptor.java
@@ -0,0 +1,110 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.base.AbstractSingleActivityOperatorDescriptor;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public abstract class AbstractTreeIndexOperatorDescriptor extends AbstractSingleActivityOperatorDescriptor implements
+        ITreeIndexOperatorDescriptorHelper {
+
+    private static final long serialVersionUID = 1L;
+
+    protected final IFileSplitProvider fileSplitProvider;
+
+    protected final IBinaryComparatorFactory[] comparatorFactories;
+
+    protected final ITreeIndexFrameFactory interiorFrameFactory;
+    protected final ITreeIndexFrameFactory leafFrameFactory;
+
+    protected final IStorageManagerInterface storageManager;
+    protected final IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider;
+
+    protected final ITypeTrait[] typeTraits;
+
+    protected final ITreeIndexOpHelperFactory opHelperFactory;
+
+    public AbstractTreeIndexOperatorDescriptor(JobSpecification spec, int inputArity, int outputArity,
+            RecordDescriptor recDesc, IStorageManagerInterface storageManager,
+            IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider, IFileSplitProvider fileSplitProvider,
+            ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory,
+            ITypeTrait[] typeTraits, IBinaryComparatorFactory[] comparatorFactories,
+            ITreeIndexOpHelperFactory opHelperFactory) {
+        super(spec, inputArity, outputArity);
+        this.fileSplitProvider = fileSplitProvider;
+        this.storageManager = storageManager;
+        this.treeIndexRegistryProvider = treeIndexRegistryProvider;
+        this.interiorFrameFactory = interiorFrameFactory;
+        this.leafFrameFactory = leafFrameFactory;
+        this.typeTraits = typeTraits;
+        this.comparatorFactories = comparatorFactories;
+        this.opHelperFactory = opHelperFactory;
+        if (outputArity > 0)
+            recordDescriptors[0] = recDesc;
+    }
+
+    @Override
+    public IFileSplitProvider getTreeIndexFileSplitProvider() {
+        return fileSplitProvider;
+    }
+
+    @Override
+    public IBinaryComparatorFactory[] getTreeIndexComparatorFactories() {
+        return comparatorFactories;
+    }
+
+    @Override
+    public ITypeTrait[] getTreeIndexTypeTraits() {
+        return typeTraits;
+    }
+
+    @Override
+    public ITreeIndexFrameFactory getTreeIndexInteriorFactory() {
+        return interiorFrameFactory;
+    }
+
+    @Override
+    public ITreeIndexFrameFactory getTreeIndexLeafFactory() {
+        return leafFrameFactory;
+    }
+
+    @Override
+    public IStorageManagerInterface getStorageManager() {
+        return storageManager;
+    }
+
+    @Override
+    public IIndexRegistryProvider<ITreeIndex> getTreeIndexRegistryProvider() {
+        return treeIndexRegistryProvider;
+    }
+
+    @Override
+    public RecordDescriptor getRecordDescriptor() {
+        return recordDescriptors[0];
+    }
+
+    @Override
+    public ITreeIndexOpHelperFactory getTreeIndexOpHelperFactory() {
+        return opHelperFactory;
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IIndexRegistryProvider.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IIndexRegistryProvider.java
new file mode 100644
index 0000000..aadcaf9
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IIndexRegistryProvider.java
@@ -0,0 +1,24 @@
+/*
+ * 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.dataflow;
+
+import java.io.Serializable;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+
+public interface IIndexRegistryProvider<IndexType> extends Serializable {
+    public IndexRegistry<IndexType> getRegistry(IHyracksStageletContext ctx);
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/ITreeIndexOpHelperFactory.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/ITreeIndexOpHelperFactory.java
new file mode 100644
index 0000000..fa37fab
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/ITreeIndexOpHelperFactory.java
@@ -0,0 +1,10 @@
+package edu.uci.ics.hyracks.storage.am.common.dataflow;
+
+import java.io.Serializable;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+
+public interface ITreeIndexOpHelperFactory extends Serializable {
+    public TreeIndexOpHelper createTreeIndexOpHelper(ITreeIndexOperatorDescriptorHelper opDesc,
+            final IHyracksStageletContext ctx, int partition, IndexHelperOpenMode mode);
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/ITreeIndexOperatorDescriptorHelper.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/ITreeIndexOperatorDescriptorHelper.java
new file mode 100644
index 0000000..6ca4529
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/ITreeIndexOperatorDescriptorHelper.java
@@ -0,0 +1,30 @@
+package edu.uci.ics.hyracks.storage.am.common.dataflow;
+
+import edu.uci.ics.hyracks.api.dataflow.IActivityNode;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public interface ITreeIndexOperatorDescriptorHelper extends IActivityNode {
+    public IFileSplitProvider getTreeIndexFileSplitProvider();
+
+    public IBinaryComparatorFactory[] getTreeIndexComparatorFactories();
+
+    public ITypeTrait[] getTreeIndexTypeTraits();
+
+    public ITreeIndexFrameFactory getTreeIndexInteriorFactory();
+
+    public ITreeIndexFrameFactory getTreeIndexLeafFactory();
+
+    public IStorageManagerInterface getStorageManager();
+
+    public IIndexRegistryProvider<ITreeIndex> getTreeIndexRegistryProvider();
+
+    public RecordDescriptor getRecordDescriptor();
+
+    public ITreeIndexOpHelperFactory getTreeIndexOpHelperFactory();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexHelperOpenMode.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexHelperOpenMode.java
new file mode 100644
index 0000000..aa41184
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexHelperOpenMode.java
@@ -0,0 +1,5 @@
+package edu.uci.ics.hyracks.storage.am.common.dataflow;
+
+public enum IndexHelperOpenMode {
+    OPEN, CREATE, ENLIST
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexRegistry.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexRegistry.java
new file mode 100644
index 0000000..de00d5a
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexRegistry.java
@@ -0,0 +1,53 @@
+/*
+ * 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.dataflow;
+
+import java.util.HashMap;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+public class IndexRegistry<IndexType> {
+
+    private HashMap<Integer, IndexType> map = new HashMap<Integer, IndexType>();
+    private Lock registryLock = new ReentrantLock();
+
+    public IndexType get(int fileId) {
+        return map.get(fileId);
+    }
+
+    public void lock() {
+        registryLock.lock();
+    }
+
+    public void unlock() {
+        registryLock.unlock();
+    }
+
+    public void register(int fileId, IndexType index) {
+        map.put(fileId, index);
+    }
+
+    public void unregister(int fileId) {
+        try {
+            map.remove(fileId);
+        } catch (Exception e) {
+        }
+    }
+
+    public int size() {
+        return map.size();
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/PermutingFrameTupleReference.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/PermutingFrameTupleReference.java
new file mode 100644
index 0000000..3db9db2
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/PermutingFrameTupleReference.java
@@ -0,0 +1,65 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.IFrameTupleReference;
+
+public class PermutingFrameTupleReference implements IFrameTupleReference {
+    private IFrameTupleAccessor fta;
+    private int tIndex;
+    private int[] fieldPermutation;
+
+    public void setFieldPermutation(int[] fieldPermutation) {
+        this.fieldPermutation = fieldPermutation;
+    }
+
+    public void reset(IFrameTupleAccessor fta, int tIndex) {
+        this.fta = fta;
+        this.tIndex = tIndex;
+    }
+
+    @Override
+    public IFrameTupleAccessor getFrameTupleAccessor() {
+        return fta;
+    }
+
+    @Override
+    public int getTupleIndex() {
+        return tIndex;
+    }
+
+    @Override
+    public int getFieldCount() {
+        return fieldPermutation.length;
+    }
+
+    @Override
+    public byte[] getFieldData(int fIdx) {
+        return fta.getBuffer().array();
+    }
+
+    @Override
+    public int getFieldStart(int fIdx) {
+        return fta.getTupleStartOffset(tIndex) + fta.getFieldSlotsLength()
+                + fta.getFieldStartOffset(tIndex, fieldPermutation[fIdx]);
+    }
+
+    @Override
+    public int getFieldLength(int fIdx) {
+        return fta.getFieldLength(tIndex, fieldPermutation[fIdx]);
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexBulkLoadOperatorDescriptor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexBulkLoadOperatorDescriptor.java
new file mode 100644
index 0000000..7d585b3
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexBulkLoadOperatorDescriptor.java
@@ -0,0 +1,54 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.IOperatorNodePushable;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.job.IOperatorEnvironment;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public class TreeIndexBulkLoadOperatorDescriptor extends AbstractTreeIndexOperatorDescriptor {
+
+    private static final long serialVersionUID = 1L;
+
+    private final int[] fieldPermutation;
+    private final float fillFactor;
+
+    public TreeIndexBulkLoadOperatorDescriptor(JobSpecification spec, IStorageManagerInterface storageManager,
+            IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider, IFileSplitProvider fileSplitProvider,
+            ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory,
+            ITypeTrait[] typeTraits, IBinaryComparatorFactory[] comparatorFactories, int[] fieldPermutation,
+            float fillFactor, ITreeIndexOpHelperFactory opHelperFactory) {
+        super(spec, 1, 0, null, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
+                leafFrameFactory, typeTraits, comparatorFactories, opHelperFactory);
+        this.fieldPermutation = fieldPermutation;
+        this.fillFactor = fillFactor;
+    }
+
+    @Override
+    public IOperatorNodePushable createPushRuntime(IHyracksStageletContext ctx, IOperatorEnvironment env,
+            IRecordDescriptorProvider recordDescProvider, int partition, int nPartitions) {
+        return new TreeIndexBulkLoadOperatorNodePushable(this, ctx, partition, fieldPermutation, fillFactor,
+                recordDescProvider);
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexBulkLoadOperatorNodePushable.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexBulkLoadOperatorNodePushable.java
new file mode 100644
index 0000000..2001039
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexBulkLoadOperatorNodePushable.java
@@ -0,0 +1,90 @@
+/*
+ * 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.dataflow;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
+import edu.uci.ics.hyracks.dataflow.std.base.AbstractUnaryInputSinkOperatorNodePushable;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrame;
+
+public class TreeIndexBulkLoadOperatorNodePushable extends AbstractUnaryInputSinkOperatorNodePushable {
+    private float fillFactor;
+    private final TreeIndexOpHelper treeIndexOpHelper;
+    private FrameTupleAccessor accessor;
+    private IIndexBulkLoadContext bulkLoadCtx;
+
+    private IRecordDescriptorProvider recordDescProvider;
+
+    private PermutingFrameTupleReference tuple = new PermutingFrameTupleReference();
+
+    public TreeIndexBulkLoadOperatorNodePushable(AbstractTreeIndexOperatorDescriptor opDesc,
+            IHyracksStageletContext ctx, int partition, int[] fieldPermutation, float fillFactor,
+            IRecordDescriptorProvider recordDescProvider) {
+        treeIndexOpHelper = opDesc.getTreeIndexOpHelperFactory().createTreeIndexOpHelper(opDesc, ctx, partition,
+                IndexHelperOpenMode.CREATE);
+        this.fillFactor = fillFactor;
+        this.recordDescProvider = recordDescProvider;
+        tuple.setFieldPermutation(fieldPermutation);
+    }
+
+    @Override
+    public void open() throws HyracksDataException {
+        AbstractTreeIndexOperatorDescriptor opDesc = (AbstractTreeIndexOperatorDescriptor) treeIndexOpHelper
+                .getOperatorDescriptor();
+        RecordDescriptor recDesc = recordDescProvider.getInputRecordDescriptor(opDesc.getOperatorId(), 0);
+        accessor = new FrameTupleAccessor(treeIndexOpHelper.getHyracksStageletContext().getFrameSize(), recDesc);
+        ITreeIndexMetaDataFrame metaFrame = new LIFOMetaDataFrame();
+        try {
+            treeIndexOpHelper.init();
+            treeIndexOpHelper.getTreeIndex().open(treeIndexOpHelper.getIndexFileId());
+            bulkLoadCtx = treeIndexOpHelper.getTreeIndex().beginBulkLoad(fillFactor, treeIndexOpHelper.getLeafFrame(),
+                    treeIndexOpHelper.getInteriorFrame(), metaFrame);
+        } catch (Exception e) {
+            // cleanup in case of failure
+            treeIndexOpHelper.deinit();
+            throw new HyracksDataException(e);
+        }
+    }
+
+    @Override
+    public void nextFrame(ByteBuffer buffer) throws HyracksDataException {
+        accessor.reset(buffer);
+        int tupleCount = accessor.getTupleCount();
+        for (int i = 0; i < tupleCount; i++) {
+            tuple.reset(accessor, i);
+            treeIndexOpHelper.getTreeIndex().bulkLoadAddTuple(bulkLoadCtx, tuple);
+        }
+    }
+
+    @Override
+    public void close() throws HyracksDataException {
+        try {
+            treeIndexOpHelper.getTreeIndex().endBulkLoad(bulkLoadCtx);
+        } finally {
+            treeIndexOpHelper.deinit();
+        }
+    }
+
+    @Override
+    public void flush() throws HyracksDataException {
+    }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorDescriptor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorDescriptor.java
new file mode 100644
index 0000000..73b5323
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorDescriptor.java
@@ -0,0 +1,47 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.IOperatorNodePushable;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.job.IOperatorEnvironment;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public class TreeIndexDiskOrderScanOperatorDescriptor extends AbstractTreeIndexOperatorDescriptor {
+
+    private static final long serialVersionUID = 1L;
+
+    public TreeIndexDiskOrderScanOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc,
+            IStorageManagerInterface storageManager, IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider,
+            IFileSplitProvider fileSplitProvider, ITreeIndexFrameFactory interiorFrameFactory,
+            ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] typeTraits, ITreeIndexOpHelperFactory opHelperFactory) {
+        super(spec, 0, 1, recDesc, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
+                leafFrameFactory, typeTraits, null, opHelperFactory);
+    }
+
+    @Override
+    public IOperatorNodePushable createPushRuntime(IHyracksStageletContext ctx, IOperatorEnvironment env,
+            IRecordDescriptorProvider recordDescProvider, int partition, int nPartitions) {
+        return new TreeIndexDiskOrderScanOperatorNodePushable(this, ctx, partition);
+    }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorNodePushable.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorNodePushable.java
new file mode 100644
index 0000000..415b9e3
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorNodePushable.java
@@ -0,0 +1,104 @@
+/*
+ * 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.dataflow;
+
+import java.io.DataOutput;
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
+import edu.uci.ics.hyracks.dataflow.common.comm.util.FrameUtils;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.std.base.AbstractUnaryOutputSourceOperatorNodePushable;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
+
+public class TreeIndexDiskOrderScanOperatorNodePushable extends AbstractUnaryOutputSourceOperatorNodePushable {
+    private final TreeIndexOpHelper treeIndexOpHelper;
+
+    public TreeIndexDiskOrderScanOperatorNodePushable(AbstractTreeIndexOperatorDescriptor opDesc,
+            IHyracksStageletContext ctx, int partition) {
+        treeIndexOpHelper = opDesc.getTreeIndexOpHelperFactory().createTreeIndexOpHelper(opDesc, ctx, partition,
+                IndexHelperOpenMode.OPEN);
+    }
+
+    @Override
+    public void initialize() throws HyracksDataException {
+
+        ITreeIndexFrame cursorFrame = treeIndexOpHelper.getOperatorDescriptor().getTreeIndexLeafFactory().createFrame();
+        ITreeIndexCursor cursor = treeIndexOpHelper.createDiskOrderScanCursor(cursorFrame);
+        ITreeIndexMetaDataFrame metaFrame = new LIFOMetaDataFrame();
+
+        IndexOpContext diskOrderScanOpCtx = treeIndexOpHelper.getTreeIndex().createOpContext(IndexOp.DISKORDERSCAN,
+                cursorFrame, null, null);
+        try {
+
+            treeIndexOpHelper.init();
+
+            try {
+                treeIndexOpHelper.getTreeIndex().diskOrderScan(cursor, cursorFrame, metaFrame, diskOrderScanOpCtx);
+
+                int fieldCount = treeIndexOpHelper.getTreeIndex().getFieldCount();
+                ByteBuffer frame = treeIndexOpHelper.getHyracksStageletContext().allocateFrame();
+                FrameTupleAppender appender = new FrameTupleAppender(treeIndexOpHelper.getHyracksStageletContext()
+                        .getFrameSize());
+                appender.reset(frame, true);
+                ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+                DataOutput dos = tb.getDataOutput();
+
+                while (cursor.hasNext()) {
+                    tb.reset();
+                    cursor.next();
+
+                    ITupleReference frameTuple = cursor.getTuple();
+                    for (int i = 0; i < frameTuple.getFieldCount(); i++) {
+                        dos.write(frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
+                        tb.addFieldEndOffset();
+                    }
+
+                    if (!appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize())) {
+                        FrameUtils.flushFrame(frame, writer);
+                        appender.reset(frame, true);
+                        if (!appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize())) {
+                            throw new IllegalStateException();
+                        }
+                    }
+                }
+
+                if (appender.getTupleCount() > 0) {
+                    FrameUtils.flushFrame(frame, writer);
+                }
+            } finally {
+                cursor.close();
+                writer.close();
+            }
+
+        } catch (Exception e) {
+            deinitialize();
+            throw new HyracksDataException(e);
+        }
+    }
+
+    @Override
+    public void deinitialize() throws HyracksDataException {
+        treeIndexOpHelper.deinit();
+    }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDropOperatorDescriptor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDropOperatorDescriptor.java
new file mode 100644
index 0000000..2cfa905
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDropOperatorDescriptor.java
@@ -0,0 +1,50 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.IOperatorNodePushable;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.job.IOperatorEnvironment;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.base.AbstractSingleActivityOperatorDescriptor;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public class TreeIndexDropOperatorDescriptor extends AbstractSingleActivityOperatorDescriptor {
+
+    private static final long serialVersionUID = 1L;
+
+    private IStorageManagerInterface storageManager;
+    private IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider;
+    private IFileSplitProvider fileSplitProvider;
+
+    public TreeIndexDropOperatorDescriptor(JobSpecification spec, IStorageManagerInterface storageManager,
+            IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider, IFileSplitProvider fileSplitProvider) {
+        super(spec, 0, 0);
+        this.storageManager = storageManager;
+        this.treeIndexRegistryProvider = treeIndexRegistryProvider;
+        this.fileSplitProvider = fileSplitProvider;
+    }
+
+    @Override
+    public IOperatorNodePushable createPushRuntime(IHyracksStageletContext ctx, IOperatorEnvironment env,
+            IRecordDescriptorProvider recordDescProvider, int partition, int nPartitions) {
+        return new TreeIndexDropOperatorNodePushable(ctx, storageManager, treeIndexRegistryProvider, fileSplitProvider,
+                partition);
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDropOperatorNodePushable.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDropOperatorNodePushable.java
new file mode 100644
index 0000000..71346f7
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDropOperatorNodePushable.java
@@ -0,0 +1,108 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.common.dataflow;
+
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+import edu.uci.ics.hyracks.api.comm.IFrameWriter;
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.dataflow.std.base.AbstractOperatorNodePushable;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public class TreeIndexDropOperatorNodePushable extends AbstractOperatorNodePushable {
+    private static final Logger LOGGER = Logger.getLogger(TreeIndexDropOperatorNodePushable.class.getName());
+
+    private final IHyracksStageletContext ctx;
+    private IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider;
+    private IStorageManagerInterface storageManager;
+    private IFileSplitProvider fileSplitProvider;
+    private int partition;
+
+    public TreeIndexDropOperatorNodePushable(IHyracksStageletContext ctx, IStorageManagerInterface storageManager,
+            IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider, IFileSplitProvider fileSplitProvider,
+            int partition) {
+        this.ctx = ctx;
+        this.storageManager = storageManager;
+        this.treeIndexRegistryProvider = treeIndexRegistryProvider;
+        this.fileSplitProvider = fileSplitProvider;
+        this.partition = partition;
+    }
+
+    @Override
+    public void deinitialize() throws HyracksDataException {
+    }
+
+    @Override
+    public int getInputArity() {
+        return 0;
+    }
+
+    @Override
+    public IFrameWriter getInputFrameWriter(int index) {
+        return null;
+    }
+
+    @Override
+    public void initialize() throws HyracksDataException {
+        try {
+
+            IndexRegistry<ITreeIndex> treeIndexRegistry = treeIndexRegistryProvider.getRegistry(ctx);
+            IBufferCache bufferCache = storageManager.getBufferCache(ctx);
+            IFileMapProvider fileMapProvider = storageManager.getFileMapProvider(ctx);
+
+            FileReference f = fileSplitProvider.getFileSplits()[partition].getLocalFile();
+
+            boolean fileIsMapped = fileMapProvider.isMapped(f);
+            if (!fileIsMapped) {
+                throw new HyracksDataException("Cannot drop Tree with name " + f.toString()
+                        + ". No file mapping exists.");
+            }
+
+            int indexFileId = fileMapProvider.lookupFileId(f);
+
+            // unregister tree instance
+            treeIndexRegistry.lock();
+            try {
+                treeIndexRegistry.unregister(indexFileId);
+            } finally {
+                treeIndexRegistry.unlock();
+            }
+
+            // remove name to id mapping
+            bufferCache.deleteFile(indexFileId);
+        }
+        // TODO: for the time being we don't throw,
+        // with proper exception handling (no hanging job problem) we should
+        // throw
+        catch (Exception e) {
+            if (LOGGER.isLoggable(Level.WARNING)) {
+                LOGGER.warning("Tree Drop Operator Failed Due To Exception: " + e.getMessage());
+            }
+        }
+    }
+
+    @Override
+    public void setOutputFrameWriter(int index, IFrameWriter writer, RecordDescriptor recordDesc) {
+    }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorDescriptor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorDescriptor.java
new file mode 100644
index 0000000..0961a4f
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorDescriptor.java
@@ -0,0 +1,56 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.IOperatorNodePushable;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.job.IOperatorEnvironment;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+// re-create in-memory state for a tree index that has already been built (i.e., the file exists):
+// 1. register files in file manager (FileManager)
+// 2. create file mappings (FileMappingProvider)
+// 3. register tree index instance (IndexRegistry)
+
+public class TreeIndexFileEnlistmentOperatorDescriptor extends AbstractTreeIndexOperatorDescriptor {
+
+    private static final long serialVersionUID = 1L;
+
+    public TreeIndexFileEnlistmentOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc,
+            IStorageManagerInterface storageManager, IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider,
+            IFileSplitProvider fileSplitProvider, ITreeIndexFrameFactory interiorFrameFactory,
+            ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] typeTraits,
+            IBinaryComparatorFactory[] comparatorFactories, ITreeIndexOpHelperFactory opHelperFactory) {
+        super(spec, 0, 0, recDesc, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
+                leafFrameFactory, typeTraits, comparatorFactories, opHelperFactory);
+    }
+
+    @Override
+    public IOperatorNodePushable createPushRuntime(IHyracksStageletContext ctx, IOperatorEnvironment env,
+            IRecordDescriptorProvider recordDescProvider, int partition, int partitions) throws HyracksDataException {
+        return new TreeIndexFileEnlistmentOperatorNodePushable(this, ctx, partition);
+    }
+
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorNodePushable.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorNodePushable.java
new file mode 100644
index 0000000..8ff6586
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorNodePushable.java
@@ -0,0 +1,60 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.comm.IFrameWriter;
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.std.base.AbstractOperatorNodePushable;
+
+public class TreeIndexFileEnlistmentOperatorNodePushable extends AbstractOperatorNodePushable {
+
+    private final TreeIndexOpHelper treeIndexOpHelper;
+
+    public TreeIndexFileEnlistmentOperatorNodePushable(AbstractTreeIndexOperatorDescriptor opDesc,
+            IHyracksStageletContext ctx, int partition) {
+        treeIndexOpHelper = opDesc.getTreeIndexOpHelperFactory().createTreeIndexOpHelper(opDesc, ctx, partition,
+                IndexHelperOpenMode.ENLIST);
+    }
+
+    @Override
+    public void deinitialize() throws HyracksDataException {
+    }
+
+    @Override
+    public int getInputArity() {
+        return 0;
+    }
+
+    @Override
+    public IFrameWriter getInputFrameWriter(int index) {
+        return null;
+    }
+
+    @Override
+    public void initialize() throws HyracksDataException {
+        try {
+            treeIndexOpHelper.init();
+        } finally {
+            treeIndexOpHelper.deinit();
+        }
+    }
+
+    @Override
+    public void setOutputFrameWriter(int index, IFrameWriter writer, RecordDescriptor recordDesc) {
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorDescriptor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorDescriptor.java
new file mode 100644
index 0000000..c8141b9
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorDescriptor.java
@@ -0,0 +1,58 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.IOperatorNodePushable;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.job.IOperatorEnvironment;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public class TreeIndexInsertUpdateDeleteOperatorDescriptor extends AbstractTreeIndexOperatorDescriptor {
+
+    private static final long serialVersionUID = 1L;
+
+    private final int[] fieldPermutation;
+
+    private IndexOp op;
+
+    public TreeIndexInsertUpdateDeleteOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc,
+            IStorageManagerInterface storageManager, IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider,
+            IFileSplitProvider fileSplitProvider, ITreeIndexFrameFactory interiorFrameFactory,
+            ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] typeTraits,
+            IBinaryComparatorFactory[] comparatorFactories, int[] fieldPermutation, IndexOp op,
+            ITreeIndexOpHelperFactory opHelperFactory) {
+        super(spec, 1, 1, recDesc, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
+                leafFrameFactory, typeTraits, comparatorFactories, opHelperFactory);
+        this.fieldPermutation = fieldPermutation;
+        this.op = op;
+    }
+
+    @Override
+    public IOperatorNodePushable createPushRuntime(IHyracksStageletContext ctx, IOperatorEnvironment env,
+            IRecordDescriptorProvider recordDescProvider, int partition, int nPartitions) {
+        return new TreeIndexInsertUpdateDeleteOperatorNodePushable(this, ctx, partition, fieldPermutation,
+                recordDescProvider, op);
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorNodePushable.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorNodePushable.java
new file mode 100644
index 0000000..74a9efc
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorNodePushable.java
@@ -0,0 +1,119 @@
+/*
+ * 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.dataflow;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
+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.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
+
+public class TreeIndexInsertUpdateDeleteOperatorNodePushable extends AbstractUnaryInputUnaryOutputOperatorNodePushable {
+    private final TreeIndexOpHelper treeIndexOpHelper;
+    private FrameTupleAccessor accessor;
+    private final IRecordDescriptorProvider recordDescProvider;
+    private final IndexOp op;
+    private final PermutingFrameTupleReference tuple = new PermutingFrameTupleReference();
+    private ByteBuffer writeBuffer;
+    private IndexOpContext opCtx;
+
+    public TreeIndexInsertUpdateDeleteOperatorNodePushable(AbstractTreeIndexOperatorDescriptor opDesc,
+            IHyracksStageletContext ctx, int partition, int[] fieldPermutation,
+            IRecordDescriptorProvider recordDescProvider, IndexOp op) {
+        treeIndexOpHelper = opDesc.getTreeIndexOpHelperFactory().createTreeIndexOpHelper(opDesc, ctx, partition,
+                IndexHelperOpenMode.OPEN);
+        this.recordDescProvider = recordDescProvider;
+        this.op = op;
+        tuple.setFieldPermutation(fieldPermutation);
+    }
+
+    @Override
+    public void open() throws HyracksDataException {
+        AbstractTreeIndexOperatorDescriptor opDesc = (AbstractTreeIndexOperatorDescriptor) treeIndexOpHelper
+                .getOperatorDescriptor();
+        RecordDescriptor inputRecDesc = recordDescProvider.getInputRecordDescriptor(opDesc.getOperatorId(), 0);
+        accessor = new FrameTupleAccessor(treeIndexOpHelper.getHyracksStageletContext().getFrameSize(), inputRecDesc);
+        writeBuffer = treeIndexOpHelper.getHyracksStageletContext().allocateFrame();
+        try {
+            treeIndexOpHelper.init();
+            treeIndexOpHelper.getTreeIndex().open(treeIndexOpHelper.getIndexFileId());
+            opCtx = treeIndexOpHelper.getTreeIndex().createOpContext(op, treeIndexOpHelper.getLeafFrame(),
+                    treeIndexOpHelper.getInteriorFrame(), new LIFOMetaDataFrame());
+        } catch (Exception e) {
+            // cleanup in case of failure
+            treeIndexOpHelper.deinit();
+            throw new HyracksDataException(e);
+        }
+    }
+
+    @Override
+    public void nextFrame(ByteBuffer buffer) throws HyracksDataException {
+        final ITreeIndex treeIndex = treeIndexOpHelper.getTreeIndex();
+        accessor.reset(buffer);
+
+        int tupleCount = accessor.getTupleCount();
+        for (int i = 0; i < tupleCount; i++) {
+            tuple.reset(accessor, i);
+            try {
+                switch (op) {
+
+                    case INSERT: {
+                        treeIndex.insert(tuple, opCtx);
+                    }
+                        break;
+
+                    case DELETE: {
+                        treeIndex.delete(tuple, opCtx);
+                    }
+                        break;
+
+                    default: {
+                        throw new HyracksDataException("Unsupported operation " + op
+                                + " in tree index InsertUpdateDelete operator");
+                    }
+
+                }
+
+            } catch (Exception e) {
+                e.printStackTrace();
+            }
+        }
+
+        // pass a copy of the frame to next op
+        System.arraycopy(buffer.array(), 0, writeBuffer.array(), 0, buffer.capacity());
+        FrameUtils.flushFrame(writeBuffer, writer);
+    }
+
+    @Override
+    public void close() throws HyracksDataException {
+        try {
+            writer.close();
+        } finally {
+            treeIndexOpHelper.deinit();
+        }
+    }
+
+    @Override
+    public void flush() throws HyracksDataException {
+    }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexOpHelper.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexOpHelper.java
new file mode 100644
index 0000000..fca6d8d
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexOpHelper.java
@@ -0,0 +1,176 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.impls.TreeDiskOrderScanCursor;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public abstract class TreeIndexOpHelper {
+
+    protected ITreeIndexFrame interiorFrame;
+    protected ITreeIndexFrame leafFrame;
+    protected MultiComparator cmp;
+
+    protected ITreeIndex treeIndex;
+    protected int indexFileId = -1;
+    protected int partition;
+
+    protected ITreeIndexOperatorDescriptorHelper opDesc;
+    protected IHyracksStageletContext ctx;
+
+    protected IndexHelperOpenMode mode;
+
+    public TreeIndexOpHelper(ITreeIndexOperatorDescriptorHelper opDesc, final IHyracksStageletContext ctx,
+            int partition, IndexHelperOpenMode mode) {
+        this.opDesc = opDesc;
+        this.ctx = ctx;
+        this.mode = mode;
+        this.partition = partition;
+    }
+
+    public void init() throws HyracksDataException {
+        IBufferCache bufferCache = opDesc.getStorageManager().getBufferCache(ctx);
+        IFileMapProvider fileMapProvider = opDesc.getStorageManager().getFileMapProvider(ctx);
+        IFileSplitProvider fileSplitProvider = opDesc.getTreeIndexFileSplitProvider();
+
+        FileReference f = fileSplitProvider.getFileSplits()[partition].getLocalFile();
+        boolean fileIsMapped = fileMapProvider.isMapped(f);
+
+        switch (mode) {
+
+            case OPEN: {
+                if (!fileIsMapped) {
+                    throw new HyracksDataException("Trying to open tree index from unmapped file " + f.toString());
+                }
+            }
+                break;
+
+            case CREATE:
+            case ENLIST: {
+                if (!fileIsMapped) {
+                    bufferCache.createFile(f);
+                }
+            }
+                break;
+
+        }
+
+        int fileId = fileMapProvider.lookupFileId(f);
+        try {
+            bufferCache.openFile(fileId);
+        } catch (HyracksDataException e) {
+            // revert state of buffer cache since file failed to open
+            if (!fileIsMapped) {
+                bufferCache.deleteFile(fileId);
+            }
+            throw e;
+        }
+
+        // only set indexFileId member when openFile() succeeds,
+        // otherwise deinit() will try to close the file that failed to open
+        indexFileId = fileId;
+
+        interiorFrame = opDesc.getTreeIndexInteriorFactory().createFrame();
+        leafFrame = opDesc.getTreeIndexLeafFactory().createFrame();
+
+        IndexRegistry<ITreeIndex> treeIndexRegistry = opDesc.getTreeIndexRegistryProvider().getRegistry(ctx);
+        treeIndex = treeIndexRegistry.get(indexFileId);
+        if (treeIndex == null) {
+
+            // create new tree and register it
+            treeIndexRegistry.lock();
+            try {
+                // check if tree has already been registered by another thread
+                treeIndex = treeIndexRegistry.get(indexFileId);
+                if (treeIndex == null) {
+                    // this thread should create and register the tree
+
+                    IBinaryComparator[] comparators = new IBinaryComparator[opDesc.getTreeIndexComparatorFactories().length];
+                    for (int i = 0; i < opDesc.getTreeIndexComparatorFactories().length; i++) {
+                        comparators[i] = opDesc.getTreeIndexComparatorFactories()[i].createBinaryComparator();
+                    }
+
+                    cmp = new MultiComparator(opDesc.getTreeIndexTypeTraits(), comparators);
+
+                    treeIndex = createTreeIndex();
+                    if (mode == IndexHelperOpenMode.CREATE) {
+                        ITreeIndexMetaDataFrame metaFrame = treeIndex.getFreePageManager().getMetaDataFrameFactory()
+                                .createFrame();
+                        try {
+                            treeIndex.create(indexFileId, leafFrame, metaFrame);
+                        } catch (Exception e) {
+                            throw new HyracksDataException(e);
+                        }
+                    }
+                    treeIndex.open(indexFileId);
+                    treeIndexRegistry.register(indexFileId, treeIndex);
+                }
+            } finally {
+                treeIndexRegistry.unlock();
+            }
+        }
+    }
+
+    // MUST be overridden
+    public ITreeIndex createTreeIndex() throws HyracksDataException {
+        throw new HyracksDataException("createTreeIndex Operation not implemented.");
+    }
+
+    public ITreeIndexCursor createDiskOrderScanCursor(ITreeIndexFrame leafFrame) throws HyracksDataException {
+        return new TreeDiskOrderScanCursor(leafFrame);
+    }
+
+    public void deinit() throws HyracksDataException {
+        if (indexFileId != -1) {
+            IBufferCache bufferCache = opDesc.getStorageManager().getBufferCache(ctx);
+            bufferCache.closeFile(indexFileId);
+        }
+    }
+
+    public ITreeIndex getTreeIndex() {
+        return treeIndex;
+    }
+
+    public IHyracksStageletContext getHyracksStageletContext() {
+        return ctx;
+    }
+
+    public ITreeIndexOperatorDescriptorHelper getOperatorDescriptor() {
+        return opDesc;
+    }
+
+    public ITreeIndexFrame getLeafFrame() {
+        return leafFrame;
+    }
+
+    public ITreeIndexFrame getInteriorFrame() {
+        return interiorFrame;
+    }
+
+    public int getIndexFileId() {
+        return indexFileId;
+    }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorDescriptor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorDescriptor.java
new file mode 100644
index 0000000..574e727
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorDescriptor.java
@@ -0,0 +1,33 @@
+package edu.uci.ics.hyracks.storage.am.common.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.IOperatorNodePushable;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.job.IOperatorEnvironment;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public class TreeIndexStatsOperatorDescriptor extends AbstractTreeIndexOperatorDescriptor {
+
+    private static final long serialVersionUID = 1L;
+
+    public TreeIndexStatsOperatorDescriptor(JobSpecification spec, IStorageManagerInterface storageManager,
+            IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider, IFileSplitProvider fileSplitProvider,
+            ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory,
+            ITypeTrait[] typeTraits, IBinaryComparatorFactory[] comparatorFactories,
+            ITreeIndexOpHelperFactory opHelperFactory) {
+        super(spec, 0, 0, null, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
+                leafFrameFactory, typeTraits, comparatorFactories, opHelperFactory);
+    }
+
+    @Override
+    public IOperatorNodePushable createPushRuntime(IHyracksStageletContext ctx, IOperatorEnvironment env,
+            IRecordDescriptorProvider recordDescProvider, int partition, int nPartitions) {
+        return new TreeIndexStatsOperatorNodePushable(this, ctx, partition);
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorNodePushable.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorNodePushable.java
new file mode 100644
index 0000000..f47855f
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorNodePushable.java
@@ -0,0 +1,78 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.storage.am.common.dataflow;
+
+import edu.uci.ics.hyracks.api.comm.IFrameWriter;
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+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.common.buffercache.IBufferCache;
+
+public class TreeIndexStatsOperatorNodePushable extends AbstractOperatorNodePushable {
+    private final TreeIndexOpHelper treeIndexOpHelper;
+    private final IHyracksStageletContext ctx;
+    private TreeIndexStatsGatherer statsGatherer;
+
+    public TreeIndexStatsOperatorNodePushable(AbstractTreeIndexOperatorDescriptor opDesc, IHyracksStageletContext ctx,
+            int partition) {
+        treeIndexOpHelper = opDesc.getTreeIndexOpHelperFactory().createTreeIndexOpHelper(opDesc, ctx, partition,
+                IndexHelperOpenMode.CREATE);
+        this.ctx = ctx;
+    }
+
+    @Override
+    public void deinitialize() throws HyracksDataException {
+    }
+
+    @Override
+    public int getInputArity() {
+        return 0;
+    }
+
+    @Override
+    public IFrameWriter getInputFrameWriter(int index) {
+        return null;
+    }
+
+    @Override
+    public void initialize() throws HyracksDataException {
+        try {
+            treeIndexOpHelper.init();
+            treeIndexOpHelper.getTreeIndex().open(treeIndexOpHelper.getIndexFileId());
+
+            ITreeIndex treeIndex = treeIndexOpHelper.getTreeIndex();
+            IBufferCache bufferCache = treeIndexOpHelper.getOperatorDescriptor().getStorageManager()
+                    .getBufferCache(ctx);
+
+            statsGatherer = new TreeIndexStatsGatherer(bufferCache, treeIndex.getFreePageManager(),
+                    treeIndexOpHelper.getIndexFileId(), treeIndex.getRootPageId());
+            TreeIndexStats stats = statsGatherer.gatherStats(treeIndex.getLeafFrameFactory().createFrame(), treeIndex
+                    .getInteriorFrameFactory().createFrame(), treeIndex.getFreePageManager().getMetaDataFrameFactory()
+                    .createFrame());
+            System.err.println(stats.toString());
+        } catch (Exception e) {
+            treeIndexOpHelper.deinit();
+            throw new HyracksDataException(e);
+        }
+    }
+
+    @Override
+    public void setOutputFrameWriter(int index, IFrameWriter writer, RecordDescriptor recordDesc) {
+    }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/AbstractSlotManager.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/AbstractSlotManager.java
new file mode 100644
index 0000000..87fea47
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/AbstractSlotManager.java
@@ -0,0 +1,60 @@
+/*
+ * 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.frames;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ISlotManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+
+public abstract class AbstractSlotManager implements ISlotManager {
+
+    protected static final int slotSize = 4;
+    protected ITreeIndexFrame frame;
+
+    @Override
+    public int getTupleOff(int offset) {
+        return frame.getBuffer().getInt(offset);
+    }
+
+    @Override
+    public void setSlot(int offset, int value) {
+        frame.getBuffer().putInt(offset, value);
+    }
+
+    @Override
+    public int getSlotEndOff() {
+        return frame.getBuffer().capacity() - (frame.getTupleCount() * slotSize);
+    }
+
+    @Override
+    public int getSlotStartOff() {
+        return frame.getBuffer().capacity() - slotSize;
+    }
+
+    @Override
+    public int getSlotSize() {
+        return slotSize;
+    }
+
+    @Override
+    public void setFrame(ITreeIndexFrame frame) {
+        this.frame = frame;
+    }
+
+    @Override
+    public int getSlotOff(int tupleIndex) {
+        return getSlotStartOff() - tupleIndex * slotSize;
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/FrameOpSpaceStatus.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/FrameOpSpaceStatus.java
new file mode 100644
index 0000000..97a4730
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/FrameOpSpaceStatus.java
@@ -0,0 +1,20 @@
+/*
+ * 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.frames;
+
+public enum FrameOpSpaceStatus {
+    INSUFFICIENT_SPACE, SUFFICIENT_CONTIGUOUS_SPACE, SUFFICIENT_SPACE
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrame.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrame.java
new file mode 100644
index 0000000..b621b89
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrame.java
@@ -0,0 +1,115 @@
+/*
+ * 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.frames;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+// all meta pages of this kind have a negative level
+// the first meta page has level -1, all other meta pages have level -2
+// the first meta page is special because it guarantees to have a correct max page
+// other meta pages (i.e., with level -2) have junk in the max page field
+
+public class LIFOMetaDataFrame implements ITreeIndexMetaDataFrame {
+
+    protected static final int tupleCountOff = 0;
+    protected static final int freeSpaceOff = tupleCountOff + 4;
+    protected static final int maxPageOff = freeSpaceOff + 4;
+    protected static final int dummyFieldOff = maxPageOff + 4;
+    protected static final byte levelOff = dummyFieldOff + 4;
+    protected static final byte nextPageOff = levelOff + 1;
+
+    protected ICachedPage page = null;
+    protected ByteBuffer buf = null;
+
+    public int getMaxPage() {
+        return buf.getInt(maxPageOff);
+    }
+
+    public void setMaxPage(int maxPage) {
+        buf.putInt(maxPageOff, maxPage);
+    }
+
+    public int getFreePage() {
+        int tupleCount = buf.getInt(tupleCountOff);
+        if (tupleCount > 0) {
+            // return the last page from the linked list of free pages
+            // TODO: this is a dumb policy, but good enough for now
+            int lastPageOff = buf.getInt(freeSpaceOff) - 4;
+            buf.putInt(freeSpaceOff, lastPageOff);
+            buf.putInt(tupleCountOff, tupleCount - 1);
+            return buf.getInt(lastPageOff);
+        } else {
+            return -1;
+        }
+    }
+
+    // must be checked before adding free page
+    // user of this class is responsible for getting a free page as a new meta
+    // page, latching it, etc. if there is no space on this page
+    public boolean hasSpace() {
+        return buf.getInt(freeSpaceOff) + 4 < buf.capacity();
+    }
+
+    // on bounds checking is done, there must be free space
+    public void addFreePage(int freePage) {
+        int freeSpace = buf.getInt(freeSpaceOff);
+        buf.putInt(freeSpace, freePage);
+        buf.putInt(freeSpaceOff, freeSpace + 4);
+        buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
+    }
+
+    @Override
+    public byte getLevel() {
+        return buf.get(levelOff);
+    }
+
+    @Override
+    public void setLevel(byte level) {
+        buf.put(levelOff, level);
+    }
+
+    @Override
+    public ICachedPage getPage() {
+        return page;
+    }
+
+    @Override
+    public void setPage(ICachedPage page) {
+        this.page = page;
+        this.buf = page.getBuffer();
+    }
+
+    @Override
+    public void initBuffer(int level) {
+        buf.putInt(freeSpaceOff, nextPageOff + 4);
+        buf.putInt(tupleCountOff, 0);
+        buf.putInt(levelOff, level);
+        buf.putInt(nextPageOff, -1);
+    }
+
+    @Override
+    public int getNextPage() {
+        return buf.getInt(nextPageOff);
+    }
+
+    @Override
+    public void setNextPage(int nextPage) {
+        buf.putInt(nextPageOff, nextPage);
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrameFactory.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrameFactory.java
new file mode 100644
index 0000000..409c8b2
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrameFactory.java
@@ -0,0 +1,26 @@
+/*
+ * 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.frames;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+
+public class LIFOMetaDataFrameFactory implements ITreeIndexMetaDataFrameFactory {
+    @Override
+    public ITreeIndexMetaDataFrame createFrame() {
+        return new LIFOMetaDataFrame();
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java
new file mode 100644
index 0000000..af1e337
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java
@@ -0,0 +1,324 @@
+/*
+ * 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.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.storage.am.common.api.ISlotManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleMode;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleNoExactMatchPolicy;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.SlotOffTupleOff;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public abstract class TreeIndexNSMFrame implements ITreeIndexFrame {
+
+    protected static final int pageLsnOff = 0; // 0
+    protected static final int tupleCountOff = pageLsnOff + 4; // 4
+    protected static final int freeSpaceOff = tupleCountOff + 4; // 8
+    protected static final int totalFreeSpaceOff = freeSpaceOff + 4; // 16
+    protected static final byte levelOff = totalFreeSpaceOff + 4;
+    protected static final byte smFlagOff = levelOff + 1;
+
+    protected ICachedPage page = null;
+    protected ByteBuffer buf = null;
+    protected ISlotManager slotManager;
+
+    protected ITreeIndexTupleWriter tupleWriter;
+    protected ITreeIndexTupleReference frameTuple;
+
+    public TreeIndexNSMFrame(ITreeIndexTupleWriter tupleWriter, ISlotManager slotManager) {
+        this.tupleWriter = tupleWriter;
+        this.frameTuple = tupleWriter.createTupleReference();
+        this.slotManager = slotManager;
+    }
+
+    @Override
+    public void initBuffer(byte level) {
+        buf.putInt(pageLsnOff, 0); // TODO: might to set to a different lsn
+        // during creation
+        buf.putInt(tupleCountOff, 0);
+        resetSpaceParams();
+        buf.put(levelOff, level);
+        buf.put(smFlagOff, (byte) 0);
+    }
+
+    @Override
+    public boolean isLeaf() {
+        return buf.get(levelOff) == 0;
+    }
+
+    @Override
+    public boolean isInterior() {
+        return buf.get(levelOff) > 0;
+    }
+
+    @Override
+    public byte getLevel() {
+        return buf.get(levelOff);
+    }
+
+    @Override
+    public void setLevel(byte level) {
+        buf.put(levelOff, level);
+    }
+
+    @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 int getFreeSpaceOff() {
+        return buf.getInt(freeSpaceOff);
+    }
+
+    @Override
+    public void setFreeSpaceOff(int freeSpace) {
+        buf.putInt(freeSpaceOff, freeSpace);
+    }
+
+    @Override
+    public void setPage(ICachedPage page) {
+        this.page = page;
+        this.buf = page.getBuffer();
+        slotManager.setFrame(this);
+    }
+
+    @Override
+    public ByteBuffer getBuffer() {
+        return page.getBuffer();
+    }
+
+    @Override
+    public ICachedPage getPage() {
+        return page;
+    }
+
+    @Override
+    public boolean compact(MultiComparator cmp) {
+        resetSpaceParams();
+        frameTuple.setFieldCount(cmp.getFieldCount());
+
+        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;
+            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 void delete(ITupleReference tuple, MultiComparator cmp, boolean exactDelete) throws Exception {
+
+        frameTuple.setFieldCount(cmp.getFieldCount());
+        int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.FTM_EXACT,
+                FindTupleNoExactMatchPolicy.FTP_HIGHER_KEY);
+        int slotOff = slotManager.getSlotOff(tupleIndex);
+        if (tupleIndex < 0) {
+            throw new TreeIndexException("Key to be deleted does not exist.");
+        } else {
+            if (exactDelete) {
+                // check the non-key columns for equality by byte-by-byte
+                // comparison
+                int tupleOff = slotManager.getTupleOff(slotOff);
+                frameTuple.resetByTupleOffset(buf, tupleOff);
+
+                int comparison = cmp.fieldRangeCompare(tuple, frameTuple, cmp.getKeyFieldCount() - 1,
+                        cmp.getFieldCount() - cmp.getKeyFieldCount());
+                if (comparison != 0) {
+                    throw new TreeIndexException(
+                            "Cannot delete tuple. Byte-by-byte comparison failed to prove equality.");
+                }
+            }
+
+            int tupleOff = slotManager.getTupleOff(slotOff);
+            frameTuple.resetByTupleOffset(buf, tupleOff);
+            int tupleSize = tupleWriter.bytesRequired(frameTuple);
+
+            // perform deletion (we just do a memcpy to overwrite the slot)
+            int slotStartOff = slotManager.getSlotEndOff();
+            int length = slotOff - slotStartOff;
+            System.arraycopy(buf.array(), slotStartOff, buf.array(), slotStartOff + slotManager.getSlotSize(), length);
+
+            // maintain space information
+            buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
+            buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + tupleSize + slotManager.getSlotSize());
+        }
+    }
+
+    @Override
+    public 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 FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
+        else if (bytesRequired + slotManager.getSlotSize() <= buf.getInt(totalFreeSpaceOff))
+            return FrameOpSpaceStatus.SUFFICIENT_SPACE;
+        else
+            return FrameOpSpaceStatus.INSUFFICIENT_SPACE;
+    }
+
+    @Override
+    public FrameOpSpaceStatus hasSpaceUpdate(int rid, ITupleReference tuple, MultiComparator cmp) {
+        // TODO Auto-generated method stub
+        return FrameOpSpaceStatus.INSUFFICIENT_SPACE;
+    }
+
+    protected void resetSpaceParams() {
+        buf.putInt(freeSpaceOff, smFlagOff + 1);
+        buf.putInt(totalFreeSpaceOff, buf.capacity() - (smFlagOff + 1));
+    }
+
+    @Override
+    public int findTupleIndex(ITupleReference tuple, MultiComparator cmp) throws Exception {
+        frameTuple.setFieldCount(cmp.getFieldCount());
+        return slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.FTM_INCLUSIVE,
+                FindTupleNoExactMatchPolicy.FTP_HIGHER_KEY);
+    }
+
+    @Override
+    public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception {
+        slotManager.insertSlot(tupleIndex, buf.getInt(freeSpaceOff));
+        int bytesWritten = tupleWriter.writeTuple(tuple, buf, buf.getInt(freeSpaceOff));
+        buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
+        buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + bytesWritten);
+        buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - bytesWritten - slotManager.getSlotSize());
+    }
+
+    @Override
+    public void update(int rid, ITupleReference tuple) throws Exception {
+        // TODO Auto-generated method stub
+
+    }
+
+    @Override
+    public void printHeader() {
+        // TODO Auto-generated method stub
+
+    }
+
+    @Override
+    public int getTupleCount() {
+        return buf.getInt(tupleCountOff);
+    }
+
+    public ISlotManager getSlotManager() {
+        return slotManager;
+    }
+
+    @Override
+    public String printKeys(MultiComparator cmp, ISerializerDeserializer[] fields) throws HyracksDataException {
+        StringBuilder strBuilder = new StringBuilder();
+        int tupleCount = buf.getInt(tupleCountOff);
+        frameTuple.setFieldCount(fields.length);
+        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 getTupleOffset(int slotNum) {
+        return slotManager.getTupleOff(slotManager.getSlotStartOff() - slotNum * slotManager.getSlotSize());
+    }
+
+    @Override
+    public int getPageLsn() {
+        return buf.getInt(pageLsnOff);
+    }
+
+    @Override
+    public void setPageLsn(int pageLsn) {
+        buf.putInt(pageLsnOff, pageLsn);
+    }
+
+    @Override
+    public int getTotalFreeSpace() {
+        return buf.getInt(totalFreeSpaceOff);
+    }
+
+    @Override
+    public boolean compress(MultiComparator cmp) {
+        return false;
+    }
+
+    @Override
+    public int getSlotSize() {
+        return slotManager.getSlotSize();
+    }
+
+    @Override
+    public void setPageTupleFieldCount(int fieldCount) {
+        frameTuple.setFieldCount(fieldCount);
+    }
+
+    public ITreeIndexTupleWriter getTupleWriter() {
+        return tupleWriter;
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManager.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManager.java
new file mode 100644
index 0000000..42bf70f
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManager.java
@@ -0,0 +1,187 @@
+package edu.uci.ics.hyracks.storage.am.common.freepage;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
+
+public class LinkedListFreePageManager implements IFreePageManager {
+
+    private static final byte META_PAGE_LEVEL_INDICATOR = -1;
+    private static final byte FREE_PAGE_LEVEL_INDICATOR = -2;
+    private final IBufferCache bufferCache;
+    private final int fileId;
+    private final int headPage;
+    private final ITreeIndexMetaDataFrameFactory metaDataFrameFactory;
+
+    public LinkedListFreePageManager(IBufferCache bufferCache, int fileId, int headPage,
+            ITreeIndexMetaDataFrameFactory metaDataFrameFactory) {
+        this.bufferCache = bufferCache;
+        this.fileId = fileId;
+        this.headPage = headPage;
+        this.metaDataFrameFactory = metaDataFrameFactory;
+    }
+
+    @Override
+    public void addFreePage(ITreeIndexMetaDataFrame metaFrame, int freePage) throws HyracksDataException {
+
+        ICachedPage metaNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, headPage), false);
+        metaNode.acquireWriteLatch();
+
+        try {
+            metaFrame.setPage(metaNode);
+
+            if (metaFrame.hasSpace()) {
+                metaFrame.addFreePage(freePage);
+            } else {
+                // allocate a new page in the chain of meta pages
+                int newPage = metaFrame.getFreePage();
+                if (newPage < 0) {
+                    throw new Exception("Inconsistent Meta Page State. It has no space, but it also has no entries.");
+                }
+
+                ICachedPage newNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, newPage), false);
+                newNode.acquireWriteLatch();
+
+                try {
+                    int metaMaxPage = metaFrame.getMaxPage();
+
+                    // copy metaDataPage to newNode
+                    System.arraycopy(metaNode.getBuffer().array(), 0, newNode.getBuffer().array(), 0, metaNode
+                            .getBuffer().capacity());
+
+                    metaFrame.initBuffer(META_PAGE_LEVEL_INDICATOR);
+                    metaFrame.setNextPage(newPage);
+                    metaFrame.setMaxPage(metaMaxPage);
+                    metaFrame.addFreePage(freePage);
+                } finally {
+                    newNode.releaseWriteLatch();
+                    bufferCache.unpin(newNode);
+                }
+            }
+        } catch (Exception e) {
+            e.printStackTrace();
+        } finally {
+            metaNode.releaseWriteLatch();
+            bufferCache.unpin(metaNode);
+        }
+    }
+
+    @Override
+    public int getFreePage(ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
+        ICachedPage metaNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, headPage), false);
+
+        metaNode.acquireWriteLatch();
+
+        int freePage = -1;
+        try {
+            metaFrame.setPage(metaNode);
+            freePage = metaFrame.getFreePage();
+            if (freePage < 0) { // no free page entry on this page
+                int nextPage = metaFrame.getNextPage();
+                if (nextPage > 0) { // sibling may have free pages
+                    ICachedPage nextNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, nextPage), false);
+
+                    nextNode.acquireWriteLatch();
+                    // we copy over the free space entries of nextpage into the
+                    // first meta page (metaDataPage)
+                    // we need to link the first page properly to the next page
+                    // of nextpage
+                    try {
+                        // remember entries that remain unchanged
+                        int maxPage = metaFrame.getMaxPage();
+
+                        // copy entire page (including sibling pointer, free
+                        // page entries, and all other info)
+                        // after this copy nextPage is considered a free page
+                        System.arraycopy(nextNode.getBuffer().array(), 0, metaNode.getBuffer().array(), 0, nextNode
+                                .getBuffer().capacity());
+
+                        // reset unchanged entry
+                        metaFrame.setMaxPage(maxPage);
+
+                        freePage = metaFrame.getFreePage();
+                        // sibling also has no free pages, this "should" not
+                        // happen, but we deal with it anyway just to be safe
+                        if (freePage < 0) {
+                            freePage = nextPage;
+                        } else {
+                            metaFrame.addFreePage(nextPage);
+                        }
+                    } finally {
+                        nextNode.releaseWriteLatch();
+                        bufferCache.unpin(nextNode);
+                    }
+                } else {
+                    freePage = metaFrame.getMaxPage();
+                    freePage++;
+                    metaFrame.setMaxPage(freePage);
+                }
+            }
+        } finally {
+            metaNode.releaseWriteLatch();
+            bufferCache.unpin(metaNode);
+        }
+
+        return freePage;
+    }
+
+    @Override
+    public int getMaxPage(ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
+        ICachedPage metaNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, headPage), false);
+        metaNode.acquireWriteLatch();
+        int maxPage = -1;
+        try {
+            metaFrame.setPage(metaNode);
+            maxPage = metaFrame.getMaxPage();
+        } finally {
+            metaNode.releaseWriteLatch();
+            bufferCache.unpin(metaNode);
+        }
+        return maxPage;
+    }
+
+    @Override
+    public void init(ITreeIndexMetaDataFrame metaFrame, int currentMaxPage) throws HyracksDataException {
+        // initialize meta data page
+        ICachedPage metaNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, headPage), true);
+
+        metaNode.acquireWriteLatch();
+        try {
+            metaFrame.setPage(metaNode);
+            metaFrame.initBuffer(META_PAGE_LEVEL_INDICATOR);
+            metaFrame.setMaxPage(currentMaxPage);
+        } finally {
+            metaNode.releaseWriteLatch();
+            bufferCache.unpin(metaNode);
+        }
+    }
+
+    @Override
+    public ITreeIndexMetaDataFrameFactory getMetaDataFrameFactory() {
+        return metaDataFrameFactory;
+    }
+
+    @Override
+    public byte getFreePageLevelIndicator() {
+        return FREE_PAGE_LEVEL_INDICATOR;
+    }
+
+    @Override
+    public byte getMetaPageLevelIndicator() {
+        return META_PAGE_LEVEL_INDICATOR;
+    }
+
+    @Override
+    public boolean isFreePage(ITreeIndexMetaDataFrame metaFrame) {
+        return metaFrame.getLevel() == FREE_PAGE_LEVEL_INDICATOR;
+    }
+
+    @Override
+    public boolean isMetaPage(ITreeIndexMetaDataFrame metaFrame) {
+        return metaFrame.getLevel() == META_PAGE_LEVEL_INDICATOR;
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
new file mode 100644
index 0000000..2c2cb5e
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
@@ -0,0 +1,150 @@
+/*
+ * 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.impls;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
+
+public class TreeDiskOrderScanCursor implements ITreeIndexCursor {
+
+    private int tupleIndex = 0;
+    private int fileId = -1;
+    int currentPageId = -1;
+    int maxPageId = -1;
+    private ICachedPage page = null;
+    private ITreeIndexFrame frame = null;
+    private IBufferCache bufferCache = null;
+
+    private ITreeIndexTupleReference frameTuple;
+
+    public TreeDiskOrderScanCursor(ITreeIndexFrame frame) {
+        this.frame = frame;
+        this.frameTuple = frame.getTupleWriter().createTupleReference();
+    }
+
+    @Override
+    public void close() throws Exception {
+        page.releaseReadLatch();
+        bufferCache.unpin(page);
+        page = null;
+    }
+
+    @Override
+    public ITreeIndexTupleReference getTuple() {
+        return frameTuple;
+    }
+
+    @Override
+    public ICachedPage getPage() {
+        return page;
+    }
+
+    private boolean positionToNextLeaf(boolean skipCurrent) throws HyracksDataException {
+        while ((frame.getLevel() != 0 || skipCurrent) && (currentPageId <= maxPageId) || (frame.getTupleCount() == 0)) {
+            currentPageId++;
+
+            ICachedPage nextPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, currentPageId), false);
+            nextPage.acquireReadLatch();
+
+            page.releaseReadLatch();
+            bufferCache.unpin(page);
+
+            page = nextPage;
+            frame.setPage(page);
+            tupleIndex = 0;
+            skipCurrent = false;
+        }
+        if (currentPageId <= maxPageId)
+            return true;
+        else
+            return false;
+    }
+
+    @Override
+    public boolean hasNext() throws Exception {
+        if (tupleIndex >= frame.getTupleCount()) {
+            boolean nextLeafExists = positionToNextLeaf(true);
+            if (nextLeafExists) {
+                frameTuple.resetByTupleIndex(frame, tupleIndex);
+                return true;
+            } else {
+                return false;
+            }
+        }
+
+        frameTuple.resetByTupleIndex(frame, tupleIndex);
+        return true;
+    }
+
+    @Override
+    public void next() throws Exception {
+        tupleIndex++;
+    }
+
+    @Override
+    public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
+        // in case open is called multiple times without closing
+        if (page != null) {
+            page.releaseReadLatch();
+            bufferCache.unpin(page);
+        }
+
+        page = initialState.getPage();
+        tupleIndex = 0;
+        frame.setPage(page);
+        MultiComparator lowKeyCmp = searchPred.getLowKeyComparator();
+        frameTuple.setFieldCount(lowKeyCmp.getFieldCount());
+        boolean leafExists = positionToNextLeaf(false);
+        if (!leafExists) {
+            throw new HyracksDataException(
+                    "Failed to open disk-order scan cursor for tree index. Traget tree index has no leaves.");
+        }
+    }
+
+    @Override
+    public void reset() {
+        tupleIndex = 0;
+        currentPageId = -1;
+        maxPageId = -1;
+        page = null;
+    }
+
+    @Override
+    public void setBufferCache(IBufferCache bufferCache) {
+        this.bufferCache = bufferCache;
+    }
+
+    @Override
+    public void setFileId(int fileId) {
+        this.fileId = fileId;
+    }
+
+    public void setCurrentPageId(int currentPageId) {
+        this.currentPageId = currentPageId;
+    }
+
+    public void setMaxPageId(int maxPageId) {
+        this.maxPageId = maxPageId;
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleMode.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleMode.java
new file mode 100644
index 0000000..cea2500
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleMode.java
@@ -0,0 +1,20 @@
+/*
+ * 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.ophelpers;
+
+public enum FindTupleMode {
+    FTM_INCLUSIVE, FTM_EXCLUSIVE, FTM_EXACT
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleNoExactMatchPolicy.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleNoExactMatchPolicy.java
new file mode 100644
index 0000000..0d534ed
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleNoExactMatchPolicy.java
@@ -0,0 +1,20 @@
+/*
+ * 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.ophelpers;
+
+public enum FindTupleNoExactMatchPolicy {
+    FTP_LOWER_KEY, FTP_HIGHER_KEY
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOp.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOp.java
new file mode 100644
index 0000000..e40c5c8
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOp.java
@@ -0,0 +1,20 @@
+/*
+ * 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.ophelpers;
+
+public enum IndexOp {
+    INSERT, DELETE, UPDATE, SEARCH, DISKORDERSCAN
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOpContext.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOpContext.java
new file mode 100644
index 0000000..4f6e656
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOpContext.java
@@ -0,0 +1,5 @@
+package edu.uci.ics.hyracks.storage.am.common.ophelpers;
+
+public interface IndexOpContext {
+    void reset();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IntArrayList.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IntArrayList.java
new file mode 100644
index 0000000..46551dd
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IntArrayList.java
@@ -0,0 +1,89 @@
+/*
+ * 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.ophelpers;
+
+public class IntArrayList {
+    private int[] data;
+    private int size;
+    private int first;
+    private final int growth;
+
+    public IntArrayList(int initialCapacity, int growth) {
+        data = new int[initialCapacity];
+        size = 0;
+        first = 0;
+        this.growth = growth;
+    }
+
+    public int size() {
+        return size;
+    }
+
+    public int first() {
+        return first;
+    }
+
+    public void add(int i) {
+        if (size == data.length) {
+            int[] newData = new int[data.length + growth];
+            System.arraycopy(data, 0, newData, 0, data.length);
+            data = newData;
+        }
+
+        data[size++] = i;
+    }
+
+    public void removeLast() {
+        if (size > 0)
+            size--;
+    }
+
+    // WARNING: caller is responsible for checking size > 0
+    public int getLast() {
+        return data[size - 1];
+    }
+
+    public int get(int i) {
+        return data[i];
+    }
+
+    // WARNING: caller is responsible for checking i < size
+    public void set(int i, int value) {
+        data[i] = value;
+
+    }
+
+    public int getFirst() {
+        return data[first];
+    }
+
+    public void moveFirst() {
+        first++;
+    }
+
+    public void clear() {
+        size = 0;
+        first = 0;
+    }
+
+    public boolean isLast() {
+        return size == first;
+    }
+
+    public boolean isEmpty() {
+        return size == 0;
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java
new file mode 100644
index 0000000..1842bf8
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java
@@ -0,0 +1,102 @@
+/*
+ * 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.ophelpers;
+
+import java.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+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.dataflow.common.data.comparators.IntegerBinaryComparatorFactory;
+
+public class MultiComparator {
+
+    private static final long serialVersionUID = 1L;
+
+    private IBinaryComparator[] cmps = null;
+    private ITypeTrait[] typeTraits;
+
+    private IBinaryComparator intCmp = IntegerBinaryComparatorFactory.INSTANCE.createBinaryComparator();
+
+    public IBinaryComparator getIntCmp() {
+        return intCmp;
+    }
+
+    public MultiComparator(ITypeTrait[] typeTraits, IBinaryComparator[] cmps) {
+        this.typeTraits = typeTraits;
+        this.cmps = cmps;
+    }
+
+    public int compare(ITupleReference tupleA, ITupleReference tupleB) {
+        for (int i = 0; i < cmps.length; i++) {
+            int cmp = cmps[i].compare(tupleA.getFieldData(i), tupleA.getFieldStart(i), tupleA.getFieldLength(i),
+                    tupleB.getFieldData(i), tupleB.getFieldStart(i), tupleB.getFieldLength(i));
+            if (cmp < 0)
+                return -1;
+            else if (cmp > 0)
+                return 1;
+        }
+        return 0;
+    }
+
+    public int fieldRangeCompare(ITupleReference tupleA, ITupleReference tupleB, int startFieldIndex, int numFields) {
+        for (int i = startFieldIndex; i < startFieldIndex + numFields; i++) {
+            int cmp = cmps[i].compare(tupleA.getFieldData(i), tupleA.getFieldStart(i), tupleA.getFieldLength(i),
+                    tupleB.getFieldData(i), tupleB.getFieldStart(i), tupleB.getFieldLength(i));
+            if (cmp < 0)
+                return -1;
+            else if (cmp > 0)
+                return 1;
+        }
+        return 0;
+    }
+
+    public String printTuple(ITupleReference tuple, ISerializerDeserializer[] fields) throws HyracksDataException {
+        StringBuilder strBuilder = new StringBuilder();
+        for (int i = 0; i < tuple.getFieldCount(); i++) {
+            ByteArrayInputStream inStream = new ByteArrayInputStream(tuple.getFieldData(i), tuple.getFieldStart(i),
+                    tuple.getFieldLength(i));
+            DataInput dataIn = new DataInputStream(inStream);
+            Object o = fields[i].deserialize(dataIn);
+            strBuilder.append(o.toString() + " ");
+        }
+        return strBuilder.toString();
+    }
+
+    public IBinaryComparator[] getComparators() {
+        return cmps;
+    }
+
+    public int getKeyFieldCount() {
+        return cmps.length;
+    }
+
+    public void setComparators(IBinaryComparator[] cmps) {
+        this.cmps = cmps;
+    }
+
+    public int getFieldCount() {
+        return typeTraits.length;
+    }
+
+    public ITypeTrait[] getTypeTraits() {
+        return typeTraits;
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/SlotOffTupleOff.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/SlotOffTupleOff.java
new file mode 100644
index 0000000..4fc1861
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/SlotOffTupleOff.java
@@ -0,0 +1,33 @@
+/*
+ * 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.ophelpers;
+
+public class SlotOffTupleOff implements Comparable<SlotOffTupleOff> {
+    public int tupleIndex;
+    public int slotOff;
+    public int tupleOff;
+
+    public SlotOffTupleOff(int tupleIndex, int slotOff, int recOff) {
+        this.tupleIndex = tupleIndex;
+        this.slotOff = slotOff;
+        this.tupleOff = recOff;
+    }
+
+    @Override
+    public int compareTo(SlotOffTupleOff o) {
+        return tupleOff - o.tupleOff;
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleReference.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleReference.java
new file mode 100644
index 0000000..f9e00ac
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleReference.java
@@ -0,0 +1,94 @@
+/*
+ * 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.tuples;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+
+public class SimpleTupleReference implements ITreeIndexTupleReference {
+
+    protected ByteBuffer buf;
+    protected int fieldStartIndex;
+    protected int fieldCount;
+    protected int tupleStartOff;
+    protected int nullFlagsBytes;
+    protected int fieldSlotsBytes;
+
+    @Override
+    public void resetByTupleOffset(ByteBuffer buf, int tupleStartOff) {
+        this.buf = buf;
+        this.tupleStartOff = tupleStartOff;
+    }
+
+    @Override
+    public void resetByTupleIndex(ITreeIndexFrame frame, int tupleIndex) {
+        resetByTupleOffset(frame.getBuffer(), frame.getTupleOffset(tupleIndex));
+    }
+
+    @Override
+    public void setFieldCount(int fieldCount) {
+        this.fieldCount = fieldCount;
+        nullFlagsBytes = getNullFlagsBytes();
+        fieldSlotsBytes = getFieldSlotsBytes();
+        fieldStartIndex = 0;
+    }
+
+    @Override
+    public void setFieldCount(int fieldStartIndex, int fieldCount) {
+        this.fieldCount = fieldCount;
+        this.fieldStartIndex = fieldStartIndex;
+    }
+
+    @Override
+    public int getFieldCount() {
+        return fieldCount;
+    }
+
+    @Override
+    public byte[] getFieldData(int fIdx) {
+        return buf.array();
+    }
+
+    @Override
+    public int getFieldLength(int fIdx) {
+        if (fIdx == 0) {
+            return buf.getShort(tupleStartOff + nullFlagsBytes);
+        } else {
+            return buf.getShort(tupleStartOff + nullFlagsBytes + fIdx * 2)
+                    - buf.getShort(tupleStartOff + nullFlagsBytes + ((fIdx - 1) * 2));
+        }
+    }
+
+    @Override
+    public int getFieldStart(int fIdx) {
+        if (fIdx == 0) {
+            return tupleStartOff + nullFlagsBytes + fieldSlotsBytes;
+        } else {
+            return tupleStartOff + nullFlagsBytes + fieldSlotsBytes
+                    + buf.getShort(tupleStartOff + nullFlagsBytes + ((fIdx - 1) * 2));
+        }
+    }
+
+    protected int getNullFlagsBytes() {
+        return (int) Math.ceil(fieldCount / 8.0);
+    }
+
+    protected int getFieldSlotsBytes() {
+        return fieldCount * 2;
+    }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriter.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriter.java
new file mode 100644
index 0000000..1730c4a
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriter.java
@@ -0,0 +1,110 @@
+/*
+ * 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.tuples;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+
+public class SimpleTupleWriter implements ITreeIndexTupleWriter {
+
+    @Override
+    public int bytesRequired(ITupleReference tuple) {
+        int bytes = getNullFlagsBytes(tuple) + getFieldSlotsBytes(tuple);
+        for (int i = 0; i < tuple.getFieldCount(); i++) {
+            bytes += tuple.getFieldLength(i);
+        }
+        return bytes;
+    }
+
+    @Override
+    public int bytesRequired(ITupleReference tuple, int startField, int numFields) {
+        int bytes = getNullFlagsBytes(tuple, startField, numFields) + getFieldSlotsBytes(tuple, startField, numFields);
+        for (int i = startField; i < startField + numFields; i++) {
+            bytes += tuple.getFieldLength(i);
+        }
+        return bytes;
+    }
+
+    @Override
+    public ITreeIndexTupleReference createTupleReference() {
+        return new SimpleTupleReference();
+    }
+
+    @Override
+    public int writeTuple(ITupleReference tuple, ByteBuffer targetBuf, int targetOff) {
+        int runner = targetOff;
+        int nullFlagsBytes = getNullFlagsBytes(tuple);
+        int fieldSlotsBytes = getFieldSlotsBytes(tuple);
+        for (int i = 0; i < nullFlagsBytes; i++) {
+            targetBuf.put(runner++, (byte) 0);
+        }
+        runner += fieldSlotsBytes;
+
+        int fieldEndOff = 0;
+        for (int i = 0; i < tuple.getFieldCount(); i++) {
+            System.arraycopy(tuple.getFieldData(i), tuple.getFieldStart(i), targetBuf.array(), runner,
+                    tuple.getFieldLength(i));
+            fieldEndOff += tuple.getFieldLength(i);
+            runner += tuple.getFieldLength(i);
+            targetBuf.putShort(targetOff + nullFlagsBytes + i * 2, (short) fieldEndOff);
+        }
+
+        return runner - targetOff;
+    }
+
+    @Override
+    public int writeTupleFields(ITupleReference tuple, int startField, int numFields, ByteBuffer targetBuf,
+            int targetOff) {
+        int runner = targetOff;
+        int nullFlagsBytes = getNullFlagsBytes(tuple, startField, numFields);
+        for (int i = 0; i < nullFlagsBytes; i++) {
+            targetBuf.put(runner++, (byte) 0);
+        }
+        runner += getFieldSlotsBytes(tuple, startField, numFields);
+
+        int fieldEndOff = 0;
+        int fieldCounter = 0;
+        for (int i = startField; i < startField + numFields; i++) {
+            System.arraycopy(tuple.getFieldData(i), tuple.getFieldStart(i), targetBuf.array(), runner,
+                    tuple.getFieldLength(i));
+            fieldEndOff += tuple.getFieldLength(i);
+            runner += tuple.getFieldLength(i);
+            targetBuf.putShort(targetOff + nullFlagsBytes + fieldCounter * 2, (short) fieldEndOff);
+            fieldCounter++;
+        }
+
+        return runner - targetOff;
+    }
+
+    protected int getNullFlagsBytes(ITupleReference tuple) {
+        return (int) Math.ceil((double) tuple.getFieldCount() / 8.0);
+    }
+
+    protected int getFieldSlotsBytes(ITupleReference tuple) {
+        return tuple.getFieldCount() * 2;
+    }
+
+    protected int getNullFlagsBytes(ITupleReference tuple, int startField, int numFields) {
+        return (int) Math.ceil((double) numFields / 8.0);
+    }
+
+    protected int getFieldSlotsBytes(ITupleReference tuple, int startField, int numFields) {
+        return numFields * 2;
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriterFactory.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriterFactory.java
new file mode 100644
index 0000000..ebb2905
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriterFactory.java
@@ -0,0 +1,30 @@
+/*
+ * 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.tuples;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
+
+public class SimpleTupleWriterFactory implements ITreeIndexTupleWriterFactory {
+
+    private static final long serialVersionUID = 1L;
+
+    @Override
+    public ITreeIndexTupleWriter createTupleWriter() {
+        return new SimpleTupleWriter();
+    }
+
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleReference.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleReference.java
new file mode 100644
index 0000000..4f571b3
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleReference.java
@@ -0,0 +1,120 @@
+/*
+ * 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.tuples;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+
+public class TypeAwareTupleReference implements ITreeIndexTupleReference {
+    protected ByteBuffer buf;
+    protected int fieldStartIndex;
+    protected int fieldCount;
+    protected int tupleStartOff;
+    protected int nullFlagsBytes;
+    protected int dataStartOff;
+
+    protected ITypeTrait[] typeTraits;
+    protected VarLenIntEncoderDecoder encDec = new VarLenIntEncoderDecoder();
+    protected int[] decodedFieldSlots;
+
+    public TypeAwareTupleReference(ITypeTrait[] typeTraits) {
+        this.typeTraits = typeTraits;
+        this.fieldStartIndex = 0;
+    }
+
+    @Override
+    public void resetByTupleOffset(ByteBuffer buf, int tupleStartOff) {
+        this.buf = buf;
+        this.tupleStartOff = tupleStartOff;
+
+        // decode field slots
+        int field = 0;
+        int cumul = 0;
+        int end = fieldStartIndex + fieldCount;
+        encDec.reset(buf.array(), tupleStartOff + nullFlagsBytes);
+        for (int i = fieldStartIndex; i < end; i++) {
+            int staticDataLen = typeTraits[i].getStaticallyKnownDataLength();
+            if (staticDataLen == ITypeTrait.VARIABLE_LENGTH) {
+                cumul += encDec.decode();
+                decodedFieldSlots[field++] = cumul;
+            } else {
+                cumul += staticDataLen;
+                decodedFieldSlots[field++] = cumul;
+            }
+        }
+        dataStartOff = encDec.getPos();
+    }
+
+    @Override
+    public void resetByTupleIndex(ITreeIndexFrame frame, int tupleIndex) {
+        resetByTupleOffset(frame.getBuffer(), frame.getTupleOffset(tupleIndex));
+    }
+
+    @Override
+    public void setFieldCount(int fieldCount) {
+        this.fieldCount = fieldCount;
+        if (decodedFieldSlots == null) {
+            decodedFieldSlots = new int[fieldCount];
+        } else {
+            if (fieldCount > decodedFieldSlots.length) {
+                decodedFieldSlots = new int[fieldCount];
+            }
+        }
+        nullFlagsBytes = getNullFlagsBytes();
+        this.fieldStartIndex = 0;
+    }
+
+    @Override
+    public void setFieldCount(int fieldStartIndex, int fieldCount) {
+        setFieldCount(fieldCount);
+        this.fieldStartIndex = fieldStartIndex;
+    }
+
+    @Override
+    public int getFieldCount() {
+        return fieldCount;
+    }
+
+    @Override
+    public byte[] getFieldData(int fIdx) {
+        return buf.array();
+    }
+
+    @Override
+    public int getFieldLength(int fIdx) {
+        if (fIdx == 0) {
+            return decodedFieldSlots[0];
+        } else {
+            return decodedFieldSlots[fIdx] - decodedFieldSlots[fIdx - 1];
+        }
+    }
+
+    @Override
+    public int getFieldStart(int fIdx) {
+        if (fIdx == 0) {
+            return dataStartOff;
+        } else {
+            return dataStartOff + decodedFieldSlots[fIdx - 1];
+        }
+    }
+
+    protected int getNullFlagsBytes() {
+        return (int) Math.ceil(fieldCount / 8.0);
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriter.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriter.java
new file mode 100644
index 0000000..81b48e5
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriter.java
@@ -0,0 +1,148 @@
+/*
+ * 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.tuples;
+
+import java.nio.ByteBuffer;
+
+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.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+
+public class TypeAwareTupleWriter implements ITreeIndexTupleWriter {
+
+    protected ITypeTrait[] typeTraits;
+    protected VarLenIntEncoderDecoder encDec = new VarLenIntEncoderDecoder();
+
+    public TypeAwareTupleWriter(ITypeTrait[] typeTraits) {
+        this.typeTraits = typeTraits;
+    }
+
+    @Override
+    public int bytesRequired(ITupleReference tuple) {
+        int bytes = getNullFlagsBytes(tuple) + getFieldSlotsBytes(tuple);
+        for (int i = 0; i < tuple.getFieldCount(); i++) {
+            bytes += tuple.getFieldLength(i);
+        }
+        return bytes;
+    }
+
+    @Override
+    public int bytesRequired(ITupleReference tuple, int startField, int numFields) {
+        int bytes = getNullFlagsBytes(numFields) + getFieldSlotsBytes(tuple, startField, numFields);
+        for (int i = startField; i < startField + numFields; i++) {
+            bytes += tuple.getFieldLength(i);
+        }
+        return bytes;
+    }
+
+    @Override
+    public ITreeIndexTupleReference createTupleReference() {
+        return new TypeAwareTupleReference(typeTraits);
+    }
+
+    @Override
+    public int writeTuple(ITupleReference tuple, ByteBuffer targetBuf, int targetOff) {
+        int runner = targetOff;
+        int nullFlagsBytes = getNullFlagsBytes(tuple);
+        // write null indicator bits
+        for (int i = 0; i < nullFlagsBytes; i++) {
+            targetBuf.put(runner++, (byte) 0);
+        }
+
+        // write field slots for variable length fields
+        encDec.reset(targetBuf.array(), runner);
+        for (int i = 0; i < tuple.getFieldCount(); i++) {
+            if (typeTraits[i].getStaticallyKnownDataLength() == ITypeTrait.VARIABLE_LENGTH) {
+                encDec.encode(tuple.getFieldLength(i));
+            }
+        }
+        runner = encDec.getPos();
+
+        // write data fields
+        for (int i = 0; i < tuple.getFieldCount(); i++) {
+            System.arraycopy(tuple.getFieldData(i), tuple.getFieldStart(i), targetBuf.array(), runner,
+                    tuple.getFieldLength(i));
+            runner += tuple.getFieldLength(i);
+        }
+
+        return runner - targetOff;
+    }
+
+    @Override
+    public int writeTupleFields(ITupleReference tuple, int startField, int numFields, ByteBuffer targetBuf,
+            int targetOff) {
+        int runner = targetOff;
+        int nullFlagsBytes = getNullFlagsBytes(numFields);
+        // write null indicator bits
+        for (int i = 0; i < nullFlagsBytes; i++) {
+            targetBuf.put(runner++, (byte) 0);
+        }
+
+        // write field slots for variable length fields
+        encDec.reset(targetBuf.array(), runner);
+        for (int i = startField; i < startField + numFields; i++) {
+            if (typeTraits[i].getStaticallyKnownDataLength() == ITypeTrait.VARIABLE_LENGTH) {
+                encDec.encode(tuple.getFieldLength(i));
+            }
+        }
+        runner = encDec.getPos();
+
+        for (int i = startField; i < startField + numFields; i++) {
+            System.arraycopy(tuple.getFieldData(i), tuple.getFieldStart(i), targetBuf.array(), runner,
+                    tuple.getFieldLength(i));
+            runner += tuple.getFieldLength(i);
+        }
+
+        return runner - targetOff;
+    }
+
+    protected int getNullFlagsBytes(ITupleReference tuple) {
+        return (int) Math.ceil((double) tuple.getFieldCount() / 8.0);
+    }
+
+    protected int getFieldSlotsBytes(ITupleReference tuple) {
+        int fieldSlotBytes = 0;
+        for (int i = 0; i < tuple.getFieldCount(); i++) {
+            if (typeTraits[i].getStaticallyKnownDataLength() == ITypeTrait.VARIABLE_LENGTH) {
+                fieldSlotBytes += encDec.getBytesRequired(tuple.getFieldLength(i));
+            }
+        }
+        return fieldSlotBytes;
+    }
+
+    protected int getNullFlagsBytes(int numFields) {
+        return (int) Math.ceil((double) numFields / 8.0);
+    }
+
+    protected int getFieldSlotsBytes(ITupleReference tuple, int startField, int numFields) {
+        int fieldSlotBytes = 0;
+        for (int i = startField; i < startField + numFields; i++) {
+            if (typeTraits[i].getStaticallyKnownDataLength() == ITypeTrait.VARIABLE_LENGTH) {
+                fieldSlotBytes += encDec.getBytesRequired(tuple.getFieldLength(i));
+            }
+        }
+        return fieldSlotBytes;
+    }
+
+    public ITypeTrait[] getTypeTraits() {
+        return typeTraits;
+    }
+
+    public void setTypeTraits(ITypeTrait[] typeTraits) {
+        this.typeTraits = typeTraits;
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriterFactory.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriterFactory.java
new file mode 100644
index 0000000..82072ae
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriterFactory.java
@@ -0,0 +1,36 @@
+/*
+ * 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.tuples;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
+
+public class TypeAwareTupleWriterFactory implements ITreeIndexTupleWriterFactory {
+
+    private static final long serialVersionUID = 1L;
+    private ITypeTrait[] typeTraits;
+
+    public TypeAwareTupleWriterFactory(ITypeTrait[] typeTraits) {
+        this.typeTraits = typeTraits;
+    }
+
+    @Override
+    public ITreeIndexTupleWriter createTupleWriter() {
+        return new TypeAwareTupleWriter(typeTraits);
+    }
+
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/VarLenIntEncoderDecoder.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/VarLenIntEncoderDecoder.java
new file mode 100644
index 0000000..d266d41
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/VarLenIntEncoderDecoder.java
@@ -0,0 +1,88 @@
+/*
+ * 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.tuples;
+
+// encodes positive integers in a variable-byte format
+
+public class VarLenIntEncoderDecoder {
+    public static final int ENCODE_MASK = 0x0000007F;
+    public static final byte CONTINUE_CHUNK = (byte) 0x80;
+    public static final byte DECODE_MASK = (byte) 0x7F;
+
+    private byte[] encTmp = new byte[5];
+
+    private int pos;
+    private byte[] bytes;
+
+    public void reset(byte[] bytes, int pos) {
+        this.bytes = bytes;
+        this.pos = pos;
+    }
+
+    public int encode(int val) {
+        int origPos = 0;
+        int tmpPos = 0;
+        while (val > ENCODE_MASK) {
+            encTmp[tmpPos++] = (byte) (val & ENCODE_MASK);
+            val = val >>> 7;
+        }
+        encTmp[tmpPos++] = (byte) (val);
+
+        // reverse order to optimize for decoding speed
+        for (int i = 0; i < tmpPos - 1; i++) {
+            bytes[pos++] = (byte) (encTmp[tmpPos - 1 - i] | CONTINUE_CHUNK);
+        }
+        bytes[pos++] = encTmp[0];
+
+        return pos - origPos;
+    }
+
+    public int decode() {
+        int sum = 0;
+        while ((bytes[pos] & CONTINUE_CHUNK) == CONTINUE_CHUNK) {
+            sum = (sum + (bytes[pos] & DECODE_MASK)) << 7;
+            pos++;
+        }
+        sum += bytes[pos++];
+        return sum;
+    }
+
+    // calculate the number of bytes needed for encoding
+    public int getBytesRequired(int val) {
+        int byteCount = 0;
+        while (val > ENCODE_MASK) {
+            val = val >>> 7;
+            byteCount++;
+        }
+        return byteCount + 1;
+    }
+
+    public int getPos() {
+        return pos;
+    }
+
+    // fast encoding, slow decoding version
+    /*
+     * public void encode(int val) { while(val > ENCODE_MASK) { bytes[pos++] =
+     * (byte)(((byte)(val & ENCODE_MASK)) | CONTINUE_CHUNK); val = val >>> 7; }
+     * bytes[pos++] = (byte)(val); }
+     * 
+     * public int decode() { int sum = 0; int shift = 0; while( (bytes[pos] &
+     * CONTINUE_CHUNK) == CONTINUE_CHUNK) { sum = (sum + (bytes[pos] &
+     * DECODE_MASK)) << 7 * shift++; pos++; } sum += bytes[pos++] << 7 * shift;
+     * return sum; }
+     */
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java
new file mode 100644
index 0000000..eb261da
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java
@@ -0,0 +1,84 @@
+package edu.uci.ics.hyracks.storage.am.common.utility;
+
+import java.util.ArrayList;
+import java.util.Random;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
+
+public class TreeIndexBufferCacheWarmup {
+    private final IBufferCache bufferCache;
+    private final IFreePageManager freePageManager;
+    private final int fileId;
+    private final ArrayList<IntArrayList> pagesByLevel = new ArrayList<IntArrayList>();
+    private final Random rnd = new Random();
+
+    public TreeIndexBufferCacheWarmup(IBufferCache bufferCache, IFreePageManager freePageManager, int fileId) {
+        this.bufferCache = bufferCache;
+        this.freePageManager = freePageManager;
+        this.fileId = fileId;
+    }
+
+    public void warmup(ITreeIndexFrame frame, ITreeIndexMetaDataFrame metaFrame, int[] warmupTreeLevels,
+            int[] warmupRepeats) throws HyracksDataException {
+        bufferCache.openFile(fileId);
+
+        // scan entire file to determine pages in each level
+        int maxPageId = freePageManager.getMaxPage(metaFrame);
+        for (int pageId = 0; pageId <= maxPageId; pageId++) {
+            ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+            page.acquireReadLatch();
+            try {
+                frame.setPage(page);
+                byte level = frame.getLevel();
+                while (level >= pagesByLevel.size()) {
+                    pagesByLevel.add(new IntArrayList(100, 100));
+                }
+                if (level >= 0) {
+                    // System.out.println("ADDING: " + level + " " + pageId);
+                    pagesByLevel.get(level).add(pageId);
+                }
+            } finally {
+                page.releaseReadLatch();
+                bufferCache.unpin(page);
+            }
+        }
+
+        // pin certain pages again to simulate frequent access
+        for (int i = 0; i < warmupTreeLevels.length; i++) {
+            if (warmupTreeLevels[i] < pagesByLevel.size()) {
+                int repeats = warmupRepeats[i];
+                IntArrayList pageIds = pagesByLevel.get(warmupTreeLevels[i]);
+                int[] remainingPageIds = new int[pageIds.size()];
+                for (int r = 0; r < repeats; r++) {
+                    for (int j = 0; j < pageIds.size(); j++) {
+                        remainingPageIds[j] = pageIds.get(j);
+                    }
+
+                    int remainingLength = pageIds.size();
+                    for (int j = 0; j < pageIds.size(); j++) {
+                        int index = Math.abs(rnd.nextInt()) % remainingLength;
+                        int pageId = remainingPageIds[index];
+
+                        // pin & latch then immediately unlatch & unpin
+                        ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+                        page.acquireReadLatch();
+                        page.releaseReadLatch();
+                        bufferCache.unpin(page);
+
+                        remainingPageIds[index] = remainingPageIds[remainingLength - 1];
+                        remainingLength--;
+                    }
+                }
+            }
+        }
+
+        bufferCache.closeFile(fileId);
+    }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStats.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStats.java
new file mode 100644
index 0000000..5b01b2d
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStats.java
@@ -0,0 +1,134 @@
+package edu.uci.ics.hyracks.storage.am.common.utility;
+
+import java.text.DecimalFormat;
+
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+
+public class TreeIndexStats {
+
+    private TreeIndexNodeTypeStats rootStats = new TreeIndexNodeTypeStats();
+    private TreeIndexNodeTypeStats interiorStats = new TreeIndexNodeTypeStats();
+    private TreeIndexNodeTypeStats leafStats = new TreeIndexNodeTypeStats();
+
+    private int freePages = 0;
+    private int metaPages = 0;
+    private int treeLevels = 0;
+
+    public void begin() {
+        rootStats.clear();
+        interiorStats.clear();
+        leafStats.clear();
+        freePages = 0;
+        metaPages = 0;
+        treeLevels = 0;
+    }
+
+    public void addRoot(ITreeIndexFrame frame) {
+        treeLevels = frame.getLevel() + 1;
+        rootStats.add(frame);
+    }
+
+    public void add(ITreeIndexFrame frame) {
+        if (frame.isLeaf()) {
+            leafStats.add(frame);
+        } else if (frame.isInterior()) {
+            interiorStats.add(frame);
+        }
+    }
+
+    public void add(ITreeIndexMetaDataFrame metaFrame, IFreePageManager freePageManager) {
+        if (freePageManager.isFreePage(metaFrame)) {
+            freePages++;
+        } else if (freePageManager.isMetaPage(metaFrame)) {
+            metaPages++;
+        }
+    }
+
+    public void end() {
+        // nothing here currently
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder strBuilder = new StringBuilder();
+        DecimalFormat df = new DecimalFormat("#####.##");
+
+        strBuilder.append("TREE LEVELS:  " + treeLevels + "\n");
+        strBuilder.append("FREE PAGES :  " + freePages + "\n");
+        strBuilder.append("META PAGES :  " + metaPages + "\n");
+        long totalPages = interiorStats.getNumPages() + leafStats.getNumPages() + freePages + metaPages;
+        strBuilder.append("TOTAL PAGES : " + totalPages + "\n");
+
+        strBuilder.append("\n");
+        strBuilder.append("ROOT STATS" + "\n");
+        strBuilder.append("NUM TUPLES:      " + rootStats.getNumTuples() + "\n");
+        strBuilder.append("FILL FACTOR    : " + df.format(rootStats.getAvgFillFactor()) + "\n");
+
+        if (interiorStats.getNumPages() > 0) {
+            strBuilder.append("\n");
+            strBuilder.append("INTERIOR STATS" + "\n");
+            strBuilder.append("NUM PAGES:       " + interiorStats.getNumPages() + "\n");
+            strBuilder.append("NUM TUPLES:      " + interiorStats.getNumTuples() + "\n");
+            strBuilder.append("AVG TUPLES/PAGE: " + df.format(interiorStats.getAvgNumTuples()) + "\n");
+            strBuilder.append("AVG FILL FACTOR: " + df.format(interiorStats.getAvgFillFactor()) + "\n");
+        }
+
+        if (leafStats.getNumPages() > 0) {
+            strBuilder.append("\n");
+            strBuilder.append("LEAF STATS" + "\n");
+            strBuilder.append("NUM PAGES:       " + df.format(leafStats.getNumPages()) + "\n");
+            strBuilder.append("NUM TUPLES:      " + df.format(leafStats.getNumTuples()) + "\n");
+            strBuilder.append("AVG TUPLES/PAGE: " + df.format(leafStats.getAvgNumTuples()) + "\n");
+            strBuilder.append("AVG FILL FACTOR: " + df.format(leafStats.getAvgFillFactor()) + "\n");
+        }
+
+        return strBuilder.toString();
+    }
+
+    public class TreeIndexNodeTypeStats {
+        private long numTuples;
+        private long sumTuplesSizes;
+        private long numPages;
+        private double sumFillFactors;
+
+        public void clear() {
+            numTuples = 0;
+            sumTuplesSizes = 0;
+            numPages = 0;
+        }
+
+        public void add(ITreeIndexFrame frame) {
+            numPages++;
+            numTuples += frame.getTupleCount();
+            sumFillFactors += (double) (frame.getBuffer().capacity() - frame.getTotalFreeSpace())
+                    / (double) frame.getBuffer().capacity();
+        }
+
+        public long getNumTuples() {
+            return numTuples;
+        }
+
+        public long getSumTupleSizes() {
+            return sumTuplesSizes;
+        }
+
+        public long getNumPages() {
+            return numPages;
+        }
+
+        public double getAvgNumTuples() {
+            return (double) numTuples / (double) numPages;
+        }
+
+        public double getAvgTupleSize() {
+            return (double) sumTuplesSizes / (double) numTuples;
+        }
+
+        public double getAvgFillFactor() {
+            return sumFillFactors / numPages;
+        }
+    }
+
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStatsGatherer.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStatsGatherer.java
new file mode 100644
index 0000000..fc0ab5e
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStatsGatherer.java
@@ -0,0 +1,70 @@
+package edu.uci.ics.hyracks.storage.am.common.utility;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
+
+public class TreeIndexStatsGatherer {
+
+    private final TreeIndexStats treeIndexStats = new TreeIndexStats();
+    private final IBufferCache bufferCache;
+    private final IFreePageManager freePageManager;
+    private final int fileId;
+    private final int rootPage;
+
+    public TreeIndexStatsGatherer(IBufferCache bufferCache, IFreePageManager freePageManager, int fileId, int rootPage) {
+        this.bufferCache = bufferCache;
+        this.freePageManager = freePageManager;
+        this.fileId = fileId;
+        this.rootPage = rootPage;
+    }
+
+    public TreeIndexStats gatherStats(ITreeIndexFrame leafFrame, ITreeIndexFrame interiorFrame,
+            ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
+
+        bufferCache.openFile(fileId);
+
+        treeIndexStats.begin();
+
+        int maxPageId = freePageManager.getMaxPage(metaFrame);
+        for (int pageId = 0; pageId <= maxPageId; pageId++) {
+            ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+            page.acquireReadLatch();
+            try {
+                metaFrame.setPage(page);
+                leafFrame.setPage(page);
+                interiorFrame.setPage(page);
+
+                if (leafFrame.isLeaf()) {
+                    if (pageId == rootPage) {
+                        treeIndexStats.addRoot(leafFrame);
+                    } else {
+                        treeIndexStats.add(leafFrame);
+                    }
+                } else if (interiorFrame.isInterior()) {
+                    if (pageId == rootPage) {
+                        treeIndexStats.addRoot(interiorFrame);
+                    } else {
+                        treeIndexStats.add(interiorFrame);
+                    }
+                } else {
+                    treeIndexStats.add(metaFrame, freePageManager);
+                }
+
+            } finally {
+                page.releaseReadLatch();
+                bufferCache.unpin(page);
+            }
+        }
+
+        treeIndexStats.end();
+
+        bufferCache.closeFile(fileId);
+
+        return treeIndexStats;
+    }
+}