diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManagerFactory.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManagerFactory.java
new file mode 100644
index 0000000..bcf7e70
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManagerFactory.java
@@ -0,0 +1,36 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.common.freepage;
+
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+public class LinkedListFreePageManagerFactory {
+
+	private final ITreeIndexMetaDataFrameFactory metaDataFrameFactory;
+	private final IBufferCache bufferCache;
+	
+	public LinkedListFreePageManagerFactory(IBufferCache bufferCache, ITreeIndexMetaDataFrameFactory metaDataFrameFactory) {
+		this.metaDataFrameFactory = metaDataFrameFactory;
+		this.bufferCache = bufferCache;
+	}
+	
+    public IFreePageManager createFreePageManager(int fileId) {
+        return new LinkedListFreePageManager(bufferCache, fileId, 0, metaDataFrameFactory);
+    }
+
+}
diff --git a/hyracks-storage-am-lsmtree-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/impls/BTreeFactory.java b/hyracks-storage-am-lsmtree-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/impls/BTreeFactory.java
index 5816314..202ef68 100644
--- a/hyracks-storage-am-lsmtree-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/impls/BTreeFactory.java
+++ b/hyracks-storage-am-lsmtree-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/impls/BTreeFactory.java
@@ -2,8 +2,8 @@
 
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.FreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 
 public class BTreeFactory {
@@ -13,9 +13,9 @@
 	private MultiComparator cmp;
 	private ITreeIndexFrameFactory interiorFrameFactory;
 	private ITreeIndexFrameFactory leafFrameFactory;
-	private FreePageManagerFactory freePageManagerFactory;
+	private LinkedListFreePageManagerFactory freePageManagerFactory;
 	
-	public BTreeFactory(IBufferCache bufferCache, FreePageManagerFactory freePageManagerFactory, MultiComparator cmp, 
+	public BTreeFactory(IBufferCache bufferCache, LinkedListFreePageManagerFactory freePageManagerFactory, MultiComparator cmp, 
 			int fieldCount, ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory) {
 		this.bufferCache = bufferCache;
 		this.fieldCount = fieldCount;
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 76e1284..7991a37 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
@@ -29,7 +29,6 @@
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
 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.lsmtree.common.freepage.FreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.InMemoryFreePageManager;
 import edu.uci.ics.hyracks.storage.am.lsmtree.tuples.LSMTypeAwareTupleReference;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
diff --git a/hyracks-storage-am-lsmtree-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/perf/LSMTreeUtils.java b/hyracks-storage-am-lsmtree-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/perf/LSMTreeUtils.java
index 08a2aa2..2071583 100644
--- a/hyracks-storage-am-lsmtree-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/perf/LSMTreeUtils.java
+++ b/hyracks-storage-am-lsmtree-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/perf/LSMTreeUtils.java
@@ -9,8 +9,8 @@
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.FreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.InMemoryFreePageManager;
 import edu.uci.ics.hyracks.storage.am.lsmtree.impls.BTreeFactory;
 import edu.uci.ics.hyracks.storage.am.lsmtree.impls.LSMTree;
@@ -35,7 +35,7 @@
 		// For the Flush Mechanism
 		LSMEntireTupleWriterFactory flushTupleWriterFactory = new LSMEntireTupleWriterFactory(typeTraits);
 		ITreeIndexFrameFactory flushLeafFrameFactory = BTreeUtils.getLeafFrameFactory(flushTupleWriterFactory,leafType); 
-		FreePageManagerFactory freePageManagerFactory = new FreePageManagerFactory(bufferCache, metaFrameFactory);
+		LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(bufferCache, metaFrameFactory);
 		BTreeFactory bTreeFactory = new BTreeFactory(bufferCache, freePageManagerFactory, cmp, typeTraits.length, interiorFrameFactory, flushLeafFrameFactory);
         
         LSMTree lsmtree = new LSMTree(memCache, bufferCache, typeTraits.length, cmp, memFreePageManager, 
diff --git a/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/freepage/FreePageManagerFactory.java b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/freepage/FreePageManagerFactory.java
deleted file mode 100644
index cacc2c9..0000000
--- a/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/freepage/FreePageManagerFactory.java
+++ /dev/null
@@ -1,23 +0,0 @@
-package edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage;
-
-import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
-import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
-import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
-
-
-public class FreePageManagerFactory {
-
-	private final ITreeIndexMetaDataFrameFactory metaDataFrameFactory;
-	private final IBufferCache bufferCache;
-	
-	public FreePageManagerFactory(IBufferCache bufferCache, ITreeIndexMetaDataFrameFactory metaDataFrameFactory) {
-		this.metaDataFrameFactory = metaDataFrameFactory;
-		this.bufferCache = bufferCache;
-	}
-	
-    public IFreePageManager createFreePageManager(int fileId) {
-        return new LinkedListFreePageManager(bufferCache, fileId, 0, metaDataFrameFactory);
-    }
-
-}
diff --git a/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/freepage/InMemoryFreePageManager.java b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/freepage/InMemoryFreePageManager.java
index 62dcf55..4ad5386 100644
--- a/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/freepage/InMemoryFreePageManager.java
+++ b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/freepage/InMemoryFreePageManager.java
@@ -27,28 +27,23 @@
     protected final AtomicInteger currentPageId = new AtomicInteger();
     protected final ITreeIndexMetaDataFrameFactory metaDataFrameFactory;
 
-    public InMemoryFreePageManager(int maxCapacity, ITreeIndexMetaDataFrameFactory metaDataFrameFactory) {
-        // Since the range of CacheArray in InMemoryBufferCache is 0 ~
-        // maxCapacity-1
-        this.capacity = maxCapacity - 1;
+    public InMemoryFreePageManager(int capacity, ITreeIndexMetaDataFrameFactory metaDataFrameFactory) {
+        // We start the currentPageId from 1, because the BTree uses
+        // the first page as metadata page, and the second page as root page.
+        // (when returning free pages we first increment, then get)
         currentPageId.set(1);
+        this.capacity = capacity;
         this.metaDataFrameFactory = metaDataFrameFactory;
     }
 
-    public int getCurrentCapacity() {
-        return currentPageId.get();
-    }
-
     @Override
     public int getFreePage(ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
+        // The very call returns page id 2 because the BTree uses
+        // the first page as metadata page, and the second page as root page.
         return currentPageId.incrementAndGet();
     }
 
     @Override
-    public void addFreePage(ITreeIndexMetaDataFrame metaFrame, int freePage) throws HyracksDataException {
-    }
-
-    @Override
     public int getMaxPage(ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
         return currentPageId.get();
     }
@@ -63,6 +58,22 @@
         return metaDataFrameFactory;
     }
 
+    public int getCapacity() {
+        return capacity - 2;
+    }
+    
+    public void reset() {
+        currentPageId.set(1);
+    }
+
+    public boolean isFull() {
+        return currentPageId.get() >= capacity;
+    }
+
+    @Override
+    public void addFreePage(ITreeIndexMetaDataFrame metaFrame, int freePage) throws HyracksDataException {
+    }
+
     @Override
     public byte getMetaPageLevelIndicator() {
         return 0;
@@ -82,12 +93,4 @@
     public boolean isFreePage(ITreeIndexMetaDataFrame metaFrame) {
         return false;
     }
-
-    public void reset() {
-        currentPageId.set(1);
-    }
-    
-    public boolean isFull() {
-        return currentPageId.get() >= capacity;
-    }
 }
diff --git a/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/TreeFactory.java b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/TreeFactory.java
index ed702c4..8b59129 100644
--- a/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/TreeFactory.java
+++ b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/TreeFactory.java
@@ -2,8 +2,8 @@
 
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.FreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 
 public abstract class TreeFactory {
@@ -13,9 +13,9 @@
     protected MultiComparator cmp;
     protected ITreeIndexFrameFactory interiorFrameFactory;
     protected ITreeIndexFrameFactory leafFrameFactory;
-    protected FreePageManagerFactory freePageManagerFactory;
+    protected LinkedListFreePageManagerFactory freePageManagerFactory;
 
-    public TreeFactory(IBufferCache bufferCache, FreePageManagerFactory freePageManagerFactory, MultiComparator cmp,
+    public TreeFactory(IBufferCache bufferCache, LinkedListFreePageManagerFactory freePageManagerFactory, MultiComparator cmp,
             int fieldCount, ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory) {
         this.bufferCache = bufferCache;
         this.fieldCount = fieldCount;
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/BTreeFactory.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/BTreeFactory.java
index c6d94ff..2330e42 100644
--- a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/BTreeFactory.java
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/BTreeFactory.java
@@ -3,14 +3,14 @@
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.FreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.impls.TreeFactory;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 
 public class BTreeFactory extends TreeFactory {
 
-    public BTreeFactory(IBufferCache bufferCache, FreePageManagerFactory freePageManagerFactory, MultiComparator cmp,
+    public BTreeFactory(IBufferCache bufferCache, LinkedListFreePageManagerFactory freePageManagerFactory, MultiComparator cmp,
             int fieldCount, ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory) {
         super(bufferCache, freePageManagerFactory, cmp, fieldCount, interiorFrameFactory, leafFrameFactory);
     }
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/RTreeFactory.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/RTreeFactory.java
index 2657739..31d0bda 100644
--- a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/RTreeFactory.java
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/RTreeFactory.java
@@ -2,15 +2,15 @@
 
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.FreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.impls.TreeFactory;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
 import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
 
 public class RTreeFactory extends TreeFactory {
 
-    public RTreeFactory(IBufferCache bufferCache, FreePageManagerFactory freePageManagerFactory, MultiComparator cmp,
+    public RTreeFactory(IBufferCache bufferCache, LinkedListFreePageManagerFactory freePageManagerFactory, MultiComparator cmp,
             int fieldCount, ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory) {
         super(bufferCache, freePageManagerFactory, cmp, fieldCount, interiorFrameFactory, leafFrameFactory);
     }
diff --git a/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeDeleteTest.java b/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeDeleteTest.java
index c7f208b..7fd913f 100644
--- a/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeDeleteTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeDeleteTest.java
@@ -36,8 +36,8 @@
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
 import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.FreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.InMemoryBufferCache;
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.InMemoryFreePageManager;
 import edu.uci.ics.hyracks.storage.am.lsmtree.impls.BTreeFactory;
@@ -98,7 +98,7 @@
 
         InMemoryFreePageManager memFreePageManager = new InMemoryFreePageManager(100, metaFrameFactory);
 
-        FreePageManagerFactory freePageManagerFactory = new FreePageManagerFactory(bufferCache, metaFrameFactory);
+        LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(bufferCache, metaFrameFactory);
         BTreeFactory bTreeFactory = new BTreeFactory(bufferCache, freePageManagerFactory, cmp, fieldCount,
                 interiorFrameFactory, insertLeafFrameFactory);
 
@@ -246,7 +246,7 @@
 
         InMemoryFreePageManager memFreePageManager = new InMemoryFreePageManager(100, metaFrameFactory);
 
-        FreePageManagerFactory freePageManagerFactory = new FreePageManagerFactory(bufferCache, metaFrameFactory);
+        LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(bufferCache, metaFrameFactory);
         BTreeFactory bTreeFactory = new BTreeFactory(bufferCache, freePageManagerFactory, cmp, fieldCount,
                 interiorFrameFactory, insertLeafFrameFactory);
 
@@ -429,7 +429,7 @@
 
         InMemoryFreePageManager memFreePageManager = new InMemoryFreePageManager(100, metaFrameFactory);
 
-        FreePageManagerFactory freePageManagerFactory = new FreePageManagerFactory(bufferCache, metaFrameFactory);
+        LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(bufferCache, metaFrameFactory);
         BTreeFactory bTreeFactory = new BTreeFactory(bufferCache, freePageManagerFactory, cmp, fieldCount,
                 interiorFrameFactory, insertLeafFrameFactory);
 
@@ -608,7 +608,7 @@
 
         InMemoryFreePageManager memFreePageManager = new InMemoryFreePageManager(100, metaFrameFactory);
 
-        FreePageManagerFactory freePageManagerFactory = new FreePageManagerFactory(bufferCache, metaFrameFactory);
+        LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(bufferCache, metaFrameFactory);
         BTreeFactory bTreeFactory = new BTreeFactory(bufferCache, freePageManagerFactory, cmp, fieldCount,
                 interiorFrameFactory, insertLeafFrameFactory);
 
@@ -717,7 +717,7 @@
 
         InMemoryFreePageManager memFreePageManager = new InMemoryFreePageManager(100, metaFrameFactory);
 
-        FreePageManagerFactory freePageManagerFactory = new FreePageManagerFactory(bufferCache, metaFrameFactory);
+        LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(bufferCache, metaFrameFactory);
         BTreeFactory bTreeFactory = new BTreeFactory(bufferCache, freePageManagerFactory, cmp, fieldCount,
                 interiorFrameFactory, insertLeafFrameFactory);
 
@@ -900,7 +900,7 @@
 
         InMemoryFreePageManager memFreePageManager = new InMemoryFreePageManager(100, metaFrameFactory);
 
-        FreePageManagerFactory freePageManagerFactory = new FreePageManagerFactory(bufferCache, metaFrameFactory);
+        LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(bufferCache, metaFrameFactory);
         BTreeFactory bTreeFactory = new BTreeFactory(bufferCache, freePageManagerFactory, cmp, fieldCount,
                 interiorFrameFactory, insertLeafFrameFactory);
 
diff --git a/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeFlushTest.java b/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeFlushTest.java
index 07a128c..0c40485 100644
--- a/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeFlushTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeFlushTest.java
@@ -31,8 +31,8 @@
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
 import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.FreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.InMemoryBufferCache;
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.InMemoryFreePageManager;
 import edu.uci.ics.hyracks.storage.am.lsmtree.impls.BTreeFactory;
@@ -370,7 +370,7 @@
         // For the Flush Mechanism
         LSMEntireTupleWriterFactory flushTupleWriterFactory = new LSMEntireTupleWriterFactory(typeTraits);
         ITreeIndexFrameFactory flushLeafFrameFactory = new BTreeNSMLeafFrameFactory(flushTupleWriterFactory);
-        FreePageManagerFactory freePageManagerFactory = new FreePageManagerFactory(bufferCache, metaFrameFactory);
+        LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(bufferCache, metaFrameFactory);
         BTreeFactory bTreeFactory = new BTreeFactory(bufferCache, freePageManagerFactory, cmp, fieldCount,
                 interiorFrameFactory, flushLeafFrameFactory);
 
diff --git a/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeMergeTest.java b/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeMergeTest.java
index 60583ef..24677f7 100644
--- a/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeMergeTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeMergeTest.java
@@ -31,8 +31,8 @@
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
 import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.FreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.InMemoryBufferCache;
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.InMemoryFreePageManager;
 import edu.uci.ics.hyracks.storage.am.lsmtree.impls.BTreeFactory;
@@ -96,7 +96,7 @@
         // For the Flush Mechanism
         LSMEntireTupleWriterFactory flushTupleWriterFactory = new LSMEntireTupleWriterFactory(typeTraits);
         ITreeIndexFrameFactory flushLeafFrameFactory = new BTreeNSMLeafFrameFactory(flushTupleWriterFactory);
-        FreePageManagerFactory freePageManagerFactory = new FreePageManagerFactory(bufferCache, metaFrameFactory);
+        LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(bufferCache, metaFrameFactory);
         BTreeFactory bTreeFactory = new BTreeFactory(bufferCache, freePageManagerFactory, cmp, fieldCount,
                 interiorFrameFactory, flushLeafFrameFactory);
 
diff --git a/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeSearchTest.java b/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeSearchTest.java
index 5a7cd36..a342076 100644
--- a/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeSearchTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsmtree-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/btree/LSMTreeSearchTest.java
@@ -40,9 +40,9 @@
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
 import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
-import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.FreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.InMemoryBufferCache;
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.InMemoryFreePageManager;
 import edu.uci.ics.hyracks.storage.am.lsmtree.impls.BTreeFactory;
@@ -109,7 +109,7 @@
 
         LSMEntireTupleWriterFactory flushTupleWriterFactory = new LSMEntireTupleWriterFactory(typeTraits);
         ITreeIndexFrameFactory flushLeafFrameFactory = new BTreeNSMLeafFrameFactory(flushTupleWriterFactory);
-        FreePageManagerFactory freePageManagerFactory = new FreePageManagerFactory(bufferCache, metaFrameFactory);
+        LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(bufferCache, metaFrameFactory);
         BTreeFactory bTreeFactory = new BTreeFactory(bufferCache, freePageManagerFactory, cmp, fieldCount,
                 interiorFrameFactory, flushLeafFrameFactory);
 
diff --git a/hyracks-tests/hyracks-storage-am-lsmtree-common-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/InMemoryBufferCacheTest.java b/hyracks-tests/hyracks-storage-am-lsmtree-common-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/InMemoryBufferCacheTest.java
index 308c2cc..02746c8 100644
--- a/hyracks-tests/hyracks-storage-am-lsmtree-common-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/InMemoryBufferCacheTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsmtree-common-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/InMemoryBufferCacheTest.java
@@ -15,115 +15,46 @@
 
 package edu.uci.ics.hyracks.storage.am.lsmtree.common;
 
+import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
+import java.util.HashSet;
+
 import org.junit.Test;
 
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.InMemoryBufferCache;
 import edu.uci.ics.hyracks.storage.common.buffercache.HeapBufferAllocator;
-import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
-import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCacheInternal;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
 
 public class InMemoryBufferCacheTest{
-	
     private static final int PAGE_SIZE = 256;
-    private static final int NUM_PAGES = 10;
-	
-    //TEST InMemoryBufferCache.pin()
+    private static final int NUM_PAGES = 100;
+    private HashSet<ICachedPage> pinnedPages = new HashSet<ICachedPage>();
+    
     @Test
-    public void InMemoryBufferCacheTest01() throws Exception {
-        IBufferCache memBufferCache = new InMemoryBufferCache(new HeapBufferAllocator(), PAGE_SIZE, NUM_PAGES);
-
-        try {
-        	ICachedPage memCachedPage = memBufferCache.pin(10, true);
-        	if(memCachedPage != null) {
-        		return;
-        	}
-        	else {
-        		fail("fail to pin");
-        	}
+    public void test01() throws Exception {
+        InMemoryBufferCache memBufferCache = new InMemoryBufferCache(new HeapBufferAllocator(), PAGE_SIZE, NUM_PAGES);
+        int dummyFileId = 0;
+        // Pin all pages, and make sure they return unique ICachedPages.
+        // We expect no overflow pages.
+        for (int i = 0; i < NUM_PAGES; i++) {
+            ICachedPage page = memBufferCache.pin(BufferedFileHandle.getDiskPageId(dummyFileId, i), false);
+            if (pinnedPages.contains(page)) {
+                fail("Id collision for ICachedPage, caused by id: " + i);
+            }
+            pinnedPages.add(page);
+            assertEquals(0, memBufferCache.getNumOverflowPages());
         }
-        catch (ArrayIndexOutOfBoundsException e){
-        	System.out.println("Catch exception: " + e);
-        	return;
-        }
-        catch (Exception e) {
-        	fail("Unexpected exception!");
+        // Pin pages above capacity. We expect to be given new overflow pages.
+        // Going above capacity should be very rare, but nevertheless succeed.
+        for (int i = 0; i < 100; i++) {
+            ICachedPage page = memBufferCache.pin(BufferedFileHandle.getDiskPageId(dummyFileId, i + NUM_PAGES), false);
+            if (pinnedPages.contains(page)) {
+                fail("Id collision for ICachedPage, caused by overflow id: " + i);
+            }
+            pinnedPages.add(page);
+            assertEquals(i + 1, memBufferCache.getNumOverflowPages());
         }
     }
-    
-    //TEST InMemoryBufferCache.pin()
-	//expect ArrayIndexOutOfBoundsException
-    @Test
-    public void InMemoryBufferCacheTest02() throws Exception {
-    	
-        IBufferCache memBufferCache = new InMemoryBufferCache(new HeapBufferAllocator(), PAGE_SIZE, NUM_PAGES);
-
-        try {
-        	ICachedPage memCachedPage = memBufferCache.pin(500, true);
-        	if(memCachedPage != null) {
-        		return;
-        	}
-        	else {
-        		fail("fail to pin");
-        	}
-        }
-        catch (ArrayIndexOutOfBoundsException e){
-        	System.out.println("Catch exception: " + e);
-        	return;
-        }
-        catch (Exception e) {
-        	fail("Unexpected exception!");
-        }
-    }
-    
-    //TEST InMemoryBufferCache.getPage()
-    @Test
-    public void InMemoryBufferCacheTest03() throws Exception {
-    	
-        IBufferCache memBufferCache = new InMemoryBufferCache(new HeapBufferAllocator(), PAGE_SIZE, NUM_PAGES);
-
-        try {
-        	ICachedPage memCachedPage = ((IBufferCacheInternal) memBufferCache).getPage(20);
-        	if(memCachedPage != null) {
-        		return;
-        	}
-        	else {
-        		fail("fail to pin");
-        	}
-        }
-        catch (ArrayIndexOutOfBoundsException e){
-        	System.out.println("Catch exception: " + e);
-        	return;
-        }
-        catch (Exception e) {
-        	fail("Unexpected exception!");
-        }
-    } 
-    
-    //TEST InMemoryBufferCache.getPage()
-    //expect ArrayIndexOutOfBoundsException
-    @Test
-    public void InMemoryBufferCacheTest04() throws Exception {
-    	
-        IBufferCache memBufferCache = new InMemoryBufferCache(new HeapBufferAllocator(), PAGE_SIZE, NUM_PAGES);
-
-        try {
-        	ICachedPage memCachedPage = ((IBufferCacheInternal) memBufferCache).getPage(1000);
-        	if(memCachedPage != null) {
-        		return;
-        	}
-        	else {
-        		fail("fail to pin");
-        	}
-        }
-        catch (ArrayIndexOutOfBoundsException e){
-        	System.out.println("Catch exception: " + e);
-        	return;
-        }
-        catch (Exception e) {
-        	fail("Unexpected exception!");
-        }
-    } 
 }
diff --git a/hyracks-tests/hyracks-storage-am-lsmtree-common-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/InMemoryFreePageManagerTest.java b/hyracks-tests/hyracks-storage-am-lsmtree-common-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/InMemoryFreePageManagerTest.java
index 3978aa6..0cc4d107 100644
--- a/hyracks-tests/hyracks-storage-am-lsmtree-common-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/InMemoryFreePageManagerTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsmtree-common-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/InMemoryFreePageManagerTest.java
@@ -15,21 +15,51 @@
 
 package edu.uci.ics.hyracks.storage.am.lsmtree.common;
 
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
 import org.junit.Test;
 
-import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 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.lsmtree.common.freepage.InMemoryFreePageManager;
 
 public class InMemoryFreePageManagerTest {
 
-    @Test
-    public void InMemoryFreePageManagerTest01() throws Exception {
-        ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
-        IFreePageManager memFreePageManager = new InMemoryFreePageManager(10, metaFrameFactory);
-        for (int i = 0; i < 5; i++) {
-            memFreePageManager.getFreePage(null);
+    private final int NUM_PAGES = 100;
+    
+    private void testInMemoryFreePageManager(InMemoryFreePageManager memFreePageManager) throws HyracksDataException {
+        // The first two pages are reserved for the BTree's metadata page and
+        // root page.
+        // The "actual" capacity is therefore numPages - 2.
+        int capacity = memFreePageManager.getCapacity();
+        assertEquals(capacity, NUM_PAGES - 2);
+        for (int i = 0; i < capacity; i++) {
+            int pageId = memFreePageManager.getFreePage(null);
+            // The free pages start from page 2;
+            assertEquals(i + 2, pageId);
+            assertFalse(memFreePageManager.isFull());
         }
+        // Start asking for 100 pages above the capacity.
+        // Asking for pages above the capacity should be very rare, but
+        // nevertheless succeed.
+        // We expect isFull() to return true.
+        for (int i = 0; i < 100; i++) {
+            int pageId = memFreePageManager.getFreePage(null);
+            assertEquals(capacity + i + 2, pageId);
+            assertTrue(memFreePageManager.isFull());
+        }
+    }
+    
+    @Test
+    public void test01() throws HyracksDataException {
+        ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+        InMemoryFreePageManager memFreePageManager = new InMemoryFreePageManager(NUM_PAGES, metaFrameFactory);
+        testInMemoryFreePageManager(memFreePageManager);
+        // We expect exactly the same behavior after a reset().
+        memFreePageManager.reset();
+        testInMemoryFreePageManager(memFreePageManager);
     }
 }
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 668759d..0a412b3 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
@@ -32,8 +32,8 @@
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
 import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.FreePageManagerFactory;
 import edu.uci.ics.hyracks.storage.am.lsmtree.common.freepage.InMemoryFreePageManager;
 import edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls.BTreeFactory;
 import edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls.LSMRTree;
@@ -115,7 +115,7 @@
 
         InMemoryFreePageManager memFreePageManager = new LSMRTreeInMemoryFreePageManager(100, metaFrameFactory);
 
-        FreePageManagerFactory freePageManagerFactory = new FreePageManagerFactory(bufferCache, metaFrameFactory);
+        LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(bufferCache, metaFrameFactory);
 
         RTreeFactory rTreeFactory = new RTreeFactory(bufferCache, freePageManagerFactory, cmp, fieldCount,
                 rtreeInteriorFrameFactory, rtreeLeafFrameFactory);