diff --git a/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/data/accessors/FrameTupleReference.java b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/data/accessors/FrameTupleReference.java
index ff45eba..a21d5e9 100644
--- a/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/data/accessors/FrameTupleReference.java
+++ b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/data/accessors/FrameTupleReference.java
@@ -1,3 +1,18 @@
+/*
+ * 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.dataflow.common.data.accessors;
 
 import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
diff --git a/hyracks-examples/hyracks-integration-tests/src/test/java/edu/uci/ics/hyracks/tests/btree/BTreeSecondaryIndexSearchOperatorTest.java b/hyracks-examples/hyracks-integration-tests/src/test/java/edu/uci/ics/hyracks/tests/btree/BTreeSecondaryIndexSearchOperatorTest.java
index 60c3b13..57fef2e 100644
--- a/hyracks-examples/hyracks-integration-tests/src/test/java/edu/uci/ics/hyracks/tests/btree/BTreeSecondaryIndexSearchOperatorTest.java
+++ b/hyracks-examples/hyracks-integration-tests/src/test/java/edu/uci/ics/hyracks/tests/btree/BTreeSecondaryIndexSearchOperatorTest.java
@@ -361,7 +361,6 @@
 	public static void cleanup() throws Exception {
 		File primary = new File(primaryFileName);
 		primary.deleteOnExit();
-
 		File secondary = new File(secondaryFileName);
 		secondary.deleteOnExit();
 	}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeDuplicateKeyException.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeDuplicateKeyException.java
similarity index 83%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeDuplicateKeyException.java
rename to hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeDuplicateKeyException.java
index 1aa7fff..7105670 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeDuplicateKeyException.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeDuplicateKeyException.java
@@ -1,4 +1,4 @@
-package edu.uci.ics.hyracks.storage.am.btree.impls;
+package edu.uci.ics.hyracks.storage.am.btree.exceptions;
 
 public class BTreeDuplicateKeyException extends BTreeException {
     private static final long serialVersionUID = 1L;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeException.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeException.java
similarity index 95%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeException.java
rename to hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeException.java
index 1658989..1e09658 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeException.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeException.java
@@ -13,7 +13,7 @@
  * limitations under the License.
  */
 
-package edu.uci.ics.hyracks.storage.am.btree.impls;
+package edu.uci.ics.hyracks.storage.am.btree.exceptions;
 
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
 
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeNotUpdateableException.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeNotUpdateableException.java
new file mode 100644
index 0000000..fb2e4a4
--- /dev/null
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeNotUpdateableException.java
@@ -0,0 +1,13 @@
+package edu.uci.ics.hyracks.storage.am.btree.exceptions;
+
+public class BTreeNotUpdateableException extends BTreeException {
+    private static final long serialVersionUID = 1L;
+    
+    public BTreeNotUpdateableException(Exception e) {
+        super(e);
+    }
+    
+    public BTreeNotUpdateableException(String message) {
+        super(message);
+    }
+}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
index f74e2ee..b662c4e 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
@@ -30,8 +30,8 @@
 import edu.uci.ics.hyracks.storage.am.btree.api.IFrameCompressor;
 import edu.uci.ics.hyracks.storage.am.btree.api.IPrefixSlotManager;
 import edu.uci.ics.hyracks.storage.am.btree.compressors.FieldPrefixCompressor;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeDuplicateKeyException;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeDuplicateKeyException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
 import edu.uci.ics.hyracks.storage.am.btree.impls.FieldPrefixPrefixTupleReference;
 import edu.uci.ics.hyracks.storage.am.btree.impls.FieldPrefixSlotManager;
 import edu.uci.ics.hyracks.storage.am.btree.impls.FieldPrefixTupleReference;
@@ -67,8 +67,8 @@
     protected ICachedPage page = null;
     protected ByteBuffer buf = null;
     public IFrameCompressor compressor;
-    public IPrefixSlotManager slotManager; // TODO: should be protected, but
-    // will trigger some refactoring
+    // TODO: Should be protected, but will trigger some refactoring.
+    public IPrefixSlotManager slotManager;
 
     private ITreeIndexTupleWriter tupleWriter;
 
@@ -258,11 +258,98 @@
     }
 
     @Override
-    public FrameOpSpaceStatus hasSpaceUpdate(ITupleReference tuple, int oldTupleIndex, MultiComparator cmp) {
-        // TODO Auto-generated method stub
+    public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception {
+        int slot = slotManager.insertSlot(tupleIndex, buf.getInt(freeSpaceOff));
+        int prefixSlotNum = slotManager.decodeFirstSlotField(slot);
+        int numPrefixFields = 0;
+        if (prefixSlotNum != FieldPrefixSlotManager.TUPLE_UNCOMPRESSED) {
+            int prefixSlotOff = slotManager.getPrefixSlotOff(prefixSlotNum);
+            int prefixSlot = buf.getInt(prefixSlotOff);
+            numPrefixFields = slotManager.decodeFirstSlotField(prefixSlot);
+        } else {
+            buf.putInt(uncompressedTupleCountOff, buf.getInt(uncompressedTupleCountOff) + 1);
+        }
+
+        int freeSpace = buf.getInt(freeSpaceOff);
+        int bytesWritten = tupleWriter.writeTupleFields(tuple, numPrefixFields,
+                tuple.getFieldCount() - numPrefixFields, buf, freeSpace);
+
+        buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
+        buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + bytesWritten);
+        buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - bytesWritten - slotManager.getSlotSize());
+    }
+    
+    @Override
+    public FrameOpSpaceStatus hasSpaceUpdate(ITupleReference newTuple, int oldTupleIndex, MultiComparator cmp) {
+        int tupleIndex = slotManager.decodeSecondSlotField(oldTupleIndex);
+        frameTuple.resetByTupleIndex(this, tupleIndex);
+        // TODO: Do we need to set the field count here?
+        //frameTuple.setFieldCount(cmp.getFieldCount());
+        
+        int oldTupleBytes = 0;
+        int newTupleBytes = 0;
+        
+        int numPrefixFields = frameTuple.getNumPrefixFields();
+        int numFields = frameTuple.getFieldCount();
+        if (numPrefixFields != 0) {
+            // Check the space requirements for updating the suffix of the original tuple.            
+            oldTupleBytes = frameTuple.getSuffixTupleSize();
+            newTupleBytes = tupleWriter.bytesRequired(newTuple, numPrefixFields, numFields - numPrefixFields); 
+        } else {
+            // The original tuple is uncompressed.
+            oldTupleBytes = frameTuple.getTupleSize();
+            newTupleBytes = tupleWriter.bytesRequired(newTuple);
+        }
+        
+        int additionalBytesRequired = newTupleBytes - oldTupleBytes;
+        // Enough space for an in-place update?
+        if (additionalBytesRequired <= 0) {
+            return FrameOpSpaceStatus.SUFFICIENT_INPLACE_SPACE;
+        }
+        
+        int freeContiguous = buf.capacity() - buf.getInt(freeSpaceOff)
+                - ((buf.getInt(tupleCountOff) + buf.getInt(prefixTupleCountOff)) * slotManager.getSlotSize());
+        
+        // Enough space if we delete the old tuple and insert the new one without compaction? 
+        if (newTupleBytes <= freeContiguous) {
+            return FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
+        }
+        // Enough space if we delete the old tuple and compact?
+        if (additionalBytesRequired <= buf.getInt(totalFreeSpaceOff)) {
+            return FrameOpSpaceStatus.SUFFICIENT_SPACE;
+        }
         return FrameOpSpaceStatus.INSUFFICIENT_SPACE;
     }
 
+    @Override
+    public void update(ITupleReference newTuple, int oldTupleIndex, boolean inPlace) throws Exception {
+        int tupleIndex = slotManager.decodeSecondSlotField(oldTupleIndex);
+        int tupleSlotOff = slotManager.getTupleSlotOff(tupleIndex);
+        int tupleSlot = buf.getInt(tupleSlotOff);
+        int prefixSlotNum = slotManager.decodeFirstSlotField(tupleSlot);
+        int suffixTupleStartOff = slotManager.decodeSecondSlotField(tupleSlot);                
+        
+        frameTuple.resetByTupleIndex(this, tupleIndex);
+        int numFields = frameTuple.getFieldCount();
+        int numPrefixFields = frameTuple.getNumPrefixFields();
+        int oldTupleBytes = frameTuple.getSuffixTupleSize();
+        int bytesWritten = 0;        
+        
+        if (inPlace) {
+            // Overwrite the old tuple suffix in place.
+            bytesWritten = tupleWriter.writeTupleFields(newTuple, numPrefixFields, numFields - numPrefixFields, buf, suffixTupleStartOff);
+        } else {
+            // Insert the new tuple suffix at the end of the free space, and change the slot value (effectively "deleting" the old tuple).
+            int newSuffixTupleStartOff = buf.getInt(freeSpaceOff);
+            bytesWritten = tupleWriter.writeTupleFields(newTuple, numPrefixFields, numFields - numPrefixFields, buf, newSuffixTupleStartOff);
+            // Update slot value using the same prefix slot num.
+            slotManager.setSlot(tupleSlotOff, slotManager.encodeSlotFields(prefixSlotNum, newSuffixTupleStartOff));
+            // Update contiguous free space pointer.
+            buf.putInt(freeSpaceOff, newSuffixTupleStartOff + bytesWritten);
+        }
+        buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + oldTupleBytes - bytesWritten);
+    }
+    
     protected void resetSpaceParams() {
         buf.putInt(freeSpaceOff, getOrigFreeSpaceOff());
         buf.putInt(totalFreeSpaceOff, getOrigTotalFreeSpace());
@@ -310,34 +397,6 @@
     }
 
     @Override
-    public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception {
-        int slot = slotManager.insertSlot(tupleIndex, buf.getInt(freeSpaceOff));
-        int prefixSlotNum = slotManager.decodeFirstSlotField(slot);
-        int numPrefixFields = 0;
-        if (prefixSlotNum != FieldPrefixSlotManager.TUPLE_UNCOMPRESSED) {
-            int prefixSlotOff = slotManager.getPrefixSlotOff(prefixSlotNum);
-            int prefixSlot = buf.getInt(prefixSlotOff);
-            numPrefixFields = slotManager.decodeFirstSlotField(prefixSlot);
-        } else {
-            buf.putInt(uncompressedTupleCountOff, buf.getInt(uncompressedTupleCountOff) + 1);
-        }
-
-        int freeSpace = buf.getInt(freeSpaceOff);
-        int bytesWritten = tupleWriter.writeTupleFields(tuple, numPrefixFields,
-                tuple.getFieldCount() - numPrefixFields, buf, freeSpace);
-
-        buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
-        buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + bytesWritten);
-        buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - bytesWritten - slotManager.getSlotSize());
-    }
-
-    @Override
-    public void update(ITupleReference newTuple, int oldTupleIndex, boolean inPlace) throws Exception {
-        // TODO Auto-generated method stub
-
-    }
-    
-    @Override
     public void printHeader() {
         // TODO Auto-generated method stub
 
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeLeafFrameType.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeLeafFrameType.java
new file mode 100644
index 0000000..6ff44be
--- /dev/null
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeLeafFrameType.java
@@ -0,0 +1,6 @@
+package edu.uci.ics.hyracks.storage.am.btree.frames;
+
+public enum BTreeLeafFrameType {
+    REGULAR_NSM,
+    FIELD_PREFIX_COMPRESSED_NSM
+}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
index 0d56cb0..3ccd039 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
@@ -26,7 +26,7 @@
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeDuplicateKeyException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeDuplicateKeyException;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ISplitKey;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
index 0ffc400..aa01ccb 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
@@ -20,7 +20,7 @@
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeDuplicateKeyException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeDuplicateKeyException;
 import edu.uci.ics.hyracks.storage.am.common.api.ISplitKey;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
index d1ba794..335630a 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
@@ -16,7 +16,6 @@
 package edu.uci.ics.hyracks.storage.am.btree.impls;
 
 import java.util.ArrayList;
-import java.util.Collections;
 import java.util.concurrent.locks.ReadWriteLock;
 import java.util.concurrent.locks.ReentrantReadWriteLock;
 
@@ -26,7 +25,8 @@
 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.BTreeFieldPrefixNSMLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNotUpdateableException;
 import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrame;
 import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
 import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
@@ -44,7 +44,6 @@
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.common.ophelpers.SlotOffTupleOff;
 import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriter;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
@@ -121,36 +120,13 @@
 
     @Override
     public void create(int fileId, ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame) throws Exception {
-
-        if (created)
-            return;
-
         treeLatch.writeLock().lock();
         try {
-
-            // check if another thread beat us to it
-            if (created)
+            if (created) {
                 return;
-
-            freePageManager.init(metaFrame, rootPage);
-
-            // initialize root page
-            ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), true);
-            pins++;
-
-            rootNode.acquireWriteLatch();
-            writeLatchesAcquired++;
-            try {
-                leafFrame.setPage(rootNode);
-                leafFrame.initBuffer((byte) 0);
-            } finally {
-                rootNode.releaseWriteLatch();
-                writeLatchesReleased++;
-                bufferCache.unpin(rootNode);
-                unpins++;
             }
-            currentLevel = 0;
-
+            freePageManager.init(metaFrame, rootPage);
+            initRoot(leafFrame, true);
             created = true;
         } finally {
             treeLatch.writeLock().unlock();
@@ -381,14 +357,14 @@
         ctx.interiorFrame.setPage(originalPage);
     }
 
-    private void reinitRoot(BTreeOpContext ctx) throws HyracksDataException {
-        ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), false);
+    private void initRoot(ITreeIndexFrame leafFrame, boolean firstInit) throws HyracksDataException {
+        ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), firstInit);
         pins++;
         rootNode.acquireWriteLatch();
         writeLatchesAcquired++;
         try {
-            ctx.leafFrame.setPage(rootNode);
-            ctx.leafFrame.initBuffer((byte) 0);
+            leafFrame.setPage(rootNode);
+            leafFrame.initBuffer((byte) 0);
             currentLevel = 0; // debug
         } finally {
             rootNode.releaseWriteLatch();
@@ -489,7 +465,7 @@
             if (ctx.splitKey.getBuffer() != null) {
                 if (ctx.op == IndexOp.DELETE) {
                     // Reset level of root to zero.
-                    reinitRoot(ctx);
+                    initRoot(ctx.leafFrame, false);
                 } else {
                     // Insert or update op. Create a new root.
                     createNewRoot(ctx);
@@ -510,6 +486,12 @@
 
     @Override
     public void update(ITupleReference tuple, IndexOpContext ictx) throws Exception {
+        // Updating a tuple's key necessitates deleting the old entry, and inserting the new entry.
+        // This call only allows updating of non-key fields.
+        // The user of the BTree is responsible for dealing with non-key updates (i.e., doing a delete + insert). 
+        if (cmp.getFieldCount() == cmp.getKeyFieldCount()) {
+            throw new BTreeNotUpdateableException("Cannot perform updates when the entire tuple forms the key.");
+        }
         insertUpdateOrDelete(tuple, ictx);
     }
     
@@ -806,7 +788,7 @@
                     treeLatchesAcquired++;
 
                     try {
-                        ctx.leafFrame.delete(tuple, cmp, true);
+                        ctx.leafFrame.delete(tuple, cmp, false);
                         // to propagate the deletion we only need to make the
                         // splitKey != null
                         // we can reuse data to identify which key to delete in
@@ -879,7 +861,7 @@
                 }
             }
         } else { // leaf will not become empty
-            ctx.leafFrame.delete(tuple, cmp, true);
+            ctx.leafFrame.delete(tuple, cmp, false);
             node.releaseWriteLatch();
             writeLatchesReleased++;
             bufferCache.unpin(node);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
index bacd16c..3929433 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
@@ -24,7 +24,7 @@
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
 
 public final class BTreeOpContext implements IndexOpContext {
-    public final IndexOp op;
+    public IndexOp op;
     public final IBTreeLeafFrame leafFrame;
     public final IBTreeInteriorFrame interiorFrame;
     public final ITreeIndexMetaDataFrame metaFrame;
@@ -67,4 +67,8 @@
             smPages.clear();
         opRestarts = 0;
     }
+    
+    public void setIndexOp(IndexOp op) {
+        this.op = op;
+    }
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixTupleReference.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixTupleReference.java
index 27c63f0..09be0bb 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixTupleReference.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixTupleReference.java
@@ -46,7 +46,7 @@
 
     @Override
     public void setFieldCount(int fieldStartIndex, int fieldCount) {
-        // not implemented
+        throw new UnsupportedOperationException("Not supported.");
     }
 
     @Override
@@ -88,13 +88,25 @@
     // unsupported operation
     @Override
     public void resetByTupleOffset(ByteBuffer buf, int tupleStartOffset) {
-        frame = null;
+        throw new UnsupportedOperationException("Resetting this type of frame by offset is not supported.");
     }
 
     @Override
     public int getTupleSize() {
-        // TODO Auto-generated method stub
-        return 0;
+        return getSuffixTupleSize() + getPrefixTupleSize();
+    }
+    
+    public int getSuffixTupleSize() {
+        helperTuple.setFieldCount(numPrefixFields, fieldCount - numPrefixFields);
+        helperTuple.resetByTupleOffset(frame.getBuffer(), suffixTupleStartOff);
+        return helperTuple.getTupleSize();
+    }
+    
+    public int getPrefixTupleSize() {
+        if (numPrefixFields == 0) return 0;
+        helperTuple.setFieldCount(numPrefixFields);
+        helperTuple.resetByTupleOffset(frame.getBuffer(), prefixTupleStartOff);
+        return helperTuple.getTupleSize();
     }
     
     public int getNumPrefixFields() {
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeUtils.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeUtils.java
new file mode 100644
index 0000000..39a3e20
--- /dev/null
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeUtils.java
@@ -0,0 +1,58 @@
+package edu.uci.ics.hyracks.storage.am.btree.util;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeFieldPrefixNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+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.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
+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.common.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+public class BTreeUtils {
+    public static BTree createBTree(IBufferCache bufferCache, int btreeFileId, ITypeTrait[] typeTraits, IBinaryComparator[] cmps, BTreeLeafFrameType leafType) throws BTreeException {
+        MultiComparator cmp = new MultiComparator(typeTraits, cmps);
+        TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(typeTraits);
+        ITreeIndexFrameFactory leafFrameFactory = getLeafFrameFactory(tupleWriterFactory, leafType);
+        ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+        ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+        IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, btreeFileId, 0, metaFrameFactory);
+        BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, cmp);
+        return btree;
+    }
+    
+    public static MultiComparator getSearchMultiComparator(MultiComparator btreeCmp, ITupleReference searchKey) {
+        if (btreeCmp.getKeyFieldCount() == searchKey.getFieldCount()) {
+            return btreeCmp;
+        }
+        IBinaryComparator[] cmps = new IBinaryComparator[searchKey.getFieldCount()];
+        for (int i = 0; i < searchKey.getFieldCount(); i++) {
+            cmps[i] = btreeCmp.getComparators()[i];
+        }
+        return new MultiComparator(btreeCmp.getTypeTraits(), cmps);
+    }
+    
+    public static ITreeIndexFrameFactory getLeafFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory, BTreeLeafFrameType leafType) throws BTreeException {
+        switch(leafType) {
+            case REGULAR_NSM: {
+                return new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+            }
+            case FIELD_PREFIX_COMPRESSED_NSM: {
+                return new BTreeFieldPrefixNSMLeafFrameFactory(tupleWriterFactory);
+            }
+            default: {
+                throw new BTreeException("Unknown BTreeLeafFrameType: " + leafType.toString());
+            }
+        }
+    }
+}
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
index 7c576e0..e1a0dd6 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
@@ -15,7 +15,9 @@
 
 package edu.uci.ics.hyracks.storage.am.common.impls;
 
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
 import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
@@ -30,17 +32,18 @@
 
 	private int tupleIndex = 0;
 	private int fileId = -1;
-	int currentPageId = -1;
-	int maxPageId = -1;
+	private int currentPageId = -1;
+	private int maxPageId = -1;
 	private ICachedPage page = null;
 	private ITreeIndexFrame frame = null;
 	private IBufferCache bufferCache = null;
-
+	private int fieldCount;
+	
 	private ITreeIndexTupleReference frameTuple;
 
 	public TreeDiskOrderScanCursor(ITreeIndexFrame frame) {
-		this.frame = frame;
-		this.frameTuple = frame.getTupleWriter().createTupleReference();
+		this.frame = frame;		
+		this.frameTuple = frame.createTupleReference();
 	}
 
 	@Override
@@ -62,8 +65,7 @@
 
 	private boolean positionToNextLeaf(boolean skipCurrent)
 			throws HyracksDataException {
-		while ((frame.getLevel() != 0 || skipCurrent)
-				&& (currentPageId <= maxPageId) || (frame.getTupleCount() == 0)) {
+		while ((frame.getLevel() != 0 || skipCurrent) && (currentPageId <= maxPageId)) {
 			currentPageId++;
 
 			ICachedPage nextPage = bufferCache.pin(
@@ -86,18 +88,20 @@
 	}
 
 	@Override
-	public boolean hasNext() throws Exception {
+	public boolean hasNext() throws Exception {		
+		if (currentPageId > maxPageId) {
+			return false;
+		}
 		if (tupleIndex >= frame.getTupleCount()) {
 			boolean nextLeafExists = positionToNextLeaf(true);
 			if (nextLeafExists) {
-				frameTuple.resetByTupleIndex(frame, tupleIndex);
+				frameTuple.resetByTupleIndex(frame, tupleIndex);				
 				return true;
 			} else {
 				return false;
 			}
-		}
-
-		frameTuple.resetByTupleIndex(frame, tupleIndex);
+		}		
+		frameTuple.resetByTupleIndex(frame, tupleIndex);		
 		return true;
 	}
 
@@ -115,15 +119,12 @@
 			bufferCache.unpin(page);
 		}
 		page = initialState.getPage();
-		tupleIndex = 0;
+		tupleIndex = 0;		
 		frame.setPage(page);
 		MultiComparator lowKeyCmp = searchPred.getLowKeyComparator();
-		frameTuple.setFieldCount(lowKeyCmp.getFieldCount());
-		boolean leafExists = positionToNextLeaf(false);
-		if (!leafExists) {
-			throw new HyracksDataException(
-					"Failed to open disk-order scan cursor for tree index. Traget tree index has no leaves.");
-		}
+		fieldCount = lowKeyCmp.getFieldCount();
+		frameTuple.setFieldCount(fieldCount);
+		positionToNextLeaf(false);
 	}
 
 	@Override
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java
deleted file mode 100644
index a189953..0000000
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java
+++ /dev/null
@@ -1,13 +0,0 @@
-package edu.uci.ics.hyracks.storage.am.btree;
-
-import org.junit.Test;
-
-import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
-
-public class BTreeDeleteTest extends AbstractBTreeTest {
-
-    @Test
-    public void blubb() {
-        
-    }
-}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java
index 7ef38b6..10d96d2 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java
@@ -16,7 +16,6 @@
 package edu.uci.ics.hyracks.storage.am.btree;
 
 import java.io.DataOutput;
-import java.io.File;
 import java.nio.ByteBuffer;
 import java.util.Random;
 
@@ -31,7 +30,6 @@
 import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
 import edu.uci.ics.hyracks.api.dataflow.value.TypeTrait;
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
-import edu.uci.ics.hyracks.api.io.FileReference;
 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;
@@ -40,19 +38,15 @@
 import edu.uci.ics.hyracks.dataflow.common.data.comparators.IntegerBinaryComparatorFactory;
 import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
 import edu.uci.ics.hyracks.storage.am.btree.api.IPrefixSlotManager;
+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.impls.BTreeException;
 import edu.uci.ics.hyracks.storage.am.btree.impls.FieldPrefixSlotManager;
 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.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 BTreeFieldPrefixNSMTest extends AbstractBTreeTest {
 
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java
deleted file mode 100644
index 973385a..0000000
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java
+++ /dev/null
@@ -1,183 +0,0 @@
-/*
- * 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.Test;
-
-import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
-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.dataflow.common.util.TupleUtils;
-import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
-import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
-import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestUtils;
-
-/**
- * Tests the BTree insert operation in the following scenarios:
- * 1.   Integer fields:
- * 1.1. One key, one value
- * 1.2. Two keys, no value
- * 1.3. Two keys, two values
- * 2.   String fields:
- * 2.1. One key, one value
- * 2.2. Two keys, no value
- * 2.3. Two keys, two values
- * 
- * Each tests consists of the following steps:
- * 1. Insert randomly generated tuples.
- * 2. Perform ordered scan and print results.
- * 3. Perform disk-order scan and print results.
- * 4. Perform range search and print results.
- * 
- */
-@SuppressWarnings("rawtypes")
-public class BTreeInsertTest extends AbstractBTreeTest {        
-    
-    @Test
-    public void oneIntKeyAndValue() throws Exception {        
-        LOGGER.info("BTree Test With One Int Key And Value.");
-        
-        ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
-        BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, 1);
-        BTreeTestUtils.fillIntBTree(testCtx, 10000);
-
-        BTreeTestUtils.checkOrderedScan(testCtx);
-        BTreeTestUtils.checkDiskOrderScan(testCtx);
-        
-        // Range search in [-1000, 1000];
-        ITupleReference lowKey = TupleUtils.createIntegerTuple(-1000);
-        ITupleReference highKey = TupleUtils.createIntegerTuple(1000);
-        BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);        
-        
-        testCtx.btree.close();
-    }
-    
-    @Test
-    public void twoIntKeys() throws Exception {        
-        LOGGER.info("BTree Test With Two Int Keys.");
-        
-        ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
-        BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, 2);
-        BTreeTestUtils.fillIntBTree(testCtx, 10000);
-        
-        BTreeTestUtils.checkOrderedScan(testCtx);
-        BTreeTestUtils.checkDiskOrderScan(testCtx);
-
-        // Range search in [50 0, 50 500];
-        ITupleReference lowKey = TupleUtils.createIntegerTuple(50, 0);
-        ITupleReference highKey = TupleUtils.createIntegerTuple(50, 500);
-        BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);        
-        
-        // Prefix range search in [50, 50]
-        ITupleReference prefixLowKey = TupleUtils.createIntegerTuple(50);
-        ITupleReference prefixHighKey = TupleUtils.createIntegerTuple(50);
-        BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true);
-        
-        testCtx.btree.close();
-    }
-    
-    @Test
-    public void twoIntKeysAndValues() throws Exception {        
-        LOGGER.info("BTree Test With Two Int Keys And Values.");
-        
-        ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
-        BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, 2);
-        BTreeTestUtils.fillIntBTree(testCtx, 10000);
-        
-        BTreeTestUtils.checkOrderedScan(testCtx);
-        BTreeTestUtils.checkDiskOrderScan(testCtx);
-
-        // Range search in [50 100, 100 100];
-        ITupleReference lowKey = TupleUtils.createIntegerTuple(-100, -100);
-        ITupleReference highKey = TupleUtils.createIntegerTuple(100, 100);
-        BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);        
-        
-        // Prefix range search in [50, 50]
-        ITupleReference prefixLowKey = TupleUtils.createIntegerTuple(50);
-        ITupleReference prefixHighKey = TupleUtils.createIntegerTuple(50);
-        BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true);
-        
-        testCtx.btree.close();
-    }
-    
-    @Test
-    public void oneStringKeyAndValue() throws Exception {        
-        LOGGER.info("BTree Test With One String Key And Value.");
-        
-        ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
-        BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, 1);
-        BTreeTestUtils.fillStringBTree(testCtx, 10000);
-        
-        BTreeTestUtils.checkOrderedScan(testCtx);
-        BTreeTestUtils.checkDiskOrderScan(testCtx);
-
-        // Range search in ["cbf", cc7"]
-        ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
-        ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7");
-        BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);        
-        
-        testCtx.btree.close();
-    }
-    
-    @Test
-    public void twoStringKeys() throws Exception {        
-        LOGGER.info("BTree Test With Two String Keys.");
-        
-        ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
-        BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, 2);
-        BTreeTestUtils.fillStringBTree(testCtx, 10000);
-        
-        BTreeTestUtils.checkOrderedScan(testCtx);
-        BTreeTestUtils.checkDiskOrderScan(testCtx);
-
-        // Range search in ["cbf", "ddd", cc7", "eee"]
-        ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf", "ddd");
-        ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7", "eee");
-        BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);   
-        
-        // Prefix range search in ["cbf", cc7"]
-        ITupleReference prefixLowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
-        ITupleReference prefixHighKey = TupleUtils.createTuple(fieldSerdes, "cc7");
-        BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true); 
-        
-        testCtx.btree.close();
-    }
-    
-    @Test
-    public void twoStringKeysAndValues() throws Exception {        
-        LOGGER.info("BTree Test With Two String Keys And Values.");
-        
-        ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
-        BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, 2);
-        BTreeTestUtils.fillStringBTree(testCtx, 10000);
-        
-        BTreeTestUtils.checkOrderedScan(testCtx);
-        BTreeTestUtils.checkDiskOrderScan(testCtx);
-
-        // Range search in ["cbf", "ddd", cc7", "eee"]
-        ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf", "ddd");
-        ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7", "eee");
-        BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);        
-        
-        // Prefix range search in ["cbf", cc7"]
-        ITupleReference prefixLowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
-        ITupleReference prefixHighKey = TupleUtils.createTuple(fieldSerdes, "cc7");
-        BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true); 
-        
-        testCtx.btree.close();
-    }
-}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
index 09eb7ea..1253c6f 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
@@ -150,7 +150,7 @@
         TreeIndexStatsGatherer statsGatherer = new TreeIndexStatsGatherer(bufferCache, freePageManager, fileId,
                 btree.getRootPageId());
         TreeIndexStats stats = statsGatherer.gatherStats(leafFrame, interiorFrame, metaFrame);
-        LOGGER.info(stats.toString());
+        LOGGER.info("\n" + stats.toString());
 
         TreeIndexBufferCacheWarmup bufferCacheWarmup = new TreeIndexBufferCacheWarmup(bufferCache, freePageManager,
                 fileId);
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
index 05e8941..f1469f1 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
@@ -293,7 +293,7 @@
     // fixed-length "value" field
     // fill B-tree with random values using insertions (not bulk load)
     // perform ordered scan and range search
-    //@Test
+    @Test
     public void test02() throws Exception {
 
         LOGGER.info("COMPOSITE KEY TEST");
@@ -391,7 +391,6 @@
             //System.out.println("---------------------------------");
         }
 
-        /*
         long end = System.currentTimeMillis();
         long duration = end - start;
         LOGGER.info("DURATION: " + duration);
@@ -468,7 +467,7 @@
                 rangeCursor.next();
                 ITupleReference frameTuple = rangeCursor.getTuple();
                 String rec = cmp.printTuple(frameTuple, recDescSers);
-                print(rec + "\n");
+                LOGGER.info(rec);
             }
         } catch (Exception e) {
             e.printStackTrace();
@@ -476,7 +475,6 @@
             rangeCursor.close();
         }
 
-        */
 
         btree.close();
         bufferCache.closeFile(fileId);
@@ -488,7 +486,7 @@
     // variable-length "value" field
     // fill B-tree with random values using insertions (not bulk load)
     // perform ordered scan and range search
-    //@Test
+    @Test
     public void test03() throws Exception {
 
         LOGGER.info("VARIABLE-LENGTH KEY TEST");
@@ -661,7 +659,7 @@
     // fill B-tree with random values using insertions, then delete entries
     // one-by-one
     // repeat procedure a few times on same B-tree
-    //@Test
+    @Test
     public void test04() throws Exception {
 
         LOGGER.info("DELETION TEST");
@@ -1028,7 +1026,7 @@
     // insert 100,000 records in bulk
     // B-tree has a composite key to "simulate" non-unique index creation
     // do range search
-    //@Test
+    @Test
     public void test06() throws Exception {
 
         LOGGER.info("BULK LOAD TEST");
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTestDriver.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTestDriver.java
new file mode 100644
index 0000000..ef1e5e3
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTestDriver.java
@@ -0,0 +1,119 @@
+package edu.uci.ics.hyracks.storage.am.btree;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+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.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
+
+@SuppressWarnings("rawtypes")
+public abstract class BTreeTestDriver extends AbstractBTreeTest {
+
+    protected static final int numTuplesToInsert = 10000;
+    
+    protected abstract void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType, ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey) throws Exception;
+    protected abstract String getTestOpName();
+    
+    @Test
+    public void oneIntKeyAndValue() throws Exception {        
+        LOGGER.info("BTree " + getTestOpName() + " Test With One Int Key And Value.");
+                
+        ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+        // Range search in [-1000, 1000]
+        ITupleReference lowKey = TupleUtils.createIntegerTuple(-1000);
+        ITupleReference highKey = TupleUtils.createIntegerTuple(1000);
+        
+        runTest(fieldSerdes, 1, BTreeLeafFrameType.REGULAR_NSM, lowKey, highKey, null, null);
+        runTest(fieldSerdes, 1, BTreeLeafFrameType.FIELD_PREFIX_COMPRESSED_NSM, lowKey, highKey, null, null);
+    }
+    
+    @Test
+    public void twoIntKeys() throws Exception {        
+        LOGGER.info("BTree " + getTestOpName() + " Test With Two Int Keys.");
+        
+        ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+        
+        // Range search in [50 0, 50 500]
+        ITupleReference lowKey = TupleUtils.createIntegerTuple(50, 0);
+        ITupleReference highKey = TupleUtils.createIntegerTuple(50, 500);
+        
+        // Prefix range search in [50, 50]
+        ITupleReference prefixLowKey = TupleUtils.createIntegerTuple(50);
+        ITupleReference prefixHighKey = TupleUtils.createIntegerTuple(50);
+        
+        runTest(fieldSerdes, 2, BTreeLeafFrameType.REGULAR_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+        runTest(fieldSerdes, 2, BTreeLeafFrameType.FIELD_PREFIX_COMPRESSED_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+    }
+    
+    @Test
+    public void twoIntKeysAndValues() throws Exception {        
+        LOGGER.info("BTree " + getTestOpName() + " Test With Two Int Keys And Values.");
+        
+        ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+        
+        // Range search in [50 100, 100 100]
+        ITupleReference lowKey = TupleUtils.createIntegerTuple(-100, -100);
+        ITupleReference highKey = TupleUtils.createIntegerTuple(100, 100);
+        
+        // Prefix range search in [50, 50]
+        ITupleReference prefixLowKey = TupleUtils.createIntegerTuple(50);
+        ITupleReference prefixHighKey = TupleUtils.createIntegerTuple(50);
+        
+        runTest(fieldSerdes, 2, BTreeLeafFrameType.REGULAR_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+        runTest(fieldSerdes, 2, BTreeLeafFrameType.FIELD_PREFIX_COMPRESSED_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+    }        
+    
+    @Test
+    public void oneStringKeyAndValue() throws Exception {        
+        LOGGER.info("BTree " + getTestOpName() + " Test With One String Key And Value.");
+        
+        ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
+        
+        // Range search in ["cbf", cc7"]
+        ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
+        ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7");
+        
+        runTest(fieldSerdes, 1, BTreeLeafFrameType.REGULAR_NSM, lowKey, highKey, null, null);
+        runTest(fieldSerdes, 1, BTreeLeafFrameType.FIELD_PREFIX_COMPRESSED_NSM, lowKey, highKey, null, null);
+    }
+    
+    @Test
+    public void twoStringKeys() throws Exception {        
+        LOGGER.info("BTree " + getTestOpName() + " Test With Two String Keys.");
+        
+        ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
+        
+        // Range search in ["cbf", "ddd", cc7", "eee"]
+        ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf", "ddd");
+        ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7", "eee");
+        
+        // Prefix range search in ["cbf", cc7"]
+        ITupleReference prefixLowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
+        ITupleReference prefixHighKey = TupleUtils.createTuple(fieldSerdes, "cc7");
+        
+        runTest(fieldSerdes, 2, BTreeLeafFrameType.REGULAR_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+        runTest(fieldSerdes, 2, BTreeLeafFrameType.FIELD_PREFIX_COMPRESSED_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+    }
+    
+    @Test
+    public void twoStringKeysAndValues() throws Exception {        
+        LOGGER.info("BTree " + getTestOpName() + " Test With Two String Keys And Values.");
+        
+        ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
+        
+        // Range search in ["cbf", "ddd", cc7", "eee"]
+        ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf", "ddd");
+        ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7", "eee");
+        
+        // Prefix range search in ["cbf", cc7"]
+        ITupleReference prefixLowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
+        ITupleReference prefixHighKey = TupleUtils.createTuple(fieldSerdes, "cc7");
+        
+        runTest(fieldSerdes, 2, BTreeLeafFrameType.REGULAR_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+        runTest(fieldSerdes, 2, BTreeLeafFrameType.FIELD_PREFIX_COMPRESSED_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BulkLoadTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BulkLoadTest.java
new file mode 100644
index 0000000..49d08a3
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BulkLoadTest.java
@@ -0,0 +1,53 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.btree;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+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.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestUtils;
+
+@SuppressWarnings("rawtypes")
+public class BulkLoadTest extends BTreeTestDriver {
+    
+    @Override
+    protected void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType, ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey) throws Exception {
+        BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, numKeys, leafType);
+
+        // We assume all fieldSerdes are of the same type. Check the first one to determine which field types to generate.
+        if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
+            BTreeTestUtils.bulkLoadIntTuples(testCtx, numTuplesToInsert, rnd);
+        } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
+            BTreeTestUtils.bulkLoadStringTuples(testCtx, numTuplesToInsert, rnd);
+        }
+
+        BTreeTestUtils.checkPointSearches(testCtx);
+        BTreeTestUtils.checkOrderedScan(testCtx);
+        BTreeTestUtils.checkDiskOrderScan(testCtx);
+        BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);
+        if (prefixLowKey != null && prefixHighKey != null) {
+            BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true);
+        }
+    }
+
+    @Override
+    protected String getTestOpName() {
+        return "BulkLoad";
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/DeleteTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/DeleteTest.java
new file mode 100644
index 0000000..2157adb
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/DeleteTest.java
@@ -0,0 +1,63 @@
+/*
+ * 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 edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+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.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestUtils;
+
+@SuppressWarnings("rawtypes")
+public class DeleteTest extends BTreeTestDriver {
+    
+    private static final int numInsertRounds = 3;
+    private static final int numDeleteRounds = 3;
+    
+    @Override
+    protected void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType, ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey) throws Exception {
+        BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, numKeys, leafType);
+        for (int i = 0; i < numInsertRounds; i++) {
+            
+            // We assume all fieldSerdes are of the same type. Check the first one to determine which field types to generate.
+            if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
+                BTreeTestUtils.insertIntTuples(testCtx, numTuplesToInsert, rnd);
+            } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
+                BTreeTestUtils.insertStringTuples(testCtx, numTuplesToInsert, rnd);
+            }
+            
+            int numTuplesPerDeleteRound = (int)Math.ceil((float)testCtx.checkTuples.size() / (float)numDeleteRounds);
+            for(int j = 0; j < numDeleteRounds; j++) {
+                BTreeTestUtils.deleteTuples(testCtx, numTuplesPerDeleteRound, rnd);
+                
+                BTreeTestUtils.checkPointSearches(testCtx);
+                BTreeTestUtils.checkOrderedScan(testCtx);
+                BTreeTestUtils.checkDiskOrderScan(testCtx);
+                BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);
+                if (prefixLowKey != null && prefixHighKey != null) {
+                    BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true);
+                }
+            }
+        }
+    }
+
+    @Override
+    protected String getTestOpName() {
+        return "Delete";
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/InsertTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/InsertTest.java
new file mode 100644
index 0000000..fa3f895
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/InsertTest.java
@@ -0,0 +1,65 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.btree;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+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.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestUtils;
+
+/**
+ * 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 InsertTest extends BTreeTestDriver {        
+    @Override
+    protected void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType, ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey) throws Exception {
+        BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, numKeys, leafType);
+        // We assume all fieldSerdes are of the same type. Check the first one to determine which field types to generate.
+        if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
+            BTreeTestUtils.insertIntTuples(testCtx, numTuplesToInsert, rnd);
+        } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
+            BTreeTestUtils.insertStringTuples(testCtx, numTuplesToInsert, rnd);
+        }
+        
+        BTreeTestUtils.checkPointSearches(testCtx);
+        BTreeTestUtils.checkOrderedScan(testCtx);
+        BTreeTestUtils.checkDiskOrderScan(testCtx);
+                
+        BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);
+        if (prefixLowKey != null && prefixHighKey != null) {
+            BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true);
+        }
+        testCtx.btree.close();
+    }
+
+    @Override
+    protected String getTestOpName() {
+        return "Insert";
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java
index 82adfde..9e8a7cd 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java
@@ -38,11 +38,11 @@
 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.BTreeFieldPrefixNSMLeafFrameFactory;
 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.BTreeException;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/UpdateTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/UpdateTest.java
new file mode 100644
index 0000000..b40539f
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/UpdateTest.java
@@ -0,0 +1,64 @@
+/*
+ * 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 edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+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.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestUtils;
+
+@SuppressWarnings("rawtypes")
+public class UpdateTest extends BTreeTestDriver {
+    private static final int numUpdateRounds = 3;
+    
+    @Override
+    protected void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType, ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey) throws Exception {
+        // This is a noop because we can only update non-key fields.
+        if (fieldSerdes.length == numKeys) {
+            return;
+        }
+        
+        BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, numKeys, leafType);
+
+        // We assume all fieldSerdes are of the same type. Check the first one to determine which field types to generate.
+        if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
+            BTreeTestUtils.insertIntTuples(testCtx, numTuplesToInsert, rnd);
+        } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
+            BTreeTestUtils.insertStringTuples(testCtx, numTuplesToInsert, rnd);
+        }
+
+        int numTuplesPerDeleteRound = (int)Math.ceil((float)testCtx.checkTuples.size() / (float)numUpdateRounds);
+        for(int j = 0; j < numUpdateRounds; j++) {
+            BTreeTestUtils.updateTuples(testCtx, numTuplesPerDeleteRound, rnd);
+
+            BTreeTestUtils.checkPointSearches(testCtx);
+            BTreeTestUtils.checkOrderedScan(testCtx);
+            BTreeTestUtils.checkDiskOrderScan(testCtx);
+            BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);
+            if (prefixLowKey != null && prefixHighKey != null) {
+                BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true);
+            }
+        }
+    }
+
+    @Override
+    protected String getTestOpName() {
+        return "Update";
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java
index 19ae81a..dff1e9c 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java
@@ -3,6 +3,7 @@
 import java.io.File;
 import java.text.SimpleDateFormat;
 import java.util.Date;
+import java.util.Random;
 import java.util.logging.Logger;
 
 import org.junit.After;
@@ -18,20 +19,22 @@
 
 public abstract class AbstractBTreeTest {
     protected static final Logger LOGGER = Logger.getLogger(AbstractBTreeTest.class.getName());
-
+    public static final long RANDOM_SEED = 50;
+    
     private static final int PAGE_SIZE = 256;
     private static final int NUM_PAGES = 10;
     private static final int MAX_OPEN_FILES = 10;
     private static final int HYRACKS_FRAME_SIZE = 128;
-    
+        
     protected IHyracksTaskContext ctx; 
     protected IBufferCache bufferCache;
     protected int btreeFileId;
     
+    protected final Random rnd = new Random();
     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 String fileName;
+    protected String fileName;    
     
     @Before
     public void setUp() throws HyracksDataException {
@@ -44,6 +47,7 @@
         bufferCache.createFile(file);
         btreeFileId = fmp.lookupFileId(file);
         bufferCache.openFile(btreeFileId);
+        rnd.setSeed(RANDOM_SEED);
     }
     
     @After
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestUtils.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestUtils.java
index 52bebe6..f73d1a1 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestUtils.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestUtils.java
@@ -5,6 +5,7 @@
 import java.io.ByteArrayInputStream;
 import java.io.DataInput;
 import java.io.DataInputStream;
+import java.io.DataOutput;
 import java.util.Iterator;
 import java.util.NavigableSet;
 import java.util.Random;
@@ -15,52 +16,38 @@
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.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.data.marshalling.UTF8StringSerializerDeserializer;
 import edu.uci.ics.hyracks.dataflow.common.util.SerdeUtils;
 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.frames.BTreeNSMInteriorFrameFactory;
-import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeDuplicateKeyException;
+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.btree.impls.BTreeDuplicateKeyException;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
 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.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.TreeDiskOrderScanCursor;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 
 @SuppressWarnings("rawtypes")
 public class BTreeTestUtils {
-    private static final Logger LOGGER = Logger.getLogger(BTreeTestUtils.class.getName());
-    private static final long RANDOM_SEED = 50;
+    private static final Logger LOGGER = Logger.getLogger(BTreeTestUtils.class.getName());    
     
-    public static BTree createBTree(IBufferCache bufferCache, int btreeFileId, ITypeTrait[] typeTraits, IBinaryComparator[] cmps) {
-        MultiComparator cmp = new MultiComparator(typeTraits, cmps);
-        TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(typeTraits);
-        ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);        
-        ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
-        ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
-        IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, btreeFileId, 0, metaFrameFactory);
-        BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, cmp);
-        return btree;
-    }
-    
-    public static BTreeTestContext createBTreeTestContext(IBufferCache bufferCache, int btreeFileId, ISerializerDeserializer[] fieldSerdes, int numKeyFields) throws Exception {        
+    public static BTreeTestContext createBTreeTestContext(IBufferCache bufferCache, int btreeFileId, ISerializerDeserializer[] fieldSerdes, int numKeyFields, BTreeLeafFrameType leafType) throws Exception {        
         ITypeTrait[] typeTraits = SerdeUtils.serdesToTypeTraits(fieldSerdes, fieldSerdes.length);
         IBinaryComparator[] cmps = SerdeUtils.serdesToComparators(fieldSerdes, numKeyFields);
         
-        BTree btree = BTreeTestUtils.createBTree(bufferCache, btreeFileId, typeTraits, cmps);
+        BTree btree = BTreeUtils.createBTree(bufferCache, btreeFileId, typeTraits, cmps, leafType);
         
         IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) btree.getLeafFrameFactory().createFrame();
         IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame) btree.getInteriorFrameFactory().createFrame();
@@ -87,7 +74,7 @@
     }
     
     @SuppressWarnings("unchecked")
-    private static CheckTuple createCheckTupleFromTuple(ITupleReference tuple, int numKeys, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {
+    private static CheckTuple createCheckTupleFromTuple(ITupleReference tuple, ISerializerDeserializer[] fieldSerdes, int numKeys) throws HyracksDataException {
         CheckTuple checkTuple = new CheckTuple(fieldSerdes.length, numKeys);
         int numFields = Math.min(fieldSerdes.length, tuple.getFieldCount());
         for (int i = 0; i < numFields; i++) {
@@ -101,6 +88,18 @@
         return checkTuple;
     }
     
+    @SuppressWarnings("unchecked")
+    private static void createTupleFromCheckTuple(CheckTuple checkTuple, ArrayTupleBuilder tupleBuilder, ArrayTupleReference tuple, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {
+        int fieldCount = tupleBuilder.getFieldEndOffsets().length; 
+        DataOutput dos = tupleBuilder.getDataOutput();
+        tupleBuilder.reset();
+        for (int i = 0; i < fieldCount; i++) {
+            fieldSerdes[i].serialize(checkTuple.get(i), dos);
+            tupleBuilder.addFieldEndOffset();
+        }
+        tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
+    }
+    
     public static void checkOrderedScan(BTreeTestContext testCtx) throws Exception {
         LOGGER.info("Testing Ordered Scan:");
         ITreeIndexCursor scanCursor = new BTreeRangeSearchCursor(testCtx.leafFrame);
@@ -138,7 +137,7 @@
             while (diskOrderCursor.hasNext()) {
                 diskOrderCursor.next();
                 ITupleReference tuple = diskOrderCursor.getTuple();
-                CheckTuple checkTuple = createCheckTupleFromTuple(tuple, testCtx.btree.getMultiComparator().getKeyFieldCount(), testCtx.fieldSerdes);
+                CheckTuple checkTuple = createCheckTupleFromTuple(tuple, testCtx.fieldSerdes, testCtx.btree.getMultiComparator().getKeyFieldCount());
                 if (!testCtx.checkTuples.contains(checkTuple)) {
                     fail("Disk-order scan returned unexpected answer: " + checkTuple.toString());
                 }
@@ -157,19 +156,19 @@
     
     public static void checkRangeSearch(BTreeTestContext testCtx, ITupleReference lowKey, ITupleReference highKey, boolean lowKeyInclusive, boolean highKeyInclusive) throws Exception {
         LOGGER.info("Testing Range Search:");
-        MultiComparator lowKeyCmp = getSearchMultiComparator(testCtx.btree.getMultiComparator(), lowKey);
-        MultiComparator highKeyCmp = getSearchMultiComparator(testCtx.btree.getMultiComparator(), highKey);
+        MultiComparator lowKeyCmp = BTreeUtils.getSearchMultiComparator(testCtx.btree.getMultiComparator(), lowKey);
+        MultiComparator highKeyCmp = BTreeUtils.getSearchMultiComparator(testCtx.btree.getMultiComparator(), highKey);
         ITreeIndexCursor searchCursor = new BTreeRangeSearchCursor(testCtx.leafFrame);
         RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, lowKeyInclusive, highKeyInclusive, lowKeyCmp, highKeyCmp);
         BTreeOpContext searchOpCtx = testCtx.btree.createOpContext(IndexOp.SEARCH, testCtx.leafFrame, testCtx.interiorFrame, null);
         testCtx.btree.search(searchCursor, rangePred, searchOpCtx);
         // Get the subset of elements from the expected set within given key range.
-        CheckTuple lowKeyCheck = createCheckTupleFromTuple(lowKey, lowKeyCmp.getKeyFieldCount(), testCtx.fieldSerdes);
-        CheckTuple highKeyCheck = createCheckTupleFromTuple(highKey, highKeyCmp.getKeyFieldCount(), testCtx.fieldSerdes);
+        CheckTuple lowKeyCheck = createCheckTupleFromTuple(lowKey, testCtx.fieldSerdes, lowKeyCmp.getKeyFieldCount());
+        CheckTuple highKeyCheck = createCheckTupleFromTuple(highKey, testCtx.fieldSerdes, highKeyCmp.getKeyFieldCount());
         NavigableSet<CheckTuple> expectedSubset = null;
         if (lowKeyCmp.getKeyFieldCount() < testCtx.btree.getMultiComparator().getKeyFieldCount() || 
                 highKeyCmp.getKeyFieldCount() < testCtx.btree.getMultiComparator().getKeyFieldCount()) {
-            // Searching on a key prefix (on low key or high key or both).
+            // Searching on a key prefix (low key or high key or both).
             expectedSubset = getPrefixExpectedSubset(testCtx.checkTuples, lowKeyCheck, highKeyCheck);
         } else {
             // Searching on all key fields.
@@ -196,6 +195,48 @@
         }
     }
     
+    public static void checkPointSearches(BTreeTestContext testCtx) throws Exception {
+        LOGGER.info("Testing Point Searches On All Expected Keys:");        
+        ITreeIndexCursor searchCursor = new BTreeRangeSearchCursor(testCtx.leafFrame);
+        
+        ArrayTupleBuilder lowKeyBuilder = new ArrayTupleBuilder(testCtx.btree.getMultiComparator().getKeyFieldCount());
+        ArrayTupleReference lowKey = new ArrayTupleReference();
+        ArrayTupleBuilder highKeyBuilder = new ArrayTupleBuilder(testCtx.btree.getMultiComparator().getKeyFieldCount());
+        ArrayTupleReference highKey = new ArrayTupleReference();
+        
+        BTreeOpContext searchOpCtx = testCtx.btree.createOpContext(IndexOp.SEARCH, testCtx.leafFrame, testCtx.interiorFrame, null);
+        RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, true, true, null, null);
+
+        // Iterate through expected tuples, and perform a point search in the BTree to verify the tuple can be reached.
+        for (CheckTuple checkTuple : testCtx.checkTuples) {
+            createTupleFromCheckTuple(checkTuple, lowKeyBuilder, lowKey, testCtx.fieldSerdes);
+            createTupleFromCheckTuple(checkTuple, highKeyBuilder, highKey, testCtx.fieldSerdes);
+            MultiComparator lowKeyCmp = BTreeUtils.getSearchMultiComparator(testCtx.btree.getMultiComparator(), lowKey);
+            MultiComparator highKeyCmp = BTreeUtils.getSearchMultiComparator(testCtx.btree.getMultiComparator(), highKey);
+                        
+            rangePred.setLowKey(lowKey, true);
+            rangePred.setHighKey(highKey, true);
+            rangePred.setLowKeyComparator(lowKeyCmp);
+            rangePred.setHighKeyComparator(highKeyCmp);
+            
+            testCtx.btree.search(searchCursor, rangePred, searchOpCtx);
+            
+            try {
+                // We expect exactly one answer.
+                if (searchCursor.hasNext()) {
+                    searchCursor.next();
+                    ITupleReference tuple = searchCursor.getTuple();
+                    compareActualAndExpected(tuple, checkTuple, testCtx.fieldSerdes);
+                }
+                if (searchCursor.hasNext()) {
+                    fail("Point search returned more than one answer.");
+                }
+            } finally {
+                searchCursor.close();
+            }
+        }
+    }
+    
     @SuppressWarnings("unchecked")
     // Create a new TreeSet containing the elements satisfying the prefix search.
     // Implementing prefix search by changing compareTo() in CheckTuple does not work.
@@ -225,17 +266,6 @@
         return expectedSubset;
     }
     
-    public static MultiComparator getSearchMultiComparator(MultiComparator btreeCmp, ITupleReference searchKey) {
-        if (btreeCmp.getKeyFieldCount() == searchKey.getFieldCount()) {
-            return btreeCmp;
-        }
-        IBinaryComparator[] cmps = new IBinaryComparator[searchKey.getFieldCount()];
-        for (int i = 0; i < searchKey.getFieldCount(); i++) {
-            cmps[i] = btreeCmp.getComparators()[i];
-        }
-        return new MultiComparator(btreeCmp.getTypeTraits(), cmps);
-    }
-    
     private static String printCursorResults(BTree btree, ITreeIndexCursor cursor, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException, Exception {
         StringBuilder strBuilder = new StringBuilder();
         strBuilder.append("\n");
@@ -248,13 +278,10 @@
         return strBuilder.toString();
     }
     
-    public static void fillIntBTree(BTreeTestContext testCtx, int numTuples) throws Exception {
+    public static void insertIntTuples(BTreeTestContext testCtx, int numTuples, Random rnd) throws Exception {
         int numFields = testCtx.getFieldCount();
         int numKeyFields = testCtx.getKeyFieldCount();
         
-        Random rnd = new Random();
-        rnd.setSeed(RANDOM_SEED);
-        
         BTreeOpContext insertOpCtx = testCtx.btree.createOpContext(IndexOp.INSERT, testCtx.leafFrame, testCtx.interiorFrame, testCtx.metaFrame);
         
         int[] tupleValues = new int[testCtx.getFieldCount()];
@@ -288,13 +315,11 @@
         }
     }
     
-    public static void fillStringBTree(BTreeTestContext testCtx, int numTuples) throws Exception {
+    public static void insertStringTuples(BTreeTestContext testCtx, int numTuples, Random rnd) throws Exception {
         int numFields = testCtx.getFieldCount();
         int numKeyFields = testCtx.getKeyFieldCount();
         
         BTreeOpContext insertOpCtx = testCtx.btree.createOpContext(IndexOp.INSERT, testCtx.leafFrame, testCtx.interiorFrame, testCtx.metaFrame);
-        Random rnd = new Random();
-        rnd.setSeed(RANDOM_SEED);
         Object[] tupleValues = new Object[numFields];
         for (int i = 0; i < numTuples; i++) {
             if ((i + 1) % (numTuples / 10) == 0) {
@@ -324,6 +349,156 @@
         }
     }
 
+    public static void bulkLoadIntTuples(BTreeTestContext testCtx, int numTuples, Random rnd) throws Exception {
+        int numFields = testCtx.getFieldCount();
+        int numKeyFields = testCtx.getKeyFieldCount();
+        int[] tupleValues = new int[testCtx.getFieldCount()];
+        int maxValue = (int)Math.ceil(Math.pow(numTuples, 1.0/(double)numKeyFields));
+        for (int i = 0; i < numTuples; i++) {
+            // Set keys.
+            for (int j = 0; j < numKeyFields; j++) {
+                tupleValues[j] = rnd.nextInt() % maxValue;
+            }
+            // Set values.
+            for (int j = numKeyFields; j < numFields; j++) {
+                tupleValues[j] = j;
+            }
+            
+            // Set expected values. We also use these as the pre-sorted stream for bulk loading.
+            CheckTuple<Integer> checkTuple = new CheckTuple<Integer>(numFields, numKeyFields);
+            for(int v : tupleValues) {
+                checkTuple.add(v);
+            }            
+            testCtx.checkTuples.add(checkTuple);
+        }
+        
+        bulkLoadCheckTuples(testCtx, numTuples);
+    }
+    
+    public static void bulkLoadStringTuples(BTreeTestContext testCtx, int numTuples, Random rnd) throws Exception {
+        int numFields = testCtx.getFieldCount();
+        int numKeyFields = testCtx.getKeyFieldCount();
+        String[] tupleValues = new String[numFields];
+        for (int i = 0; i < numTuples; i++) {
+            // Set keys.
+            for (int j = 0; j < numKeyFields; j++) {
+                int length = (Math.abs(rnd.nextInt()) % 10) + 1;
+                tupleValues[j] = getRandomString(length, rnd);
+            }
+            // Set values.
+            for (int j = numKeyFields; j < numFields; j++) {
+                tupleValues[j] = getRandomString(5, rnd);
+            }
+            // Set expected values. We also use these as the pre-sorted stream for bulk loading.
+            CheckTuple<String> checkTuple = new CheckTuple<String>(numFields, numKeyFields);
+            for(String v : tupleValues) {
+                checkTuple.add(v);
+            }            
+            testCtx.checkTuples.add(checkTuple);
+        }
+        
+        bulkLoadCheckTuples(testCtx, numTuples);
+    }
+    
+    private static void bulkLoadCheckTuples(BTreeTestContext testCtx, int numTuples) throws HyracksDataException {
+        int numFields = testCtx.getFieldCount();
+        ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(numFields);
+        ArrayTupleReference tuple = new ArrayTupleReference();
+        // Perform bulk load.
+        IIndexBulkLoadContext bulkLoadCtx = testCtx.btree.beginBulkLoad(0.7f, testCtx.leafFrame, testCtx.interiorFrame, testCtx.metaFrame);
+        int c = 1;
+        for (CheckTuple checkTuple : testCtx.checkTuples) {
+            if (c % (numTuples / 10) == 0) {
+                LOGGER.info("Bulk Loading Tuple " + c + "/" + numTuples);
+            }
+            createTupleFromCheckTuple(checkTuple, tupleBuilder, tuple, testCtx.fieldSerdes);
+            testCtx.btree.bulkLoadAddTuple(bulkLoadCtx, tuple);
+            c++;
+        }
+        testCtx.btree.endBulkLoad(bulkLoadCtx);
+    }
+    
+    public static void deleteTuples(BTreeTestContext testCtx, int numTuples, Random rnd) throws Exception {
+        ArrayTupleBuilder deleteTupleBuilder = new ArrayTupleBuilder(testCtx.btree.getMultiComparator().getKeyFieldCount());
+        ArrayTupleReference deleteTuple = new ArrayTupleReference();
+        int numCheckTuples = testCtx.checkTuples.size();
+        BTreeOpContext deleteOpCtx = testCtx.btree.createOpContext(IndexOp.DELETE, testCtx.leafFrame, testCtx.interiorFrame, testCtx.metaFrame);
+        // Copy CheckTuple references into array, so we can randomly pick from there.
+        CheckTuple[] checkTuples = new CheckTuple[numCheckTuples];
+        int idx = 0;
+        for (CheckTuple checkTuple : testCtx.checkTuples) {
+            checkTuples[idx++] = checkTuple;
+        }
+        for (int i = 0; i < numTuples && numCheckTuples > 0; i++) {
+            if ((i + 1) % (numTuples / 10) == 0) {
+                LOGGER.info("Deleting Tuple " + (i + 1) + "/" + numTuples);
+            }
+            int checkTupleIdx = Math.abs(rnd.nextInt() % numCheckTuples);
+            CheckTuple checkTuple = checkTuples[checkTupleIdx];            
+            createTupleFromCheckTuple(checkTuple, deleteTupleBuilder, deleteTuple, testCtx.fieldSerdes);          
+            testCtx.btree.delete(deleteTuple, deleteOpCtx);
+            
+            // Remove check tuple from expected results.
+            testCtx.checkTuples.remove(checkTuple);
+            
+            // Swap with last "valid" CheckTuple.
+            CheckTuple tmp = checkTuples[numCheckTuples - 1];
+            checkTuples[numCheckTuples - 1] = checkTuple;
+            checkTuples[checkTupleIdx] = tmp;
+            numCheckTuples--;
+        }
+    }
+    
+    @SuppressWarnings("unchecked")
+    public static void updateTuples(BTreeTestContext testCtx, int numTuples, Random rnd) throws Exception {
+        int fieldCount = testCtx.btree.getMultiComparator().getFieldCount();
+        int keyFieldCount = testCtx.btree.getMultiComparator().getKeyFieldCount();
+        // This is a noop because we can only update non-key fields.
+        if (fieldCount == keyFieldCount) {
+            return;
+        }
+        ArrayTupleBuilder updateTupleBuilder = new ArrayTupleBuilder(fieldCount);
+        ArrayTupleReference updateTuple = new ArrayTupleReference();
+        int numCheckTuples = testCtx.checkTuples.size();
+        BTreeOpContext updateOpCtx = testCtx.btree.createOpContext(IndexOp.UPDATE, testCtx.leafFrame, testCtx.interiorFrame, testCtx.metaFrame);
+        // Copy CheckTuple references into array, so we can randomly pick from there.
+        CheckTuple[] checkTuples = new CheckTuple[numCheckTuples];
+        int idx = 0;
+        for (CheckTuple checkTuple : testCtx.checkTuples) {
+            checkTuples[idx++] = checkTuple;
+        }
+        for (int i = 0; i < numTuples && numCheckTuples > 0; i++) {
+            if ((i + 1) % (numTuples / 10) == 0) {
+                LOGGER.info("Updating Tuple " + (i + 1) + "/" + numTuples);
+            }
+            int checkTupleIdx = Math.abs(rnd.nextInt() % numCheckTuples);
+            CheckTuple checkTuple = checkTuples[checkTupleIdx];
+            // Update check tuple's non-key fields.
+            for (int j = keyFieldCount; j < fieldCount; j++) {
+                Comparable newValue = getRandomUpdateValue(testCtx.fieldSerdes[j], rnd);
+                checkTuple.set(j, newValue);
+            }
+            
+            createTupleFromCheckTuple(checkTuple, updateTupleBuilder, updateTuple, testCtx.fieldSerdes);            
+            testCtx.btree.update(updateTuple, updateOpCtx);
+            
+            // Swap with last "valid" CheckTuple.
+            CheckTuple tmp = checkTuples[numCheckTuples - 1];
+            checkTuples[numCheckTuples - 1] = checkTuple;
+            checkTuples[checkTupleIdx] = tmp;
+            numCheckTuples--;
+        }
+    }
+    
+    private static Comparable getRandomUpdateValue(ISerializerDeserializer serde, Random rnd) {
+        if (serde instanceof IntegerSerializerDeserializer) {
+            return Integer.valueOf(rnd.nextInt());
+        } else if (serde instanceof UTF8StringSerializerDeserializer) {
+            return getRandomString(10, rnd);
+        }
+        return null;
+    }
+    
     public static String getRandomString(int length, Random rnd) {
         String s = Long.toHexString(Double.doubleToLongBits(rnd.nextDouble()));
         StringBuilder strBuilder = new StringBuilder();
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/CheckTuple.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/CheckTuple.java
index 97874be..f945ab9 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/CheckTuple.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/CheckTuple.java
@@ -47,6 +47,10 @@
         return (T)tuple[idx];
     }
     
+    public void set(int idx, T e) {
+        tuple[idx] = e;
+    }
+    
     public int size() {
         return tuple.length;
     }