diff --git a/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/freepage/InMemoryBufferCache.java b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/freepage/InMemoryBufferCache.java
index 100cf79..d667336 100644
--- a/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/freepage/InMemoryBufferCache.java
+++ b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/freepage/InMemoryBufferCache.java
@@ -121,7 +121,7 @@
 		// Do nothing.
 	}
 
-    private class CachedPage implements ICachedPageInternal {
+    public class CachedPage implements ICachedPageInternal {
         private final int cpid;
         private final ByteBuffer buffer;
         private final ReadWriteLock latch;
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMBTreeOpContext.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMBTreeOpContext.java
index f35ee34..6c4f98a 100644
--- a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMBTreeOpContext.java
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMBTreeOpContext.java
@@ -9,15 +9,15 @@
 
 public final class LSMBTreeOpContext extends BTreeOpContext {
 
-    public final BTree.BTreeAccessor memBtreeAccessor;
+    public final BTree.BTreeAccessor memBTreeAccessor;
 
     public LSMBTreeOpContext(BTree.BTreeAccessor memBtreeAccessor, ITreeIndexFrameFactory leafFrameFactory,
             ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexMetaDataFrame metaFrame, MultiComparator cmp) {
         super(leafFrameFactory, interiorFrameFactory, metaFrame, cmp);
 
-        this.memBtreeAccessor = memBtreeAccessor;
+        this.memBTreeAccessor = memBtreeAccessor;
         // Overwrite the BTree accessor's op context with our LSMBTreeOpContext.
-        this.memBtreeAccessor.setOpContext(this);
+        this.memBTreeAccessor.setOpContext(this);
 
         reset(op);
     }
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 c308473..2c837bf 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
@@ -7,6 +7,7 @@
 import edu.uci.ics.hyracks.api.io.FileReference;
 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.exceptions.BTreeDuplicateKeyException;
 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;
@@ -47,11 +48,13 @@
     private final ITreeIndexFrameFactory btreeInteriorFrameFactory;
     private final ITreeIndexFrameFactory rtreeLeafFrameFactory;
     private final ITreeIndexFrameFactory btreeLeafFrameFactory;
-    private final MultiComparator cmp;
+    private final MultiComparator rtreeCmp;
+    private final MultiComparator btreeCmp;
 
     // TODO: change to private, it's public only for LSMTreeSearchTest
     public LinkedList<ITreeIndex> inDiskRTreeList;
     public LinkedList<ITreeIndex> inDiskBTreeList;
+
     private LinkedList<ITreeIndex> mergedInDiskRTreeList;
     private LinkedList<ITreeIndex> mergedInDiskBTreeList;
     private int inDiskTreeCounter;
@@ -59,15 +62,17 @@
     private final BTreeFactory bTreeFactory;
     private final IFileMapManager fileMapManager;
     private int threadReferenceCounter;
+    private int threadRefCount;
     private boolean flushFlag;
 
-    public LSMRTree(IBufferCache rtreeMemCache, IBufferCache bufferCache, int fieldCount, MultiComparator cmp,
-    		InMemoryFreePageManager memFreePageManager, ITreeIndexFrameFactory rtreeInteriorFrameFactory,
-            ITreeIndexFrameFactory btreeInteriorFrameFactory, ITreeIndexFrameFactory rtreeLeafFrameFactory,
-            ITreeIndexFrameFactory btreeLeafFrameFactory, RTreeFactory rTreeFactory, BTreeFactory bTreeFactory,
-            IFileMapManager fileMapManager) {
+    public LSMRTree(IBufferCache rtreeMemCache, IBufferCache bufferCache, int fieldCount, MultiComparator rtreeCmp,
+            MultiComparator btreeCmp, InMemoryFreePageManager memFreePageManager,
+            ITreeIndexFrameFactory rtreeInteriorFrameFactory, ITreeIndexFrameFactory btreeInteriorFrameFactory,
+            ITreeIndexFrameFactory rtreeLeafFrameFactory, ITreeIndexFrameFactory btreeLeafFrameFactory,
+            RTreeFactory rTreeFactory, BTreeFactory bTreeFactory, IFileMapManager fileMapManager) {
         this.bufferCache = bufferCache;
-        this.cmp = cmp;
+        this.rtreeCmp = rtreeCmp;
+        this.btreeCmp = btreeCmp;
         this.rtreeInteriorFrameFactory = rtreeInteriorFrameFactory;
         this.btreeInteriorFrameFactory = btreeInteriorFrameFactory;
         this.rtreeLeafFrameFactory = rtreeLeafFrameFactory;
@@ -80,6 +85,7 @@
         this.inDiskTreeCounter = 0;
         this.fileMapManager = fileMapManager;
         this.threadReferenceCounter = 0;
+        this.threadRefCount = 0;
         this.created = false;
         this.flushFlag = false;
 
@@ -96,9 +102,9 @@
             e.printStackTrace();
         }
 
-        memRTree = new RTree(rtreeMemCache, fieldCount, cmp, memFreePageManager, rtreeInteriorFrameFactory,
+        memRTree = new RTree(rtreeMemCache, fieldCount, rtreeCmp, memFreePageManager, rtreeInteriorFrameFactory,
                 rtreeLeafFrameFactory);
-        memBTree = new BTree(rtreeMemCache, fieldCount, cmp, memFreePageManager, btreeInteriorFrameFactory,
+        memBTree = new BTree(rtreeMemCache, fieldCount, btreeCmp, memFreePageManager, btreeInteriorFrameFactory,
                 btreeLeafFrameFactory);
     }
 
@@ -226,13 +232,11 @@
         // RTree.
         IIndexBulkLoadContext rtreeBulkLoadCtx = inDiskRTree.beginBulkLoad(1.0f);
 
-        int i = 0;
         try {
             while (rtreeScanCursor.hasNext()) {
                 rtreeScanCursor.next();
                 ITupleReference frameTuple = rtreeScanCursor.getTuple();
                 inDiskRTree.bulkLoadAddTuple(frameTuple, rtreeBulkLoadCtx);
-                i++;
             }
         } finally {
             rtreeScanCursor.close();
@@ -296,7 +300,7 @@
         memBTree.create(btreeFileId);
     }
 
-    private void decreaseThreadReferenceCounter() throws Exception {
+    public void decreaseThreadReferenceCounter() throws Exception {
         synchronized (this) {
             threadReferenceCounter--;
             if (flushFlag == true) {
@@ -310,144 +314,101 @@
             }
         }
     }
+    
+    public void threadEnter() {
+        threadRefCount++;
+    }
+    
+    public void threadExit() throws Exception {
+        synchronized (this) {
+            threadRefCount--;
+            // Check if we've reached or exceeded the maximum number of pages.
+            if (!flushFlag && memFreePageManager.isFull()) {
+                flushFlag = true;
+            }
+            // Flush will only be handled by last exiting thread.
+            if (flushFlag && threadRefCount == 0) {
+                flush();
+                flushFlag = false;
+            }
+        }
+    }
 
     private void insert(ITupleReference tuple, LSMTreeOpContext ctx) throws HyracksDataException, TreeIndexException {
-        try {
-            boolean continuePerformOp = false;
-            while (continuePerformOp == false) {
-            	synchronized (this) {
-            		if (!flushFlag) {
-            			threadReferenceCounter++;
-            			continuePerformOp = true;
-            		}
-            	}
-            }
-            ctx.LSMRTreeOpContext.memRtreeAccessor.insert(tuple);
-            decreaseThreadReferenceCounter();
-            // Check if we've reached or exceeded the maximum number of pages.
-            // Note: It doesn't matter if this inserter or another concurrent
-            // inserter caused the overflow.
-            // The first inserter reaching this code, should set the flush flag.
-            // Also, setting the flush flag multiple times doesn't hurt.
-            if (memFreePageManager.isFull()) {
-            	synchronized (this) {
-                    // If flushFlag is false it means we are the first inserter
-                    // to
-                    // trigger the flush. If flushFlag is already set to true,
-                    // there's no harm in setting it to true again.
-                    flushFlag = true;
-                    threadReferenceCounter--;
-                    if (threadReferenceCounter == 0) {
-                        flush();
-                        ctx.LSMRTreeOpContext.reset(IndexOp.INSERT);
-                        ctx.LSMRTreeOpContext.memRtreeAccessor.insert(tuple);
-                        flushFlag = false;
-                        return;
-                    } else if (threadReferenceCounter < 0) {
-                        throw new Error("Thread reference counter is below zero. This indicates a programming error!");
-                    }
+        boolean waitForFlush = false;
+        do {
+            synchronized (this) {
+                if (!flushFlag) {
+                    threadEnter();
+                    waitForFlush = false;
                 }
             }
+        } while (waitForFlush == true);
+        ctx.LSMRTreeOpContext.memRTreeAccessor.insert(tuple);
+        try {
+            threadExit();
         } catch (Exception e) {
             e.printStackTrace();
         }
     }
 
     private void delete(ITupleReference tuple, LSMTreeOpContext ctx) throws HyracksDataException, TreeIndexException {
-        try {
-        	boolean continuePerformOp = false;
-        	while (continuePerformOp == false) {
-        		synchronized (this) {
-        			if (!flushFlag) {
-        				threadReferenceCounter++;
-        				continuePerformOp = true;
-        			}
-        		}
-        	}
-        	ctx.LSMBTreeOpContext.memBtreeAccessor.insert(tuple);
-        	decreaseThreadReferenceCounter();
-            // Check if we've reached or exceeded the maximum number of pages.
-            // Note: It doesn't matter if this inserter or another concurrent
-            // inserter caused the overflow.
-            // The first inserter reaching this code, should set the flush flag.
-            // Also, setting the flush flag multiple times doesn't hurt.
-            if (memFreePageManager.isFull()) {
-            	synchronized (this) {
-                    // If flushFlag is false it means we are the first inserter
-                    // to
-                    // trigger the flush. If flushFlag is already set to true,
-                    // there's no harm in setting it to true again.
-                    flushFlag = true;
-                    threadReferenceCounter--;
-                    if (threadReferenceCounter == 0) {
-                        flush();
-                        ctx.LSMBTreeOpContext.reset(IndexOp.INSERT);
-                        ctx.LSMBTreeOpContext.memBtreeAccessor.insert(tuple);
-                        flushFlag = false;
-                        return;
-                    } else if (threadReferenceCounter < 0) {
-                        throw new Error("Thread reference counter is below zero. This indicates a programming error!");
-                    }
+        boolean waitForFlush = false;
+        do {
+            synchronized (this) {
+                if (!flushFlag) {
+                    threadEnter();
+                    waitForFlush = false;
                 }
             }
+        } while (waitForFlush == true);
+        ctx.LSMBTreeOpContext.memBTreeAccessor.insert(tuple);
+        try {
+            threadExit();
         } catch (Exception e) {
             e.printStackTrace();
         }
     }
 
-    private void search(ITreeIndexCursor cursor, ISearchPredicate searchPred, LSMTreeOpContext ctx) throws Exception {
-        // int numberOfInDiskTrees;
-        // ListIterator<InDiskTreeInfo> inDiskTreeInfoListIterator;
-        // boolean continuePerformOp = false;
-        //
-        // ctx.reset(IndexOp.SEARCH);
-        //
-        // while (continuePerformOp == false) {
-        // synchronized (this) {
-        // if (!flushFlag) {
-        // threadReferenceCounter++;
-        // continuePerformOp = true;
-        // }
-        // }
-        // }
-        //
-        // // in-disk
-        // synchronized (inDiskTreeInfoList) {
-        // numberOfInDiskTrees = inDiskTreeInfoList.size();
-        // inDiskTreeInfoListIterator = inDiskTreeInfoList.listIterator();
-        // }
-        //
-        // LSMTreeCursorInitialState initialState = new
-        // LSMTreeCursorInitialState(numberOfInDiskTrees + 1,
-        // insertLeafFrameFactory, cmp, this);
-        // cursor.open(initialState, pred);
-        //
-        // BTree[] onDiskBtrees = new BTree[numberOfInDiskTrees];
-        // ITreeIndexAccessor[] onDiskBtreeAccessors = new
-        // ITreeIndexAccessor[numberOfInDiskTrees];
-        //
-        // for (int i = 0; i < numberOfInDiskTrees; i++) {
-        // // get btree instances for in-disk trees
-        // if (inDiskTreeInfoListIterator.hasNext()) {
-        // onDiskBtrees[i] = ((InDiskTreeInfo)
-        // inDiskTreeInfoListIterator.next()).getBTree();
-        // } else {
-        // throw new HyracksDataException("Cannot find in-disk tree instance");
-        // }
-        // onDiskBtreeAccessors[i] = onDiskBtrees[i].createAccessor();
-        // onDiskBtreeAccessors[i].search(((LSMTreeRangeSearchCursor)
-        // cursor).getCursor(i + 1), pred);
-        // }
-        //
-        // // in-memory
-        // ctx.memBtreeAccessor.search(((LSMTreeRangeSearchCursor)
-        // cursor).getCursor(0), pred);
-        //
-        // LSMPriorityQueueComparator LSMPriorityQueueCmp = new
-        // LSMPriorityQueueComparator(cmp);
-        // ((LSMTreeRangeSearchCursor)
-        // cursor).initPriorityQueue(numberOfInDiskTrees + 1,
-        // LSMPriorityQueueCmp);
+    private void search(ITreeIndexCursor cursor, ISearchPredicate rtreeSearchPred, LSMTreeOpContext ctx)
+            throws Exception {
+
+        boolean continuePerformOp = false;
+        ctx.reset(IndexOp.SEARCH);
+
+        while (continuePerformOp == false) {
+            synchronized (this) {
+                if (!flushFlag) {
+                    threadReferenceCounter++;
+                    continuePerformOp = true;
+                }
+            }
+        }
+
+        int numberOfInDiskTrees;
+        synchronized (inDiskRTreeList) {
+            numberOfInDiskTrees = inDiskRTreeList.size();
+        }
+
+        LSMRTreeCursorInitialState initialState = new LSMRTreeCursorInitialState(numberOfInDiskTrees + 1,
+                rtreeLeafFrameFactory, rtreeInteriorFrameFactory, btreeLeafFrameFactory, btreeCmp,
+                ctx.LSMBTreeOpContext.memBTreeAccessor, this);
+        cursor.open(initialState, rtreeSearchPred);
+
+        ITreeIndexAccessor[] onDiskRTreeAccessors = new ITreeIndexAccessor[numberOfInDiskTrees];
+
+        for (int i = 0; i < numberOfInDiskTrees; i++) {
+            onDiskRTreeAccessors[i] = inDiskRTreeList.get(i).createAccessor();
+            onDiskRTreeAccessors[i].search(((LSMRTreeSearchCursor) cursor).getRTreeCursor(i + 1), rtreeSearchPred);
+        }
+
+        // in-memory
+        ctx.LSMRTreeOpContext.memRTreeAccessor.search(((LSMRTreeSearchCursor) cursor).getRTreeCursor(0),
+                rtreeSearchPred);
+    }
+
+    public LinkedList<ITreeIndex> getInDiskBTreeList() {
+        return inDiskBTreeList;
     }
 
     private LSMTreeOpContext createOpContext() {
@@ -457,7 +418,7 @@
                 (IRTreeInteriorFrame) rtreeInteriorFrameFactory.createFrame(), memFreePageManager
                         .getMetaDataFrameFactory().createFrame(), 8), new LSMBTreeOpContext(
                 (BTree.BTreeAccessor) memBTree.createAccessor(), btreeLeafFrameFactory, btreeInteriorFrameFactory,
-                memFreePageManager.getMetaDataFrameFactory().createFrame(), cmp));
+                memFreePageManager.getMetaDataFrameFactory().createFrame(), btreeCmp));
     }
 
     private class LSMRTreeAccessor implements ITreeIndexAccessor {
@@ -506,3 +467,4 @@
     }
 
 }
+
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeCursorInitialState.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeCursorInitialState.java
new file mode 100644
index 0000000..3838899
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeCursorInitialState.java
@@ -0,0 +1,69 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls;
+
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public class LSMRTreeCursorInitialState implements ICursorInitialState {
+
+    private int numberOfTrees;
+    private ITreeIndexFrameFactory rtreeInteriorFrameFactory;
+    private ITreeIndexFrameFactory rtreeLeafFrameFactory;
+    private ITreeIndexFrameFactory btreeLeafFrameFactory;
+    private MultiComparator btreeCmp;
+    private LSMRTree lsmRTree;
+    private BTree.BTreeAccessor memBtreeAccessor;
+
+    public LSMRTreeCursorInitialState(int numberOfTrees, ITreeIndexFrameFactory rtreeLeafFrameFactory,
+            ITreeIndexFrameFactory rtreeInteriorFrameFactory, ITreeIndexFrameFactory btreeLeafFrameFactory,
+            MultiComparator btreeCmp, BTree.BTreeAccessor memBtreeAccessor, LSMRTree lsmRTree) {
+        this.numberOfTrees = numberOfTrees;
+        this.rtreeLeafFrameFactory = rtreeLeafFrameFactory;
+        this.rtreeInteriorFrameFactory = rtreeInteriorFrameFactory;
+        this.btreeLeafFrameFactory = btreeLeafFrameFactory;
+        this.btreeCmp = btreeCmp;
+        this.lsmRTree = lsmRTree;
+        this.memBtreeAccessor = memBtreeAccessor;
+    }
+
+    public int getNumberOfTrees() {
+        return numberOfTrees;
+    }
+
+    public ITreeIndexFrameFactory getRTreeInteriorFrameFactory() {
+        return rtreeInteriorFrameFactory;
+    }
+
+    public ITreeIndexFrameFactory getRTreeLeafFrameFactory() {
+        return rtreeLeafFrameFactory;
+    }
+
+    public ITreeIndexFrameFactory getBTreeLeafFrameFactory() {
+        return btreeLeafFrameFactory;
+    }
+
+    public MultiComparator getBTreeCmp() {
+        return btreeCmp;
+    }
+
+    @Override
+    public ICachedPage getPage() {
+        return null;
+    }
+
+    @Override
+    public void setPage(ICachedPage page) {
+    }
+
+    public BTree.BTreeAccessor getMemBtreeAccessor() {
+        return memBtreeAccessor;
+    }
+
+    public LSMRTree getLsmRTree() {
+        return lsmRTree;
+    }
+
+}
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeInMemoryBufferCache.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeInMemoryBufferCache.java
index 39a3665..5162c68 100644
--- a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeInMemoryBufferCache.java
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeInMemoryBufferCache.java
@@ -1,5 +1,7 @@
 package edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls;
 
+import java.nio.ByteBuffer;
+
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.InMemoryBufferCache;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICacheMemoryAllocator;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
@@ -16,10 +18,28 @@
         int pageId = BufferedFileHandle.getPageId(dpid);
         int fileId = BufferedFileHandle.getFileId(dpid);
 
-        if (pageId == 0 || pageId == 1) {
-            return pages[pageId + 2 * fileId];
+        if (pageId < pages.length) {
+            // Common case: Return regular page.
+            
+            if (pageId == 0 || pageId == 1) {
+                return pages[pageId + 2 * fileId];
+            } else {
+                return pages[pageId];
+            }
         } else {
-            return pages[pageId];
+            // Rare case: Return overflow page, possibly expanding overflow
+            // array.
+            synchronized (overflowPages) {
+                int numNewPages = pageId - pages.length - overflowPages.size() + 1;
+                if (numNewPages > 0) {
+                    ByteBuffer[] buffers = allocator.allocate(pageSize, numNewPages);
+                    for (int i = 0; i < numNewPages; i++) {
+                        CachedPage overflowPage = new CachedPage(pages.length + overflowPages.size(), buffers[i]);
+                        overflowPages.add(overflowPage);
+                    }
+                }
+                return overflowPages.get(pageId - pages.length);
+            }
         }
     }
 
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeInMemoryFreePageManager.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeInMemoryFreePageManager.java
index 6a08899..1511e474 100644
--- a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeInMemoryFreePageManager.java
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeInMemoryFreePageManager.java
@@ -7,8 +7,12 @@
 
 public class LSMRTreeInMemoryFreePageManager extends InMemoryFreePageManager {
 
-    public LSMRTreeInMemoryFreePageManager(int maxCapacity, ITreeIndexMetaDataFrameFactory metaDataFrameFactory) {
-        super(maxCapacity, metaDataFrameFactory);
+    public LSMRTreeInMemoryFreePageManager(int capacity, ITreeIndexMetaDataFrameFactory metaDataFrameFactory) {
+        super(capacity, metaDataFrameFactory);
+        // We start the currentPageId from 3, because the RTree uses
+        // the first page as metadata page, and the second page as root page.
+        // And the BTree uses the third page as metadata, and the third page as root page 
+        // (when returning free pages we first increment, then get)
         currentPageId.set(3);
     }
 
@@ -17,6 +21,10 @@
         currentPageId.set(3);
     }
 
+    public int getCapacity() {
+        return capacity - 4;
+    }
+    
     public void reset() {
         currentPageId.set(3);
     }
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeOpContext.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeOpContext.java
index a3df90f..57a0413 100644
--- a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeOpContext.java
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeOpContext.java
@@ -9,16 +9,16 @@
 
 public final class LSMRTreeOpContext extends RTreeOpContext {
     
-    public final RTree.RTreeAccessor memRtreeAccessor;
+    public final RTree.RTreeAccessor memRTreeAccessor;
 
     public LSMRTreeOpContext(RTree.RTreeAccessor memRtreeAccessor, IRTreeLeafFrame leafFrame,
             IRTreeInteriorFrame interiorFrame, ITreeIndexMetaDataFrame metaFrame, int treeHeightHint) {
 
         super(leafFrame, interiorFrame, metaFrame, treeHeightHint);
 
-        this.memRtreeAccessor = memRtreeAccessor;
+        this.memRTreeAccessor = memRtreeAccessor;
         // Overwrite the RTree accessor's op context with our LSMRTreeOpContext.
-        this.memRtreeAccessor.setOpContext(this);
+        this.memRTreeAccessor.setOpContext(this);
 
         reset(op);
     }
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
new file mode 100644
index 0000000..17f2d95
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeSearchCursor.java
@@ -0,0 +1,162 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls;
+
+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.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+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.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSearchCursor;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public class LSMRTreeSearchCursor implements ITreeIndexCursor {
+
+    private BTreeRangeSearchCursor[] btreeCursors;
+    private RTreeSearchCursor[] rtreeCursors;
+    private BTree.BTreeAccessor memBtreeAccessor;
+    private ITreeIndexAccessor[] onDiskBTreeAccessors;
+    private int currentCursror;
+    private MultiComparator btreeCmp;
+    private int numberOfTrees;
+    private LSMRTree lsmRTree;
+    private RangePredicate btreeRangePredicate;
+    private ITupleReference frameTuple;
+
+    public LSMRTreeSearchCursor() {
+        currentCursror = 0;
+    }
+
+    public RTreeSearchCursor getRTreeCursor(int cursorIndex) {
+        return rtreeCursors[cursorIndex];
+    }
+
+    @Override
+    public void reset() {
+        // do nothing
+    }
+
+    @Override
+    public boolean hasNext() throws Exception {
+        for (int i = currentCursror; i < numberOfTrees; i++) {
+            while (rtreeCursors[i].hasNext()) {
+                rtreeCursors[i].next();
+                ITupleReference currentTuple = rtreeCursors[i].getTuple();
+                boolean killerTupleFound = false;
+                for (int j = 0; j <= i; j++) {
+                    btreeRangePredicate.setHighKey(currentTuple, true);
+                    btreeRangePredicate.setLowKey(currentTuple, true);
+
+                    if (j == 0) {
+                        memBtreeAccessor.search(btreeCursors[j], btreeRangePredicate);
+                    } else {
+                        onDiskBTreeAccessors[j - 1].search(btreeCursors[j], btreeRangePredicate);
+                    }
+
+                    if (btreeCursors[j].hasNext()) {
+                        killerTupleFound = true;
+                        break;
+                    }
+                }
+                if (!killerTupleFound) {
+                    frameTuple = currentTuple;
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+    @Override
+    public void next() throws Exception {
+        while (true) {
+            if (currentCursror < numberOfTrees || rtreeCursors[currentCursror].hasNext()) {
+                break;
+            } else {
+                currentCursror++;
+            }
+        }
+    }
+
+    @Override
+    public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
+
+        lsmRTree = ((LSMRTreeCursorInitialState) initialState).getLsmRTree();
+        btreeCmp = ((LSMRTreeCursorInitialState) initialState).getBTreeCmp();
+        memBtreeAccessor = ((LSMRTreeCursorInitialState) initialState).getMemBtreeAccessor();
+
+        numberOfTrees = ((LSMRTreeCursorInitialState) initialState).getNumberOfTrees();
+
+        rtreeCursors = new RTreeSearchCursor[numberOfTrees];
+        btreeCursors = new BTreeRangeSearchCursor[numberOfTrees];
+
+        onDiskBTreeAccessors = new ITreeIndexAccessor[numberOfTrees - 1];
+
+        for (int i = 0; i < numberOfTrees; i++) {
+            if (i < ((LSMRTreeCursorInitialState) initialState).getNumberOfTrees() - 1) { // we
+                                                                                          // already
+                                                                                          // have
+                                                                                          // an
+                                                                                          // accessor
+                                                                                          // for
+                                                                                          // the
+                                                                                          // in-memory
+                                                                                          // b-tree
+                onDiskBTreeAccessors[i] = lsmRTree.getInDiskBTreeList().get(i).createAccessor();
+            }
+
+            rtreeCursors[i] = new RTreeSearchCursor((IRTreeInteriorFrame) ((LSMRTreeCursorInitialState) initialState)
+                    .getRTreeInteriorFrameFactory().createFrame(),
+                    (IRTreeLeafFrame) ((LSMRTreeCursorInitialState) initialState).getRTreeLeafFrameFactory()
+                            .createFrame());
+
+            btreeCursors[i] = new BTreeRangeSearchCursor((IBTreeLeafFrame) ((LSMRTreeCursorInitialState) initialState)
+                    .getBTreeLeafFrameFactory().createFrame(), false);
+        }
+        btreeRangePredicate = new RangePredicate(true, null, null, true, true, btreeCmp, btreeCmp);
+    }
+
+    @Override
+    public ICachedPage getPage() {
+        // do nothing
+        return null;
+    }
+
+    @Override
+    public void close() throws Exception {
+        lsmRTree.decreaseThreadReferenceCounter();
+        for (int i = 0; i < numberOfTrees; i++) {
+            rtreeCursors[i].close();
+            btreeCursors[i].close();
+        }
+        rtreeCursors = null;
+        btreeCursors = null;
+    }
+
+    @Override
+    public void setBufferCache(IBufferCache bufferCache) {
+        // do nothing
+    }
+
+    @Override
+    public void setFileId(int fileId) {
+        // do nothing
+    }
+
+    @Override
+    public ITupleReference getTuple() {
+        return frameTuple;
+    }
+
+    @Override
+    public boolean exclusiveLatchNodes() {
+        return false;
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-lsmtree-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/LSMRTreeTest.java b/hyracks-tests/hyracks-storage-am-lsmtree-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/LSMRTreeTest.java
index 0a412b3..cb21305 100644
--- a/hyracks-tests/hyracks-storage-am-lsmtree-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/LSMRTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsmtree-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/LSMRTreeTest.java
@@ -1,8 +1,12 @@
 package edu.uci.ics.hyracks.storage.am.lsmtree.rtree;
 
+import java.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
 import java.io.DataOutput;
 import java.io.File;
 import java.nio.ByteBuffer;
+import java.util.ArrayList;
 import java.util.Random;
 import java.util.logging.Level;
 
@@ -22,12 +26,14 @@
 import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
 import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.FrameTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
 import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
 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.common.api.IPrimitiveValueProviderFactory;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
@@ -39,10 +45,12 @@
 import edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls.LSMRTree;
 import edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls.LSMRTreeInMemoryBufferCacheFactory;
 import edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls.LSMRTreeInMemoryFreePageManager;
+import edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls.LSMRTreeSearchCursor;
 import edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls.LSMTypeAwareTupleWriterFactory;
 import edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls.RTreeFactory;
 import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrameFactory;
 import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
 import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 import edu.uci.ics.hyracks.storage.common.file.IFileMapManager;
@@ -53,7 +61,7 @@
 public class LSMRTreeTest extends AbstractLSMTreeTest {
 
     private static final int PAGE_SIZE = 256;
-    private static final int NUM_PAGES = 100;
+    private static final int NUM_PAGES = 1000;
     private static final int MAX_OPEN_FILES = 100;
     private static final int HYRACKS_FRAME_SIZE = 128;
     private IHyracksTaskContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
@@ -75,13 +83,24 @@
                 NUM_PAGES);
         IBufferCache memBufferCache = inMemBufferCacheFactory.createInMemoryBufferCache();
 
-        // declare keys
-        int keyFieldCount = 4;
-        IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
-        cmps[0] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY).createBinaryComparator();
-        cmps[1] = cmps[0];
-        cmps[2] = cmps[0];
-        cmps[3] = cmps[0];
+        // declare r-tree keys
+        int rtreeKeyFieldCount = 4;
+        IBinaryComparator[] rtreeCmps = new IBinaryComparator[rtreeKeyFieldCount];
+        rtreeCmps[0] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY).createBinaryComparator();
+        rtreeCmps[1] = rtreeCmps[0];
+        rtreeCmps[2] = rtreeCmps[0];
+        rtreeCmps[3] = rtreeCmps[0];
+
+        // declare b-tree keys
+        int btreeKeyFieldCount = 7;
+        IBinaryComparator[] btreeCmps = new IBinaryComparator[btreeKeyFieldCount];
+        btreeCmps[0] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY).createBinaryComparator();
+        btreeCmps[1] = btreeCmps[0];
+        btreeCmps[2] = btreeCmps[0];
+        btreeCmps[3] = btreeCmps[0];
+        btreeCmps[4] = btreeCmps[0];
+        btreeCmps[5] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY).createBinaryComparator();
+        btreeCmps[6] = btreeCmps[0];
 
         // declare tuple fields
         int fieldCount = 7;
@@ -94,11 +113,12 @@
         typeTraits[5] = IntegerPointable.TYPE_TRAITS;
         typeTraits[6] = DoublePointable.TYPE_TRAITS;
 
-        MultiComparator cmp = new MultiComparator(cmps);
+        MultiComparator rtreeCmp = new MultiComparator(rtreeCmps);
+        MultiComparator btreeCmp = new MultiComparator(btreeCmps);
 
         // create value providers
         IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
-                cmps.length, DoublePointable.FACTORY);
+                rtreeCmps.length, DoublePointable.FACTORY);
 
         LSMTypeAwareTupleWriterFactory rtreeTupleWriterFactory = new LSMTypeAwareTupleWriterFactory(typeTraits, false);
         LSMTypeAwareTupleWriterFactory btreeTupleWriterFactory = new LSMTypeAwareTupleWriterFactory(typeTraits, true);
@@ -113,21 +133,22 @@
 
         ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
 
-        InMemoryFreePageManager memFreePageManager = new LSMRTreeInMemoryFreePageManager(100, metaFrameFactory);
+        InMemoryFreePageManager memFreePageManager = new LSMRTreeInMemoryFreePageManager(1000, metaFrameFactory);
 
-        LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(bufferCache, metaFrameFactory);
+        LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(bufferCache,
+                metaFrameFactory);
 
-        RTreeFactory rTreeFactory = new RTreeFactory(bufferCache, freePageManagerFactory, cmp, fieldCount,
+        RTreeFactory rTreeFactory = new RTreeFactory(bufferCache, freePageManagerFactory, rtreeCmp, fieldCount,
                 rtreeInteriorFrameFactory, rtreeLeafFrameFactory);
-        BTreeFactory bTreeFactory = new BTreeFactory(bufferCache, freePageManagerFactory, cmp, fieldCount,
+        BTreeFactory bTreeFactory = new BTreeFactory(bufferCache, freePageManagerFactory, btreeCmp, fieldCount,
                 btreeInteriorFrameFactory, btreeLeafFrameFactory);
 
-        LSMRTree lsmrtree = new LSMRTree(memBufferCache, bufferCache, fieldCount, cmp, memFreePageManager,
-                rtreeInteriorFrameFactory, btreeInteriorFrameFactory, rtreeLeafFrameFactory, btreeLeafFrameFactory,
-                rTreeFactory, bTreeFactory, (IFileMapManager) fmp);
+        LSMRTree lsmRTree = new LSMRTree(memBufferCache, bufferCache, fieldCount, rtreeCmp, btreeCmp,
+                memFreePageManager, rtreeInteriorFrameFactory, btreeInteriorFrameFactory, rtreeLeafFrameFactory,
+                btreeLeafFrameFactory, rTreeFactory, bTreeFactory, (IFileMapManager) fmp);
 
-        lsmrtree.create(fileId);
-        lsmrtree.open(fileId);
+        lsmRTree.create(fileId);
+        lsmRTree.open(fileId);
 
         ByteBuffer frame = ctx.allocateFrame();
         FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
@@ -147,7 +168,7 @@
 
         FrameTupleReference tuple = new FrameTupleReference();
 
-        ITreeIndexAccessor lsmTreeAccessor = lsmrtree.createAccessor();
+        ITreeIndexAccessor lsmTreeAccessor = lsmRTree.createAccessor();
 
         Random rnd = new Random();
         rnd.setSeed(50);
@@ -193,6 +214,9 @@
                 // }
             }
 
+            if (i == 1691) {
+                System.out.println();
+            }
             try {
                 lsmTreeAccessor.insert(tuple);
             } catch (TreeIndexException e) {
@@ -201,6 +225,65 @@
             }
         }
 
+        for (int i = 0; i < 50; i++) {
+            double p1x = rnd.nextDouble();
+            double p1y = rnd.nextDouble();
+            double p2x = rnd.nextDouble();
+            double p2y = rnd.nextDouble();
+
+            int pk = rnd.nextInt();
+
+            tb.reset();
+            DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1x, p2x), dos);
+            tb.addFieldEndOffset();
+            DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1y, p2y), dos);
+            tb.addFieldEndOffset();
+            DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1x, p2x), dos);
+            tb.addFieldEndOffset();
+            DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1y, p2y), dos);
+            tb.addFieldEndOffset();
+            IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
+            tb.addFieldEndOffset();
+
+            appender.reset(frame, true);
+            appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+
+            tuple.reset(accessor, 0);
+
+            if (LOGGER.isLoggable(Level.INFO)) {
+                LOGGER.info(i + " Searching for: " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " "
+                        + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y));
+            }
+
+            ITreeIndexCursor searchCursor = new LSMRTreeSearchCursor();
+            SearchPredicate searchPredicate = new SearchPredicate(tuple, rtreeCmp);
+
+            lsmTreeAccessor.search(searchCursor, searchPredicate);
+
+            ArrayList<Integer> results = new ArrayList<Integer>();
+            try {
+                while (searchCursor.hasNext()) {
+                    searchCursor.next();
+                    ITupleReference frameTuple = searchCursor.getTuple();
+                    ByteArrayInputStream inStream = new ByteArrayInputStream(frameTuple.getFieldData(4),
+                            frameTuple.getFieldStart(4), frameTuple.getFieldLength(4));
+                    DataInput dataIn = new DataInputStream(inStream);
+                    Integer res = IntegerSerializerDeserializer.INSTANCE.deserialize(dataIn);
+                    results.add(res);
+                    if (results.size() == 1632) {
+                        System.out.println();
+                    }
+                }
+            } catch (Exception e) {
+                e.printStackTrace();
+            } finally {
+                searchCursor.close();
+            }
+            if (LOGGER.isLoggable(Level.INFO)) {
+                LOGGER.info("There are " + results.size() + " objects that satisfy the query");
+            }
+        }
+
         rnd.setSeed(50);
         for (int i = 0; i < 5000; i++) {
 
@@ -249,7 +332,7 @@
             }
         }
 
-        lsmrtree.close();
+        lsmRTree.close();
         bufferCache.closeFile(fileId);
         memBufferCache.close();
     }