diff --git a/hyracks/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java b/hyracks/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
index 689843b..42e876c 100644
--- a/hyracks/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
+++ b/hyracks/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
@@ -879,8 +879,12 @@
 
         @Override
         public void delete(ITupleReference tuple) throws HyracksDataException, TreeIndexException {
-            ctx.setOperation(IndexOperation.DELETE);
-            btree.delete(tuple, ctx);
+            try {
+                ctx.setOperation(IndexOperation.DELETE);
+                btree.delete(tuple, ctx);
+            } catch (BTreeNonExistentKeyException e) {
+                //allow deletion of non-existing keys
+            }
         }
 
         @Override