diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
index a079527..3c5bce8 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
@@ -27,10 +27,6 @@
 
     public int getNextLeaf();
 
-    public void setPrevLeaf(int prevPage);
-
-    public int getPrevLeaf();    
-
     public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference pageTuple, MultiComparator cmp,
             FindTupleMode ftm, FindTupleNoExactMatchPolicy ftp) throws HyracksDataException;
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
index 6e9ad81..a82203f 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
@@ -58,8 +58,7 @@
     protected static final int uncompressedTupleCountOff = smFlagOff + 1; // 22
     protected static final int prefixTupleCountOff = uncompressedTupleCountOff + 4; // 26
 
-    protected static final int prevLeafOff = prefixTupleCountOff + 4; // 30
-    protected static final int nextLeafOff = prevLeafOff + 4; // 34
+    protected static final int nextLeafOff = prefixTupleCountOff + 4; // 30
 
     protected ICachedPage page = null;
     protected ByteBuffer buf = null;
@@ -343,7 +342,6 @@
         buf.putInt(prefixTupleCountOff, 0);
         buf.put(levelOff, level);
         buf.put(smFlagOff, (byte) 0);
-        buf.putInt(prevLeafOff, -1);
         buf.putInt(nextLeafOff, -1);
     }
 
@@ -402,7 +400,6 @@
         strBuilder.append("smFlagOff:                 " + smFlagOff + "\n");
         strBuilder.append("uncompressedTupleCountOff: " + uncompressedTupleCountOff + "\n");
         strBuilder.append("prefixTupleCountOff:       " + prefixTupleCountOff + "\n");
-        strBuilder.append("prevLeafOff:               " + prevLeafOff + "\n");
         strBuilder.append("nextLeafOff:               " + nextLeafOff + "\n");
         return strBuilder.toString();
     }
@@ -658,20 +655,10 @@
     }
 
     @Override
-    public void setPrevLeaf(int page) {
-        buf.putInt(prevLeafOff, page);
-    }
-
-    @Override
     public int getNextLeaf() {
         return buf.getInt(nextLeafOff);
     }
 
-    @Override
-    public int getPrevLeaf() {
-        return buf.getInt(prevLeafOff);
-    }
-
     public int getUncompressedTupleCount() {
         return buf.getInt(uncompressedTupleCountOff);
     }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
index 40a7670..4770307 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
@@ -32,8 +32,7 @@
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
 
 public class BTreeNSMLeafFrame extends TreeIndexNSMFrame implements IBTreeLeafFrame {
-    protected static final int prevLeafOff = smFlagOff + 1;
-    protected static final int nextLeafOff = prevLeafOff + 4;
+    protected static final int nextLeafOff = smFlagOff + 1;
     private MultiComparator cmp;
     
     public BTreeNSMLeafFrame(ITreeIndexTupleWriter tupleWriter) {
@@ -43,7 +42,6 @@
     @Override
     public void initBuffer(byte level) {
         super.initBuffer(level);
-        buf.putInt(prevLeafOff, -1);
         buf.putInt(nextLeafOff, -1);
     }
 
@@ -53,21 +51,11 @@
     }
 
     @Override
-    public void setPrevLeaf(int page) {
-        buf.putInt(prevLeafOff, page);
-    }
-
-    @Override
     public int getNextLeaf() {
         return buf.getInt(nextLeafOff);
     }
 
     @Override
-    public int getPrevLeaf() {
-        return buf.getInt(prevLeafOff);
-    }
-
-    @Override
     public int findInsertTupleIndex(ITupleReference tuple) throws TreeIndexException {
         int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.EXCLUSIVE_ERROR_IF_EXISTS,
                 FindTupleNoExactMatchPolicy.HIGHER_KEY);
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 3e155a0..b90a89a 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
@@ -26,6 +26,7 @@
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNonExistentKeyException;
 import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNotUpdateableException;
 import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrame;
 import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
@@ -103,16 +104,6 @@
         fileId = -1;
     }
 
-    private void addFreePages(BTreeOpContext ctx) throws HyracksDataException {
-        for (int i = 0; i < ctx.freePages.size(); i++) {
-            // Root page is special, never add it to free pages.
-            if (ctx.freePages.get(i) != rootPage) {
-                freePageManager.addFreePage(ctx.metaFrame, ctx.freePages.get(i));
-            }
-        }
-        ctx.freePages.clear();
-    }
-    
     private void diskOrderScan(ITreeIndexCursor icursor, BTreeOpContext ctx) throws HyracksDataException {
         TreeDiskOrderScanCursor cursor = (TreeDiskOrderScanCursor) icursor;
         ctx.reset();
@@ -204,39 +195,26 @@
                 false);
         leftNode.acquireWriteLatch();
         try {
-            ICachedPage rightNode = bufferCache.pin(
-                    BufferedFileHandle.getDiskPageId(fileId, ctx.splitKey.getRightPage()), false);
-            rightNode.acquireWriteLatch();
+            int newLeftId = freePageManager.getFreePage(ctx.metaFrame);
+            ICachedPage newLeftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, newLeftId), true);
+            newLeftNode.acquireWriteLatch();
             try {
-                int newLeftId = freePageManager.getFreePage(ctx.metaFrame);
-                ICachedPage newLeftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, newLeftId), true);
-                newLeftNode.acquireWriteLatch();
-                try {
-                    // Copy left child to new left child.
-                    System.arraycopy(leftNode.getBuffer().array(), 0, newLeftNode.getBuffer().array(), 0, newLeftNode
-                            .getBuffer().capacity());
-                    ctx.interiorFrame.setPage(newLeftNode);
-                    ctx.interiorFrame.setSmFlag(false);
-                    // Change sibling pointer if children are leaves.
-                    ctx.leafFrame.setPage(rightNode);
-                    if (ctx.leafFrame.isLeaf()) {
-                        ctx.leafFrame.setPrevLeaf(newLeftId);
-                    }
-                    // Initialize new root (leftNode becomes new root).
-                    ctx.interiorFrame.setPage(leftNode);
-                    ctx.interiorFrame.initBuffer((byte) (ctx.leafFrame.getLevel() + 1));
-                    // Will be cleared later in unsetSmPages.
-                    ctx.interiorFrame.setSmFlag(true);
-                    ctx.splitKey.setLeftPage(newLeftId);
-                    int targetTupleIndex = ctx.interiorFrame.findInsertTupleIndex(ctx.splitKey.getTuple());
-                    ctx.interiorFrame.insert(ctx.splitKey.getTuple(), targetTupleIndex);
-                } finally {
-                    newLeftNode.releaseWriteLatch();
-                    bufferCache.unpin(newLeftNode);
-                }
+                // Copy left child to new left child.
+                System.arraycopy(leftNode.getBuffer().array(), 0, newLeftNode.getBuffer().array(), 0, newLeftNode
+                        .getBuffer().capacity());
+                ctx.interiorFrame.setPage(newLeftNode);
+                ctx.interiorFrame.setSmFlag(false);
+                // Initialize new root (leftNode becomes new root).
+                ctx.interiorFrame.setPage(leftNode);
+                ctx.interiorFrame.initBuffer((byte) (ctx.leafFrame.getLevel() + 1));
+                // Will be cleared later in unsetSmPages.
+                ctx.interiorFrame.setSmFlag(true);
+                ctx.splitKey.setLeftPage(newLeftId);
+                int targetTupleIndex = ctx.interiorFrame.findInsertTupleIndex(ctx.splitKey.getTuple());
+                ctx.interiorFrame.insert(ctx.splitKey.getTuple(), targetTupleIndex);
             } finally {
-                rightNode.releaseWriteLatch();
-                bufferCache.unpin(rightNode);
+                newLeftNode.releaseWriteLatch();
+                bufferCache.unpin(newLeftNode);
             }
         } finally {
             leftNode.releaseWriteLatch();
@@ -264,18 +242,10 @@
             }
             // Split key propagated?
             if (ctx.splitKey.getBuffer() != null) {
-                if (ctx.op == IndexOp.DELETE) {
-                    // Reset level of root to zero.
-                    initRoot(ctx.leafFrame, false);
-                } else {
-                    // Insert or update op. Create a new root.
-                    createNewRoot(ctx);
-                }
+                // Insert or update op. Create a new root.
+                createNewRoot(ctx);
             }
             unsetSmPages(ctx);
-            if (ctx.op == IndexOp.DELETE) {
-                addFreePages(ctx);
-            }
             repeatOp = false;
         }
     }
@@ -341,67 +311,43 @@
     }
     
     private boolean performLeafSplit(int pageId, ITupleReference tuple, BTreeOpContext ctx) throws Exception {    	
-    	// Lock is released in unsetSmPages(), after sm has fully completed.
+        // Lock is released in unsetSmPages(), after sm has fully completed.
         if (!treeLatch.writeLock().tryLock()) {
-        	return true;
+            return true;
         }
-    	int rightSiblingPageId = ctx.leafFrame.getNextLeaf();
-        ICachedPage rightSibling = null;
-        if (rightSiblingPageId > 0) {
-            rightSibling = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rightSiblingPageId),
-                    false);
-        }
+        int rightPageId = freePageManager.getFreePage(ctx.metaFrame);
+        ICachedPage rightNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rightPageId),
+                true);
+        rightNode.acquireWriteLatch();
         try {
-            int rightPageId = freePageManager.getFreePage(ctx.metaFrame);
-            ICachedPage rightNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rightPageId),
-                    true);
-            rightNode.acquireWriteLatch();
-            try {
-                IBTreeLeafFrame rightFrame = ctx.createLeafFrame();
-                rightFrame.setPage(rightNode);
-                rightFrame.initBuffer((byte) 0);
-                rightFrame.setMultiComparator(cmp);
-                ctx.leafFrame.split(rightFrame, tuple, ctx.splitKey);
+            IBTreeLeafFrame rightFrame = ctx.createLeafFrame();
+            rightFrame.setPage(rightNode);
+            rightFrame.initBuffer((byte) 0);
+            rightFrame.setMultiComparator(cmp);
+            ctx.leafFrame.split(rightFrame, tuple, ctx.splitKey);
 
-                ctx.smPages.add(pageId);
-                ctx.smPages.add(rightPageId);
-                ctx.leafFrame.setSmFlag(true);
-                rightFrame.setSmFlag(true);
+            ctx.smPages.add(pageId);
+            ctx.smPages.add(rightPageId);
+            ctx.leafFrame.setSmFlag(true);
+            rightFrame.setSmFlag(true);
 
-                rightFrame.setNextLeaf(ctx.leafFrame.getNextLeaf());
-                rightFrame.setPrevLeaf(pageId);
-                ctx.leafFrame.setNextLeaf(rightPageId);
+            rightFrame.setNextLeaf(ctx.leafFrame.getNextLeaf());
+            ctx.leafFrame.setNextLeaf(rightPageId);
 
-                // TODO: we just use increasing numbers as pageLsn,
-                // we
-                // should tie this together with the LogManager and
-                // TransactionManager
-                rightFrame.setPageLsn(rightFrame.getPageLsn() + 1);
-                ctx.leafFrame.setPageLsn(ctx.leafFrame.getPageLsn() + 1);
+            // TODO: we just use increasing numbers as pageLsn,
+            // we
+            // should tie this together with the LogManager and
+            // TransactionManager
+            rightFrame.setPageLsn(rightFrame.getPageLsn() + 1);
+            ctx.leafFrame.setPageLsn(ctx.leafFrame.getPageLsn() + 1);
 
-                ctx.splitKey.setPages(pageId, rightPageId);
-                
-                if (rightSibling != null) {
-                	rightSibling.acquireWriteLatch();
-                    try {
-                        // Reuse rightFrame for modification.
-                        rightFrame.setPage(rightSibling);
-                        rightFrame.setPrevLeaf(rightPageId);
-                    } finally {
-                        rightSibling.releaseWriteLatch();
-                    }
-                }
-            } finally {
-                rightNode.releaseWriteLatch();
-                bufferCache.unpin(rightNode);
-            }
+            ctx.splitKey.setPages(pageId, rightPageId);
         } catch (Exception e) {
             treeLatch.writeLock().unlock();
             throw e;
         } finally {
-            if (rightSibling != null) {
-                bufferCache.unpin(rightSibling);
-            }
+            rightNode.releaseWriteLatch();
+            bufferCache.unpin(rightNode);
         }
         return false;
     }
@@ -507,134 +453,20 @@
     }
 
     private boolean deleteLeaf(ICachedPage node, int pageId, ITupleReference tuple, BTreeOpContext ctx) throws Exception {
+        // Simply delete the tuple, and don't do any rebalancing.
+        // This means that there could be underflow, even an empty page that is
+        // pointed to by an interior node.
         ctx.leafFrame.setPage(node);
+        if (ctx.leafFrame.getTupleCount() == 0) {
+            throw new BTreeNonExistentKeyException("Trying to delete a tuple with a nonexistent key in leaf node.");
+        }
         int tupleIndex = ctx.leafFrame.findDeleteTupleIndex(tuple);
-        
-        // Will this leaf become empty?
-        if (ctx.leafFrame.getTupleCount() > 1) {
-            // Leaf will not become empty.
-            ctx.leafFrame.delete(tuple, tupleIndex);
-            node.releaseWriteLatch();
-            bufferCache.unpin(node);
-            return false;
-        }
-        
-        // Leaf will become empty. 
-        IBTreeLeafFrame siblingFrame = (IBTreeLeafFrame) leafFrameFactory.createFrame();
-        siblingFrame.setMultiComparator(cmp);
-        ICachedPage leftNode = null;
-        ICachedPage rightNode = null;
-        int nextLeaf = ctx.leafFrame.getNextLeaf();
-        int prevLeaf = ctx.leafFrame.getPrevLeaf();
-        // Try to get the tree latch, if it's already taken, then restart this operation
-        // to avoid latch deadlock.
-        if (!treeLatch.writeLock().tryLock()) {
-        	return true;
-        }
-        try {
-        	if (prevLeaf > 0) {
-        		leftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, prevLeaf), false);
-        	}
-        	try {
-        		if (nextLeaf > 0) {
-        			rightNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, nextLeaf), false);
-        		}
-        		try {
-        			try {
-        				ctx.leafFrame.delete(tuple, tupleIndex);
-        				// To propagate the deletion we only need to make the
-        				// splitKey != null.
-        				// Reuse data to identify which key to delete in the parent.
-        				ctx.splitKey.initData(1);
-        			} catch (Exception e) {
-        				// Don't propagate deletion.
-        				ctx.splitKey.reset();
-        				throw e;
-        			}
-
-        			// TODO: Tie together with logging.
-        			ctx.leafFrame.setPageLsn(ctx.leafFrame.getPageLsn() + 1);
-        			ctx.leafFrame.setLevel(freePageManager.getFreePageLevelIndicator());
-
-        			ctx.smPages.add(pageId);
-        			ctx.leafFrame.setSmFlag(true);
-
-        			node.releaseWriteLatch();
-        			bufferCache.unpin(node);
-
-        			if (leftNode != null) {
-        				leftNode.acquireWriteLatch();
-        				try {
-        					siblingFrame.setPage(leftNode);
-        					siblingFrame.setNextLeaf(nextLeaf);
-        					// TODO: Tie together with logging.
-        					siblingFrame.setPageLsn(siblingFrame.getPageLsn() + 1);
-        				} finally {
-        					leftNode.releaseWriteLatch();
-        				}
-        			}
-
-        			if (rightNode != null) {
-        				rightNode.acquireWriteLatch();
-        				try {
-        					siblingFrame.setPage(rightNode);
-        					siblingFrame.setPrevLeaf(prevLeaf);
-        					// TODO: Tie together with logging.
-        					siblingFrame.setPageLsn(siblingFrame.getPageLsn() + 1);
-        				} finally {
-        					rightNode.releaseWriteLatch();
-        				}
-        			}
-        			// Register pageId as a free.
-        			ctx.freePages.add(pageId);
-        		} finally {
-        			if (rightNode != null) {
-                		bufferCache.unpin(rightNode);
-                	}
-        		}
-        	} finally {
-        		if (leftNode != null) {
-        			bufferCache.unpin(leftNode);
-        		}
-        	}
-        } catch (Exception e) {
-        	treeLatch.writeLock().unlock();
-        	throw e;
-        }
+        ctx.leafFrame.delete(tuple, tupleIndex);
+        node.releaseWriteLatch();
+        bufferCache.unpin(node);
         return false;
     }
 
-    private void deleteInterior(ICachedPage node, int pageId, ITupleReference tuple, BTreeOpContext ctx)
-            throws Exception {
-        ctx.interiorFrame.setPage(node);
-
-        int tupleIndex = ctx.interiorFrame.findDeleteTupleIndex(tuple);
-        
-        // this means there is only a child pointer but no key, this case
-        // propagates the split
-        if (ctx.interiorFrame.getTupleCount() == 0) {
-            ctx.interiorFrame.setPageLsn(ctx.interiorFrame.getPageLsn() + 1); // TODO:
-            // tie
-            // together
-            // with
-            // logging
-            ctx.leafFrame.setLevel(freePageManager.getFreePageLevelIndicator());
-            ctx.smPages.add(pageId);
-            ctx.interiorFrame.setSmFlag(true);
-            ctx.interiorFrame.setRightmostChildPageId(-1); // this node is
-            // completely empty
-            // register this pageId as a free page
-            ctx.freePages.add(pageId);
-
-        } else {
-            ctx.interiorFrame.delete(tuple, tupleIndex);
-            // TODO: Tie together with logging.
-            ctx.interiorFrame.setPageLsn(ctx.interiorFrame.getPageLsn() + 1);
-            // Don't propagate deletion.
-            ctx.splitKey.reset();
-        }
-    }
-
     private final void acquireLatch(ICachedPage node, BTreeOpContext ctx, boolean isLeaf) {
         if (!isLeaf || (ctx.op == IndexOp.SEARCH && !ctx.cursor.exclusiveLatchNodes())) {
             node.acquireReadLatch();
@@ -716,19 +548,14 @@
                         
                         switch (ctx.op) {
                             case INSERT:
-                            case UPDATE:
-                            case DELETE: {
+                            case UPDATE: {
                                 // Is there a propagated split key?
                                 if (ctx.splitKey.getBuffer() != null) {
                                     node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
                                     node.acquireWriteLatch();
                                     try {
-                                        if (ctx.op == IndexOp.DELETE) {
-                                            deleteInterior(node, pageId, ctx.pred.getLowKey(), ctx);                                          
-                                        } else {
-                                            // Insert or update op. Both can cause split keys to propagate upwards.                                            
-                                            insertInterior(node, pageId, ctx.splitKey.getTuple(), ctx);
-                                        }
+                                        // Insert or update op. Both can cause split keys to propagate upwards.                                            
+                                        insertInterior(node, pageId, ctx.splitKey.getTuple(), ctx);
                                     } finally {
                                         node.releaseWriteLatch();
                                         bufferCache.unpin(node);
@@ -738,6 +565,14 @@
                                 }
                                 break;
                             }
+                            
+                            case DELETE: {
+                                if (ctx.splitKey.getBuffer() != null) {
+                                    throw new BTreeException("Split key was propagated during delete. Delete allows empty leaf pages.");
+                                }
+                                break;
+                            }
+                                
                             default: {
                                 // Do nothing for Search and DiskOrderScan.
                                 break;
@@ -947,7 +782,6 @@
                     ctx.splitKey.getBuffer().array(), 0);
             ctx.splitKey.getTuple().resetByTupleOffset(ctx.splitKey.getBuffer(), 0);
             ctx.splitKey.setLeftPage(leafFrontier.pageId);
-            int prevPageId = leafFrontier.pageId;
             leafFrontier.pageId = freePageManager.getFreePage(ctx.metaFrame);
 
             leafFrame.setNextLeaf(leafFrontier.pageId);
@@ -962,7 +796,6 @@
             leafFrontier.page.acquireWriteLatch();
             leafFrame.setPage(leafFrontier.page);
             leafFrame.initBuffer((byte) 0);
-            leafFrame.setPrevLeaf(prevPageId);
         }
 
         leafFrame.setPage(leafFrontier.page);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
index 5946594..8bf4db3 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
@@ -86,17 +86,20 @@
     }
 
     private void fetchNextLeafPage(int nextLeafPage) throws HyracksDataException {
-        ICachedPage nextLeaf = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, nextLeafPage), false);
-        if (exclusiveLatchNodes) {
-            nextLeaf.acquireWriteLatch();
-            page.releaseWriteLatch();
-        } else {
-            nextLeaf.acquireReadLatch();
-            page.releaseReadLatch();
-        }
-        bufferCache.unpin(page);
-        page = nextLeaf;
-        frame.setPage(page);
+        do {
+            ICachedPage nextLeaf = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, nextLeafPage), false);
+            if (exclusiveLatchNodes) {
+                nextLeaf.acquireWriteLatch();
+                page.releaseWriteLatch();
+            } else {
+                nextLeaf.acquireReadLatch();
+                page.releaseReadLatch();
+            }
+            bufferCache.unpin(page);
+            page = nextLeaf;
+            frame.setPage(page);
+            nextLeafPage = frame.getNextLeaf();
+        } while (frame.getTupleCount() == 0 && nextLeafPage > 0);
     }
 
     @Override
@@ -106,7 +109,6 @@
             if (nextLeafPage >= 0) {
                 fetchNextLeafPage(nextLeafPage);
                 tupleIndex = 0;
-
                 stopTupleIndex = getHighKeyIndex();
                 if (stopTupleIndex < 0) {
                     return false;
@@ -196,7 +198,7 @@
         } else {
             highKeyFtp = FindTupleNoExactMatchPolicy.LOWER_KEY;
         }
-
+        
         tupleIndex = getLowKeyIndex();
         stopTupleIndex = getHighKeyIndex();
         tupleIndexInc = 1;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
index 15b63ec..533b5b7 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
@@ -61,7 +61,7 @@
 
 	private boolean positionToNextLeaf(boolean skipCurrent)
 			throws HyracksDataException {
-		while ((frame.getLevel() != 0 || skipCurrent) && (currentPageId <= maxPageId)) {
+		while ((frame.getLevel() != 0 || skipCurrent || frame.getTupleCount() == 0) && (currentPageId <= maxPageId)) {
 			currentPageId++;
 
 			ICachedPage nextPage = bufferCache.pin(
@@ -77,10 +77,11 @@
 			tupleIndex = 0;
 			skipCurrent = false;
 		}
-		if (currentPageId <= maxPageId)
+		if (currentPageId <= maxPageId) {
 			return true;
-		else
+		} else {
 			return false;
+		}
 	}
 
 	@Override