diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/pom.xml b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/pom.xml
new file mode 100644
index 0000000..fc22c77
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/pom.xml
@@ -0,0 +1,50 @@
+<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-btree-test</artifactId>
+  <version>0.2.2-SNAPSHOT</version>
+  <name>hyracks-storage-am-btree-test</name>
+
+  <parent>
+    <groupId>edu.uci.ics.hyracks</groupId>
+    <artifactId>hyracks-tests</artifactId>
+    <version>0.2.2-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>junit</groupId>
+  		<artifactId>junit</artifactId>
+  		<version>4.8.1</version>
+  		<type>jar</type>
+  		<scope>test</scope>
+  	</dependency>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-storage-am-btree</artifactId>
+  		<version>0.2.2-SNAPSHOT</version>
+  		<type>jar</type>
+  		<scope>compile</scope>
+  	</dependency>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-test-support</artifactId>
+  		<version>0.2.2-SNAPSHOT</version>
+  		<type>jar</type>
+  		<scope>test</scope>
+  	</dependency>
+  </dependencies>
+</project>
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeBulkLoadTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeBulkLoadTest.java
new file mode 100644
index 0000000..11c47c7
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeBulkLoadTest.java
@@ -0,0 +1,61 @@
+/*
+ * 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.btree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexBulkLoadTest;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
+
+@SuppressWarnings("rawtypes")
+public class BTreeBulkLoadTest extends OrderedIndexBulkLoadTest {
+
+    public BTreeBulkLoadTest() {
+        super(BTreeTestHarness.LEAF_FRAMES_TO_TEST, 1);
+    }
+
+    private final BTreeTestHarness harness = new BTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+            BTreeLeafFrameType leafType) throws Exception {
+        return BTreeTestContext.create(harness.getBufferCache(), harness.getBTreeFileId(), fieldSerdes, numKeys,
+                leafType);
+    }
+
+    @Override
+    protected Random getRandom() {
+        return harness.getRandom();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java
new file mode 100644
index 0000000..0205540
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java
@@ -0,0 +1,61 @@
+/*
+ * 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.btree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexDeleteTest;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
+
+@SuppressWarnings("rawtypes")
+public class BTreeDeleteTest extends OrderedIndexDeleteTest {
+
+    public BTreeDeleteTest() {
+        super(BTreeTestHarness.LEAF_FRAMES_TO_TEST);
+    }
+
+    private final BTreeTestHarness harness = new BTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+            BTreeLeafFrameType leafType) throws Exception {
+        return BTreeTestContext.create(harness.getBufferCache(), harness.getBTreeFileId(), fieldSerdes, numKeys,
+                leafType);
+    }
+
+    @Override
+    protected Random getRandom() {
+        return harness.getRandom();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeExamplesTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeExamplesTest.java
new file mode 100644
index 0000000..f4f8b12
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeExamplesTest.java
@@ -0,0 +1,52 @@
+/*
+ * 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.btree;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexExamplesTest;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+
+public class BTreeExamplesTest extends OrderedIndexExamplesTest {
+    private final BTreeTestHarness harness = new BTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+    
+    protected ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparatorFactory[] cmpFactories) throws TreeIndexException {
+        return BTreeUtils.createBTree(harness.getBufferCache(), harness.getOpCallback(), typeTraits, cmpFactories,
+                BTreeLeafFrameType.REGULAR_NSM);
+    }
+    
+    protected int getIndexFileId() {
+        return harness.getBTreeFileId();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java
new file mode 100644
index 0000000..0b6cf4d
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java
@@ -0,0 +1,71 @@
+/*
+ * 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.btree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexInsertTest;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
+
+/**
+ * Tests the BTree insert operation with strings and integer fields using
+ * various numbers of key and payload fields.
+ * 
+ * Each tests first fills a BTree with randomly generated tuples. We compare the
+ * following operations against expected results: 1. Point searches for all
+ * tuples. 2. Ordered scan. 3. Disk-order scan. 4. Range search (and prefix
+ * search for composite keys).
+ * 
+ */
+@SuppressWarnings("rawtypes")
+public class BTreeInsertTest extends OrderedIndexInsertTest {
+
+    public BTreeInsertTest() {
+        super(BTreeTestHarness.LEAF_FRAMES_TO_TEST);
+    }
+
+    private final BTreeTestHarness harness = new BTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+            BTreeLeafFrameType leafType) throws Exception {
+        return BTreeTestContext.create(harness.getBufferCache(), harness.getBTreeFileId(), fieldSerdes, numKeys,
+                leafType);
+    }
+
+    @Override
+    protected Random getRandom() {
+        return harness.getRandom();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeSearchCursorTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeSearchCursorTest.java
new file mode 100644
index 0000000..4003cf1
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeSearchCursorTest.java
@@ -0,0 +1,421 @@
+/*
+ * 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.btree;
+
+import java.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Random;
+import java.util.TreeSet;
+import java.util.logging.Level;
+
+import org.junit.Before;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+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.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+public class BTreeSearchCursorTest extends AbstractBTreeTest {
+    // Declare fields
+    int fieldCount = 2;
+    ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+
+    TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(typeTraits);
+    ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+    ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
+
+    Random rnd = new Random(50);
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        super.setUp();
+        typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+        typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+    }
+
+    @Test
+    public void uniqueIndexTest() throws Exception {
+        if (LOGGER.isLoggable(Level.INFO)) {
+            LOGGER.info("TESTING RANGE SEARCH CURSOR ON UNIQUE INDEX");
+        }
+
+        IBufferCache bufferCache = harness.getBufferCache();
+        int btreeFileId = harness.getBTreeFileId();
+        
+        // declare keys
+        int keyFieldCount = 1;
+        IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+        cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+        ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+        ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+
+        IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) leafFrameFactory.createFrame();
+        IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame) interiorFrameFactory.createFrame();
+
+        IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+
+        BTree btree = new BTree(bufferCache, NoOpOperationCallback.INSTANCE, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
+        btree.create(btreeFileId);
+        btree.open(btreeFileId);
+
+        ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
+        ArrayTupleReference tuple = new ArrayTupleReference();
+
+        ITreeIndexAccessor indexAccessor = btree.createAccessor();
+
+        // generate keys
+        int numKeys = 50;
+        int maxKey = 1000;
+        TreeSet<Integer> uniqueKeys = new TreeSet<Integer>();
+        ArrayList<Integer> keys = new ArrayList<Integer>();
+        while (uniqueKeys.size() < numKeys) {
+            int key = rnd.nextInt() % maxKey;
+            uniqueKeys.add(key);
+        }
+        for (Integer i : uniqueKeys) {
+            keys.add(i);
+        }
+
+        // insert keys into btree
+        for (int i = 0; i < keys.size(); i++) {
+
+            TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i);
+            tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
+
+            try {
+                indexAccessor.insert(tuple);
+            } catch (BTreeException e) {
+            } catch (Exception e) {
+                e.printStackTrace();
+            }
+        }
+
+        // btree.printTree(leafFrame, interiorFrame, recDescSers);
+
+        int minSearchKey = -100;
+        int maxSearchKey = 100;
+
+        // forward searches
+        performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, true, false);
+        performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, false, true, false);
+        performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, false, false);
+        performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, true, false);
+
+        btree.close();
+    }
+
+    @Test
+    public void nonUniqueIndexTest() throws Exception {
+        if (LOGGER.isLoggable(Level.INFO)) {
+            LOGGER.info("TESTING RANGE SEARCH CURSOR ON NONUNIQUE INDEX");
+        }
+
+        IBufferCache bufferCache = harness.getBufferCache();
+        int btreeFileId = harness.getBTreeFileId();
+        
+        // declare keys
+        int keyFieldCount = 2;
+        IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+        cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        cmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+        ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+        ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+
+        IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) leafFrameFactory.createFrame();
+        IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame) interiorFrameFactory.createFrame();
+
+        IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+
+        BTree btree = new BTree(bufferCache, NoOpOperationCallback.INSTANCE, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
+        btree.create(btreeFileId);
+        btree.open(btreeFileId);
+
+        ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
+        ArrayTupleReference tuple = new ArrayTupleReference();
+
+        ITreeIndexAccessor indexAccessor = btree.createAccessor();
+
+        // generate keys
+        int numKeys = 50;
+        int maxKey = 10;
+        ArrayList<Integer> keys = new ArrayList<Integer>();
+        for (int i = 0; i < numKeys; i++) {
+            int k = rnd.nextInt() % maxKey;
+            keys.add(k);
+        }
+        Collections.sort(keys);
+
+        // insert keys into btree
+        for (int i = 0; i < keys.size(); i++) {
+
+            TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i);
+            tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
+
+            try {
+                indexAccessor.insert(tuple);
+            } catch (BTreeException e) {
+            } catch (Exception e) {
+                e.printStackTrace();
+            }
+        }
+
+        // btree.printTree(leafFrame, interiorFrame, recDescSers);
+
+        int minSearchKey = -100;
+        int maxSearchKey = 100;
+
+        // forward searches
+        performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, true, false);
+        performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, false, true, false);
+        performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, false, false);
+        performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, true, false);
+
+        btree.close();
+    }
+
+    @Test
+    public void nonUniqueFieldPrefixIndexTest() throws Exception {
+        if (LOGGER.isLoggable(Level.INFO)) {
+            LOGGER.info("TESTING RANGE SEARCH CURSOR ON NONUNIQUE FIELD-PREFIX COMPRESSED INDEX");
+        }
+
+        IBufferCache bufferCache = harness.getBufferCache();
+        int btreeFileId = harness.getBTreeFileId();
+        
+        // declare keys
+        int keyFieldCount = 2;
+        IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+        cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        cmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+        ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+        ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+
+        IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) leafFrameFactory.createFrame();
+        IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame) interiorFrameFactory.createFrame();
+
+        IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+
+        BTree btree = new BTree(bufferCache, NoOpOperationCallback.INSTANCE, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
+        btree.create(btreeFileId);
+        btree.open(btreeFileId);
+
+        ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
+        ArrayTupleReference tuple = new ArrayTupleReference();
+
+        ITreeIndexAccessor indexAccessor = btree.createAccessor();
+
+        // generate keys
+        int numKeys = 50;
+        int maxKey = 10;
+        ArrayList<Integer> keys = new ArrayList<Integer>();
+        for (int i = 0; i < numKeys; i++) {
+            int k = rnd.nextInt() % maxKey;
+            keys.add(k);
+        }
+        Collections.sort(keys);
+
+        // insert keys into btree
+        for (int i = 0; i < keys.size(); i++) {
+
+            TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i);
+            tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
+
+            try {
+                indexAccessor.insert(tuple);
+            } catch (BTreeException e) {
+            } catch (Exception e) {
+                e.printStackTrace();
+            }
+        }
+
+        // btree.printTree(leafFrame, interiorFrame, recDescSers);
+
+        int minSearchKey = -100;
+        int maxSearchKey = 100;
+
+        // forward searches
+        performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, true, false);
+        performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, false, true, false);
+        performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, false, false);
+        performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, true, false);
+
+        btree.close();
+    }
+
+    public RangePredicate createRangePredicate(int lk, int hk, boolean lowKeyInclusive,
+            boolean highKeyInclusive) throws HyracksDataException {
+
+        // create tuplereferences for search keys
+        ITupleReference lowKey = TupleUtils.createIntegerTuple(lk);
+        ITupleReference highKey = TupleUtils.createIntegerTuple(hk);
+
+        IBinaryComparator[] searchCmps = new IBinaryComparator[1];
+        searchCmps[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY).createBinaryComparator();
+        MultiComparator searchCmp = new MultiComparator(searchCmps);
+
+        RangePredicate rangePred = new RangePredicate(lowKey, highKey, lowKeyInclusive, highKeyInclusive,
+                searchCmp, searchCmp);
+        return rangePred;
+    }
+
+    public void getExpectedResults(ArrayList<Integer> expectedResults, ArrayList<Integer> keys, int lk, int hk,
+            boolean lowKeyInclusive, boolean highKeyInclusive) {
+
+        // special cases
+        if (lk == hk && (!lowKeyInclusive || !highKeyInclusive))
+            return;
+        if (lk > hk)
+            return;
+
+        for (int i = 0; i < keys.size(); i++) {
+            if ((lk == keys.get(i) && lowKeyInclusive) || (hk == keys.get(i) && highKeyInclusive)) {
+                expectedResults.add(keys.get(i));
+                continue;
+            }
+
+            if (lk < keys.get(i) && hk > keys.get(i)) {
+                expectedResults.add(keys.get(i));
+                continue;
+            }
+        }
+    }
+
+    public boolean performSearches(ArrayList<Integer> keys, BTree btree, IBTreeLeafFrame leafFrame,
+            IBTreeInteriorFrame interiorFrame, int minKey, int maxKey, boolean lowKeyInclusive,
+            boolean highKeyInclusive, boolean printExpectedResults) throws Exception {
+
+        ArrayList<Integer> results = new ArrayList<Integer>();
+        ArrayList<Integer> expectedResults = new ArrayList<Integer>();
+
+        for (int i = minKey; i < maxKey; i++) {
+            for (int j = minKey; j < maxKey; j++) {
+
+                results.clear();
+                expectedResults.clear();
+
+                int lowKey = i;
+                int highKey = j;
+
+                ITreeIndexCursor rangeCursor = new BTreeRangeSearchCursor(leafFrame, false);
+                RangePredicate rangePred = createRangePredicate(lowKey, highKey, lowKeyInclusive,
+                        highKeyInclusive);
+                ITreeIndexAccessor indexAccessor = btree.createAccessor();
+                indexAccessor.search(rangeCursor, rangePred);
+
+                try {
+                    while (rangeCursor.hasNext()) {
+                        rangeCursor.next();
+                        ITupleReference frameTuple = rangeCursor.getTuple();
+                        ByteArrayInputStream inStream = new ByteArrayInputStream(frameTuple.getFieldData(0),
+                                frameTuple.getFieldStart(0), frameTuple.getFieldLength(0));
+                        DataInput dataIn = new DataInputStream(inStream);
+                        Integer res = IntegerSerializerDeserializer.INSTANCE.deserialize(dataIn);
+                        results.add(res);
+                    }
+                } catch (Exception e) {
+                    e.printStackTrace();
+                } finally {
+                    rangeCursor.close();
+                }
+
+                getExpectedResults(expectedResults, keys, lowKey, highKey, lowKeyInclusive, highKeyInclusive);
+
+                if (printExpectedResults) {
+                    if (expectedResults.size() > 0) {
+                        char l, u;
+
+                        if (lowKeyInclusive)
+                            l = '[';
+                        else
+                            l = '(';
+
+                        if (highKeyInclusive)
+                            u = ']';
+                        else
+                            u = ')';
+
+                        if (LOGGER.isLoggable(Level.INFO)) {
+                            LOGGER.info("RANGE: " + l + " " + lowKey + " , " + highKey + " " + u);
+                        }
+                        StringBuilder strBuilder = new StringBuilder();
+                        for (Integer r : expectedResults) {
+                            strBuilder.append(r + " ");
+                        }
+                        if (LOGGER.isLoggable(Level.INFO)) {
+                            LOGGER.info(strBuilder.toString());
+                        }
+                    }
+                }
+
+                if (results.size() == expectedResults.size()) {
+                    for (int k = 0; k < results.size(); k++) {
+                        if (!results.get(k).equals(expectedResults.get(k))) {
+                            if (LOGGER.isLoggable(Level.INFO)) {
+                                LOGGER.info("DIFFERENT RESULTS AT: i=" + i + " j=" + j + " k=" + k);
+                                LOGGER.info(results.get(k) + " " + expectedResults.get(k));
+                            }
+                            return false;
+                        }
+                    }
+                } else {
+                    if (LOGGER.isLoggable(Level.INFO)) {
+                        LOGGER.info("UNEQUAL NUMBER OF RESULTS AT: i=" + i + " j=" + j);
+                        LOGGER.info("RESULTS: " + results.size());
+                        LOGGER.info("EXPECTED RESULTS: " + expectedResults.size());
+                    }
+                    return false;
+                }
+            }
+        }
+
+        return true;
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
new file mode 100644
index 0000000..c33b4e9
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
@@ -0,0 +1,163 @@
+package edu.uci.ics.hyracks.storage.am.btree;
+
+import java.io.DataOutput;
+import java.io.File;
+import java.nio.ByteBuffer;
+import java.util.Random;
+import java.util.logging.Level;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
+import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.FrameTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+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.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexBufferCacheWarmup;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexStats;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexStatsGatherer;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+@SuppressWarnings("rawtypes")
+public class BTreeStatsTest extends AbstractBTreeTest {
+    private static final int PAGE_SIZE = 4096;
+    private static final int NUM_PAGES = 1000;
+    private static final int MAX_OPEN_FILES = 10;
+    private static final int HYRACKS_FRAME_SIZE = 128;
+    private IHyracksTaskContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+    @Test
+    public void test01() throws Exception {
+
+        TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
+        IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+        IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+        FileReference file = new FileReference(new File(harness.getFileName()));
+        bufferCache.createFile(file);
+        int fileId = fmp.lookupFileId(file);
+        bufferCache.openFile(fileId);
+
+        // declare fields
+        int fieldCount = 2;
+        ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+        typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+        typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+
+        // declare keys
+        int keyFieldCount = 1;
+        IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+        cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+        TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(typeTraits);
+        ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+        ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+        ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+
+        IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) leafFrameFactory.createFrame();
+        IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame) interiorFrameFactory.createFrame();
+        ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
+
+        IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+
+        BTree btree = new BTree(bufferCache, NoOpOperationCallback.INSTANCE, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
+        btree.create(fileId);
+        btree.open(fileId);
+
+        Random rnd = new Random();
+        rnd.setSeed(50);
+
+        long start = System.currentTimeMillis();
+
+        if (LOGGER.isLoggable(Level.INFO)) {
+            LOGGER.info("INSERTING INTO TREE");
+        }
+
+        ByteBuffer frame = ctx.allocateFrame();
+        FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
+        ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+        DataOutput dos = tb.getDataOutput();
+
+        ISerializerDeserializer[] recDescSers = { IntegerSerializerDeserializer.INSTANCE,
+                IntegerSerializerDeserializer.INSTANCE };
+        RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
+        IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
+        accessor.reset(frame);
+        FrameTupleReference tuple = new FrameTupleReference();
+
+        ITreeIndexAccessor indexAccessor = btree.createAccessor();
+        // 10000
+        for (int i = 0; i < 100000; i++) {
+
+            int f0 = rnd.nextInt() % 100000;
+            int f1 = 5;
+
+            tb.reset();
+            IntegerSerializerDeserializer.INSTANCE.serialize(f0, dos);
+            tb.addFieldEndOffset();
+            IntegerSerializerDeserializer.INSTANCE.serialize(f1, dos);
+            tb.addFieldEndOffset();
+
+            appender.reset(frame, true);
+            appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+
+            tuple.reset(accessor, 0);
+
+            if (LOGGER.isLoggable(Level.INFO)) {
+                if (i % 10000 == 0) {
+                    long end = System.currentTimeMillis();
+                    LOGGER.info("INSERTING " + i + " : " + f0 + " " + f1 + " " + (end - start));
+                }
+            }
+
+            try {
+                indexAccessor.insert(tuple);
+            } catch (TreeIndexException e) {
+            } catch (Exception e) {
+                e.printStackTrace();
+            }
+        }
+
+        TreeIndexStatsGatherer statsGatherer = new TreeIndexStatsGatherer(bufferCache, freePageManager, fileId,
+                btree.getRootPageId());
+        TreeIndexStats stats = statsGatherer.gatherStats(leafFrame, interiorFrame, metaFrame);
+        if (LOGGER.isLoggable(Level.INFO)) {
+            LOGGER.info("\n" + stats.toString());
+        }
+
+        TreeIndexBufferCacheWarmup bufferCacheWarmup = new TreeIndexBufferCacheWarmup(bufferCache, freePageManager,
+                fileId);
+        bufferCacheWarmup.warmup(leafFrame, metaFrame, new int[] { 1, 2 }, new int[] { 2, 5 });
+
+        btree.close();
+        bufferCache.closeFile(fileId);
+        bufferCache.close();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateSearchTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateSearchTest.java
new file mode 100644
index 0000000..2b03a6a
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateSearchTest.java
@@ -0,0 +1,154 @@
+package edu.uci.ics.hyracks.storage.am.btree;
+
+import java.util.Random;
+import java.util.logging.Level;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+@SuppressWarnings("rawtypes")
+public class BTreeUpdateSearchTest extends AbstractBTreeTest {
+
+    // Update scan test on fixed-length tuples.
+    @Test
+    public void test01() throws Exception {
+        IBufferCache bufferCache = harness.getBufferCache();
+        int btreeFileId = harness.getBTreeFileId();
+        
+        // declare fields
+        int fieldCount = 2;
+        ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+        typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+        typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+
+        // declare keys
+        int keyFieldCount = 1;
+        IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+        cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+        ISerializerDeserializer[] recDescSers = { IntegerSerializerDeserializer.INSTANCE,
+                IntegerSerializerDeserializer.INSTANCE };
+
+        TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(typeTraits);
+        ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+        ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+        ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+
+        IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) leafFrameFactory.createFrame();
+
+        IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+        BTree btree = new BTree(bufferCache, NoOpOperationCallback.INSTANCE, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
+        btree.create(btreeFileId);
+        btree.open(btreeFileId);
+
+        Random rnd = new Random();
+        rnd.setSeed(50);
+
+        long start = System.currentTimeMillis();
+
+        if (LOGGER.isLoggable(Level.INFO)) {
+            LOGGER.info("INSERTING INTO TREE");
+        }
+
+        ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+        ArrayTupleReference insertTuple = new ArrayTupleReference();
+        ITreeIndexAccessor indexAccessor = btree.createAccessor();
+
+        int numInserts = 10000;
+        for (int i = 0; i < numInserts; i++) {
+            int f0 = rnd.nextInt() % 10000;
+            int f1 = 5;
+            TupleUtils.createIntegerTuple(tb, insertTuple, f0, f1);
+            if (LOGGER.isLoggable(Level.INFO)) {
+                if (i % 10000 == 0) {
+                    long end = System.currentTimeMillis();
+                    LOGGER.info("INSERTING " + i + " : " + f0 + " " + f1 + " " + (end - start));
+                }
+            }
+
+            try {
+                indexAccessor.insert(insertTuple);
+            } catch (TreeIndexException e) {
+            } catch (Exception e) {
+                e.printStackTrace();
+            }
+        }
+        long end = System.currentTimeMillis();
+        long duration = end - start;
+        if (LOGGER.isLoggable(Level.INFO)) {
+            LOGGER.info("DURATION: " + duration);
+        }
+
+        // Update scan.
+        if (LOGGER.isLoggable(Level.INFO)) {
+            LOGGER.info("UPDATE SCAN:");
+        }
+        // Set the cursor to X latch nodes.
+        ITreeIndexCursor updateScanCursor = new BTreeRangeSearchCursor(leafFrame, true);
+        RangePredicate nullPred = new RangePredicate(null, null, true, true, null, null);
+        indexAccessor.search(updateScanCursor, nullPred);
+        try {
+            while (updateScanCursor.hasNext()) {
+                updateScanCursor.next();
+                ITupleReference tuple = updateScanCursor.getTuple();
+                // Change the value field.
+                IntegerSerializerDeserializer.putInt(10, tuple.getFieldData(1), tuple.getFieldStart(1));
+            }
+        } catch (Exception e) {
+            e.printStackTrace();
+        } finally {
+            updateScanCursor.close();
+        }
+
+        // Ordered scan to verify the values.
+        if (LOGGER.isLoggable(Level.INFO)) {
+            LOGGER.info("ORDERED SCAN:");
+        }
+        // Set the cursor to X latch nodes.
+        ITreeIndexCursor scanCursor = new BTreeRangeSearchCursor(leafFrame, true);
+        indexAccessor.search(scanCursor, nullPred);
+        try {
+            while (scanCursor.hasNext()) {
+                scanCursor.next();
+                ITupleReference tuple = scanCursor.getTuple();
+                String rec = TupleUtils.printTuple(tuple, recDescSers);
+                if (LOGGER.isLoggable(Level.INFO)) {
+                    LOGGER.info(rec);
+                }
+            }
+        } catch (Exception e) {
+            e.printStackTrace();
+        } finally {
+            scanCursor.close();
+        }
+        btree.close();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateTest.java
new file mode 100644
index 0000000..c3b56d5
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateTest.java
@@ -0,0 +1,61 @@
+/*
+ * 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.btree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexUpdateTest;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
+
+@SuppressWarnings("rawtypes")
+public class BTreeUpdateTest extends OrderedIndexUpdateTest {
+
+    public BTreeUpdateTest() {
+        super(BTreeTestHarness.LEAF_FRAMES_TO_TEST);
+    }
+
+    private final BTreeTestHarness harness = new BTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+            BTreeLeafFrameType leafType) throws Exception {
+        return BTreeTestContext.create(harness.getBufferCache(), harness.getBTreeFileId(), fieldSerdes, numKeys,
+                leafType);
+    }
+
+    @Override
+    protected Random getRandom() {
+        return harness.getRandom();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpsertTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpsertTest.java
new file mode 100644
index 0000000..6e14607
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpsertTest.java
@@ -0,0 +1,69 @@
+/*
+ * 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.btree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
+
+/**
+ * Tests the BTree insert operation with strings and integer fields using
+ * various numbers of key and payload fields.
+ * 
+ * Each tests first fills a BTree with randomly generated tuples. We compare the
+ * following operations against expected results: 1. Point searches for all
+ * tuples. 2. Ordered scan. 3. Disk-order scan. 4. Range search (and prefix
+ * search for composite keys).
+ * 
+ */
+@SuppressWarnings("rawtypes")
+public class BTreeUpsertTest extends OrderedIndexUpsertTest {
+
+    public BTreeUpsertTest() {
+        super(BTreeTestHarness.LEAF_FRAMES_TO_TEST);
+    }
+
+    private final BTreeTestHarness harness = new BTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+            BTreeLeafFrameType leafType) throws Exception {
+        return BTreeTestContext.create(harness.getBufferCache(), harness.getBTreeFileId(), fieldSerdes, numKeys,
+                leafType);
+    }
+
+    @Override
+    protected Random getRandom() {
+        return harness.getRandom();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/FieldPrefixNSMTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/FieldPrefixNSMTest.java
new file mode 100644
index 0000000..d61d16a
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/FieldPrefixNSMTest.java
@@ -0,0 +1,225 @@
+/*
+ * 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.btree;
+
+import java.io.DataOutput;
+import java.nio.ByteBuffer;
+import java.util.Random;
+import java.util.logging.Level;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
+import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
+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.ITypeTraits;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.FrameTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeFieldPrefixNSMLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexUtils;
+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;
+
+@SuppressWarnings("rawtypes")
+public class FieldPrefixNSMTest extends AbstractBTreeTest {
+
+    private static final int PAGE_SIZE = 32768; // 32K
+    private static final int NUM_PAGES = 40;
+    private static final int MAX_OPEN_FILES = 10;
+    private static final int HYRACKS_FRAME_SIZE = 128;
+
+    public FieldPrefixNSMTest() {        
+        super(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES, HYRACKS_FRAME_SIZE);
+    }
+    
+    private ITupleReference createTuple(IHyracksTaskContext ctx, int f0, int f1, int f2, boolean print)
+            throws HyracksDataException {
+        if (print) {
+            if (LOGGER.isLoggable(Level.INFO)) {
+                LOGGER.info("CREATING: " + f0 + " " + f1 + " " + f2);
+            }
+        }
+
+        ByteBuffer buf = ctx.allocateFrame();
+        FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
+        ArrayTupleBuilder tb = new ArrayTupleBuilder(3);
+        DataOutput dos = tb.getDataOutput();
+        
+        ISerializerDeserializer[] recDescSers = { IntegerSerializerDeserializer.INSTANCE,
+                IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+        RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
+        IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
+        accessor.reset(buf);
+        FrameTupleReference tuple = new FrameTupleReference();
+
+        tb.reset();
+        IntegerSerializerDeserializer.INSTANCE.serialize(f0, dos);
+        tb.addFieldEndOffset();
+        IntegerSerializerDeserializer.INSTANCE.serialize(f1, dos);
+        tb.addFieldEndOffset();
+        IntegerSerializerDeserializer.INSTANCE.serialize(f2, dos);
+        tb.addFieldEndOffset();
+
+        appender.reset(buf, true);
+        appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+
+        tuple.reset(accessor, 0);
+
+        return tuple;
+    }
+
+    @Test
+    public void test01() throws Exception {        
+        
+        // declare fields
+        int fieldCount = 3;
+        ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+        typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+        typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+        typeTraits[2] = IntegerPointable.TYPE_TRAITS;
+
+        // declare keys
+        int keyFieldCount = 3;
+        IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
+        cmps[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY).createBinaryComparator();
+        cmps[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY).createBinaryComparator();
+        cmps[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY).createBinaryComparator();
+        MultiComparator cmp = new MultiComparator(cmps);
+
+        // just for printing
+        ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE,
+                IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+
+        Random rnd = new Random();
+        rnd.setSeed(50);
+
+        IBufferCache bufferCache = harness.getBufferCache();
+        int btreeFileId = harness.getBTreeFileId();
+        IHyracksTaskContext ctx = harness.getHyracksTaskContext();
+        ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(btreeFileId, 0), false);
+        try {
+
+            ITreeIndexTupleWriter tupleWriter = new TypeAwareTupleWriter(typeTraits);
+            BTreeFieldPrefixNSMLeafFrame frame = new BTreeFieldPrefixNSMLeafFrame(tupleWriter);
+            frame.setPage(page);
+            frame.initBuffer((byte) 0);
+            frame.setMultiComparator(cmp);
+            frame.setPrefixTupleCount(0);
+
+            String before = new String();
+            String after = new String();
+
+            int compactFreq = 5;
+            int compressFreq = 5;
+            int smallMax = 10;
+            int numRecords = 1000;
+
+            int[][] savedFields = new int[numRecords][3];
+
+            // insert records with random calls to compact and compress
+            for (int i = 0; i < numRecords; i++) {
+
+                if (LOGGER.isLoggable(Level.INFO)) {
+                    if ((i + 1) % 100 == 0) {
+                        LOGGER.info("INSERTING " + (i + 1) + " / " + numRecords);
+                    }
+                }
+
+                int a = rnd.nextInt() % smallMax;
+                int b = rnd.nextInt() % smallMax;
+                int c = i;
+
+                ITupleReference tuple = createTuple(ctx, a, b, c, false);
+                try {
+                    int targetTupleIndex = frame.findInsertTupleIndex(tuple);
+                    frame.insert(tuple, targetTupleIndex);
+                } catch (BTreeException e) {
+                    e.printStackTrace();
+                } catch (Exception e) {
+                    e.printStackTrace();
+                }
+
+                savedFields[i][0] = a;
+                savedFields[i][1] = b;
+                savedFields[i][2] = c;
+
+                if (rnd.nextInt() % compactFreq == 0) {
+                    before = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+                    frame.compact();
+                    after = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+                    Assert.assertEquals(before, after);
+                }
+
+                if (rnd.nextInt() % compressFreq == 0) {
+                    before = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+                    frame.compress();
+                    after = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+                    Assert.assertEquals(before, after);
+                }
+
+            }
+
+            // delete records with random calls to compact and compress
+            for (int i = 0; i < numRecords; i++) {
+                if (LOGGER.isLoggable(Level.INFO)) {
+                    if ((i + 1) % 100 == 0) {
+                        LOGGER.info("DELETING " + (i + 1) + " / " + numRecords);
+                    }
+                }
+
+                ITupleReference tuple = createTuple(ctx, savedFields[i][0], savedFields[i][1], savedFields[i][2], false);
+                try {
+                    int tupleIndex = frame.findDeleteTupleIndex(tuple);
+                    frame.delete(tuple, tupleIndex);
+                } catch (Exception e) {
+                }
+
+                if (rnd.nextInt() % compactFreq == 0) {
+                    before = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+                    frame.compact();
+                    after = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+                    Assert.assertEquals(before, after);
+                }
+
+                if (rnd.nextInt() % compressFreq == 0) {
+                    before = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+                    frame.compress();
+                    after = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+                    Assert.assertEquals(before, after);
+                }
+            }
+
+        } finally {
+            bufferCache.unpin(page);
+        }
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/StorageManagerTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/StorageManagerTest.java
new file mode 100644
index 0000000..9ec64b5
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/StorageManagerTest.java
@@ -0,0 +1,259 @@
+/*
+ * 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.btree;
+
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+import java.util.logging.Level;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
+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;
+import edu.uci.ics.hyracks.storage.common.sync.LatchType;
+
+public class StorageManagerTest extends AbstractBTreeTest {	
+    public class PinnedLatchedPage {
+        public final ICachedPage page;
+        public final LatchType latch;
+        public final int pageId;
+
+        public PinnedLatchedPage(ICachedPage page, int pageId, LatchType latch) {
+            this.page = page;
+            this.pageId = pageId;
+            this.latch = latch;
+        }
+    }
+
+    public enum FileAccessType {
+        FTA_READONLY, FTA_WRITEONLY, FTA_MIXED, FTA_UNLATCHED
+    }
+
+    public class FileAccessWorker implements Runnable {
+        private int workerId;
+        private final IBufferCache bufferCache;
+        private final int maxPages;
+        private final int fileId;
+        private final long thinkTime;
+        private final int maxLoopCount;
+        private final int maxPinnedPages;
+        private final int closeFileChance;
+        private final FileAccessType fta;
+        private int loopCount = 0;
+        private boolean fileIsOpen = false;
+        private Random rnd = new Random(50);
+        private List<PinnedLatchedPage> pinnedPages = new LinkedList<PinnedLatchedPage>();
+
+        public FileAccessWorker(int workerId, IBufferCache bufferCache, FileAccessType fta, int fileId, int maxPages,
+                int maxPinnedPages, int maxLoopCount, int closeFileChance, long thinkTime) {
+            this.bufferCache = bufferCache;
+            this.fileId = fileId;
+            this.maxPages = maxPages;
+            this.maxLoopCount = maxLoopCount;
+            this.maxPinnedPages = maxPinnedPages;
+            this.thinkTime = thinkTime;
+            this.closeFileChance = closeFileChance;
+            this.workerId = workerId;
+            this.fta = fta;
+        }
+
+        private void pinRandomPage() {
+            int pageId = Math.abs(rnd.nextInt() % maxPages);
+
+            if (LOGGER.isLoggable(Level.INFO)) {
+                LOGGER.info(workerId + " PINNING PAGE: " + pageId);
+            }
+
+            try {
+                ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+                LatchType latch = null;
+
+                switch (fta) {
+
+                    case FTA_UNLATCHED: {
+                        latch = null;
+                    }
+                        break;
+
+                    case FTA_READONLY: {
+                        if (LOGGER.isLoggable(Level.INFO)) {
+                            LOGGER.info(workerId + " S LATCHING: " + pageId);
+                        }
+                        page.acquireReadLatch();
+                        latch = LatchType.LATCH_S;
+                    }
+                        break;
+
+                    case FTA_WRITEONLY: {
+                        if (LOGGER.isLoggable(Level.INFO)) {
+                            LOGGER.info(workerId + " X LATCHING: " + pageId);
+                        }
+                        page.acquireWriteLatch();
+                        latch = LatchType.LATCH_X;
+                    }
+                        break;
+
+                    case FTA_MIXED: {
+                        if (rnd.nextInt() % 2 == 0) {
+                            if (LOGGER.isLoggable(Level.INFO)) {
+                                LOGGER.info(workerId + " S LATCHING: " + pageId);
+                            }
+                            page.acquireReadLatch();
+                            latch = LatchType.LATCH_S;
+                        } else {
+                            if (LOGGER.isLoggable(Level.INFO)) {
+                                LOGGER.info(workerId + " X LATCHING: " + pageId);
+                            }
+                            page.acquireWriteLatch();
+                            latch = LatchType.LATCH_X;
+                        }
+                    }
+                        break;
+
+                }
+
+                PinnedLatchedPage plPage = new PinnedLatchedPage(page, pageId, latch);
+                pinnedPages.add(plPage);
+            } catch (HyracksDataException e) {
+                e.printStackTrace();
+            }
+        }
+
+        private void unpinRandomPage() {
+            int index = Math.abs(rnd.nextInt() % pinnedPages.size());
+            try {
+                PinnedLatchedPage plPage = pinnedPages.get(index);
+
+                if (plPage.latch != null) {
+                    if (plPage.latch == LatchType.LATCH_S) {
+                        if (LOGGER.isLoggable(Level.INFO)) {
+                            LOGGER.info(workerId + " S UNLATCHING: " + plPage.pageId);
+                        }
+                        plPage.page.releaseReadLatch();
+                    } else {
+                        if (LOGGER.isLoggable(Level.INFO)) {
+                            LOGGER.info(workerId + " X UNLATCHING: " + plPage.pageId);
+                        }
+                        plPage.page.releaseWriteLatch();
+                    }
+                }
+                if (LOGGER.isLoggable(Level.INFO)) {
+                    LOGGER.info(workerId + " UNPINNING PAGE: " + plPage.pageId);
+                }
+
+                bufferCache.unpin(plPage.page);
+                pinnedPages.remove(index);
+            } catch (HyracksDataException e) {
+                e.printStackTrace();
+            }
+        }
+
+        private void openFile() {
+            if (LOGGER.isLoggable(Level.INFO)) {
+                LOGGER.info(workerId + " OPENING FILE: " + fileId);
+            }
+            try {
+                bufferCache.openFile(fileId);
+                fileIsOpen = true;
+            } catch (HyracksDataException e) {
+                e.printStackTrace();
+            }
+        }
+
+        private void closeFile() {
+            if (LOGGER.isLoggable(Level.INFO)) {
+                LOGGER.info(workerId + " CLOSING FILE: " + fileId);
+            }
+            try {
+                bufferCache.closeFile(fileId);
+                fileIsOpen = false;
+            } catch (HyracksDataException e) {
+                e.printStackTrace();
+            }
+        }
+
+        @Override
+        public void run() {
+
+            openFile();
+
+            while (loopCount < maxLoopCount) {
+                loopCount++;
+
+                if (LOGGER.isLoggable(Level.INFO)) {
+                    LOGGER.info(workerId + " LOOP: " + loopCount + "/" + maxLoopCount);
+                }
+
+                if (fileIsOpen) {
+
+                    // pin some pages
+                    int pagesToPin = Math.abs(rnd.nextInt()) % (maxPinnedPages - pinnedPages.size());
+                    for (int i = 0; i < pagesToPin; i++) {
+                        pinRandomPage();
+                    }
+
+                    // do some thinking
+                    try {
+                        Thread.sleep(thinkTime);
+                    } catch (InterruptedException e) {
+                        e.printStackTrace();
+                    }
+
+                    // unpin some pages
+                    if (!pinnedPages.isEmpty()) {
+                        int pagesToUnpin = Math.abs(rnd.nextInt()) % pinnedPages.size();
+                        for (int i = 0; i < pagesToUnpin; i++) {
+                            unpinRandomPage();
+                        }
+                    }
+
+                    // possibly close file
+                    int closeFileCheck = Math.abs(rnd.nextInt()) % closeFileChance;
+                    if (pinnedPages.isEmpty() || closeFileCheck == 0) {
+                        int numPinnedPages = pinnedPages.size();
+                        for (int i = 0; i < numPinnedPages; i++) {
+                            unpinRandomPage();
+                        }
+                        closeFile();
+                    }
+                } else {
+                    openFile();
+                }
+            }
+
+            if (fileIsOpen) {
+                int numPinnedPages = pinnedPages.size();
+                for (int i = 0; i < numPinnedPages; i++) {
+                    unpinRandomPage();
+                }
+                closeFile();
+            }
+        }
+    }
+
+    @Test
+    public void oneThreadOneFileTest() throws Exception { 
+		Thread worker = new Thread(new FileAccessWorker(0,
+				harness.getBufferCache(), FileAccessType.FTA_UNLATCHED,
+				harness.getBTreeFileId(), 10, 10, 100, 10, 0));
+        worker.start();
+        worker.join();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeMultiThreadTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeMultiThreadTest.java
new file mode 100644
index 0000000..596fa31
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeMultiThreadTest.java
@@ -0,0 +1,91 @@
+/*
+ * 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.btree.multithread;
+
+import java.util.ArrayList;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexMultiThreadTest;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeUtils;
+import edu.uci.ics.hyracks.storage.am.common.ITreeIndexTestWorkerFactory;
+import edu.uci.ics.hyracks.storage.am.common.TestWorkloadConf;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector.TestOperation;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+
+public class BTreeMultiThreadTest extends OrderedIndexMultiThreadTest {
+
+    private BTreeTestHarness harness = new BTreeTestHarness();
+    
+    private BTreeTestWorkerFactory workerFactory = new BTreeTestWorkerFactory();
+    
+    @Override
+    protected void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @Override
+    protected void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparatorFactory[] cmpFactories) throws TreeIndexException {
+        return BTreeUtils.createBTree(harness.getBufferCache(), harness.getOpCallback(), typeTraits, cmpFactories, BTreeLeafFrameType.REGULAR_NSM);
+    }
+
+    @Override
+    protected ITreeIndexTestWorkerFactory getWorkerFactory() {
+        return workerFactory;
+    }
+
+    @Override
+    protected ArrayList<TestWorkloadConf> getTestWorkloadConf() {
+        ArrayList<TestWorkloadConf> workloadConfs = new ArrayList<TestWorkloadConf>();
+        
+        // Insert only workload.
+        TestOperation[] insertOnlyOps = new TestOperation[] { TestOperation.INSERT };
+        workloadConfs.add(new TestWorkloadConf(insertOnlyOps, getUniformOpProbs(insertOnlyOps)));
+        
+        // Inserts mixed with point searches and scans.
+        TestOperation[] insertSearchOnlyOps = new TestOperation[] { TestOperation.INSERT, TestOperation.POINT_SEARCH, TestOperation.SCAN, TestOperation.DISKORDER_SCAN };
+        workloadConfs.add(new TestWorkloadConf(insertSearchOnlyOps, getUniformOpProbs(insertSearchOnlyOps)));
+        
+        // Inserts, updates, deletes, and upserts.        
+        TestOperation[] insertDeleteUpdateUpsertOps = new TestOperation[] { TestOperation.INSERT, TestOperation.DELETE, TestOperation.UPDATE, TestOperation.UPSERT };
+        workloadConfs.add(new TestWorkloadConf(insertDeleteUpdateUpsertOps, getUniformOpProbs(insertDeleteUpdateUpsertOps)));
+        
+        // All operations mixed.
+        TestOperation[] allOps = new TestOperation[] { TestOperation.INSERT, TestOperation.DELETE, TestOperation.UPDATE, TestOperation.UPSERT, TestOperation.POINT_SEARCH, TestOperation.SCAN, TestOperation.DISKORDER_SCAN };
+        workloadConfs.add(new TestWorkloadConf(allOps, getUniformOpProbs(allOps)));
+        
+        return workloadConfs;
+    }
+
+    @Override
+    protected int getFileId() {
+        return harness.getBTreeFileId();
+    }
+
+    @Override
+    protected String getIndexTypeName() {
+        return "BTree";
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeTestWorker.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeTestWorker.java
new file mode 100644
index 0000000..7d8de7d
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeTestWorker.java
@@ -0,0 +1,133 @@
+/*
+ * 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.btree.multithread;
+
+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.ArrayTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeDuplicateKeyException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNonExistentKeyException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNotUpdateableException;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.common.AbstractTreeIndexTestWorker;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector.TestOperation;
+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.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.datagen.DataGenThread;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+
+public class BTreeTestWorker extends AbstractTreeIndexTestWorker {
+    
+    private final BTree btree;
+    private final int numKeyFields;
+    private final ArrayTupleBuilder deleteTb;
+    private final ArrayTupleReference deleteTuple = new ArrayTupleReference();
+    
+    public BTreeTestWorker(DataGenThread dataGen, TestOperationSelector opSelector, ITreeIndex index, int numBatches) {
+        super(dataGen, opSelector, index, numBatches);
+        btree = (BTree) index;
+        numKeyFields = btree.getComparatorFactories().length;
+        deleteTb = new ArrayTupleBuilder(numKeyFields);
+    }
+    
+    @Override
+    public void performOp(ITupleReference tuple, TestOperation op) throws HyracksDataException, TreeIndexException {        
+        BTree.BTreeAccessor accessor = (BTree.BTreeAccessor) indexAccessor;
+        ITreeIndexCursor searchCursor = accessor.createSearchCursor();
+        ITreeIndexCursor diskOrderScanCursor = accessor.createDiskOrderScanCursor();
+        MultiComparator cmp = accessor.getOpContext().cmp;
+        RangePredicate rangePred = new RangePredicate(tuple, tuple, true, true, cmp, cmp);
+        
+        switch (op) {
+            case INSERT:
+                try {
+                    accessor.insert(tuple);
+                } catch (BTreeDuplicateKeyException e) {
+                    // Ignore duplicate keys, since we get random tuples.
+                }
+                break;
+                
+            case DELETE:
+                // Create a tuple reference with only key fields.
+                deleteTb.reset();
+                for (int i = 0; i < numKeyFields; i++) {
+                    deleteTb.addField(tuple.getFieldData(i), tuple.getFieldStart(i), tuple.getFieldLength(i));
+                }
+                deleteTuple.reset(deleteTb.getFieldEndOffsets(), deleteTb.getByteArray());
+                try {
+                    accessor.delete(deleteTuple);
+                } catch (BTreeNonExistentKeyException e) {
+                    // Ignore non-existant keys, since we get random tuples.
+                }
+                break;
+                
+            case UPDATE:
+                try {
+                    accessor.update(tuple);
+                } catch (BTreeNonExistentKeyException e) {
+                    // Ignore non-existant keys, since we get random tuples.
+                } catch (BTreeNotUpdateableException e) {
+                    // Ignore not updateable exception due to numKeys == numFields.
+                }
+                break;
+                
+            case UPSERT:
+                accessor.upsert(tuple);
+                // Upsert should not throw. If it does, there's 
+                // a bigger problem and the test should fail.
+                break;
+                
+            case POINT_SEARCH: 
+                searchCursor.reset();
+                rangePred.setLowKey(tuple, true);
+                rangePred.setHighKey(tuple, true);
+                accessor.search(searchCursor, rangePred);
+                consumeCursorTuples(searchCursor);
+                break;
+                
+            case SCAN:
+                searchCursor.reset();
+                rangePred.setLowKey(null, true);
+                rangePred.setHighKey(null, true);
+                accessor.search(searchCursor, rangePred);
+                consumeCursorTuples(searchCursor);
+                break;
+                
+            case DISKORDER_SCAN:
+                diskOrderScanCursor.reset();
+                accessor.diskOrderScan(diskOrderScanCursor);
+                consumeCursorTuples(diskOrderScanCursor);
+                break;                            
+            
+            default:
+                throw new HyracksDataException("Op " + op.toString() + " not supported.");
+        }
+    }
+    
+    private void consumeCursorTuples(ITreeIndexCursor cursor) throws HyracksDataException {
+        try {
+            while(cursor.hasNext()) {
+                cursor.next();
+            }
+        } finally {
+            cursor.close();
+        }
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeTestWorkerFactory.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeTestWorkerFactory.java
new file mode 100644
index 0000000..dc4d883
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeTestWorkerFactory.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.btree.multithread;
+
+import edu.uci.ics.hyracks.storage.am.common.AbstractTreeIndexTestWorker;
+import edu.uci.ics.hyracks.storage.am.common.ITreeIndexTestWorkerFactory;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.datagen.DataGenThread;
+
+public class BTreeTestWorkerFactory implements ITreeIndexTestWorkerFactory {
+    @Override
+    public AbstractTreeIndexTestWorker create(DataGenThread dataGen, TestOperationSelector opSelector,
+            ITreeIndex index, int numBatches) {
+        return new BTreeTestWorker(dataGen, opSelector, index, numBatches);
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java
new file mode 100644
index 0000000..f4eca1b
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java
@@ -0,0 +1,46 @@
+/*
+ * 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.btree.util;
+
+import java.util.logging.Logger;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+
+public abstract class AbstractBTreeTest {
+	protected final Logger LOGGER = Logger.getLogger(BTreeTestHarness.class.getName());
+	protected final BTreeTestHarness harness;
+	
+	public AbstractBTreeTest() {
+		harness = new BTreeTestHarness();
+    }
+    
+    public AbstractBTreeTest(int pageSize, int numPages, int maxOpenFiles, int hyracksFrameSize) {
+    	harness = new BTreeTestHarness(pageSize, numPages, maxOpenFiles, hyracksFrameSize);
+    }
+	
+	@Before
+	public void setUp() throws HyracksDataException {
+		harness.setUp();
+    }
+	
+	@After
+    public void tearDown() throws HyracksDataException {
+		harness.tearDown();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestContext.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestContext.java
new file mode 100644
index 0000000..b820f93
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestContext.java
@@ -0,0 +1,57 @@
+/*
+ * 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.btree.util;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.dataflow.common.util.SerdeUtils;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+@SuppressWarnings("rawtypes")
+public class BTreeTestContext extends OrderedIndexTestContext {
+    
+    public BTreeTestContext(ISerializerDeserializer[] fieldSerdes, ITreeIndex treeIndex) {
+        super(fieldSerdes, treeIndex);
+    }
+
+    @Override
+    public int getKeyFieldCount() {
+        BTree btree = (BTree) treeIndex;
+        return btree.getComparatorFactories().length;
+    }
+    
+    @Override
+    public IBinaryComparatorFactory[] getComparatorFactories() {
+        BTree btree = (BTree) treeIndex;
+        return btree.getComparatorFactories();
+    }
+    
+    public static BTreeTestContext create(IBufferCache bufferCache, int btreeFileId, ISerializerDeserializer[] fieldSerdes, int numKeyFields, BTreeLeafFrameType leafType) throws Exception {        
+        ITypeTraits[] typeTraits = SerdeUtils.serdesToTypeTraits(fieldSerdes);
+        IBinaryComparatorFactory[] cmpFactories = SerdeUtils.serdesToComparatorFactories(fieldSerdes, numKeyFields);
+        BTree btree = BTreeUtils.createBTree(bufferCache, NoOpOperationCallback.INSTANCE, typeTraits, cmpFactories, leafType);
+        btree.create(btreeFileId);
+        btree.open(btreeFileId);
+        BTreeTestContext testCtx = new BTreeTestContext(fieldSerdes, btree);
+        return testCtx;
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestHarness.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestHarness.java
new file mode 100644
index 0000000..1b450d8
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestHarness.java
@@ -0,0 +1,132 @@
+/*
+ * 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.btree.util;
+
+import java.io.File;
+import java.text.SimpleDateFormat;
+import java.util.Date;
+import java.util.Random;
+
+import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.common.api.IOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public class BTreeTestHarness {    
+    public static final BTreeLeafFrameType[] LEAF_FRAMES_TO_TEST = new BTreeLeafFrameType[] {
+        BTreeLeafFrameType.REGULAR_NSM, BTreeLeafFrameType.FIELD_PREFIX_COMPRESSED_NSM };
+    
+    private static final long RANDOM_SEED = 50;
+    private static final int DEFAULT_PAGE_SIZE = 256;
+    private static final int DEFAULT_NUM_PAGES = 100;
+    private static final int DEFAULT_MAX_OPEN_FILES = 10;
+    private static final int DEFAULT_HYRACKS_FRAME_SIZE = 128;
+    
+    protected final int pageSize;
+    protected final int numPages;
+    protected final int maxOpenFiles;
+    protected final int hyracksFrameSize;
+        
+    protected IHyracksTaskContext ctx; 
+    protected IBufferCache bufferCache;
+    protected int btreeFileId;
+    
+    protected final Random rnd = new Random();
+    protected final SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
+    protected final String tmpDir = System.getProperty("java.io.tmpdir");
+    protected final String sep = System.getProperty("file.separator");
+    protected String fileName;
+    
+    public BTreeTestHarness() {
+    	this.pageSize = DEFAULT_PAGE_SIZE;
+    	this.numPages = DEFAULT_NUM_PAGES;
+    	this.maxOpenFiles = DEFAULT_MAX_OPEN_FILES;
+    	this.hyracksFrameSize = DEFAULT_HYRACKS_FRAME_SIZE;
+    }
+    
+    public BTreeTestHarness(int pageSize, int numPages, int maxOpenFiles, int hyracksFrameSize) {
+    	this.pageSize = pageSize;
+    	this.numPages = numPages;
+    	this.maxOpenFiles = maxOpenFiles;
+    	this.hyracksFrameSize = hyracksFrameSize;
+    }
+    
+    public void setUp() throws HyracksDataException {
+        fileName = tmpDir + sep + simpleDateFormat.format(new Date());
+        ctx = TestUtils.create(getHyracksFrameSize());
+        TestStorageManagerComponentHolder.init(pageSize, numPages, maxOpenFiles);
+        bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+        IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+        FileReference file = new FileReference(new File(fileName));
+        bufferCache.createFile(file);
+        btreeFileId = fmp.lookupFileId(file);
+        bufferCache.openFile(btreeFileId);
+        rnd.setSeed(RANDOM_SEED);
+    }
+    
+    public void tearDown() throws HyracksDataException {
+        bufferCache.closeFile(btreeFileId);
+        bufferCache.close();
+        File f = new File(fileName);
+        f.deleteOnExit();
+    }
+    
+    public IHyracksTaskContext getHyracksTaskContext() {
+    	return ctx;
+    }
+    
+    public IBufferCache getBufferCache() {
+    	return bufferCache;
+    }
+    
+    public int getBTreeFileId() {
+    	return btreeFileId;
+    }
+    
+    public String getFileName() {
+        return fileName;
+    }
+    
+    public Random getRandom() {
+    	return rnd;
+    }
+    
+    public int getPageSize() {
+        return pageSize;
+    }
+    
+    public int getNumPages() {
+        return numPages;
+    }
+    
+    public int getHyracksFrameSize() {
+        return hyracksFrameSize;
+    }
+    
+    public int getMaxOpenFiles() {
+        return maxOpenFiles;
+    }
+    
+    public IOperationCallback getOpCallback() {
+        return NoOpOperationCallback.INSTANCE;
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/pom.xml b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/pom.xml
new file mode 100644
index 0000000..5d66b81
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/pom.xml
@@ -0,0 +1,51 @@
+<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-invertedindex-test</artifactId>
+  <version>0.2.2-SNAPSHOT</version>
+  <name>hyracks-storage-am-invertedindex-test</name>
+
+  <parent>
+    <groupId>edu.uci.ics.hyracks</groupId>
+    <artifactId>hyracks-tests</artifactId>
+    <version>0.2.2-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>
+          <encoding>UTF-8</encoding>
+        </configuration>
+      </plugin>
+    </plugins>
+  </build>
+  <dependencies>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-storage-am-invertedindex</artifactId>
+  		<version>0.2.2-SNAPSHOT</version>
+  		<type>jar</type>
+  		<scope>compile</scope>
+  	</dependency>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-test-support</artifactId>
+  		<version>0.2.2-SNAPSHOT</version>
+  		<type>jar</type>
+  		<scope>test</scope>
+  	</dependency>
+  	<dependency>
+  		<groupId>junit</groupId>
+  		<artifactId>junit</artifactId>
+  		<version>4.8.1</version>
+  		<type>jar</type>
+  		<scope>test</scope>
+  	</dependency>
+  </dependencies>
+</project>
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/AbstractInvIndexSearchTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/AbstractInvIndexSearchTest.java
new file mode 100644
index 0000000..e086af6
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/AbstractInvIndexSearchTest.java
@@ -0,0 +1,193 @@
+/*
+ * 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.invertedindex;
+
+import java.io.File;
+import java.util.ArrayList;
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+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.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.data.std.primitive.UTF8StringPointable;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+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.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.invertedindex.api.IInvertedListBuilder;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.FixedSizeElementInvertedListBuilder;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.InvertedIndex;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.IBinaryTokenizer;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.ITokenFactory;
+import edu.uci.ics.hyracks.storage.am.invertedindex.util.InvertedIndexUtils;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public abstract class AbstractInvIndexSearchTest extends AbstractInvIndexTest {
+    protected final int PAGE_SIZE = 32768;
+    protected final int NUM_PAGES = 100;
+    protected final int MAX_OPEN_FILES = 10;
+    protected final int HYRACKS_FRAME_SIZE = 32768;
+    protected IHyracksTaskContext taskCtx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+    protected IBufferCache bufferCache;
+    protected IFileMapProvider fmp;
+
+    // --- BTREE ---
+
+    // create file refs
+    protected FileReference btreeFile = new FileReference(new File(btreeFileName));
+    protected int btreeFileId;
+
+    // declare token type traits
+    protected ITypeTraits[] tokenTypeTraits = new ITypeTraits[] { UTF8StringPointable.TYPE_TRAITS };
+    protected ITypeTraits[] btreeTypeTraits = InvertedIndexUtils.getBTreeTypeTraits(tokenTypeTraits);
+
+    // declare btree keys
+    protected int btreeKeyFieldCount = 1;
+    protected IBinaryComparatorFactory[] btreeCmpFactories = new IBinaryComparatorFactory[btreeKeyFieldCount];
+
+    // btree frame factories
+    protected TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(btreeTypeTraits);
+    protected ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+    protected ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+    protected ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+
+    // btree frames
+    protected ITreeIndexFrame leafFrame = leafFrameFactory.createFrame();
+    protected ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
+
+    protected IFreePageManager freePageManager;
+
+    protected BTree btree;
+
+    // --- INVERTED INDEX ---
+
+    protected FileReference invListsFile = new FileReference(new File(invListsFileName));
+    protected int invListsFileId;
+
+    protected int invListFields = 1;
+    protected ITypeTraits[] invListTypeTraits = new ITypeTraits[invListFields];
+
+    protected int invListKeys = 1;
+    protected IBinaryComparatorFactory[] invListCmpFactories = new IBinaryComparatorFactory[invListKeys];
+
+    protected InvertedIndex invIndex;
+
+    protected Random rnd = new Random();
+
+    protected ArrayTupleBuilder tb = new ArrayTupleBuilder(2);
+    protected ArrayTupleReference tuple = new ArrayTupleReference();
+
+    protected ISerializerDeserializer[] insertSerde = { UTF8StringSerializerDeserializer.INSTANCE,
+            IntegerSerializerDeserializer.INSTANCE };
+    protected RecordDescriptor insertRecDesc = new RecordDescriptor(insertSerde);
+
+    protected ArrayList<ArrayList<Integer>> checkInvLists = new ArrayList<ArrayList<Integer>>();
+
+    protected int maxId = 1000000;
+    protected int[] scanCountArray = new int[maxId];
+    protected ArrayList<Integer> expectedResults = new ArrayList<Integer>();
+
+    protected ISerializerDeserializer[] querySerde = { UTF8StringSerializerDeserializer.INSTANCE };
+    protected RecordDescriptor queryRecDesc = new RecordDescriptor(querySerde);
+
+    protected ArrayTupleBuilder queryTb = new ArrayTupleBuilder(querySerde.length);
+    protected ArrayTupleReference queryTuple = new ArrayTupleReference();
+
+    protected ITokenFactory tokenFactory;
+    protected IBinaryTokenizer tokenizer;
+
+    protected IIndexCursor resultCursor;
+
+    protected abstract void setTokenizer();
+    
+    /**
+     * Initialize members, generate data, and bulk load the inverted index.
+     */
+    @Before
+    public void start() throws Exception {
+        TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
+        bufferCache = TestStorageManagerComponentHolder.getBufferCache(taskCtx);
+        fmp = TestStorageManagerComponentHolder.getFileMapProvider(taskCtx);
+
+        // --- BTREE ---
+
+        bufferCache.createFile(btreeFile);
+        btreeFileId = fmp.lookupFileId(btreeFile);
+        bufferCache.openFile(btreeFileId);
+
+        btreeCmpFactories[0] = PointableBinaryComparatorFactory.of(UTF8StringPointable.FACTORY);
+
+        freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+
+        btree = new BTree(bufferCache, NoOpOperationCallback.INSTANCE, btreeTypeTraits.length, btreeCmpFactories,
+                freePageManager, interiorFrameFactory, leafFrameFactory);
+        btree.create(btreeFileId);
+        btree.open(btreeFileId);
+
+        // --- INVERTED INDEX ---
+
+        setTokenizer();
+        
+        bufferCache.createFile(invListsFile);
+        invListsFileId = fmp.lookupFileId(invListsFile);
+        bufferCache.openFile(invListsFileId);
+
+        invListTypeTraits[0] = IntegerPointable.TYPE_TRAITS;
+        invListCmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+        IInvertedListBuilder invListBuilder = new FixedSizeElementInvertedListBuilder(invListTypeTraits);
+        invIndex = new InvertedIndex(bufferCache, btree, invListTypeTraits, invListCmpFactories, invListBuilder);
+        invIndex.open(invListsFileId);
+
+        rnd.setSeed(50);
+    }
+
+    @After
+    public void deinit() throws HyracksDataException {
+        AbstractInvIndexTest.tearDown();
+        btree.close();
+        invIndex.close();
+        bufferCache.closeFile(btreeFileId);
+        bufferCache.closeFile(invListsFileId);
+        bufferCache.close();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/AbstractInvIndexTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/AbstractInvIndexTest.java
new file mode 100644
index 0000000..cc8ab15
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/AbstractInvIndexTest.java
@@ -0,0 +1,43 @@
+/*
+ * 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.invertedindex;
+
+import java.io.File;
+import java.text.SimpleDateFormat;
+import java.util.Date;
+import java.util.logging.Logger;
+
+public abstract class AbstractInvIndexTest {
+
+	protected static final Logger LOGGER = Logger
+			.getLogger(AbstractInvIndexTest.class.getName());
+
+	protected final static SimpleDateFormat simpleDateFormat = new SimpleDateFormat(
+			"ddMMyy-hhmmssSS");
+	protected final static String tmpDir = System.getProperty("java.io.tmpdir");
+	protected final static String sep = System.getProperty("file.separator");
+	protected final static String baseFileName = tmpDir + sep
+			+ simpleDateFormat.format(new Date());
+	protected final static String btreeFileName = baseFileName + "btree";
+	protected final static String invListsFileName = baseFileName + "invlists";
+
+	public static void tearDown() {
+		File btreeFile = new File(btreeFileName);
+		btreeFile.deleteOnExit();
+		File invListsFile = new File(invListsFileName);
+		invListsFile.deleteOnExit();
+	}
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/BulkLoadTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/BulkLoadTest.java
new file mode 100644
index 0000000..9fdc1c4
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/BulkLoadTest.java
@@ -0,0 +1,294 @@
+/*
+ * 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.invertedindex;
+
+import java.io.DataOutput;
+import java.io.File;
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
+import junit.framework.Assert;
+
+import org.junit.AfterClass;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
+import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.data.std.primitive.UTF8StringPointable;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.FrameTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+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.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.invertedindex.api.IInvertedListBuilder;
+import edu.uci.ics.hyracks.storage.am.invertedindex.api.IInvertedListCursor;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.FixedSizeElementInvertedListBuilder;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.FixedSizeElementInvertedListCursor;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.InvertedIndex;
+import edu.uci.ics.hyracks.storage.am.invertedindex.util.InvertedIndexUtils;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public class BulkLoadTest extends AbstractInvIndexTest {
+
+    private static final int PAGE_SIZE = 32768;
+    private static final int NUM_PAGES = 100;
+    private static final int MAX_OPEN_FILES = 10;
+    private static final int HYRACKS_FRAME_SIZE = 32768;
+    private IHyracksTaskContext stageletCtx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+    /**
+     * This test generates a list of <word-token, id> pairs which are pre-sorted
+     * on the token. Those pairs for the input to an inverted-index bulk load.
+     * The contents of the inverted lists are verified against the generated
+     * data.
+     */
+    @Test
+    public void singleFieldPayloadTest() throws Exception {
+
+        TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
+        IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(stageletCtx);
+        IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(stageletCtx);
+
+        // create file refs
+        FileReference btreeFile = new FileReference(new File(btreeFileName));
+        bufferCache.createFile(btreeFile);
+        int btreeFileId = fmp.lookupFileId(btreeFile);
+        bufferCache.openFile(btreeFileId);
+
+        FileReference invListsFile = new FileReference(new File(invListsFileName));
+        bufferCache.createFile(invListsFile);
+        int invListsFileId = fmp.lookupFileId(invListsFile);
+        bufferCache.openFile(invListsFileId);
+
+        // Declare token type traits, and compute BTree type traits.
+        ITypeTraits[] tokenTypeTraits = new ITypeTraits[] { UTF8StringPointable.TYPE_TRAITS };
+        ITypeTraits[] btreeTypeTraits = InvertedIndexUtils.getBTreeTypeTraits(tokenTypeTraits);
+
+        // declare btree keys
+        int keyFieldCount = 1;
+        IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+        cmpFactories[0] = PointableBinaryComparatorFactory.of(UTF8StringPointable.FACTORY);
+
+        TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(btreeTypeTraits);
+        ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+        ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+        ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+
+        ITreeIndexFrame leafFrame = leafFrameFactory.createFrame();
+
+        IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+
+        BTree btree = new BTree(bufferCache, NoOpOperationCallback.INSTANCE, btreeTypeTraits.length, cmpFactories,
+                freePageManager, interiorFrameFactory, leafFrameFactory);
+        btree.create(btreeFileId);
+        btree.open(btreeFileId);
+
+        int invListFields = 1;
+        ITypeTraits[] invListTypeTraits = new ITypeTraits[invListFields];
+        invListTypeTraits[0] = IntegerPointable.TYPE_TRAITS;
+
+        int invListKeys = 1;
+        IBinaryComparatorFactory[] invListCmpFactories = new IBinaryComparatorFactory[invListKeys];
+        invListCmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+        IInvertedListBuilder invListBuilder = new FixedSizeElementInvertedListBuilder(invListTypeTraits);
+        InvertedIndex invIndex = new InvertedIndex(bufferCache, btree, invListTypeTraits, invListCmpFactories, invListBuilder);
+        invIndex.open(invListsFileId);
+
+        Random rnd = new Random();
+        rnd.setSeed(50);
+
+        ByteBuffer frame = stageletCtx.allocateFrame();
+        FrameTupleAppender appender = new FrameTupleAppender(stageletCtx.getFrameSize());
+        ArrayTupleBuilder tb = new ArrayTupleBuilder(2);
+        DataOutput dos = tb.getDataOutput();
+
+        ISerializerDeserializer[] insertSerde = { UTF8StringSerializerDeserializer.INSTANCE,
+                IntegerSerializerDeserializer.INSTANCE };
+        RecordDescriptor insertRecDesc = new RecordDescriptor(insertSerde);
+        IFrameTupleAccessor accessor = new FrameTupleAccessor(stageletCtx.getFrameSize(), insertRecDesc);
+        accessor.reset(frame);
+        FrameTupleReference tuple = new FrameTupleReference();
+
+        List<String> tokens = new ArrayList<String>();
+        tokens.add("compilers");
+        tokens.add("computer");
+        tokens.add("databases");
+        tokens.add("fast");
+        tokens.add("hyracks");
+        tokens.add("major");
+        tokens.add("science");
+        tokens.add("systems");
+        tokens.add("university");
+
+        ArrayList<ArrayList<Integer>> checkListElements = new ArrayList<ArrayList<Integer>>();
+        for (int i = 0; i < tokens.size(); i++) {
+            checkListElements.add(new ArrayList<Integer>());
+        }
+
+        int maxId = 1000000;
+        int addProb = 0;
+        int addProbStep = 10;
+
+        IIndexBulkLoadContext ctx = invIndex.beginBulkLoad(BTree.DEFAULT_FILL_FACTOR);
+
+        for (int i = 0; i < tokens.size(); i++) {
+
+            addProb += addProbStep * (i + 1);
+            for (int j = 0; j < maxId; j++) {
+                if ((Math.abs(rnd.nextInt()) % addProb) == 0) {
+
+                    tb.reset();
+                    UTF8StringSerializerDeserializer.INSTANCE.serialize(tokens.get(i), dos);
+                    tb.addFieldEndOffset();
+                    IntegerSerializerDeserializer.INSTANCE.serialize(j, dos);
+                    tb.addFieldEndOffset();
+
+                    checkListElements.get(i).add(j);
+
+                    appender.reset(frame, true);
+                    appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+
+                    tuple.reset(accessor, 0);
+
+                    try {
+                        invIndex.bulkLoadAddTuple(tuple, ctx);
+                    } catch (Exception e) {
+                        e.printStackTrace();
+                    }
+                }
+            }
+        }
+        invIndex.endBulkLoad(ctx);
+
+        // ------- START VERIFICATION -----------
+
+        ITreeIndexCursor btreeCursor = new BTreeRangeSearchCursor((IBTreeLeafFrame) leafFrame, false);
+        FrameTupleReference searchKey = new FrameTupleReference();
+        MultiComparator btreeCmp = MultiComparator.create(cmpFactories);
+        RangePredicate btreePred = new RangePredicate(searchKey, searchKey, true, true, btreeCmp, btreeCmp);
+
+        IInvertedListCursor invListCursor = new FixedSizeElementInvertedListCursor(bufferCache, invListsFileId,
+                invListTypeTraits);
+
+        ISerializerDeserializer[] tokenSerde = { UTF8StringSerializerDeserializer.INSTANCE };
+        RecordDescriptor tokenRecDesc = new RecordDescriptor(tokenSerde);
+        FrameTupleAppender tokenAppender = new FrameTupleAppender(stageletCtx.getFrameSize());
+        ArrayTupleBuilder tokenTupleBuilder = new ArrayTupleBuilder(1);
+        DataOutput tokenDos = tokenTupleBuilder.getDataOutput();
+        IFrameTupleAccessor tokenAccessor = new FrameTupleAccessor(stageletCtx.getFrameSize(), tokenRecDesc);
+        tokenAccessor.reset(frame);
+
+        ITreeIndexAccessor btreeAccessor = invIndex.getBTree().createAccessor();
+
+        // verify created inverted lists one-by-one
+        for (int i = 0; i < tokens.size(); i++) {
+
+            tokenTupleBuilder.reset();
+            UTF8StringSerializerDeserializer.INSTANCE.serialize(tokens.get(i), tokenDos);
+            tokenTupleBuilder.addFieldEndOffset();
+
+            tokenAppender.reset(frame, true);
+            tokenAppender.append(tokenTupleBuilder.getFieldEndOffsets(), tokenTupleBuilder.getByteArray(), 0,
+                    tokenTupleBuilder.getSize());
+
+            searchKey.reset(tokenAccessor, 0);
+
+            invIndex.openCursor(btreeCursor, btreePred, btreeAccessor, invListCursor);
+
+            invListCursor.pinPagesSync();
+            int checkIndex = 0;
+            while (invListCursor.hasNext()) {
+                invListCursor.next();
+                ITupleReference invListTuple = invListCursor.getTuple();
+                int invListElement = IntegerSerializerDeserializer.getInt(invListTuple.getFieldData(0),
+                        invListTuple.getFieldStart(0));
+                int checkInvListElement = checkListElements.get(i).get(checkIndex).intValue();
+                Assert.assertEquals(invListElement, checkInvListElement);
+                checkIndex++;
+            }
+            invListCursor.unpinPages();
+            Assert.assertEquals(checkIndex, checkListElements.get(i).size());
+        }
+
+        // check that non-existing tokens have an empty inverted list
+        List<String> nonExistingTokens = new ArrayList<String>();
+        nonExistingTokens.add("watermelon");
+        nonExistingTokens.add("avocado");
+        nonExistingTokens.add("lemon");
+
+        for (int i = 0; i < nonExistingTokens.size(); i++) {
+
+            tokenTupleBuilder.reset();
+            UTF8StringSerializerDeserializer.INSTANCE.serialize(nonExistingTokens.get(i), tokenDos);
+            tokenTupleBuilder.addFieldEndOffset();
+
+            tokenAppender.reset(frame, true);
+            tokenAppender.append(tokenTupleBuilder.getFieldEndOffsets(), tokenTupleBuilder.getByteArray(), 0,
+                    tokenTupleBuilder.getSize());
+
+            searchKey.reset(tokenAccessor, 0);
+
+            invIndex.openCursor(btreeCursor, btreePred, btreeAccessor, invListCursor);
+
+            invListCursor.pinPagesSync();
+            Assert.assertEquals(invListCursor.hasNext(), false);
+            invListCursor.unpinPages();
+        }
+
+        btree.close();
+        bufferCache.closeFile(btreeFileId);
+        bufferCache.closeFile(invListsFileId);
+        bufferCache.close();
+    }
+
+    @AfterClass
+    public static void deinit() {
+        AbstractInvIndexTest.tearDown();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/FixedSizeFrameTupleTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/FixedSizeFrameTupleTest.java
new file mode 100644
index 0000000..9c7ec09
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/FixedSizeFrameTupleTest.java
@@ -0,0 +1,75 @@
+/*
+ * 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.invertedindex;
+
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.Random;
+
+import junit.framework.Assert;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.FixedSizeFrameTupleAccessor;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.FixedSizeFrameTupleAppender;
+
+public class FixedSizeFrameTupleTest {
+
+    private static int FRAME_SIZE = 4096;
+
+    private Random rnd = new Random(50);
+
+    /**
+     * This test verifies the correct behavior of the FixedSizeFrameTuple class.
+     * Frames containing FixedSizeFrameTuple's require neither tuple slots nor
+     * field slots. The tests inserts generated data into a frame until the
+     * frame is full, and then verifies the frame's contents.
+     * 
+     */
+    @Test
+    public void singleFieldTest() throws Exception {
+        ByteBuffer buffer = ByteBuffer.allocate(FRAME_SIZE);
+
+        ITypeTraits[] fields = new ITypeTraits[1];
+        fields[0] = IntegerPointable.TYPE_TRAITS;
+
+        FixedSizeFrameTupleAppender ftapp = new FixedSizeFrameTupleAppender(FRAME_SIZE, fields);
+        FixedSizeFrameTupleAccessor ftacc = new FixedSizeFrameTupleAccessor(FRAME_SIZE, fields);
+
+        boolean frameHasSpace = true;
+
+        ArrayList<Integer> check = new ArrayList<Integer>();
+
+        ftapp.reset(buffer, true);
+        while (frameHasSpace) {
+            int val = rnd.nextInt();
+            frameHasSpace = ftapp.append(val);
+            if (frameHasSpace) {
+                check.add(val);
+                ftapp.incrementTupleCount(1);
+            }
+        }
+
+        ftacc.reset(buffer);
+        for (int i = 0; i < ftacc.getTupleCount(); i++) {
+            int val = IntegerSerializerDeserializer.getInt(ftacc.getBuffer().array(), ftacc.getTupleStartOffset(i));
+            Assert.assertEquals(check.get(i).intValue(), val);
+        }
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/NGramTokenizerTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/NGramTokenizerTest.java
new file mode 100644
index 0000000..5f15a91
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/NGramTokenizerTest.java
@@ -0,0 +1,247 @@
+/**
+ * Copyright 2010-2011 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 at
+ *
+ *     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.
+ * 
+ * Author: Alexander Behm <abehm (at) ics.uci.edu>
+ */
+
+package edu.uci.ics.hyracks.storage.am.invertedindex;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.io.DataOutput;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashMap;
+
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.AbstractUTF8Token;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.HashedUTF8NGramTokenFactory;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.IToken;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.NGramUTF8StringBinaryTokenizer;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.UTF8NGramTokenFactory;
+
+public class NGramTokenizerTest {
+
+	private char PRECHAR = '#';
+	private char POSTCHAR = '$';
+
+	private String str = "Jürgen S. Generic's Car";
+	private byte[] inputBuffer;
+
+	private int gramLength = 3;
+
+	private void getExpectedGrams(String s, int gramLength,
+			ArrayList<String> grams, boolean prePost) {
+
+		String tmp = s.toLowerCase();
+		if (prePost) {
+			StringBuilder preBuilder = new StringBuilder();
+			for (int i = 0; i < gramLength - 1; i++) {
+				preBuilder.append(PRECHAR);
+			}
+			String pre = preBuilder.toString();
+
+			StringBuilder postBuilder = new StringBuilder();
+			for (int i = 0; i < gramLength - 1; i++) {
+				postBuilder.append(POSTCHAR);
+			}
+			String post = postBuilder.toString();
+
+			tmp = pre + s.toLowerCase() + post;
+		}
+
+		for (int i = 0; i < tmp.length() - gramLength + 1; i++) {
+			String gram = tmp.substring(i, i + gramLength);
+			grams.add(gram);
+		}
+	}
+
+	@Before
+	public void init() throws Exception {
+		// serialize string into bytes
+		ByteArrayOutputStream baos = new ByteArrayOutputStream();
+		DataOutput dos = new DataOutputStream(baos);
+		dos.writeUTF(str);
+		inputBuffer = baos.toByteArray();
+	}
+
+	void runTestNGramTokenizerWithCountedHashedUTF8Tokens(boolean prePost)
+			throws IOException {
+		HashedUTF8NGramTokenFactory tokenFactory = new HashedUTF8NGramTokenFactory();
+		NGramUTF8StringBinaryTokenizer tokenizer = new NGramUTF8StringBinaryTokenizer(
+				gramLength, prePost, false, false, tokenFactory);
+		tokenizer.reset(inputBuffer, 0, inputBuffer.length);
+
+		ArrayList<String> expectedGrams = new ArrayList<String>();
+		getExpectedGrams(str, gramLength, expectedGrams, prePost);
+		ArrayList<Integer> expectedHashedGrams = new ArrayList<Integer>();
+		HashMap<String, Integer> gramCounts = new HashMap<String, Integer>();
+		for (String s : expectedGrams) {
+			Integer count = gramCounts.get(s);
+			if (count == null) {
+				count = 1;
+				gramCounts.put(s, count);
+			} else {
+				count++;
+			}
+
+			int hash = tokenHash(s, count);
+			expectedHashedGrams.add(hash);
+		}
+
+		int tokenCount = 0;
+
+		while (tokenizer.hasNext()) {
+			tokenizer.next();
+
+			// serialize hashed token
+			ByteArrayOutputStream tokenBaos = new ByteArrayOutputStream();
+			DataOutput tokenDos = new DataOutputStream(tokenBaos);
+
+			IToken token = tokenizer.getToken();
+			token.serializeToken(tokenDos);
+
+			// deserialize token
+			ByteArrayInputStream bais = new ByteArrayInputStream(
+					tokenBaos.toByteArray());
+			DataInput in = new DataInputStream(bais);
+
+			Integer hashedGram = in.readInt();
+
+			// System.out.println(hashedGram);
+
+			Assert.assertEquals(expectedHashedGrams.get(tokenCount), hashedGram);
+
+			tokenCount++;
+		}
+		// System.out.println("---------");
+	}
+
+	void runTestNGramTokenizerWithHashedUTF8Tokens(boolean prePost)
+			throws IOException {
+		HashedUTF8NGramTokenFactory tokenFactory = new HashedUTF8NGramTokenFactory();
+		NGramUTF8StringBinaryTokenizer tokenizer = new NGramUTF8StringBinaryTokenizer(
+				gramLength, prePost, true, false, tokenFactory);
+		tokenizer.reset(inputBuffer, 0, inputBuffer.length);
+
+		ArrayList<String> expectedGrams = new ArrayList<String>();
+		getExpectedGrams(str, gramLength, expectedGrams, prePost);
+		ArrayList<Integer> expectedHashedGrams = new ArrayList<Integer>();
+		for (String s : expectedGrams) {
+			int hash = tokenHash(s, 1);
+			expectedHashedGrams.add(hash);
+		}
+
+		int tokenCount = 0;
+
+		while (tokenizer.hasNext()) {
+			tokenizer.next();
+
+			// serialize hashed token
+			ByteArrayOutputStream tokenBaos = new ByteArrayOutputStream();
+			DataOutput tokenDos = new DataOutputStream(tokenBaos);
+
+			IToken token = tokenizer.getToken();
+			token.serializeToken(tokenDos);
+
+			// deserialize token
+			ByteArrayInputStream bais = new ByteArrayInputStream(
+					tokenBaos.toByteArray());
+			DataInput in = new DataInputStream(bais);
+
+			Integer hashedGram = in.readInt();
+
+			// System.out.println(hashedGram);
+
+			Assert.assertEquals(expectedHashedGrams.get(tokenCount), hashedGram);
+
+			tokenCount++;
+		}
+		// System.out.println("---------");
+	}
+
+	void runTestNGramTokenizerWithUTF8Tokens(boolean prePost)
+			throws IOException {
+		UTF8NGramTokenFactory tokenFactory = new UTF8NGramTokenFactory();
+		NGramUTF8StringBinaryTokenizer tokenizer = new NGramUTF8StringBinaryTokenizer(
+				gramLength, prePost, true, false, tokenFactory);
+		tokenizer.reset(inputBuffer, 0, inputBuffer.length);
+
+		ArrayList<String> expectedGrams = new ArrayList<String>();
+		getExpectedGrams(str, gramLength, expectedGrams, prePost);
+
+		int tokenCount = 0;
+
+		while (tokenizer.hasNext()) {
+			tokenizer.next();
+
+			// serialize hashed token
+			ByteArrayOutputStream tokenBaos = new ByteArrayOutputStream();
+			DataOutput tokenDos = new DataOutputStream(tokenBaos);
+
+			IToken token = tokenizer.getToken();
+			token.serializeToken(tokenDos);
+
+			// deserialize token
+			ByteArrayInputStream bais = new ByteArrayInputStream(
+					tokenBaos.toByteArray());
+			DataInput in = new DataInputStream(bais);
+
+			String strGram = in.readUTF();
+
+			// System.out.println("\"" + strGram + "\"");
+
+			Assert.assertEquals(expectedGrams.get(tokenCount), strGram);
+
+			tokenCount++;
+		}
+		// System.out.println("---------");
+	}
+
+	@Test
+	public void testNGramTokenizerWithCountedHashedUTF8Tokens()
+			throws Exception {
+		runTestNGramTokenizerWithCountedHashedUTF8Tokens(false);
+		runTestNGramTokenizerWithCountedHashedUTF8Tokens(true);
+	}
+
+	@Test
+	public void testNGramTokenizerWithHashedUTF8Tokens() throws Exception {
+		runTestNGramTokenizerWithHashedUTF8Tokens(false);
+		runTestNGramTokenizerWithHashedUTF8Tokens(true);
+	}
+
+	@Test
+	public void testNGramTokenizerWithUTF8Tokens() throws IOException {
+		runTestNGramTokenizerWithUTF8Tokens(false);
+		runTestNGramTokenizerWithUTF8Tokens(true);
+	}
+
+	public int tokenHash(String token, int tokenCount) {
+		int h = AbstractUTF8Token.GOLDEN_RATIO_32;
+		for (int i = 0; i < token.length(); i++) {
+			h ^= token.charAt(i);
+			h *= AbstractUTF8Token.GOLDEN_RATIO_32;
+		}
+		return h + tokenCount;
+	}
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/SearchPerfTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/SearchPerfTest.java
new file mode 100644
index 0000000..33bf0c5
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/SearchPerfTest.java
@@ -0,0 +1,303 @@
+/*
+ * 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.invertedindex;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.logging.Level;
+
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.invertedindex.api.IInvertedIndexSearchModifier;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.InvertedIndex.InvertedIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.InvertedIndexSearchPredicate;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.OccurrenceThresholdPanicException;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.TOccurrenceSearcher;
+import edu.uci.ics.hyracks.storage.am.invertedindex.searchmodifiers.ConjunctiveSearchModifier;
+import edu.uci.ics.hyracks.storage.am.invertedindex.searchmodifiers.JaccardSearchModifier;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.DelimitedUTF8StringBinaryTokenizer;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.UTF8WordTokenFactory;
+
+/**
+ * The purpose of this test is to evaluate the performance of searches against
+ * an inverted index. First, we generate random <token, id> pairs sorted on
+ * token, which are bulk loaded into an inverted index. Next, we build random
+ * queries from a list of predefined tokens in the index, and measure the
+ * performance of executing them with different search modifiers. We test the
+ * ConjunctiveSearchModifier and the JaccardSearchModifier.
+ * 
+ */
+public class SearchPerfTest extends AbstractInvIndexSearchTest {
+
+	protected List<String> tokens = new ArrayList<String>();
+
+	@Override
+	protected void setTokenizer() {
+		tokenFactory = new UTF8WordTokenFactory();
+		tokenizer = new DelimitedUTF8StringBinaryTokenizer(true, false,
+				tokenFactory);
+	}
+	
+	@Before
+	public void start() throws Exception {
+		super.start();
+		loadData();
+	}
+
+	public void loadData() throws HyracksDataException, TreeIndexException {
+		tokens.add("compilers");
+		tokens.add("computer");
+		tokens.add("databases");
+		tokens.add("fast");
+		tokens.add("hyracks");
+		tokens.add("major");
+		tokens.add("science");
+		tokens.add("systems");
+		tokens.add("university");
+
+		for (int i = 0; i < tokens.size(); i++) {
+			checkInvLists.add(new ArrayList<Integer>());
+		}
+
+		// for generating length-skewed inverted lists
+		int addProb = 0;
+		int addProbStep = 10;
+
+		IIndexBulkLoadContext ctx = invIndex.beginBulkLoad(BTree.DEFAULT_FILL_FACTOR);
+
+		for (int i = 0; i < tokens.size(); i++) {
+
+			addProb += addProbStep * (i + 1);
+			for (int j = 0; j < maxId; j++) {
+				if ((Math.abs(rnd.nextInt()) % addProb) == 0) {
+					tb.reset();
+					UTF8StringSerializerDeserializer.INSTANCE.serialize(
+							tokens.get(i), tb.getDataOutput());
+					tb.addFieldEndOffset();
+					IntegerSerializerDeserializer.INSTANCE.serialize(j, tb.getDataOutput());
+					tb.addFieldEndOffset();
+					tuple.reset(tb.getFieldEndOffsets(), tb.getByteArray());
+					checkInvLists.get(i).add(j);
+					try {
+						invIndex.bulkLoadAddTuple(tuple, ctx);
+					} catch (Exception e) {
+						e.printStackTrace();
+					}
+				}
+			}
+		}
+		invIndex.endBulkLoad(ctx);
+	}
+
+	/**
+	 * Determine the expected results with the ScanCount algorithm. The
+	 * ScanCount algorithm is very simple, so we can be confident the results
+	 * are correct.
+	 * 
+	 */
+	protected void fillExpectedResults(int[] queryTokenIndexes,
+			int numQueryTokens, int occurrenceThreshold) {
+		// reset scan count array
+		for (int i = 0; i < maxId; i++) {
+			scanCountArray[i] = 0;
+		}
+
+		// count occurrences
+		for (int i = 0; i < numQueryTokens; i++) {
+			ArrayList<Integer> list = checkInvLists.get(queryTokenIndexes[i]);
+			for (int j = 0; j < list.size(); j++) {
+				scanCountArray[list.get(j)]++;
+			}
+		}
+
+		// check threshold
+		expectedResults.clear();
+		for (int i = 0; i < maxId; i++) {
+			if (scanCountArray[i] >= occurrenceThreshold) {
+				expectedResults.add(i);
+			}
+		}
+	}
+
+	/**
+	 * Generates a specified number of queries. Each query consists of a set of
+	 * randomly chosen tokens that are picked from the pre-defined set of
+	 * tokens. We run each query, measure it's time, and verify it's results
+	 * against the results produced by ScanCount, implemented in
+	 * fillExpectedResults().
+	 * 
+	 */
+	private void runQueries(IInvertedIndexSearchModifier searchModifier,
+			int numQueries) throws Exception {
+
+		rnd.setSeed(50);
+
+		InvertedIndexAccessor accessor = (InvertedIndexAccessor) invIndex.createAccessor();
+		InvertedIndexSearchPredicate searchPred = new InvertedIndexSearchPredicate(tokenizer, searchModifier);
+		
+		// generate random queries
+		int[] queryTokenIndexes = new int[tokens.size()];
+		for (int i = 0; i < numQueries; i++) {
+
+			int numQueryTokens = Math.abs(rnd.nextInt() % tokens.size()) + 1;
+			for (int j = 0; j < numQueryTokens; j++) {
+				queryTokenIndexes[j] = Math.abs(rnd.nextInt() % tokens.size());
+			}
+
+			StringBuilder strBuilder = new StringBuilder();
+			for (int j = 0; j < numQueryTokens; j++) {
+				strBuilder.append(tokens.get(queryTokenIndexes[j]));
+				if (j + 1 != numQueryTokens) {
+					strBuilder.append(" ");
+				}
+			}
+
+			String queryString = strBuilder.toString();
+
+			// Serialize query.
+			queryTb.reset();
+			UTF8StringSerializerDeserializer.INSTANCE.serialize(queryString,
+					queryTb.getDataOutput());
+			queryTb.addFieldEndOffset();
+			queryTuple.reset(queryTb.getFieldEndOffsets(), queryTb.getByteArray());
+
+			// Set query tuple in search predicate.
+			searchPred.setQueryTuple(queryTuple);
+			searchPred.setQueryFieldIndex(0);
+			
+			boolean panic = false;
+
+			resultCursor = accessor.createSearchCursor();
+			int repeats = 1;
+			double totalTime = 0;
+			for (int j = 0; j < repeats; j++) {
+				long timeStart = System.currentTimeMillis();
+				try {
+					resultCursor.reset();
+					accessor.search(resultCursor, searchPred);
+				} catch (OccurrenceThresholdPanicException e) {
+					panic = true;
+				}
+				long timeEnd = System.currentTimeMillis();
+				totalTime += timeEnd - timeStart;
+			}
+			double avgTime = totalTime / (double) repeats;
+			if (LOGGER.isLoggable(Level.INFO)) {
+				LOGGER.info(i + ": " + "\"" + queryString + "\": " + avgTime
+						+ "ms");
+			}
+
+			if (!panic) {
+				TOccurrenceSearcher searcher = (TOccurrenceSearcher) accessor.getSearcher();
+				fillExpectedResults(queryTokenIndexes, numQueryTokens,
+						searcher.getOccurrenceThreshold());
+				// verify results
+				int checkIndex = 0;
+				while (resultCursor.hasNext()) {
+					resultCursor.next();
+					ITupleReference resultTuple = resultCursor.getTuple();
+					int id = IntegerSerializerDeserializer.getInt(
+							resultTuple.getFieldData(0),
+							resultTuple.getFieldStart(0));
+					Assert.assertEquals(expectedResults.get(checkIndex)
+							.intValue(), id);
+					checkIndex++;
+				}
+
+				if (expectedResults.size() != checkIndex) {
+					if (LOGGER.isLoggable(Level.INFO)) {
+						LOGGER.info("CHECKING");
+					}
+					StringBuilder expectedStrBuilder = new StringBuilder();
+					for (Integer x : expectedResults) {
+						expectedStrBuilder.append(x + " ");
+					}
+					if (LOGGER.isLoggable(Level.INFO)) {
+						LOGGER.info(expectedStrBuilder.toString());
+					}
+				}
+
+				Assert.assertEquals(expectedResults.size(), checkIndex);
+			}
+		}
+	}
+
+	/**
+	 * Runs 50 random conjunctive search queries to test the
+	 * ConjunctiveSearchModifier.
+	 * 
+	 */
+	@Test
+	public void conjunctiveKeywordQueryTest() throws Exception {
+		IInvertedIndexSearchModifier searchModifier = new ConjunctiveSearchModifier();
+		runQueries(searchModifier, 50);
+	}
+
+	/**
+	 * Runs 50 random jaccard-based search queries with thresholds 1.0, 0.9,
+	 * 0.8, 0.7, 0.6, 0.5. Tests the JaccardSearchModifier.
+	 * 
+	 */
+	@Test
+	public void jaccardKeywordQueryTest() throws Exception {
+		JaccardSearchModifier searchModifier = new JaccardSearchModifier(1.0f);
+
+		if (LOGGER.isLoggable(Level.INFO)) {
+			LOGGER.info("JACCARD: " + 1.0f);
+		}
+		searchModifier.setJaccThresh(1.0f);
+		runQueries(searchModifier, 50);
+
+		if (LOGGER.isLoggable(Level.INFO)) {
+			LOGGER.info("JACCARD: " + 0.9f);
+		}
+		searchModifier.setJaccThresh(0.9f);
+		runQueries(searchModifier, 50);
+
+		if (LOGGER.isLoggable(Level.INFO)) {
+			LOGGER.info("JACCARD: " + 0.8f);
+		}
+		searchModifier.setJaccThresh(0.8f);
+		runQueries(searchModifier, 50);
+
+		if (LOGGER.isLoggable(Level.INFO)) {
+			LOGGER.info("JACCARD: " + 0.7f);
+		}
+		searchModifier.setJaccThresh(0.7f);
+		runQueries(searchModifier, 50);
+
+		if (LOGGER.isLoggable(Level.INFO)) {
+			LOGGER.info("JACCARD: " + 0.6f);
+		}
+		searchModifier.setJaccThresh(0.6f);
+		runQueries(searchModifier, 50);
+
+		if (LOGGER.isLoggable(Level.INFO)) {
+			LOGGER.info("JACCARD: " + 0.5f);
+		}
+		searchModifier.setJaccThresh(0.5f);
+		runQueries(searchModifier, 50);
+	}
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/SearchTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/SearchTest.java
new file mode 100644
index 0000000..c3c9b99
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/SearchTest.java
@@ -0,0 +1,308 @@
+/*
+ * 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.invertedindex;
+
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.logging.Level;
+
+import org.junit.Before;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.data.std.util.ByteArrayAccessibleOutputStream;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.invertedindex.api.IInvertedIndexSearchModifier;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.InvertedIndex.InvertedIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.InvertedIndexSearchPredicate;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.OccurrenceThresholdPanicException;
+import edu.uci.ics.hyracks.storage.am.invertedindex.searchmodifiers.ConjunctiveSearchModifier;
+import edu.uci.ics.hyracks.storage.am.invertedindex.searchmodifiers.EditDistanceSearchModifier;
+import edu.uci.ics.hyracks.storage.am.invertedindex.searchmodifiers.JaccardSearchModifier;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.IToken;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.NGramUTF8StringBinaryTokenizer;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.UTF8NGramTokenFactory;
+
+public class SearchTest extends AbstractInvIndexSearchTest {
+
+	protected List<String> dataStrings = new ArrayList<String>();
+	protected List<String> firstNames = new ArrayList<String>();
+	protected List<String> lastNames = new ArrayList<String>();
+
+	protected IBinaryComparator[] btreeBinCmps;
+	
+	@Override
+	protected void setTokenizer() {
+		tokenFactory = new UTF8NGramTokenFactory();
+		tokenizer = new NGramUTF8StringBinaryTokenizer(3, false, true, false,
+				tokenFactory);
+	}
+	
+	@Before
+	public void start() throws Exception {
+		super.start();
+		btreeBinCmps = new IBinaryComparator[btreeCmpFactories.length];
+		for (int i = 0; i < btreeCmpFactories.length; i++) {
+			btreeBinCmps[i] = btreeCmpFactories[i].createBinaryComparator();
+		}
+		generateDataStrings();
+		loadData();
+	}
+
+	public void generateDataStrings() {
+		firstNames.add("Kathrin");
+		firstNames.add("Cathrin");
+		firstNames.add("Kathryn");
+		firstNames.add("Cathryn");
+		firstNames.add("Kathrine");
+		firstNames.add("Cathrine");
+		firstNames.add("Kathryne");
+		firstNames.add("Cathryne");
+		firstNames.add("Katherin");
+		firstNames.add("Catherin");
+		firstNames.add("Katheryn");
+		firstNames.add("Catheryn");
+		firstNames.add("Katherine");
+		firstNames.add("Catherine");
+		firstNames.add("Katheryne");
+		firstNames.add("Catheryne");
+		firstNames.add("John");
+		firstNames.add("Jack");
+		firstNames.add("Jonathan");
+		firstNames.add("Nathan");
+
+		lastNames.add("Miller");
+		lastNames.add("Myller");
+		lastNames.add("Keller");
+		lastNames.add("Ketler");
+		lastNames.add("Muller");
+		lastNames.add("Fuller");
+		lastNames.add("Smith");
+		lastNames.add("Smyth");
+		lastNames.add("Smithe");
+		lastNames.add("Smythe");
+
+		// Generate all 'firstName lastName' combinations as data strings
+		for (String f : firstNames) {
+			for (String l : lastNames) {
+				dataStrings.add(f + " " + l);
+			}
+		}
+	}
+
+	private class TokenIdPair implements Comparable<TokenIdPair> {
+		public ByteArrayAccessibleOutputStream baaos = new ByteArrayAccessibleOutputStream();
+		public DataOutputStream dos = new DataOutputStream(baaos);
+		public int id;
+
+		TokenIdPair(IToken token, int id) throws IOException {
+			token.serializeToken(dos);
+			this.id = id;
+		}
+
+		@Override
+		public int compareTo(TokenIdPair o) {
+			int cmp = btreeBinCmps[0].compare(baaos.getByteArray(), 0,
+					baaos.getByteArray().length, o.baaos.getByteArray(), 0,
+					o.baaos.getByteArray().length);
+			if (cmp == 0) {
+				return id - o.id;
+			} else {
+				return cmp;
+			}
+		}
+	}
+
+	public void loadData() throws IOException, TreeIndexException {
+		List<TokenIdPair> pairs = new ArrayList<TokenIdPair>();
+		// generate pairs for subsequent sorting and bulk-loading
+		int id = 0;
+		for (String s : dataStrings) {
+			ByteArrayAccessibleOutputStream baaos = new ByteArrayAccessibleOutputStream();
+			DataOutputStream dos = new DataOutputStream(baaos);
+			UTF8StringSerializerDeserializer.INSTANCE.serialize(s, dos);
+			tokenizer.reset(baaos.getByteArray(), 0, baaos.size());
+			while (tokenizer.hasNext()) {
+				tokenizer.next();
+				IToken token = tokenizer.getToken();
+				pairs.add(new TokenIdPair(token, id));
+			}
+			++id;
+		}
+		Collections.sort(pairs);
+
+		// bulk load index
+		IIndexBulkLoadContext ctx = invIndex.beginBulkLoad(BTree.DEFAULT_FILL_FACTOR);
+
+		for (TokenIdPair t : pairs) {
+			tb.reset();
+			tb.addField(t.baaos.getByteArray(), 0,
+					t.baaos.getByteArray().length);
+			IntegerSerializerDeserializer.INSTANCE.serialize(t.id, tb.getDataOutput());
+			tb.addFieldEndOffset();
+			tuple.reset(tb.getFieldEndOffsets(), tb.getByteArray());
+
+			try {
+				invIndex.bulkLoadAddTuple(tuple, ctx);
+			} catch (Exception e) {
+				e.printStackTrace();
+			}
+		}
+		invIndex.endBulkLoad(ctx);
+	}
+
+	/**
+	 * Runs a specified number of randomly picked strings from dataStrings as
+	 * queries. We run each query, measure it's time, and print it's results.
+	 * 
+	 */
+	private void runQueries(IInvertedIndexSearchModifier searchModifier,
+			int numQueries) throws Exception {
+
+		rnd.setSeed(50);
+
+		InvertedIndexAccessor accessor = (InvertedIndexAccessor) invIndex.createAccessor();
+		InvertedIndexSearchPredicate searchPred = new InvertedIndexSearchPredicate(tokenizer, searchModifier);
+		
+		for (int i = 0; i < numQueries; i++) {
+
+			int queryIndex = Math.abs(rnd.nextInt() % dataStrings.size());
+			String queryString = dataStrings.get(queryIndex);
+
+			// Serialize query.
+			queryTb.reset();
+			UTF8StringSerializerDeserializer.INSTANCE.serialize(queryString,
+					queryTb.getDataOutput());
+			queryTb.addFieldEndOffset();
+			queryTuple.reset(queryTb.getFieldEndOffsets(), queryTb.getByteArray());
+
+			// Set query tuple in search predicate.
+			searchPred.setQueryTuple(queryTuple);
+			searchPred.setQueryFieldIndex(0);
+			
+			resultCursor = accessor.createSearchCursor();
+			
+			int repeats = 1;
+			double totalTime = 0;
+			for (int j = 0; j < repeats; j++) {
+				long timeStart = System.currentTimeMillis();
+				try {
+					resultCursor.reset();
+					accessor.search(resultCursor, searchPred);
+				} catch (OccurrenceThresholdPanicException e) {
+					// ignore panic queries
+				}
+				long timeEnd = System.currentTimeMillis();
+				totalTime += timeEnd - timeStart;
+			}
+			double avgTime = totalTime / (double) repeats;
+			StringBuilder strBuilder = new StringBuilder();
+			strBuilder.append(i + ": " + "\"" + queryString + "\": " + avgTime
+					+ "ms" + "\n");
+			strBuilder.append("CANDIDATE RESULTS:\n");
+			while (resultCursor.hasNext()) {
+				resultCursor.next();
+				ITupleReference resultTuple = resultCursor.getTuple();
+				int id = IntegerSerializerDeserializer.getInt(
+						resultTuple.getFieldData(0),
+						resultTuple.getFieldStart(0));
+				strBuilder.append(id + " " + dataStrings.get(id));
+				strBuilder.append('\n');
+			}
+			// remove trailing newline
+			strBuilder.deleteCharAt(strBuilder.length() - 1);
+			if (LOGGER.isLoggable(Level.INFO)) {
+				LOGGER.info(strBuilder.toString());
+			}
+		}
+	}
+
+	/**
+	 * Runs 5 random conjunctive search queries to test the
+	 * ConjunctiveSearchModifier.
+	 * 
+	 */
+	@Test
+	public void conjunctiveQueryTest() throws Exception {
+		IInvertedIndexSearchModifier searchModifier = new ConjunctiveSearchModifier();
+		runQueries(searchModifier, 5);
+	}
+
+	/**
+	 * Runs 5 random jaccard-based search queries with thresholds 0.9, 0.8, 0.7.
+	 * Tests the JaccardSearchModifier.
+	 * 
+	 */
+	@Test
+	public void jaccardQueryTest() throws Exception {
+		JaccardSearchModifier searchModifier = new JaccardSearchModifier(1.0f);
+
+		if (LOGGER.isLoggable(Level.INFO)) {
+			LOGGER.info("JACCARD: " + 0.9f);
+		}
+		searchModifier.setJaccThresh(0.9f);
+		runQueries(searchModifier, 5);
+
+		if (LOGGER.isLoggable(Level.INFO)) {
+			LOGGER.info("JACCARD: " + 0.8f);
+		}
+		searchModifier.setJaccThresh(0.8f);
+		runQueries(searchModifier, 5);
+
+		if (LOGGER.isLoggable(Level.INFO)) {
+			LOGGER.info("JACCARD: " + 0.7f);
+		}
+		searchModifier.setJaccThresh(0.7f);
+		runQueries(searchModifier, 5);
+	}
+
+	/**
+	 * Runs 5 random edit-distance based search queries with thresholds 1, 2, 3.
+	 * Tests the EditDistanceSearchModifier.
+	 * 
+	 */
+	@Test
+	public void editDistanceQueryTest() throws Exception {
+		EditDistanceSearchModifier searchModifier = new EditDistanceSearchModifier(
+				3, 0);
+
+		if (LOGGER.isLoggable(Level.INFO)) {
+			LOGGER.info("EDIT DISTANCE: " + 1);
+		}
+		searchModifier.setEdThresh(1);
+		runQueries(searchModifier, 5);
+
+		if (LOGGER.isLoggable(Level.INFO)) {
+			LOGGER.info("EDIT DISTANCE: " + 2);
+		}
+		searchModifier.setEdThresh(2);
+		runQueries(searchModifier, 5);
+
+		if (LOGGER.isLoggable(Level.INFO)) {
+			LOGGER.info("EDIT DISTANCE: " + 3);
+		}
+		searchModifier.setEdThresh(3);
+		runQueries(searchModifier, 5);
+	}
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/WordTokenizerTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/WordTokenizerTest.java
new file mode 100644
index 0000000..53fb96d
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/WordTokenizerTest.java
@@ -0,0 +1,221 @@
+/**
+ * Copyright 2010-2011 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 at
+ *
+ *     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.
+ * 
+ * Author: Alexander Behm <abehm (at) ics.uci.edu>
+ */
+
+package edu.uci.ics.hyracks.storage.am.invertedindex;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.io.DataOutput;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashMap;
+
+import junit.framework.Assert;
+
+import org.junit.Before;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.AbstractUTF8Token;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.DelimitedUTF8StringBinaryTokenizer;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.HashedUTF8WordTokenFactory;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.IToken;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.UTF8WordTokenFactory;
+
+public class WordTokenizerTest {
+
+    private String text = "Hello World, I would like to inform you of the importance of Foo Bar. Yes, Foo Bar. Jürgen.";
+    private byte[] inputBuffer;
+
+    private ArrayList<String> expectedUTF8Tokens = new ArrayList<String>();
+    private ArrayList<Integer> expectedHashedUTF8Tokens = new ArrayList<Integer>();
+    private ArrayList<Integer> expectedCountedHashedUTF8Tokens = new ArrayList<Integer>();
+
+    private boolean isSeparator(char c) {
+        return !(Character.isLetterOrDigit(c) || Character.getType(c) == Character.OTHER_LETTER || Character.getType(c) == Character.OTHER_NUMBER);
+    }
+    
+    private void tokenize(String text, ArrayList<String> tokens) {
+    	String lowerCaseText = text.toLowerCase();
+    	int startIx = 0;
+    	
+    	// Skip separators at beginning of string.
+    	while(isSeparator(lowerCaseText.charAt(startIx))) {
+    		startIx++;
+    	}
+    	while(startIx < lowerCaseText.length()) {
+    		while(startIx < lowerCaseText.length() && isSeparator(lowerCaseText.charAt(startIx))) {
+        	    startIx++;
+        	}
+    		int tokenStart = startIx;
+    		
+    		while(startIx < lowerCaseText.length() && !isSeparator(lowerCaseText.charAt(startIx))) {
+        	    startIx++;
+        	}
+    		int tokenEnd = startIx;
+    		
+    		// Emit token.
+    		String token = lowerCaseText.substring(tokenStart, tokenEnd);
+    		
+    		tokens.add(token);
+    	}
+    }
+    
+    @Before
+    public void init() throws IOException {
+        // serialize text into bytes
+        ByteArrayOutputStream baos = new ByteArrayOutputStream();
+        DataOutput dos = new DataOutputStream(baos);
+        dos.writeUTF(text);
+        inputBuffer = baos.toByteArray();
+        
+        // init expected string tokens
+        tokenize(text, expectedUTF8Tokens);
+        
+        // hashed tokens ignoring token count
+        for (int i = 0; i < expectedUTF8Tokens.size(); i++) {
+            int hash = tokenHash(expectedUTF8Tokens.get(i), 1);
+            expectedHashedUTF8Tokens.add(hash);
+        }
+
+        // hashed tokens using token count
+        HashMap<String, Integer> tokenCounts = new HashMap<String, Integer>();
+        for (int i = 0; i < expectedUTF8Tokens.size(); i++) {
+            Integer count = tokenCounts.get(expectedUTF8Tokens.get(i));
+            if (count == null) {
+                count = 1;
+                tokenCounts.put(expectedUTF8Tokens.get(i), count);
+            } else {
+                count++;
+            }
+
+            int hash = tokenHash(expectedUTF8Tokens.get(i), count);
+            expectedCountedHashedUTF8Tokens.add(hash);
+        }
+    }
+
+    @Test
+    public void testWordTokenizerWithCountedHashedUTF8Tokens() throws IOException {
+
+        HashedUTF8WordTokenFactory tokenFactory = new HashedUTF8WordTokenFactory();
+        DelimitedUTF8StringBinaryTokenizer tokenizer = new DelimitedUTF8StringBinaryTokenizer(false, false,
+                tokenFactory);
+
+        tokenizer.reset(inputBuffer, 0, inputBuffer.length);
+
+        int tokenCount = 0;
+
+        while (tokenizer.hasNext()) {
+            tokenizer.next();
+
+            // serialize token
+            ByteArrayOutputStream tokenBaos = new ByteArrayOutputStream();
+            DataOutput tokenDos = new DataOutputStream(tokenBaos);
+
+            IToken token = tokenizer.getToken();
+            token.serializeToken(tokenDos);
+
+            // deserialize token
+            ByteArrayInputStream bais = new ByteArrayInputStream(tokenBaos.toByteArray());
+            DataInput in = new DataInputStream(bais);
+
+            Integer hashedToken = in.readInt();
+
+            Assert.assertEquals(hashedToken, expectedCountedHashedUTF8Tokens.get(tokenCount));
+
+            tokenCount++;
+        }
+    }
+
+    @Test
+    public void testWordTokenizerWithHashedUTF8Tokens() throws IOException {
+
+        HashedUTF8WordTokenFactory tokenFactory = new HashedUTF8WordTokenFactory();
+        DelimitedUTF8StringBinaryTokenizer tokenizer = new DelimitedUTF8StringBinaryTokenizer(true, false, tokenFactory);
+
+        tokenizer.reset(inputBuffer, 0, inputBuffer.length);
+
+        int tokenCount = 0;
+
+        while (tokenizer.hasNext()) {
+            tokenizer.next();
+
+            // serialize token
+            ByteArrayOutputStream tokenBaos = new ByteArrayOutputStream();
+            DataOutput tokenDos = new DataOutputStream(tokenBaos);
+
+            IToken token = tokenizer.getToken();
+            token.serializeToken(tokenDos);
+
+            // deserialize token
+            ByteArrayInputStream bais = new ByteArrayInputStream(tokenBaos.toByteArray());
+            DataInput in = new DataInputStream(bais);
+
+            Integer hashedToken = in.readInt();
+
+            Assert.assertEquals(expectedHashedUTF8Tokens.get(tokenCount), hashedToken);
+
+            tokenCount++;
+        }
+    }
+
+    @Test
+    public void testWordTokenizerWithUTF8Tokens() throws IOException {
+
+        UTF8WordTokenFactory tokenFactory = new UTF8WordTokenFactory();
+        DelimitedUTF8StringBinaryTokenizer tokenizer = new DelimitedUTF8StringBinaryTokenizer(true, false, tokenFactory);
+
+        tokenizer.reset(inputBuffer, 0, inputBuffer.length);
+
+        int tokenCount = 0;
+
+        while (tokenizer.hasNext()) {
+            tokenizer.next();
+
+            // serialize hashed token
+            ByteArrayOutputStream tokenBaos = new ByteArrayOutputStream();
+            DataOutput tokenDos = new DataOutputStream(tokenBaos);
+
+            IToken token = tokenizer.getToken();
+            token.serializeToken(tokenDos);
+
+            // deserialize token
+            ByteArrayInputStream bais = new ByteArrayInputStream(tokenBaos.toByteArray());
+            DataInput in = new DataInputStream(bais);
+
+            String strToken = in.readUTF();
+
+            Assert.assertEquals(expectedUTF8Tokens.get(tokenCount), strToken);
+
+            tokenCount++;
+        }
+    }
+
+    // JAQL Hash
+    public int tokenHash(String token, int tokenCount) {
+        int h = AbstractUTF8Token.GOLDEN_RATIO_32;
+        for (int i = 0; i < token.length(); i++) {
+        	h ^= token.charAt(i);
+            h *= AbstractUTF8Token.GOLDEN_RATIO_32;
+        }
+        return h + tokenCount;
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
new file mode 100644
index 0000000..247969e
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
@@ -0,0 +1,50 @@
+<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-rtree-test</artifactId>
+  <version>0.2.2-SNAPSHOT</version>
+  <name>hyracks-storage-am-rtree-test</name>
+
+  <parent>
+    <groupId>edu.uci.ics.hyracks</groupId>
+    <artifactId>hyracks-tests</artifactId>
+    <version>0.2.2-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>junit</groupId>
+  		<artifactId>junit</artifactId>
+  		<version>4.8.1</version>
+  		<type>jar</type>
+  		<scope>test</scope>
+  	</dependency>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-storage-am-rtree</artifactId>
+  		<version>0.2.2-SNAPSHOT</version>
+  		<type>jar</type>
+  		<scope>compile</scope>
+  	</dependency>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-test-support</artifactId>
+  		<version>0.2.2-SNAPSHOT</version>
+  		<type>jar</type>
+  		<scope>test</scope>
+  	</dependency>
+  </dependencies>
+</project>
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeBulkLoadTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeBulkLoadTest.java
new file mode 100644
index 0000000..58bca10
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeBulkLoadTest.java
@@ -0,0 +1,61 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.rtree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeBulkLoadTest;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
+
+@SuppressWarnings("rawtypes")
+public class RTreeBulkLoadTest extends AbstractRTreeBulkLoadTest {
+
+    public RTreeBulkLoadTest() {
+        super(1);
+    }
+
+    private final RTreeTestHarness harness = new RTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+            IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
+        return RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(), fieldSerdes,
+                valueProviderFactories, numKeys);
+    }
+
+    @Override
+    protected Random getRandom() {
+        return harness.getRandom();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeDeleteTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeDeleteTest.java
new file mode 100644
index 0000000..42e933e
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeDeleteTest.java
@@ -0,0 +1,57 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.rtree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeDeleteTest;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
+
+@SuppressWarnings("rawtypes")
+public class RTreeDeleteTest extends AbstractRTreeDeleteTest {
+
+    private final RTreeTestHarness harness = new RTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+            IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
+        return RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(), fieldSerdes,
+                valueProviderFactories, numKeys);
+    }
+
+    @Override
+    protected Random getRandom() {
+        return harness.getRandom();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeExamplesTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeExamplesTest.java
new file mode 100644
index 0000000..c72338e
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeExamplesTest.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.rtree;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeExamplesTest;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
+
+public class RTreeExamplesTest extends AbstractRTreeExamplesTest {
+    private final RTreeTestHarness harness = new RTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparatorFactory[] rtreeCmpFactories,
+            IBinaryComparatorFactory[] btreeCmpFactories, IPrimitiveValueProviderFactory[] valueProviderFactories)
+            throws TreeIndexException {
+        return RTreeUtils.createRTree(harness.getBufferCache(), typeTraits,
+                valueProviderFactories, rtreeCmpFactories);
+    }
+
+    @Override
+    protected int getIndexFileId() {
+        return harness.getTreeFileId();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java
new file mode 100644
index 0000000..6efa620
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java
@@ -0,0 +1,67 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.rtree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeInsertTest;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
+
+/**
+ * Tests the BTree insert operation with strings and integer fields using
+ * various numbers of key and payload fields.
+ * 
+ * Each tests first fills a BTree with randomly generated tuples. We compare the
+ * following operations against expected results: 1. Point searches for all
+ * tuples. 2. Ordered scan. 3. Disk-order scan. 4. Range search (and prefix
+ * search for composite keys).
+ * 
+ */
+@SuppressWarnings("rawtypes")
+public class RTreeInsertTest extends AbstractRTreeInsertTest {
+
+    private final RTreeTestHarness harness = new RTreeTestHarness();
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+            IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
+        return RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(), fieldSerdes,
+                valueProviderFactories, numKeys);
+    }
+
+    @Override
+    protected Random getRandom() {
+        return harness.getRandom();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
new file mode 100644
index 0000000..8332c11
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
@@ -0,0 +1,175 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.rtree;
+
+import java.util.ArrayList;
+import java.util.Random;
+import java.util.logging.Level;
+
+import org.junit.Before;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.RTreeCheckTuple;
+import edu.uci.ics.hyracks.storage.am.rtree.RTreeTestUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.AbstractRTreeTest;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+public class RTreeSearchCursorTest extends AbstractRTreeTest {
+
+    private final RTreeTestUtils rTreeTestUtils;
+    private Random rnd = new Random(50);
+
+    public RTreeSearchCursorTest() {
+        this.rTreeTestUtils = new RTreeTestUtils();
+    }
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        super.setUp();
+    }
+
+    @SuppressWarnings({ "unchecked", "rawtypes" })
+    @Test
+    public void rangeSearchTest() throws Exception {
+        if (LOGGER.isLoggable(Level.INFO)) {
+            LOGGER.info("TESTING RANGE SEARCH CURSOR FOR RTREE");
+        }
+
+        IBufferCache bufferCache = harness.getBufferCache();
+        int rtreeFileId = harness.getTreeFileId();
+
+        // Declare fields.
+        int fieldCount = 5;
+        ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+        typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+        typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+        typeTraits[2] = IntegerPointable.TYPE_TRAITS;
+        typeTraits[3] = IntegerPointable.TYPE_TRAITS;
+        typeTraits[4] = IntegerPointable.TYPE_TRAITS;
+        // Declare field serdes.
+        ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE,
+                IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE,
+                IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+
+        // Declare keys.
+        int keyFieldCount = 4;
+        IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+        cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        cmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        cmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+        cmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+        // create value providers
+        IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
+                cmpFactories.length, IntegerPointable.FACTORY);
+
+        RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
+        ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+
+        ITreeIndexFrameFactory interiorFrameFactory = new RTreeNSMInteriorFrameFactory(tupleWriterFactory,
+                valueProviderFactories);
+        ITreeIndexFrameFactory leafFrameFactory = new RTreeNSMLeafFrameFactory(tupleWriterFactory,
+                valueProviderFactories);
+
+        IRTreeInteriorFrame interiorFrame = (IRTreeInteriorFrame) interiorFrameFactory.createFrame();
+        IRTreeLeafFrame leafFrame = (IRTreeLeafFrame) leafFrameFactory.createFrame();
+        IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+
+        RTree rtree = new RTree(bufferCache, fieldCount, cmpFactories, freePageManager, interiorFrameFactory,
+                leafFrameFactory);
+        rtree.create(rtreeFileId);
+        rtree.open(rtreeFileId);
+
+        ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+        ArrayTupleReference tuple = new ArrayTupleReference();
+        ITreeIndexAccessor indexAccessor = rtree.createAccessor();
+        int numInserts = 10000;
+        ArrayList<RTreeCheckTuple> checkTuples = new ArrayList<RTreeCheckTuple>();
+        for (int i = 0; i < numInserts; i++) {
+            int p1x = rnd.nextInt();
+            int p1y = rnd.nextInt();
+            int p2x = rnd.nextInt();
+            int p2y = rnd.nextInt();
+
+            int pk = rnd.nextInt();;
+
+            TupleUtils.createIntegerTuple(tb, tuple, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+                    Math.max(p1y, p2y), pk);
+            try {
+                indexAccessor.insert(tuple);
+            } catch (TreeIndexException e) {
+            }
+            RTreeCheckTuple checkTuple = new RTreeCheckTuple(fieldCount, keyFieldCount);
+            checkTuple.add(Math.min(p1x, p2x));
+            checkTuple.add(Math.min(p1y, p2y));
+            checkTuple.add(Math.max(p1x, p2x));
+            checkTuple.add(Math.max(p1y, p2y));
+            checkTuple.add(pk);
+
+            checkTuples.add(checkTuple);
+        }
+
+        // Build key.
+        ArrayTupleBuilder keyTb = new ArrayTupleBuilder(keyFieldCount);
+        ArrayTupleReference key = new ArrayTupleReference();
+        TupleUtils.createIntegerTuple(keyTb, key, -1000, -1000, 1000, 1000);
+
+        MultiComparator cmp = MultiComparator.create(cmpFactories);
+        ITreeIndexCursor searchCursor = new RTreeSearchCursor(interiorFrame, leafFrame);
+        SearchPredicate searchPredicate = new SearchPredicate(key, cmp);
+
+        RTreeCheckTuple keyCheck = (RTreeCheckTuple) rTreeTestUtils.createCheckTupleFromTuple(key, fieldSerdes,
+                keyFieldCount);
+        ArrayList<RTreeCheckTuple> expectedResult = rTreeTestUtils.getRangeSearchExpectedResults(checkTuples, keyCheck);
+
+        rTreeTestUtils.getRangeSearchExpectedResults(checkTuples, keyCheck);
+        indexAccessor.search(searchCursor, searchPredicate);
+
+        rTreeTestUtils.checkExpectedResults(searchCursor, expectedResult, fieldSerdes, keyFieldCount, null);
+
+        rtree.close();
+    }
+
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeMultiThreadTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeMultiThreadTest.java
new file mode 100644
index 0000000..7520793
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeMultiThreadTest.java
@@ -0,0 +1,97 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.rtree.multithread;
+
+import java.util.ArrayList;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.ITreeIndexTestWorkerFactory;
+import edu.uci.ics.hyracks.storage.am.common.TestWorkloadConf;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector.TestOperation;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeMultiThreadTest;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
+
+public class RTreeMultiThreadTest extends AbstractRTreeMultiThreadTest {
+
+    private RTreeTestHarness harness = new RTreeTestHarness();
+
+    private RTreeTestWorkerFactory workerFactory = new RTreeTestWorkerFactory();
+
+    @Override
+    protected void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @Override
+    protected void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+
+    @Override
+    protected ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparatorFactory[] rtreeCmpFactories,
+            IBinaryComparatorFactory[] btreeCmpFactories, IPrimitiveValueProviderFactory[] valueProviderFactories)
+            throws TreeIndexException {
+        return RTreeUtils.createRTree(harness.getBufferCache(), typeTraits,
+                valueProviderFactories, rtreeCmpFactories);
+
+    }
+
+    @Override
+    protected ITreeIndexTestWorkerFactory getWorkerFactory() {
+        return workerFactory;
+    }
+
+    @Override
+    protected ArrayList<TestWorkloadConf> getTestWorkloadConf() {
+        ArrayList<TestWorkloadConf> workloadConfs = new ArrayList<TestWorkloadConf>();
+
+        // Insert only workload.
+        TestOperation[] insertOnlyOps = new TestOperation[] { TestOperation.INSERT };
+        workloadConfs.add(new TestWorkloadConf(insertOnlyOps, getUniformOpProbs(insertOnlyOps)));
+
+        // Inserts mixed with scans.
+        TestOperation[] insertSearchOnlyOps = new TestOperation[] { TestOperation.INSERT, TestOperation.SCAN,
+                TestOperation.DISKORDER_SCAN };
+        workloadConfs.add(new TestWorkloadConf(insertSearchOnlyOps, getUniformOpProbs(insertSearchOnlyOps)));
+
+        // Inserts and deletes.
+        TestOperation[] insertDeleteOps = new TestOperation[] { TestOperation.INSERT, TestOperation.DELETE };
+        workloadConfs.add(new TestWorkloadConf(insertDeleteOps, getUniformOpProbs(insertDeleteOps)));
+
+        // All operations mixed.
+        TestOperation[] allOps = new TestOperation[] { TestOperation.INSERT, TestOperation.DELETE, TestOperation.SCAN,
+                TestOperation.DISKORDER_SCAN };
+        workloadConfs.add(new TestWorkloadConf(allOps, getUniformOpProbs(allOps)));
+
+        return workloadConfs;
+    }
+
+    @Override
+    protected int getFileId() {
+        return harness.getTreeFileId();
+    }
+
+    @Override
+    protected String getIndexTypeName() {
+        return "RTree";
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeTestWorker.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeTestWorker.java
new file mode 100644
index 0000000..f5867e6
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeTestWorker.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.rtree.multithread;
+
+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.ArrayTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.AbstractTreeIndexTestWorker;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector.TestOperation;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexCursor;
+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.IndexException;
+import edu.uci.ics.hyracks.storage.am.common.datagen.DataGenThread;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
+
+public class RTreeTestWorker extends AbstractTreeIndexTestWorker {
+
+    private final RTree rtree;
+    private final int numFields;
+    private final ArrayTupleReference rearrangedTuple = new ArrayTupleReference();
+    private final ArrayTupleBuilder rearrangedTb;
+
+    public RTreeTestWorker(DataGenThread dataGen, TestOperationSelector opSelector, ITreeIndex index, int numBatches) {
+        super(dataGen, opSelector, index, numBatches);
+        rtree = (RTree) index;
+        numFields = rtree.getFieldCount();
+        rearrangedTb = new ArrayTupleBuilder(numFields);
+    }
+
+    @Override
+    public void performOp(ITupleReference tuple, TestOperation op) throws HyracksDataException, IndexException {
+        RTree.RTreeAccessor accessor = (RTree.RTreeAccessor) indexAccessor;
+        IIndexCursor searchCursor = accessor.createSearchCursor();
+        ITreeIndexCursor diskOrderScanCursor = accessor.createDiskOrderScanCursor();
+        MultiComparator cmp = accessor.getOpContext().cmp;
+        SearchPredicate rangePred = new SearchPredicate(tuple, cmp);
+
+        switch (op) {
+            case INSERT:
+                rearrangeTuple(tuple, cmp);
+                accessor.insert(rearrangedTuple);
+                break;
+
+            case DELETE:
+                rearrangeTuple(tuple, cmp);
+                accessor.delete(rearrangedTuple);
+                break;
+
+            case SCAN:
+                searchCursor.reset();
+                rangePred.setSearchKey(null);
+                accessor.search(searchCursor, rangePred);
+                consumeCursorTuples(searchCursor);
+                break;
+
+            case DISKORDER_SCAN:
+                diskOrderScanCursor.reset();
+                accessor.diskOrderScan(diskOrderScanCursor);
+                consumeCursorTuples(diskOrderScanCursor);
+                break;
+
+            default:
+                throw new HyracksDataException("Op " + op.toString() + " not supported.");
+        }
+    }
+
+    private void rearrangeTuple(ITupleReference tuple, MultiComparator cmp) throws HyracksDataException {
+        // Create a tuple with rearranged key values to make sure lower points
+        // have larger coordinates than high points.
+        rearrangedTb.reset();
+        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        for (int i = 0; i < maxFieldPos; i++) {
+            int j = maxFieldPos + i;
+            int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
+                    tuple.getFieldLength(i), tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j));
+            if (c > 0) {
+                rearrangedTb.addField(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j));
+            } else {
+                rearrangedTb.addField(tuple.getFieldData(i), tuple.getFieldStart(i), tuple.getFieldLength(i));
+            }
+        }
+        for (int i = 0; i < maxFieldPos; i++) {
+            int j = maxFieldPos + i;
+            int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
+                    tuple.getFieldLength(i), tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j));
+            if (c > 0) {
+                rearrangedTb.addField(tuple.getFieldData(i), tuple.getFieldStart(i), tuple.getFieldLength(i));
+            } else {
+                rearrangedTb.addField(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j));
+            }
+        }
+        for (int i = cmp.getKeyFieldCount(); i < numFields; i++) {
+            rearrangedTb.addField(tuple.getFieldData(i), tuple.getFieldStart(i), tuple.getFieldLength(i));
+        }
+        rearrangedTuple.reset(rearrangedTb.getFieldEndOffsets(), rearrangedTb.getByteArray());
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeTestWorkerFactory.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeTestWorkerFactory.java
new file mode 100644
index 0000000..d4f14ca
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeTestWorkerFactory.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.rtree.multithread;
+
+import edu.uci.ics.hyracks.storage.am.common.AbstractTreeIndexTestWorker;
+import edu.uci.ics.hyracks.storage.am.common.ITreeIndexTestWorkerFactory;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.datagen.DataGenThread;
+
+public class RTreeTestWorkerFactory implements ITreeIndexTestWorkerFactory {
+    @Override
+    public AbstractTreeIndexTestWorker create(DataGenThread dataGen, TestOperationSelector opSelector,
+            ITreeIndex index, int numBatches) {
+        return new RTreeTestWorker(dataGen, opSelector, index, numBatches);
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/AbstractRTreeTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/AbstractRTreeTest.java
new file mode 100644
index 0000000..fccb29c
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/AbstractRTreeTest.java
@@ -0,0 +1,46 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.rtree.utils;
+
+import java.util.logging.Logger;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+
+public abstract class AbstractRTreeTest {
+    protected final Logger LOGGER = Logger.getLogger(RTreeTestHarness.class.getName());
+    protected final RTreeTestHarness harness;
+
+    public AbstractRTreeTest() {
+        harness = new RTreeTestHarness();
+    }
+
+    public AbstractRTreeTest(int pageSize, int numPages, int maxOpenFiles, int hyracksFrameSize) {
+        harness = new RTreeTestHarness(pageSize, numPages, maxOpenFiles, hyracksFrameSize);
+    }
+
+    @Before
+    public void setUp() throws HyracksDataException {
+        harness.setUp();
+    }
+
+    @After
+    public void tearDown() throws HyracksDataException {
+        harness.tearDown();
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestContext.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestContext.java
new file mode 100644
index 0000000..039fb0b
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestContext.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.rtree.utils;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.dataflow.common.util.SerdeUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+@SuppressWarnings("rawtypes")
+public class RTreeTestContext extends AbstractRTreeTestContext {
+
+    public RTreeTestContext(ISerializerDeserializer[] fieldSerdes, ITreeIndex treeIndex) {
+        super(fieldSerdes, treeIndex);
+    }
+
+    @Override
+    public int getKeyFieldCount() {
+        RTree rtree = (RTree) treeIndex;
+        return rtree.getComparatorFactories().length;
+    }
+
+    @Override
+    public IBinaryComparatorFactory[] getComparatorFactories() {
+        RTree rtree = (RTree) treeIndex;
+        return rtree.getComparatorFactories();
+    }
+
+    public static RTreeTestContext create(IBufferCache bufferCache, int rtreeFileId,
+            ISerializerDeserializer[] fieldSerdes, IPrimitiveValueProviderFactory[] valueProviderFactories,
+            int numKeyFields) throws Exception {
+        ITypeTraits[] typeTraits = SerdeUtils.serdesToTypeTraits(fieldSerdes);
+        IBinaryComparatorFactory[] cmpFactories = SerdeUtils.serdesToComparatorFactories(fieldSerdes, numKeyFields);
+        RTree rtree = RTreeUtils
+                .createRTree(bufferCache, typeTraits, valueProviderFactories, cmpFactories);
+        rtree.create(rtreeFileId);
+        rtree.open(rtreeFileId);
+        RTreeTestContext testCtx = new RTreeTestContext(fieldSerdes, rtree);
+        return testCtx;
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestHarness.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestHarness.java
new file mode 100644
index 0000000..c0cec35
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestHarness.java
@@ -0,0 +1,123 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.rtree.utils;
+
+import java.io.File;
+import java.text.SimpleDateFormat;
+import java.util.Date;
+import java.util.Random;
+
+import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public class RTreeTestHarness {
+
+    private static final long RANDOM_SEED = 50;
+    private static final int DEFAULT_PAGE_SIZE = 256;
+    private static final int DEFAULT_NUM_PAGES = 1000;
+    private static final int DEFAULT_MAX_OPEN_FILES = 10;
+    private static final int DEFAULT_HYRACKS_FRAME_SIZE = 128;
+
+    protected final int pageSize;
+    protected final int numPages;
+    protected final int maxOpenFiles;
+    protected final int hyracksFrameSize;
+
+    protected IHyracksTaskContext ctx;
+    protected IBufferCache bufferCache;
+    protected int treeFileId;
+
+    protected final Random rnd = new Random();
+    protected final SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
+    protected final String tmpDir = System.getProperty("java.io.tmpdir");
+    protected final String sep = System.getProperty("file.separator");
+    protected String fileName;
+
+    public RTreeTestHarness() {
+        this.pageSize = DEFAULT_PAGE_SIZE;
+        this.numPages = DEFAULT_NUM_PAGES;
+        this.maxOpenFiles = DEFAULT_MAX_OPEN_FILES;
+        this.hyracksFrameSize = DEFAULT_HYRACKS_FRAME_SIZE;
+    }
+
+    public RTreeTestHarness(int pageSize, int numPages, int maxOpenFiles, int hyracksFrameSize) {
+        this.pageSize = pageSize;
+        this.numPages = numPages;
+        this.maxOpenFiles = maxOpenFiles;
+        this.hyracksFrameSize = hyracksFrameSize;
+    }
+
+    public void setUp() throws HyracksDataException {
+        fileName = tmpDir + sep + simpleDateFormat.format(new Date());
+        ctx = TestUtils.create(getHyracksFrameSize());
+        TestStorageManagerComponentHolder.init(pageSize, numPages, maxOpenFiles);
+        bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+        IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+        FileReference file = new FileReference(new File(fileName));
+        bufferCache.createFile(file);
+        treeFileId = fmp.lookupFileId(file);
+        bufferCache.openFile(treeFileId);
+        rnd.setSeed(RANDOM_SEED);
+    }
+
+    public void tearDown() throws HyracksDataException {
+        bufferCache.closeFile(treeFileId);
+        bufferCache.close();
+        File f = new File(fileName);
+        f.deleteOnExit();
+    }
+
+    public IHyracksTaskContext getHyracksTaskContext() {
+        return ctx;
+    }
+
+    public IBufferCache getBufferCache() {
+        return bufferCache;
+    }
+
+    public int getTreeFileId() {
+        return treeFileId;
+    }
+
+    public String getFileName() {
+        return fileName;
+    }
+
+    public Random getRandom() {
+        return rnd;
+    }
+
+    public int getPageSize() {
+        return pageSize;
+    }
+
+    public int getNumPages() {
+        return numPages;
+    }
+
+    public int getHyracksFrameSize() {
+        return hyracksFrameSize;
+    }
+
+    public int getMaxOpenFiles() {
+        return maxOpenFiles;
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/pom.xml b/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/pom.xml
new file mode 100644
index 0000000..b01f2a7
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/pom.xml
@@ -0,0 +1,49 @@
+<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-common-test</artifactId>
+  <version>0.2.2-SNAPSHOT</version>
+  <name>hyracks-storage-common-test</name>
+
+  <parent>
+    <groupId>edu.uci.ics.hyracks</groupId>
+    <artifactId>hyracks-tests</artifactId>
+    <version>0.2.2-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>junit</groupId>
+  		<artifactId>junit</artifactId>
+  		<version>4.8.1</version>
+  		<type>jar</type>
+  		<scope>test</scope>
+  	</dependency>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-storage-common</artifactId>
+  		<version>0.2.2-SNAPSHOT</version>
+  		<scope>compile</scope>
+  	</dependency>
+  	<dependency>
+  		<groupId>edu.uci.ics.hyracks</groupId>
+  		<artifactId>hyracks-test-support</artifactId>
+  		<version>0.2.2-SNAPSHOT</version>
+  		<type>jar</type>
+  		<scope>compile</scope>
+  	</dependency>
+  </dependencies>
+</project>
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/src/test/java/edu/uci/ics/hyracks/storage/common/BufferCacheRegressionTests.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/src/test/java/edu/uci/ics/hyracks/storage/common/BufferCacheRegressionTests.java
new file mode 100644
index 0000000..a649aa7
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/src/test/java/edu/uci/ics/hyracks/storage/common/BufferCacheRegressionTests.java
@@ -0,0 +1,171 @@
+package edu.uci.ics.hyracks.storage.common;
+
+import static org.junit.Assert.fail;
+
+import java.io.File;
+import java.io.IOException;
+import java.nio.ByteBuffer;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.api.io.IFileHandle;
+import edu.uci.ics.hyracks.api.io.IIOManager;
+import edu.uci.ics.hyracks.api.io.IIOManager.FileReadWriteMode;
+import edu.uci.ics.hyracks.api.io.IIOManager.FileSyncMode;
+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;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public class BufferCacheRegressionTests {
+    protected static final String tmpDir = System.getProperty("java.io.tmpdir");
+    protected static final String sep = System.getProperty("file.separator");
+
+    protected String fileName = tmpDir + sep + "flushTestFile";
+
+    private static final int PAGE_SIZE = 256;
+    private static final int HYRACKS_FRAME_SIZE = PAGE_SIZE;
+    private IHyracksTaskContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+    // We want to test the following behavior when reclaiming a file slot in the
+    // buffer cache:
+    // 1. If the file being evicted was deleted, then its dirty pages should be
+    // invalidated, but most not be flushed.
+    // 2. If the file was not deleted, then we must flush its dirty pages.
+    @Test
+    public void testFlushBehaviorOnFileEviction() throws IOException {
+        File f = new File(fileName);
+        if (f.exists()) {
+            f.delete();
+        }
+        flushBehaviorTest(true);
+        flushBehaviorTest(false);
+    }
+
+    private void flushBehaviorTest(boolean deleteFile) throws IOException {
+        TestStorageManagerComponentHolder.init(PAGE_SIZE, 10, 1);
+
+        IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+        IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+
+        FileReference firstFileRef = new FileReference(new File(fileName));
+        bufferCache.createFile(firstFileRef);
+        int firstFileId = fmp.lookupFileId(firstFileRef);
+        bufferCache.openFile(firstFileId);
+
+        // Fill the first page with known data and make it dirty by write
+        // latching it.
+        ICachedPage writePage = bufferCache.pin(BufferedFileHandle.getDiskPageId(firstFileId, 0), true);
+        writePage.acquireWriteLatch();
+        try {
+            ByteBuffer buf = writePage.getBuffer();
+            for (int i = 0; i < buf.capacity(); i++) {
+                buf.put(Byte.MAX_VALUE);
+            }
+        } finally {
+            writePage.releaseWriteLatch();
+            bufferCache.unpin(writePage);
+        }
+        bufferCache.closeFile(firstFileId);
+        if (deleteFile) {
+            bufferCache.deleteFile(firstFileId, false);
+        }
+
+        // Create a file with the same name.
+        FileReference secondFileRef = new FileReference(new File(fileName));
+        bufferCache.createFile(secondFileRef);
+        int secondFileId = fmp.lookupFileId(secondFileRef);
+
+        // This open will replace the firstFileRef's slot in the BufferCache,
+        // causing it's pages to be cleaned up. We want to make sure that those
+        // dirty pages are not flushed to the disk, because the file was
+        // declared as deleted, and
+        // somebody might be already using the same filename again (having been
+        // assigned a different fileId).
+        bufferCache.openFile(secondFileId);
+
+        // Manually open the file and inspect it's contents. We cannot simply
+        // ask the BufferCache to pin the page, because it would return the same
+        // physical memory again, and for performance reasons pages are never
+        // reset with 0's.
+        IIOManager ioManager = ctx.getIOManager();
+        FileReference testFileRef = new FileReference(new File(fileName));
+        IFileHandle testFileHandle = ioManager.open(testFileRef, FileReadWriteMode.READ_ONLY,
+                FileSyncMode.METADATA_SYNC_DATA_SYNC);
+        ByteBuffer testBuffer = ByteBuffer.allocate(PAGE_SIZE);
+        ioManager.syncRead(testFileHandle, 0, testBuffer);
+        for (int i = 0; i < testBuffer.capacity(); i++) {
+            if (deleteFile) {
+                // We deleted the file. We expect to see a clean buffer.
+                if (testBuffer.get(i) == Byte.MAX_VALUE) {
+                    fail("Page 0 of deleted file was fazily flushed in openFile(), "
+                            + "corrupting the data of a newly created file with the same name.");
+                }
+            } else {
+                // We didn't delete the file. We expect to see a buffer full of
+                // Byte.MAX_VALUE.
+                if (testBuffer.get(i) != Byte.MAX_VALUE) {
+                    fail("Page 0 of closed file was not flushed when properly, when reclaiming the file slot of fileId 0 in the BufferCache.");
+                }
+            }
+        }
+        ioManager.close(testFileHandle);
+        bufferCache.closeFile(secondFileId);
+        if (deleteFile) {
+            bufferCache.deleteFile(secondFileId, false);
+        }
+        bufferCache.close();
+    }
+
+    // Tests the behavior of the BufferCache when more than all pages are
+    // pinned. We expect an exception.
+    @Test
+    public void testPinningAllPages() throws HyracksDataException {
+        int numPages = 10;
+        TestStorageManagerComponentHolder.init(PAGE_SIZE, numPages, 1);
+
+        IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+        IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+
+        FileReference firstFileRef = new FileReference(new File(fileName));
+        bufferCache.createFile(firstFileRef);
+        int fileId = fmp.lookupFileId(firstFileRef);
+        bufferCache.openFile(fileId);
+
+        // Pin all pages.
+        ICachedPage[] pages = new ICachedPage[numPages];
+        for (int i = 0; i < numPages; ++i) {
+            pages[i] = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, i), true);
+        }
+
+        // Try to pin another page. We expect a HyracksDataException.
+        ICachedPage errorPage = null;
+        try {
+            errorPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, numPages), true);
+        } catch (HyracksDataException e) {
+            // This is the expected outcome.
+            // The BufferCache should still be able to function properly.
+            // Try unpinning all pages.
+            for (int i = 0; i < numPages; ++i) {
+                bufferCache.unpin(pages[i]);
+            }
+            // Now try pinning the page that failed above again.
+            errorPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, numPages), true);
+            // Unpin it.
+            bufferCache.unpin(errorPage);
+            // Cleanup.
+            bufferCache.closeFile(fileId);
+            bufferCache.close();
+            return;
+        } catch (Exception e) {
+            fail("Expected a HyracksDataException when pinning more pages than available but got another exception: "
+                    + e.getMessage());
+        }
+        fail("Expected a HyracksDataException when pinning more pages than available.");
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/src/test/java/edu/uci/ics/hyracks/storage/common/BufferCacheTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/src/test/java/edu/uci/ics/hyracks/storage/common/BufferCacheTest.java
new file mode 100644
index 0000000..80502eb
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/src/test/java/edu/uci/ics/hyracks/storage/common/BufferCacheTest.java
@@ -0,0 +1,310 @@
+package edu.uci.ics.hyracks.storage.common;
+
+import java.io.File;
+import java.text.SimpleDateFormat;
+import java.util.ArrayList;
+import java.util.Date;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Random;
+
+import org.junit.AfterClass;
+import org.junit.Assert;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+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;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public class BufferCacheTest {
+    protected static final List<String> openedFiles = new ArrayList<String>();
+    protected static final SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
+    protected static final String tmpDir = System.getProperty("java.io.tmpdir");
+    protected static final String sep = System.getProperty("file.separator");
+
+    private static final int PAGE_SIZE = 256;
+    private static final int NUM_PAGES = 10;
+    private static final int MAX_OPEN_FILES = 20;
+    private static final int HYRACKS_FRAME_SIZE = PAGE_SIZE;
+    private IHyracksTaskContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+    private static final Random rnd = new Random(50);
+
+    private String getFileName() {
+        String fileName = tmpDir + sep + simpleDateFormat.format(new Date()) + openedFiles.size();
+        openedFiles.add(fileName);
+        return fileName;
+    }
+
+    @Test
+    public void simpleOpenPinCloseTest() throws HyracksDataException {
+        TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
+        IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+        IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+        String fileName = getFileName();
+        FileReference file = new FileReference(new File(fileName));
+        bufferCache.createFile(file);
+        int fileId = fmp.lookupFileId(file);
+        int num = 10;
+        int testPageId = 0;
+
+        bufferCache.openFile(fileId);
+
+        ICachedPage page = null;
+
+        // tryPin should fail
+        page = bufferCache.tryPin(BufferedFileHandle.getDiskPageId(fileId, testPageId));
+        Assert.assertNull(page);
+
+        // pin page should succeed
+        page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, testPageId), true);
+        page.acquireWriteLatch();
+        try {
+            for (int i = 0; i < num; i++) {
+                page.getBuffer().putInt(i * 4, i);
+            }
+
+            // try pin should succeed         
+            ICachedPage page2 = bufferCache.tryPin(BufferedFileHandle.getDiskPageId(fileId, testPageId));
+            Assert.assertNotNull(page2);
+            bufferCache.unpin(page2);
+
+        } finally {
+            page.releaseWriteLatch();
+            bufferCache.unpin(page);
+        }
+
+        bufferCache.closeFile(fileId);
+
+        boolean exceptionThrown = false;
+
+        // tryPin should fail since file is not open
+        try {
+            page = bufferCache.tryPin(BufferedFileHandle.getDiskPageId(fileId, testPageId));
+        } catch (HyracksDataException e) {
+            exceptionThrown = true;
+        }
+        Assert.assertTrue(exceptionThrown);
+
+        // pin should fail since file is not open
+        exceptionThrown = false;
+        try {
+            page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, testPageId), false);
+        } catch (HyracksDataException e) {
+            exceptionThrown = true;
+        }
+        Assert.assertTrue(exceptionThrown);
+
+        // open file again
+        bufferCache.openFile(fileId);
+
+        // tryPin should succeed because page should still be cached        
+        page = bufferCache.tryPin(BufferedFileHandle.getDiskPageId(fileId, testPageId));
+        Assert.assertNotNull(page);
+        page.acquireReadLatch();
+        try {
+            // verify contents of page
+            for (int i = 0; i < num; i++) {
+                Assert.assertEquals(page.getBuffer().getInt(i * 4), i);
+            }
+        } finally {
+            page.releaseReadLatch();
+            bufferCache.unpin(page);
+        }
+
+        bufferCache.closeFile(fileId);
+        bufferCache.close();
+    }
+
+    @Test
+    public void simpleMaxOpenFilesTest() throws HyracksDataException {
+        TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
+        IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+        IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+
+        List<Integer> fileIds = new ArrayList<Integer>();
+
+        for (int i = 0; i < MAX_OPEN_FILES; i++) {
+            String fileName = getFileName();
+            FileReference file = new FileReference(new File(fileName));
+            bufferCache.createFile(file);
+            int fileId = fmp.lookupFileId(file);
+            bufferCache.openFile(fileId);
+            fileIds.add(fileId);
+        }
+
+        boolean exceptionThrown = false;
+
+        // since all files are open, next open should fail
+        try {
+            String fileName = getFileName();
+            FileReference file = new FileReference(new File(fileName));
+            bufferCache.createFile(file);
+            int fileId = fmp.lookupFileId(file);
+            bufferCache.openFile(fileId);
+        } catch (HyracksDataException e) {
+            exceptionThrown = true;
+        }
+        Assert.assertTrue(exceptionThrown);
+
+        // close a random file
+        int ix = Math.abs(rnd.nextInt()) % fileIds.size();
+        bufferCache.closeFile(fileIds.get(ix));
+        fileIds.remove(ix);
+
+        // now open should succeed again
+        exceptionThrown = false;
+        try {
+            String fileName = getFileName();
+            FileReference file = new FileReference(new File(fileName));
+            bufferCache.createFile(file);
+            int fileId = fmp.lookupFileId(file);
+            bufferCache.openFile(fileId);
+            fileIds.add(fileId);
+
+        } catch (HyracksDataException e) {
+            exceptionThrown = true;
+        }
+        Assert.assertFalse(exceptionThrown);
+
+        for (Integer i : fileIds) {
+            bufferCache.closeFile(i.intValue());
+        }
+
+        bufferCache.close();
+    }
+
+    @Test
+    public void contentCheckingMaxOpenFilesTest() throws HyracksDataException {
+        TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
+        IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+        IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+
+        List<Integer> fileIds = new ArrayList<Integer>();
+        Map<Integer, ArrayList<Integer>> pageContents = new HashMap<Integer, ArrayList<Integer>>();
+        int num = 10;
+        int testPageId = 0;
+
+        // open max number of files and write some stuff into their first page
+        for (int i = 0; i < MAX_OPEN_FILES; i++) {
+            String fileName = getFileName();
+            FileReference file = new FileReference(new File(fileName));
+            bufferCache.createFile(file);
+            int fileId = fmp.lookupFileId(file);
+            bufferCache.openFile(fileId);
+            fileIds.add(fileId);
+
+            ICachedPage page = null;
+            page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, testPageId), true);
+            page.acquireWriteLatch();
+            try {
+                ArrayList<Integer> values = new ArrayList<Integer>();
+                for (int j = 0; j < num; j++) {
+                    int x = Math.abs(rnd.nextInt());
+                    page.getBuffer().putInt(j * 4, x);
+                    values.add(x);
+                }
+                pageContents.put(fileId, values);
+            } finally {
+                page.releaseWriteLatch();
+                bufferCache.unpin(page);
+            }
+        }
+
+        boolean exceptionThrown = false;
+
+        // since all files are open, next open should fail
+        try {
+            String fileName = getFileName();
+            FileReference file = new FileReference(new File(fileName));
+            bufferCache.createFile(file);
+            int fileId = fmp.lookupFileId(file);
+            bufferCache.openFile(fileId);
+        } catch (HyracksDataException e) {
+            exceptionThrown = true;
+        }
+        Assert.assertTrue(exceptionThrown);
+
+        // close a few random files
+        ArrayList<Integer> closedFileIds = new ArrayList<Integer>();
+        int filesToClose = 5;
+        for (int i = 0; i < filesToClose; i++) {
+            int ix = Math.abs(rnd.nextInt()) % fileIds.size();
+            bufferCache.closeFile(fileIds.get(ix));
+            closedFileIds.add(fileIds.get(ix));
+            fileIds.remove(ix);
+        }
+
+        // now open a few new files
+        for (int i = 0; i < filesToClose; i++) {
+            String fileName = getFileName();
+            FileReference file = new FileReference(new File(fileName));
+            bufferCache.createFile(file);
+            int fileId = fmp.lookupFileId(file);
+            bufferCache.openFile(fileId);
+            fileIds.add(fileId);
+        }
+
+        // since all files are open, next open should fail
+        try {
+            String fileName = getFileName();
+            FileReference file = new FileReference(new File(fileName));
+            bufferCache.createFile(file);
+            int fileId = fmp.lookupFileId(file);
+            bufferCache.openFile(fileId);
+        } catch (HyracksDataException e) {
+            exceptionThrown = true;
+        }
+        Assert.assertTrue(exceptionThrown);
+
+        // close a few random files again        
+        for (int i = 0; i < filesToClose; i++) {
+            int ix = Math.abs(rnd.nextInt()) % fileIds.size();
+            bufferCache.closeFile(fileIds.get(ix));
+            closedFileIds.add(fileIds.get(ix));
+            fileIds.remove(ix);
+        }
+
+        // now open those closed files again and verify their contents
+        for (int i = 0; i < filesToClose; i++) {
+            int closedFileId = closedFileIds.get(i);
+            bufferCache.openFile(closedFileId);
+            fileIds.add(closedFileId);
+
+            // pin first page and verify contents
+            ICachedPage page = null;
+            page = bufferCache.pin(BufferedFileHandle.getDiskPageId(closedFileId, testPageId), false);
+            page.acquireReadLatch();
+            try {
+                ArrayList<Integer> values = pageContents.get(closedFileId);
+                for (int j = 0; j < values.size(); j++) {
+                    Assert.assertEquals(values.get(j).intValue(), page.getBuffer().getInt(j * 4));
+                }
+            } finally {
+                page.releaseReadLatch();
+                bufferCache.unpin(page);
+            }
+        }
+
+        for (Integer i : fileIds) {
+            bufferCache.closeFile(i.intValue());
+        }
+
+        bufferCache.close();
+    }
+
+    @AfterClass
+    public static void cleanup() throws Exception {
+        for (String s : openedFiles) {
+            File f = new File(s);
+            f.deleteOnExit();
+        }
+    }
+}
diff --git a/fullstack/hyracks/hyracks-tests/pom.xml b/fullstack/hyracks/hyracks-tests/pom.xml
new file mode 100644
index 0000000..cc5d7bc
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/pom.xml
@@ -0,0 +1,21 @@
+<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-tests</artifactId>
+  <version>0.2.2-SNAPSHOT</version>
+  <packaging>pom</packaging>
+  <name>hyracks-tests</name>
+
+  <parent>
+    <groupId>edu.uci.ics.hyracks</groupId>
+    <artifactId>hyracks</artifactId>
+    <version>0.2.2-SNAPSHOT</version>
+  </parent>
+
+  <modules>
+    <module>hyracks-storage-common-test</module>
+    <module>hyracks-storage-am-btree-test</module>
+    <module>hyracks-storage-am-invertedindex-test</module>
+    <module>hyracks-storage-am-rtree-test</module>
+  </modules>
+</project>