diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorNodePushable.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorNodePushable.java
index 8a8c5ce..200c861 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorNodePushable.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorNodePushable.java
@@ -90,7 +90,7 @@
         accessor = new FrameTupleAccessor(treeIndexHelper.getHyracksTaskContext().getFrameSize(), recDesc);
 
         cursorFrame = opDesc.getTreeIndexLeafFactory().createFrame();
-        setCursor();        
+        setCursor();
         writer.open();
 
         try {
@@ -98,8 +98,9 @@
             btree = (BTree) treeIndexHelper.getIndex();
 
             // Construct range predicate.
-            lowKeySearchCmp = BTreeUtils.getSearchMultiComparator(btree.getMultiComparator(), lowKey);
-            highKeySearchCmp = BTreeUtils.getSearchMultiComparator(btree.getMultiComparator(), highKey);
+            lowKeySearchCmp = BTreeUtils.getSearchMultiComparator(btree.getMultiComparator().getComparators(), lowKey);
+            highKeySearchCmp = BTreeUtils
+                    .getSearchMultiComparator(btree.getMultiComparator().getComparators(), highKey);
             rangePred = new RangePredicate(isForward, null, null, lowKeyInclusive, highKeyInclusive, lowKeySearchCmp,
                     highKeySearchCmp);
 
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 49c58b3..f2a55f7 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
@@ -1154,6 +1154,12 @@
         }
 
         @Override
+		public ITreeIndexCursor createSearchCursor() {
+			IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) btree.getLeafFrameFactory().createFrame();
+	        return new BTreeRangeSearchCursor(leafFrame, false);
+		}
+        
+        @Override
         public void search(ITreeIndexCursor cursor, ISearchPredicate searchPred) throws HyracksDataException,
                 TreeIndexException {
             ctx.reset(IndexOp.SEARCH);
@@ -1161,6 +1167,12 @@
         }
 
         @Override
+		public ITreeIndexCursor createDiskOrderScanCursor() {
+			IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) btree.getLeafFrameFactory().createFrame();
+	        return new TreeDiskOrderScanCursor(leafFrame);
+		}
+        
+        @Override
         public void diskOrderScan(ITreeIndexCursor cursor) throws HyracksDataException {
             ctx.reset(IndexOp.DISKORDERSCAN);
             btree.diskOrderScan(cursor, ctx);
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
index f6310af..a9adfbf 100644
--- 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
@@ -31,18 +31,18 @@
         return btree;
     }
     
-    public static MultiComparator getSearchMultiComparator(MultiComparator btreeCmp, ITupleReference searchKey) {
+    public static MultiComparator getSearchMultiComparator(IBinaryComparator[] cmps, ITupleReference searchKey) {
         if (searchKey == null) {
-        	return btreeCmp;
+        	return new MultiComparator(cmps);
         }
-    	if (btreeCmp.getKeyFieldCount() == searchKey.getFieldCount()) {
-            return btreeCmp;
+    	if (cmps.length == searchKey.getFieldCount()) {
+            return new MultiComparator(cmps);
         }
-        IBinaryComparator[] cmps = new IBinaryComparator[searchKey.getFieldCount()];
+        IBinaryComparator[] newCmps = new IBinaryComparator[searchKey.getFieldCount()];
         for (int i = 0; i < searchKey.getFieldCount(); i++) {
-            cmps[i] = btreeCmp.getComparators()[i];
+        	newCmps[i] = cmps[i];
         }
-        return new MultiComparator(cmps);
+        return new MultiComparator(newCmps);
     }
     
     public static ITreeIndexFrameFactory getLeafFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory, BTreeLeafFrameType leafType) throws BTreeException {
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexAccessor.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexAccessor.java
index e187aa8..e0271f3 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexAccessor.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexAccessor.java
@@ -69,6 +69,12 @@
 			TreeIndexException;
 
 	/**
+	 * Creates a cursor appropriate for passing into search().
+	 * 
+	 */
+	public ITreeIndexCursor createSearchCursor();
+	
+	/**
 	 * Open the given cursor for an index search using the given predicate as
 	 * search condition.
 	 * 
@@ -84,6 +90,12 @@
 			throws HyracksDataException, TreeIndexException;
 
 	/**
+	 * Creates a cursor appropriate for passing into diskOrderScan().
+	 * 
+	 */
+	public ITreeIndexCursor createDiskOrderScanCursor();
+	
+	/**
 	 * Open the given cursor for a disk-order scan, positioning the cursor to
 	 * the first leaf tuple.
 	 * 
diff --git a/hyracks-storage-am-lsmtree-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/impls/LSMTree.java b/hyracks-storage-am-lsmtree-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/impls/LSMTree.java
index dd3d6b4..266cc93 100644
--- a/hyracks-storage-am-lsmtree-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/impls/LSMTree.java
+++ b/hyracks-storage-am-lsmtree-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/impls/LSMTree.java
@@ -433,6 +433,11 @@
         }
 
         @Override
+        public ITreeIndexCursor createSearchCursor() {
+            return new LSMTreeRangeSearchCursor();
+        }
+        
+        @Override
         public void search(ITreeIndexCursor cursor, ISearchPredicate searchPred) throws HyracksDataException,
                 TreeIndexException {
             ctx.reset(IndexOp.SEARCH);
@@ -440,6 +445,12 @@
         }
 
         @Override
+        public ITreeIndexCursor createDiskOrderScanCursor() {
+            // TODO: Not implemented yet.
+            return null;
+        }
+        
+        @Override
         public void diskOrderScan(ITreeIndexCursor cursor) throws HyracksDataException {
             throw new UnsupportedOperationException("DiskOrderScan not supported by LSMTree");
         }
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTree.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTree.java
index fb05090..0846f07 100644
--- a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTree.java
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTree.java
@@ -282,7 +282,7 @@
     }
 
     @Override
-    public void flush() throws Exception {
+    public void flush() throws HyracksDataException, TreeIndexException {
 
         // scan the RTree
         ITreeIndexCursor rtreeScanCursor = new RTreeSearchCursor(
@@ -348,7 +348,7 @@
         threadRefCount++;
     }
 
-    public void threadExit() throws Exception {
+    public void threadExit() throws HyracksDataException, TreeIndexException {
         synchronized (this) {
             threadRefCount--;
             // Check if we've reached or exceeded the maximum number of pages.
@@ -478,6 +478,11 @@
         }
 
         @Override
+		public ITreeIndexCursor createSearchCursor() {			
+			return new LSMRTreeSearchCursor();
+		}
+        
+        @Override
         public void search(ITreeIndexCursor cursor, ISearchPredicate searchPred) throws HyracksDataException,
                 TreeIndexException {
             ctx.reset(IndexOp.SEARCH);
@@ -490,6 +495,12 @@
         }
 
         @Override
+		public ITreeIndexCursor createDiskOrderScanCursor() {
+			// TODO: Not implemented yet.
+			return null;
+		}
+        
+        @Override
         public void diskOrderScan(ITreeIndexCursor cursor) throws HyracksDataException {
             throw new UnsupportedOperationException("DiskOrderScan not supported by LSMRTree");
         }
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeSearchCursor.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeSearchCursor.java
index e8f29d4..b0c1178 100644
--- a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeSearchCursor.java
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeSearchCursor.java
@@ -10,6 +10,7 @@
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
@@ -44,7 +45,7 @@
     }
 
     @Override
-    public boolean hasNext() throws Exception {
+    public boolean hasNext() throws HyracksDataException {
         for (int i = currentCursror; i < numberOfTrees; i++) {
             while (rtreeCursors[i].hasNext()) {
                 rtreeCursors[i].next();
@@ -54,11 +55,17 @@
                     btreeRangePredicate.setHighKey(currentTuple, true);
                     btreeRangePredicate.setLowKey(currentTuple, true);
 
-                    if (j == 0) {
-                        memBtreeAccessor.search(btreeCursors[j], btreeRangePredicate);
-                    } else {
-                        onDiskBTreeAccessors[j - 1].search(btreeCursors[j], btreeRangePredicate);
-                    }
+					try {
+						if (j == 0) {
+							memBtreeAccessor.search(btreeCursors[j],
+									btreeRangePredicate);
+						} else {
+							onDiskBTreeAccessors[j - 1].search(btreeCursors[j],
+									btreeRangePredicate);
+						}
+					} catch (TreeIndexException e) {
+						throw new HyracksDataException(e);
+					}
 
                     if (btreeCursors[j].hasNext()) {
                         killerTupleFound = true;
@@ -75,7 +82,7 @@
     }
 
     @Override
-    public void next() throws Exception {
+    public void next() throws HyracksDataException {
         while (true) {
             if (currentCursror < numberOfTrees || rtreeCursors[currentCursror].hasNext()) {
                 break;
@@ -102,7 +109,7 @@
         for (int i = 0; i < numberOfTrees; i++) {
             // we already have an accessor for the in-memory b-tree
             if (i < numberOfTrees - 1) {
-                onDiskBTreeAccessors[i] = lsmRTree.getInDiskBTreeList().get(i).createAccessor();
+                onDiskBTreeAccessors[i] = lsmRTree.getOnDiskBTrees().get(i).createAccessor();
             }
 
             rtreeCursors[i] = new RTreeSearchCursor((IRTreeInteriorFrame) ((LSMRTreeCursorInitialState) initialState)
@@ -122,16 +129,20 @@
         return null;
     }
 
-    @Override
-    public void close() throws Exception {
-        lsmRTree.threadExit();
-        for (int i = 0; i < numberOfTrees; i++) {
-            rtreeCursors[i].close();
-            btreeCursors[i].close();
-        }
-        rtreeCursors = null;
-        btreeCursors = null;
-    }
+	@Override
+	public void close() throws HyracksDataException {
+		try {
+			lsmRTree.threadExit();
+		} catch (TreeIndexException e) {
+			throw new HyracksDataException(e);
+		}
+		for (int i = 0; i < numberOfTrees; i++) {
+			rtreeCursors[i].close();
+			btreeCursors[i].close();
+		}
+		rtreeCursors = null;
+		btreeCursors = null;
+	}
 
     @Override
     public void setBufferCache(IBufferCache bufferCache) {
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
index c3b83e2..96f3439 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
@@ -1080,6 +1080,13 @@
             rtree.delete(tuple, ctx);
         }
 
+		@Override
+		public ITreeIndexCursor createSearchCursor() {
+			return new RTreeSearchCursor(
+					(IRTreeInteriorFrame) interiorFrameFactory.createFrame(),
+					(IRTreeLeafFrame) leafFrameFactory.createFrame());
+		}
+        
         @Override
         public void search(ITreeIndexCursor cursor, ISearchPredicate searchPred) throws HyracksDataException,
                 TreeIndexException {
@@ -1088,6 +1095,11 @@
         }
 
         @Override
+		public ITreeIndexCursor createDiskOrderScanCursor() {
+        	return new TreeDiskOrderScanCursor(leafFrameFactory.createFrame());
+		}
+        
+        @Override
         public void diskOrderScan(ITreeIndexCursor cursor) throws HyracksDataException {
             ctx.reset(IndexOp.DISKORDERSCAN);
             rtree.diskOrderScan(cursor, ctx);
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeExamplesTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeExamplesTest.java
index 5bb86b9..c26b98e 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeExamplesTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeExamplesTest.java
@@ -32,14 +32,12 @@
 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.api.IBTreeLeafFrame;
 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.BTreeRangeSearchCursor;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
 import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
 import edu.uci.ics.hyracks.storage.am.btree.util.BTreeUtils;
 import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
@@ -49,11 +47,16 @@
 @SuppressWarnings("rawtypes")
 public class BTreeExamplesTest extends AbstractBTreeTest {
 
+	protected ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparator[] cmps) throws TreeIndexException {
+		return BTreeUtils
+                .createBTree(bufferCache, btreeFileId, typeTraits, cmps, BTreeLeafFrameType.REGULAR_NSM);
+	}
+	
     /**
      * Fixed-Length Key,Value Example.
      * 
-     * Create a BTree with one fixed-length key field and one fixed-length value
-     * field. Fill BTree with random values using insertions (not bulk load).
+     * Create a tree index with one fixed-length key field and one fixed-length value
+     * field. Fill index with random values using insertions (not bulk load).
      * Perform scans and range search.
      */
     @Test
@@ -76,10 +79,9 @@
         IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
         cmps[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY).createBinaryComparator();
 
-        BTree btree = BTreeUtils
-                .createBTree(bufferCache, btreeFileId, typeTraits, cmps, BTreeLeafFrameType.REGULAR_NSM);
-        btree.create(btreeFileId);
-        btree.open(btreeFileId);
+        ITreeIndex treeIndex = createTreeIndex(typeTraits, cmps);
+        treeIndex.create(btreeFileId);
+        treeIndex.open(btreeFileId);
 
         long start = System.currentTimeMillis();
         if (LOGGER.isLoggable(Level.INFO)) {
@@ -87,7 +89,7 @@
         }
         ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
         ArrayTupleReference tuple = new ArrayTupleReference();
-        ITreeIndexAccessor indexAccessor = btree.createAccessor();
+        ITreeIndexAccessor indexAccessor = treeIndex.createAccessor();
         int numInserts = 10000;
         for (int i = 0; i < numInserts; i++) {
             int f0 = rnd.nextInt() % numInserts;
@@ -108,8 +110,8 @@
             LOGGER.info(numInserts + " inserts in " + (end - start) + "ms");
         }
 
-        orderedScan(btree, indexAccessor, fieldSerdes);
-        diskOrderScan(btree, indexAccessor, fieldSerdes);
+        orderedScan(indexAccessor, fieldSerdes);
+        diskOrderScan(indexAccessor, fieldSerdes);
 
         // Build low key.
         ArrayTupleBuilder lowKeyTb = new ArrayTupleBuilder(keyFieldCount);
@@ -121,16 +123,16 @@
         ArrayTupleReference highKey = new ArrayTupleReference();
         TupleUtils.createIntegerTuple(highKeyTb, highKey, 1000);
 
-        rangeSearch(btree, indexAccessor, fieldSerdes, lowKey, highKey);
+        rangeSearch(cmps, indexAccessor, fieldSerdes, lowKey, highKey);
 
-        btree.close();
+        treeIndex.close();
     }
 
     /**
-     * Composite Key Example (Non-Unique B-Tree).
+     * Composite Key Example (Non-Unique Index).
      * 
-     * Create a BTree with two fixed-length key fields and one fixed-length
-     * value field. Fill BTree with random values using insertions (not bulk
+     * Create a tree index with two fixed-length key fields and one fixed-length
+     * value field. Fill index with random values using insertions (not bulk
      * load) Perform scans and range search.
      */
     @Test
@@ -155,10 +157,9 @@
         cmps[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY).createBinaryComparator();
         cmps[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY).createBinaryComparator();
 
-        BTree btree = BTreeUtils
-                .createBTree(bufferCache, btreeFileId, typeTraits, cmps, BTreeLeafFrameType.REGULAR_NSM);
-        btree.create(btreeFileId);
-        btree.open(btreeFileId);
+        ITreeIndex treeIndex = createTreeIndex(typeTraits, cmps);
+        treeIndex.create(btreeFileId);
+        treeIndex.open(btreeFileId);
 
         long start = System.currentTimeMillis();
         if (LOGGER.isLoggable(Level.INFO)) {
@@ -166,7 +167,7 @@
         }
         ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
         ArrayTupleReference tuple = new ArrayTupleReference();
-        ITreeIndexAccessor indexAccessor = btree.createAccessor();
+        ITreeIndexAccessor indexAccessor = treeIndex.createAccessor();
         int numInserts = 10000;
         for (int i = 0; i < 10000; i++) {
             int f0 = rnd.nextInt() % 2000;
@@ -188,8 +189,8 @@
             LOGGER.info(numInserts + " inserts in " + (end - start) + "ms");
         }
 
-        orderedScan(btree, indexAccessor, fieldSerdes);
-        diskOrderScan(btree, indexAccessor, fieldSerdes);
+        orderedScan(indexAccessor, fieldSerdes);
+        diskOrderScan(indexAccessor, fieldSerdes);
 
         // Build low key.
         ArrayTupleBuilder lowKeyTb = new ArrayTupleBuilder(1);
@@ -202,9 +203,9 @@
         TupleUtils.createIntegerTuple(highKeyTb, highKey, 3);
 
         // Prefix-Range search in [-3, 3]
-        rangeSearch(btree, indexAccessor, fieldSerdes, lowKey, highKey);
+        rangeSearch(cmps, indexAccessor, fieldSerdes, lowKey, highKey);
 
-        btree.close();
+        treeIndex.close();
     }
 
     /**
@@ -232,10 +233,9 @@
         IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
         cmps[0] = PointableBinaryComparatorFactory.of(UTF8StringPointable.FACTORY).createBinaryComparator();
 
-        BTree btree = BTreeUtils
-                .createBTree(bufferCache, btreeFileId, typeTraits, cmps, BTreeLeafFrameType.REGULAR_NSM);
-        btree.create(btreeFileId);
-        btree.open(btreeFileId);
+        ITreeIndex treeIndex = createTreeIndex(typeTraits, cmps);
+        treeIndex.create(btreeFileId);
+        treeIndex.open(btreeFileId);
 
         long start = System.currentTimeMillis();
         if (LOGGER.isLoggable(Level.INFO)) {
@@ -243,7 +243,7 @@
         }
         ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
         ArrayTupleReference tuple = new ArrayTupleReference();
-        ITreeIndexAccessor indexAccessor = btree.createAccessor();
+        ITreeIndexAccessor indexAccessor = treeIndex.createAccessor();
         // Max string length to be generated.
         int maxLength = 10;
         int numInserts = 10000;
@@ -266,8 +266,8 @@
             LOGGER.info(numInserts + " inserts in " + (end - start) + "ms");
         }
 
-        orderedScan(btree, indexAccessor, fieldSerdes);
-        diskOrderScan(btree, indexAccessor, fieldSerdes);
+        orderedScan(indexAccessor, fieldSerdes);
+        diskOrderScan(indexAccessor, fieldSerdes);
 
         // Build low key.
         ArrayTupleBuilder lowKeyTb = new ArrayTupleBuilder(1);
@@ -279,9 +279,9 @@
         ArrayTupleReference highKey = new ArrayTupleReference();
         TupleUtils.createTuple(highKeyTb, highKey, fieldSerdes, "cc7");
 
-        rangeSearch(btree, indexAccessor, fieldSerdes, lowKey, highKey);
+        rangeSearch(cmps, indexAccessor, fieldSerdes, lowKey, highKey);
 
-        btree.close();
+        treeIndex.close();
     }
 
     /**
@@ -311,14 +311,13 @@
         IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
         cmps[0] = PointableBinaryComparatorFactory.of(UTF8StringPointable.FACTORY).createBinaryComparator();
 
-        BTree btree = BTreeUtils
-                .createBTree(bufferCache, btreeFileId, typeTraits, cmps, BTreeLeafFrameType.REGULAR_NSM);
-        btree.create(btreeFileId);
-        btree.open(btreeFileId);
+        ITreeIndex treeIndex = createTreeIndex(typeTraits, cmps);
+        treeIndex.create(btreeFileId);
+        treeIndex.open(btreeFileId);
 
         ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
         ArrayTupleReference tuple = new ArrayTupleReference();
-        ITreeIndexAccessor indexAccessor = btree.createAccessor();
+        ITreeIndexAccessor indexAccessor = treeIndex.createAccessor();
         // Max string length to be generated.
         int runs = 3;
         for (int run = 0; run < runs; run++) {
@@ -382,7 +381,7 @@
                 break;
             }
         }
-        btree.close();
+        treeIndex.close();
     }
 
     /**
@@ -412,15 +411,14 @@
         IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
         cmps[0] = PointableBinaryComparatorFactory.of(UTF8StringPointable.FACTORY).createBinaryComparator();
 
-        BTree btree = BTreeUtils
-                .createBTree(bufferCache, btreeFileId, typeTraits, cmps, BTreeLeafFrameType.REGULAR_NSM);
-        btree.create(btreeFileId);
-        btree.open(btreeFileId);
+        ITreeIndex treeIndex = createTreeIndex(typeTraits, cmps);
+        treeIndex.create(btreeFileId);
+        treeIndex.open(btreeFileId);
 
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info("Inserting into tree...");
         }
-        ITreeIndexAccessor indexAccessor = btree.createAccessor();
+        ITreeIndexAccessor indexAccessor = treeIndex.createAccessor();
         ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
         ArrayTupleReference tuple = new ArrayTupleReference();
         int maxLength = 10;
@@ -442,7 +440,7 @@
             }
         }
         // Print before doing any updates.
-        orderedScan(btree, indexAccessor, fieldSerdes);
+        orderedScan(indexAccessor, fieldSerdes);
 
         int runs = 3;
         for (int run = 0; run < runs; run++) {
@@ -456,18 +454,19 @@
                 TupleUtils.createTuple(tb, tuple, fieldSerdes, keys[i], f1);
                 if (LOGGER.isLoggable(Level.INFO)) {
                     if (i % 1000 == 0) {
-                        LOGGER.info("UPDATING " + i);
+                        LOGGER.info("Updating " + i);
                     }
                 }
                 try {
                     indexAccessor.update(tuple);
                 } catch (TreeIndexException e) {
+                } catch (UnsupportedOperationException e) {
                 }
             }
             // Do another scan after a round of updates.
-            orderedScan(btree, indexAccessor, fieldSerdes);
+            orderedScan(indexAccessor, fieldSerdes);
         }
-        btree.close();
+        treeIndex.close();
     }
 
     /**
@@ -498,10 +497,9 @@
         cmps[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY).createBinaryComparator();
         cmps[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY).createBinaryComparator();
 
-        BTree btree = BTreeUtils
-                .createBTree(bufferCache, btreeFileId, typeTraits, cmps, BTreeLeafFrameType.REGULAR_NSM);
-        btree.create(btreeFileId);
-        btree.open(btreeFileId);
+        ITreeIndex treeIndex = createTreeIndex(typeTraits, cmps);
+        treeIndex.create(btreeFileId);
+        treeIndex.open(btreeFileId);
 
         // Load sorted records.
         int ins = 100000;
@@ -509,20 +507,20 @@
             LOGGER.info("Bulk loading " + ins + " tuples");
         }
         long start = System.currentTimeMillis();
-        IIndexBulkLoadContext bulkLoadCtx = btree.beginBulkLoad(0.7f);
+        IIndexBulkLoadContext bulkLoadCtx = treeIndex.beginBulkLoad(0.7f);
         ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
         ArrayTupleReference tuple = new ArrayTupleReference();
         for (int i = 0; i < ins; i++) {
             TupleUtils.createIntegerTuple(tb, tuple, i, i, 5);
-            btree.bulkLoadAddTuple(tuple, bulkLoadCtx);
+            treeIndex.bulkLoadAddTuple(tuple, bulkLoadCtx);
         }
-        btree.endBulkLoad(bulkLoadCtx);
+        treeIndex.endBulkLoad(bulkLoadCtx);
         long end = System.currentTimeMillis();
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info(ins + " tuples loaded in " + (end - start) + "ms");
         }
 
-        ITreeIndexAccessor indexAccessor = btree.createAccessor();
+        ITreeIndexAccessor indexAccessor = treeIndex.createAccessor();
 
         // Build low key.
         ArrayTupleBuilder lowKeyTb = new ArrayTupleBuilder(1);
@@ -535,18 +533,17 @@
         TupleUtils.createIntegerTuple(highKeyTb, highKey, 44500);
 
         // Prefix-Range search in [44444, 44500]
-        rangeSearch(btree, indexAccessor, fieldSerdes, lowKey, highKey);
+        rangeSearch(cmps, indexAccessor, fieldSerdes, lowKey, highKey);
 
-        btree.close();
+        treeIndex.close();
     }
 
-    private void orderedScan(BTree btree, ITreeIndexAccessor indexAccessor, ISerializerDeserializer[] fieldSerdes)
+    private void orderedScan(ITreeIndexAccessor indexAccessor, ISerializerDeserializer[] fieldSerdes)
             throws Exception {
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info("Ordered Scan:");
         }
-        IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) btree.getLeafFrameFactory().createFrame();
-        ITreeIndexCursor scanCursor = new BTreeRangeSearchCursor(leafFrame, false);
+        ITreeIndexCursor scanCursor = indexAccessor.createSearchCursor();        
         RangePredicate nullPred = new RangePredicate(true, null, null, true, true, null, null);
         indexAccessor.search(scanCursor, nullPred);
         try {
@@ -563,13 +560,17 @@
         }
     }
 
-    private void diskOrderScan(BTree btree, ITreeIndexAccessor indexAccessor, ISerializerDeserializer[] fieldSerdes)
+    private void diskOrderScan(ITreeIndexAccessor indexAccessor, ISerializerDeserializer[] fieldSerdes)
             throws Exception {
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info("Disk-Order Scan:");
         }
-        IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) btree.getLeafFrameFactory().createFrame();
-        TreeDiskOrderScanCursor diskOrderCursor = new TreeDiskOrderScanCursor(leafFrame);
+        TreeDiskOrderScanCursor diskOrderCursor = (TreeDiskOrderScanCursor) indexAccessor.createDiskOrderScanCursor();
+        if (diskOrderCursor == null) {
+        	if (LOGGER.isLoggable(Level.INFO)) {
+                LOGGER.info("Ignoring disk-order scan since it's not supported.");
+            }
+        }
         indexAccessor.diskOrderScan(diskOrderCursor);
         try {
             while (diskOrderCursor.hasNext()) {
@@ -585,17 +586,16 @@
         }
     }
 
-    private void rangeSearch(BTree btree, ITreeIndexAccessor indexAccessor, ISerializerDeserializer[] fieldSerdes,
+    private void rangeSearch(IBinaryComparator[] cmps, ITreeIndexAccessor indexAccessor, ISerializerDeserializer[] fieldSerdes,
             ITupleReference lowKey, ITupleReference highKey) throws Exception {
         if (LOGGER.isLoggable(Level.INFO)) {
             String lowKeyString = TupleUtils.printTuple(lowKey, fieldSerdes);
             String highKeyString = TupleUtils.printTuple(highKey, fieldSerdes);
             LOGGER.info("Range-Search in: [" + lowKeyString + ", " + highKeyString + "]");
         }
-        IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) btree.getLeafFrameFactory().createFrame();
-        MultiComparator lowKeySearchCmp = BTreeUtils.getSearchMultiComparator(btree.getMultiComparator(), lowKey);
-        MultiComparator highKeySearchCmp = BTreeUtils.getSearchMultiComparator(btree.getMultiComparator(), highKey);
-        ITreeIndexCursor rangeCursor = new BTreeRangeSearchCursor(leafFrame, false);
+        ITreeIndexCursor rangeCursor = indexAccessor.createSearchCursor();
+        MultiComparator lowKeySearchCmp = BTreeUtils.getSearchMultiComparator(cmps, lowKey);
+        MultiComparator highKeySearchCmp = BTreeUtils.getSearchMultiComparator(cmps, highKey);
         RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, true, true, lowKeySearchCmp,
                 highKeySearchCmp);
         indexAccessor.search(rangeCursor, rangePred);
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 794f24c..1ef2e83 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
@@ -160,8 +160,8 @@
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info("Testing Range Search.");
         }
-        MultiComparator lowKeyCmp = BTreeUtils.getSearchMultiComparator(testCtx.btree.getMultiComparator(), lowKey);
-        MultiComparator highKeyCmp = BTreeUtils.getSearchMultiComparator(testCtx.btree.getMultiComparator(), highKey);
+        MultiComparator lowKeyCmp = BTreeUtils.getSearchMultiComparator(testCtx.btree.getMultiComparator().getComparators(), lowKey);
+        MultiComparator highKeyCmp = BTreeUtils.getSearchMultiComparator(testCtx.btree.getMultiComparator().getComparators(), highKey);
         ITreeIndexCursor searchCursor = new BTreeRangeSearchCursor(testCtx.leafFrame, false);
         RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, lowKeyInclusive, highKeyInclusive, lowKeyCmp, highKeyCmp);
         testCtx.indexAccessor.search(searchCursor, rangePred);
@@ -214,8 +214,8 @@
         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);
+            MultiComparator lowKeyCmp = BTreeUtils.getSearchMultiComparator(testCtx.btree.getMultiComparator().getComparators(), lowKey);
+            MultiComparator highKeyCmp = BTreeUtils.getSearchMultiComparator(testCtx.btree.getMultiComparator().getComparators(), highKey);
                         
             rangePred.setLowKey(lowKey, true);
             rangePred.setHighKey(highKey, true);