[svn-r18263] Purpose: Fix bug in b-tree code

Description:
In certain cases, removal of an object in a v1  b-tree would cause the leftmost
key in the right neighbor to be overwritten.  While this did not pose a problem
for group b-trees, with chunked datasets it would overwrite the offset value
of the neighbor's leftmost child, causing corruption.  Reworked the code to
differentiate between b-trees whose children are fundamentally associated with
their left key and those who are associated with their right key.

Tested: jam, linew, amani (h5committest)

4 files changed, 299 insertions, 233 deletions

diff --git a/src/H5B.c b/src/H5B.c
index 3968986..558f5bd 100644
--- a/src/H5B.c
+++ b/src/H5B.c
@@ -850,72 +850,90 @@ H5B_insert_helper(H5F_t *f, hid_t dxpl_id, haddr_t addr, const H5B_class_t *type
 	} /* end if */
         else
 	    my_ins = H5B_INS_NOOP;
-    } else if(cmp < 0 && idx == 0 && bt->level > 0) {
-	/*
-	 * The value being inserted is less than any value in this tree.
-	 * Follow the minimum branch out of this node to a subtree.
-	 */
-	if((int)(my_ins = H5B_insert_helper(f, dxpl_id, bt->child[idx], type,
-                H5B_NKEY(bt,shared,idx), lt_key_changed, md_key,
-                udata, H5B_NKEY(bt, shared, idx + 1), rt_key_changed,
-                &child_addr/*out*/)) < 0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert minimum subtree")
-    } else if(cmp < 0 && idx == 0 && type->follow_min) {
-	/*
-	 * The value being inserted is less than any leaf node out of this
-	 * current node.  Follow the minimum branch to a leaf node and let the
-	 * subclass handle the problem.
-	 */
-	if((int)(my_ins = (type->insert)(f, dxpl_id, bt->child[idx], H5B_NKEY(bt, shared, idx),
-                 lt_key_changed, md_key, udata, H5B_NKEY(bt, shared, idx + 1),
-                 rt_key_changed, &child_addr/*out*/)) < 0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert minimum leaf node")
     } else if(cmp < 0 && idx == 0) {
-	/*
-	 * The value being inserted is less than any leaf node out of the
-	 * current node. Create a new minimum leaf node out of this B-tree
-	 * node. This node is not empty (handled above).
-	 */
-	my_ins = H5B_INS_LEFT;
-	HDmemcpy(md_key, H5B_NKEY(bt,shared,idx), type->sizeof_nkey);
-	if((type->new_node)(f, dxpl_id, H5B_INS_LEFT, H5B_NKEY(bt, shared, idx), udata,
-                 md_key, &child_addr/*out*/) < 0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert minimum leaf node")
-	*lt_key_changed = TRUE;
-    } else if(cmp > 0 && idx + 1 >= bt->nchildren && bt->level > 0) {
-	/*
-	 * The value being inserted is larger than any value in this tree.
-	 * Follow the maximum branch out of this node to a subtree.
-	 */
-	idx = bt->nchildren - 1;
-	if((int)(my_ins = H5B_insert_helper(f, dxpl_id, bt->child[idx], type,
-                H5B_NKEY(bt, shared, idx), lt_key_changed, md_key, udata,
-                H5B_NKEY(bt, shared, idx + 1), rt_key_changed, &child_addr/*out*/)) < 0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert maximum subtree")
-    } else if(cmp > 0 && idx + 1 >= bt->nchildren && type->follow_max) {
-	/*
-	 * The value being inserted is larger than any leaf node out of the
-	 * current node.  Follow the maximum branch to a leaf node and let the
-	 * subclass handle the problem.
-	 */
-	idx = bt->nchildren - 1;
-	if((int)(my_ins = (type->insert)(f, dxpl_id, bt->child[idx], H5B_NKEY(bt, shared, idx),
-                 lt_key_changed, md_key, udata, H5B_NKEY(bt, shared, idx + 1),
-                 rt_key_changed, &child_addr/*out*/)) < 0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert maximum leaf node")
+        if(bt->level > 0) {
+            /*
+             * The value being inserted is less than any value in this tree.
+             * Follow the minimum branch out of this node to a subtree.
+             */
+            if((int)(my_ins = H5B_insert_helper(f, dxpl_id, bt->child[idx], type,
+                    H5B_NKEY(bt,shared,idx), lt_key_changed, md_key,
+                    udata, H5B_NKEY(bt, shared, idx + 1), rt_key_changed,
+                    &child_addr/*out*/)) < 0)
+                HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert minimum subtree")
+        } else if(type->follow_min) {
+            /*
+             * The value being inserted is less than any leaf node out of this
+             * current node.  Follow the minimum branch to a leaf node and let
+             * the subclass handle the problem.
+             */
+            if((int)(my_ins = (type->insert)(f, dxpl_id, bt->child[idx], H5B_NKEY(bt, shared, idx),
+                    lt_key_changed, md_key, udata, H5B_NKEY(bt, shared, idx + 1),
+                    rt_key_changed, &child_addr/*out*/)) < 0)
+                HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert minimum leaf node")
+        } else {
+            /*
+             * The value being inserted is less than any leaf node out of the
+             * current node. Create a new minimum leaf node out of this B-tree
+             * node. This node is not empty (handled above).
+             */
+            my_ins = H5B_INS_LEFT;
+            HDmemcpy(md_key, H5B_NKEY(bt,shared,idx), type->sizeof_nkey);
+            if((type->new_node)(f, dxpl_id, H5B_INS_LEFT, H5B_NKEY(bt, shared, idx), udata,
+                    md_key, &child_addr/*out*/) < 0)
+                HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert minimum leaf node")
+            *lt_key_changed = TRUE;
+        } /* end else */
+
+#ifdef H5_STRICT_FORMAT_CHECKS
+        /* Since we are to the left of the leftmost key there must not be a left
+         * sibling */
+        if(H5F_addr_defined(bt->left))
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "internal error: likely corrupt key values")
+#endif /* H5_STRICT_FORMAT_CHECKS */
     } else if(cmp > 0 && idx + 1 >= bt->nchildren) {
-	/*
-	 * The value being inserted is larger than any leaf node out of the
-	 * current node.  Create a new maximum leaf node out of this B-tree
-	 * node.
-	 */
-	idx = bt->nchildren - 1;
-	my_ins = H5B_INS_RIGHT;
-	HDmemcpy(md_key, H5B_NKEY(bt, shared, idx + 1), type->sizeof_nkey);
-	if((type->new_node)(f, dxpl_id, H5B_INS_RIGHT, md_key, udata,
-                H5B_NKEY(bt, shared, idx + 1), &child_addr/*out*/) < 0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert maximum leaf node")
-	*rt_key_changed = TRUE;
+        if (bt->level > 0) {
+            /*
+            * The value being inserted is larger than any value in this tree.
+            * Follow the maximum branch out of this node to a subtree.
+            */
+            idx = bt->nchildren - 1;
+            if((int)(my_ins = H5B_insert_helper(f, dxpl_id, bt->child[idx], type,
+                    H5B_NKEY(bt, shared, idx), lt_key_changed, md_key, udata,
+                    H5B_NKEY(bt, shared, idx + 1), rt_key_changed, &child_addr/*out*/)) < 0)
+                HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert maximum subtree")
+        } else if(type->follow_max) {
+            /*
+             * The value being inserted is larger than any leaf node out of the
+             * current node.  Follow the maximum branch to a leaf node and let
+             * the subclass handle the problem.
+             */
+            idx = bt->nchildren - 1;
+            if((int)(my_ins = (type->insert)(f, dxpl_id, bt->child[idx], H5B_NKEY(bt, shared, idx),
+                    lt_key_changed, md_key, udata, H5B_NKEY(bt, shared, idx + 1),
+                    rt_key_changed, &child_addr/*out*/)) < 0)
+                HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert maximum leaf node")
+        } else {
+            /*
+             * The value being inserted is larger than any leaf node out of the
+             * current node.  Create a new maximum leaf node out of this B-tree
+             * node.
+             */
+            idx = bt->nchildren - 1;
+            my_ins = H5B_INS_RIGHT;
+            HDmemcpy(md_key, H5B_NKEY(bt, shared, idx + 1), type->sizeof_nkey);
+            if((type->new_node)(f, dxpl_id, H5B_INS_RIGHT, md_key, udata,
+                    H5B_NKEY(bt, shared, idx + 1), &child_addr/*out*/) < 0)
+                HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert maximum leaf node")
+            *rt_key_changed = TRUE;
+        } /* end else */
+
+#ifdef H5_STRICT_FORMAT_CHECKS
+        /* Since we are to the right of the rightmost key there must not be a
+         * right sibling */
+        if(H5F_addr_defined(bt->right))
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "internal error: likely corrupt key values")
+#endif /* H5_STRICT_FORMAT_CHECKS */
     } else if(cmp) {
 	/*
 	 * We couldn't figure out which branch to follow out of this node. THIS
@@ -951,17 +969,21 @@ H5B_insert_helper(H5F_t *f, hid_t dxpl_id, haddr_t addr, const H5B_class_t *type
      */
     if(*lt_key_changed) {
         bt_flags |= H5AC__DIRTIED_FLAG;
-	if(idx > 0)
-	    *lt_key_changed = FALSE;
-	else
-	    HDmemcpy(lt_key, H5B_NKEY(bt, shared, idx), type->sizeof_nkey);
+        if(idx > 0) {
+            HDassert(type->critical_key == H5B_LEFT);
+            *lt_key_changed = FALSE;
+        } /* end if */
+        else
+            HDmemcpy(lt_key, H5B_NKEY(bt, shared, idx), type->sizeof_nkey);
     } /* end if */
     if(*rt_key_changed) {
         bt_flags |= H5AC__DIRTIED_FLAG;
-	if(idx + 1 < bt->nchildren)
-	    *rt_key_changed = FALSE;
-	else
-	    HDmemcpy(rt_key, H5B_NKEY(bt, shared, idx + 1), type->sizeof_nkey);
+        if(idx + 1 < bt->nchildren) {
+            HDassert(type->critical_key == H5B_RIGHT);
+            *rt_key_changed = FALSE;
+        } /* end if */
+        else
+            HDmemcpy(rt_key, H5B_NKEY(bt, shared, idx + 1), type->sizeof_nkey);
     } /* end if */
     if(H5B_INS_CHANGE == my_ins) {
 	/*
@@ -1321,160 +1343,216 @@ H5B_remove_helper(H5F_t *f, hid_t dxpl_id, haddr_t addr, const H5B_class_t *type
      * our right key and indicate that it changed.
      */
     if(*lt_key_changed) {
+        HDassert(type->critical_key == H5B_LEFT);
         bt_flags |= H5AC__DIRTIED_FLAG;
 
-	if(idx > 0)
+        if(idx > 0)
             /* Don't propagate change out of this B-tree node */
-	    *lt_key_changed = FALSE;
-	else
-	    HDmemcpy(lt_key, H5B_NKEY(bt, shared, idx), type->sizeof_nkey);
+            *lt_key_changed = FALSE;
+        else
+            HDmemcpy(lt_key, H5B_NKEY(bt, shared, idx), type->sizeof_nkey);
     } /* end if */
     if(*rt_key_changed) {
+        HDassert(type->critical_key == H5B_RIGHT);
         bt_flags |= H5AC__DIRTIED_FLAG;
-	if(idx + 1 < bt->nchildren) {
+        if(idx + 1 < bt->nchildren)
             /* Don't propagate change out of this B-tree node */
-	    *rt_key_changed = FALSE;
-	} /* end if */
-        else {
-	    HDmemcpy(rt_key, H5B_NKEY(bt, shared, idx + 1), type->sizeof_nkey);
+            *rt_key_changed = FALSE;
+        else
+            HDmemcpy(rt_key, H5B_NKEY(bt, shared, idx + 1), type->sizeof_nkey);
+    } /* end if */
 
-            /* Since our right key was changed, we must check for a right
-             * sibling and change it's left-most key as well.
-             * (Handle the ret_value==H5B_INS_REMOVE case below)
+    /*
+     * If the subtree returned H5B_INS_REMOVE then we should remove the
+     * subtree entry from the current node.  There are four cases:
+     */
+    if(H5B_INS_REMOVE == ret_value) {
+        /* Clients should not change keys when a node is removed.  This function
+         * will handle it as appropriate, based on the value of bt->critical_key
+         */
+        HDassert(!(*lt_key_changed));
+        HDassert(!(*rt_key_changed));
+
+        if(1 == bt->nchildren) {
+            /*
+             * The subtree is the only child of this node.  Discard both
+             * keys and the subtree pointer. Free this node (unless it's the
+             * root node) and return H5B_INS_REMOVE.
              */
-            if(ret_value != H5B_INS_REMOVE && level > 0) {
+            /* Only delete the node if it is not the root node.  Note that this
+             * "level" is the opposite of bt->level */
+            if(level > 0) {
+                /* Fix siblings, making sure that the keys remain consistent
+                 * between siblings.  Overwrite the key that that is not
+                 * "critical" for any child in its node to maintain this
+                 * consistency (and avoid breaking key/child consistency) */
+                if(H5F_addr_defined(bt->left)) {
+                    if(NULL == (sibling = (H5B_t *)H5AC_protect(f, dxpl_id, H5AC_BT, bt->left, type, udata, H5AC_WRITE)))
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load node from tree")
+
+                    /* Copy right-most key from deleted node to right-most key
+                     * in its left neighbor, but only if it is not the critical
+                     * key for the right-most child of the left neighbor */
+                    if(type->critical_key == H5B_LEFT)
+                        HDmemcpy(H5B_NKEY(sibling, shared, sibling->nchildren),
+                                H5B_NKEY(bt, shared, 1), type->sizeof_nkey);
+
+                    sibling->right = bt->right;
+
+                    if(H5AC_unprotect(f, dxpl_id, H5AC_BT, bt->left, sibling, H5AC__DIRTIED_FLAG) < 0)
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
+                    sibling = NULL;   /* Make certain future references will be caught */
+                } /* end if */
                 if(H5F_addr_defined(bt->right)) {
                     if(NULL == (sibling = (H5B_t *)H5AC_protect(f, dxpl_id, H5AC_BT, bt->right, type, udata, H5AC_WRITE)))
                         HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to unlink node from tree")
 
-                    /* Make certain the native key for the right sibling is set up */
-                    HDmemcpy(H5B_NKEY(sibling, shared, 0), H5B_NKEY(bt, shared, idx + 1), type->sizeof_nkey);
+                    /* Copy left-most key from deleted node to left-most key in
+                     * its right neighbor, but only if it is not the critical
+                     * key for the left-most child of the right neighbor */
+                    if(type->critical_key == H5B_RIGHT)
+                        HDmemcpy(H5B_NKEY(sibling, shared, 0),
+                                H5B_NKEY(bt, shared, 0), type->sizeof_nkey);
+
+                    sibling->left = bt->left;
 
                     if(H5AC_unprotect(f, dxpl_id, H5AC_BT, bt->right, sibling, H5AC__DIRTIED_FLAG) < 0)
                         HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
                     sibling = NULL;   /* Make certain future references will be caught */
                 } /* end if */
-            } /* end if */
-	} /* end else */
-    } /* end if */
 
-    /*
-     * If the subtree returned H5B_INS_REMOVE then we should remove the
-     * subtree entry from the current node.  There are four cases:
-     */
-    if(H5B_INS_REMOVE == ret_value && 1 == bt->nchildren) {
-	/*
-	 * The subtree is the only child of this node.  Discard both
-	 * keys and the subtree pointer. Free this node (unless it's the
-	 * root node) and return H5B_INS_REMOVE.
-	 */
-        bt_flags |= H5AC__DIRTIED_FLAG;
-	bt->nchildren = 0;
-	if(level > 0) {
-	    if(H5F_addr_defined(bt->left)) {
-		if(NULL == (sibling = (H5B_t *)H5AC_protect(f, dxpl_id, H5AC_BT, bt->left, type, udata, H5AC_WRITE)))
-		    HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load node from tree")
-
-		sibling->right = bt->right;
-
-                if(H5AC_unprotect(f, dxpl_id, H5AC_BT, bt->left, sibling, H5AC__DIRTIED_FLAG) < 0)
-                    HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
-                sibling = NULL;   /* Make certain future references will be caught */
-	    } /* end if */
-	    if(H5F_addr_defined(bt->right)) {
-		if(NULL == (sibling = (H5B_t *)H5AC_protect(f, dxpl_id, H5AC_BT, bt->right, type, udata, H5AC_WRITE)))
-		    HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to unlink node from tree")
-
-                /* Copy left-most key from deleted node to left-most key in it's right neighbor */
-                HDmemcpy(H5B_NKEY(sibling, shared, 0), H5B_NKEY(bt, shared, 0), type->sizeof_nkey);
-
-		sibling->left = bt->left;
-
-                if(H5AC_unprotect(f, dxpl_id, H5AC_BT, bt->right, sibling, H5AC__DIRTIED_FLAG) < 0)
-                    HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
-                sibling = NULL;   /* Make certain future references will be caught */
-	    } /* end if */
-	    bt->left = HADDR_UNDEF;
-	    bt->right = HADDR_UNDEF;
-            H5_CHECK_OVERFLOW(shared->sizeof_rnode, size_t, hsize_t);
-	    if(H5AC_unprotect(f, dxpl_id, H5AC_BT, addr, bt, bt_flags | H5AC__DELETED_FLAG | H5AC__FREE_FILE_SPACE_FLAG) < 0) {
-		bt = NULL;
-                bt_flags = H5AC__NO_FLAGS_SET;
-		HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to free B-tree node")
-	    } /* end if */
-	    bt = NULL;
-            bt_flags = H5AC__NO_FLAGS_SET;
-	} /* end if */
-    } else if(H5B_INS_REMOVE == ret_value && 0 == idx) {
-	/*
-	 * The subtree is the left-most child of this node. We discard the
-	 * left-most key and the left-most child (the child has already been
-	 * freed) and shift everything down by one.  We copy the new left-most
-	 * key into lt_key and notify the caller that the left key has
-	 * changed.  Return H5B_INS_NOOP.
-	 */
-        bt_flags |= H5AC__DIRTIED_FLAG;
-	bt->nchildren -= 1;
-
-	HDmemmove(bt->native,
-		  bt->native + type->sizeof_nkey,
-		  (bt->nchildren + 1) * type->sizeof_nkey);
-	HDmemmove(bt->child,
-		  bt->child + 1,
-		  bt->nchildren * sizeof(haddr_t));
-	HDmemcpy(lt_key, H5B_NKEY(bt, shared, 0), type->sizeof_nkey);
-	*lt_key_changed = TRUE;
-	ret_value = H5B_INS_NOOP;
-    } else if(H5B_INS_REMOVE == ret_value && idx + 1 == bt->nchildren) {
-	/*
-	 * The subtree is the right-most child of this node.  We discard the
-	 * right-most key and the right-most child (the child has already been
-	 * freed).  We copy the new right-most key into rt_key and notify the
-	 * caller that the right key has changed.  Return H5B_INS_NOOP.
-	 */
-        bt_flags |= H5AC__DIRTIED_FLAG;
-	bt->nchildren -= 1;
-	HDmemcpy(rt_key, H5B_NKEY(bt, shared, bt->nchildren), type->sizeof_nkey);
-	*rt_key_changed = TRUE;
-
-        /* Since our right key was changed, we must check for a right
-         * sibling and change it's left-most key as well.
-         * (Handle the ret_value==H5B_INS_REMOVE case below)
-         */
-        if(level > 0) {
-            if(H5F_addr_defined(bt->right)) {
-                if(NULL == (sibling = (H5B_t *)H5AC_protect(f, dxpl_id, H5AC_BT, bt->right, type, udata, H5AC_WRITE)))
-                    HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to unlink node from tree")
+                /* Update bt struct */
+                bt->left = HADDR_UNDEF;
+                bt->right = HADDR_UNDEF;
+                bt->nchildren = 0;
 
-                HDmemcpy(H5B_NKEY(sibling, shared, 0), H5B_NKEY(bt, shared, bt->nchildren), type->sizeof_nkey);
-
-                if(H5AC_unprotect(f, dxpl_id, H5AC_BT, bt->right, sibling, H5AC__DIRTIED_FLAG) < 0)
-                    HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
-                sibling = NULL;   /* Make certain future references will be caught */
-            } /* end if */
-        } /* end if */
-
-	ret_value = H5B_INS_NOOP;
-    } else if(H5B_INS_REMOVE == ret_value) {
-	/*
-	 * There are subtrees out of this node to both the left and right of
-	 * the subtree being removed.  The key to the left of the subtree and
-	 * the subtree are removed from this node and all keys and nodes to
-	 * the right are shifted left by one place.  The subtree has already
-	 * been freed). Return H5B_INS_NOOP.
-	 */
-        bt_flags |= H5AC__DIRTIED_FLAG;
-	bt->nchildren -= 1;
-
-	HDmemmove(bt->native + idx * type->sizeof_nkey,
-		  bt->native + (idx + 1) * type->sizeof_nkey,
-		  (bt->nchildren + 1 - idx) * type->sizeof_nkey);
-	HDmemmove(bt->child + idx,
-		  bt->child + idx + 1,
-		  (bt->nchildren - idx) * sizeof(haddr_t));
-	ret_value = H5B_INS_NOOP;
-    } else
-	ret_value = H5B_INS_NOOP;
+                /* Delete the node from disk (via the metadata cache) */
+                bt_flags |= H5AC__DIRTIED_FLAG;
+                H5_CHECK_OVERFLOW(shared->sizeof_rnode, size_t, hsize_t);
+                if(H5AC_unprotect(f, dxpl_id, H5AC_BT, addr, bt, bt_flags | H5AC__DELETED_FLAG | H5AC__FREE_FILE_SPACE_FLAG) < 0) {
+                    bt = NULL;
+                    bt_flags = H5AC__NO_FLAGS_SET;
+                    HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to free B-tree node")
+                } /* end if */
+                bt = NULL;
+                bt_flags = H5AC__NO_FLAGS_SET;
+            } else {
+                /* We removed the last child in the root node, set the level
+                 * back to 0 (as well as nchildren) */
+                bt->nchildren = 0;
+                bt->level = 0;
+                bt_flags |= H5AC__DIRTIED_FLAG;
+            } /* end else */
+        } else if(0 == idx) {
+            /*
+             * The subtree is the left-most child of this node. We update the
+             * key and child arrays and lt_key as appropriate, depending on the
+             * status of bt->critical_key.  Return H5B_INS_NOOP.
+             */
+            if(type->critical_key == H5B_LEFT) {
+                /* Slide all keys down 1, update lt_key */
+                HDmemmove(H5B_NKEY(bt, shared, 0), H5B_NKEY(bt, shared, 1),
+                        bt->nchildren * type->sizeof_nkey);
+                HDmemcpy(lt_key, H5B_NKEY(bt, shared, 0), type->sizeof_nkey);
+                *lt_key_changed = TRUE;
+            } else
+                /* Slide all but the leftmost 2 keys down, leaving the leftmost
+                 * key intact (the right key of the leftmost child is
+                 * overwritten) */
+                HDmemmove(H5B_NKEY(bt, shared, 1), H5B_NKEY(bt, shared, 2),
+                        (bt->nchildren - 1) * type->sizeof_nkey);
+
+            HDmemmove(bt->child,
+                    bt->child + 1,
+                    (bt->nchildren - 1) * sizeof(haddr_t));
+
+            bt->nchildren -= 1;
+            bt_flags |= H5AC__DIRTIED_FLAG;
+            ret_value = H5B_INS_NOOP;
+        } else if(idx + 1 == bt->nchildren) {
+            /*
+             * The subtree is the right-most child of this node. We update the
+             * key and child arrays and rt_key as appropriate, depending on the
+             * status of bt->critical_key.  Return H5B_INS_NOOP.
+             */
+            if(type->critical_key == H5B_LEFT)
+                /* Slide the rightmost key down one, overwriting the left key of
+                 * the deleted (righmost) child */
+                HDmemmove(H5B_NKEY(bt, shared, bt->nchildren - 1),
+                        H5B_NKEY(bt, shared, bt->nchildren), type->sizeof_nkey);
+            else {
+                /* Just update rt_key */
+                HDmemcpy(rt_key, H5B_NKEY(bt, shared, bt->nchildren - 1),
+                        type->sizeof_nkey);
+                *rt_key_changed = TRUE;
+            } /* end else */
+
+            bt->nchildren -= 1;
+            bt_flags |= H5AC__DIRTIED_FLAG;
+            ret_value = H5B_INS_NOOP;
+        } else {
+            /*
+             * There are subtrees out of this node to both the left and right of
+             * the subtree being removed.  The subtree and its critical key are
+             * removed from this node and all keys and nodes to the right are
+             * shifted left by one place.  The subtree has already been freed.
+             * Return H5B_INS_NOOP.
+             */
+            if(type->critical_key == H5B_LEFT)
+                HDmemmove(H5B_NKEY(bt, shared, idx),
+                        H5B_NKEY(bt, shared, idx + 1),
+                        (bt->nchildren - idx) * type->sizeof_nkey);
+            else
+                HDmemmove(H5B_NKEY(bt, shared, idx + 1),
+                        H5B_NKEY(bt, shared, idx + 2),
+                        (bt->nchildren - 1 - idx) * type->sizeof_nkey);
+
+            HDmemmove(bt->child + idx,
+                    bt->child + idx + 1,
+                    (bt->nchildren - idx) * sizeof(haddr_t));
+
+            bt->nchildren -= 1;
+            bt_flags |= H5AC__DIRTIED_FLAG;
+            ret_value = H5B_INS_NOOP;
+        } /* end else */
+    } else /* H5B_INS_REMOVE != ret_value */
+        ret_value = H5B_INS_NOOP;
+
+    /* Patch keys in neighboring trees if necessary */
+    if(*lt_key_changed && H5F_addr_defined(bt->left)) {
+        HDassert(type->critical_key == H5B_LEFT);
+        HDassert(level > 0);
+
+        /* Update the rightmost key in the left sibling */
+        if(NULL == (sibling = (H5B_t *)H5AC_protect(f, dxpl_id, H5AC_BT,
+                bt->left, type, udata, H5AC_WRITE)))
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to unlink node from tree")
+
+        HDmemcpy(H5B_NKEY(sibling, shared, sibling->nchildren),
+                H5B_NKEY(bt, shared, 0), type->sizeof_nkey);
+
+        if(H5AC_unprotect(f, dxpl_id, H5AC_BT, bt->left, sibling,
+                H5AC__DIRTIED_FLAG) < 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
+        sibling = NULL;   /* Make certain future references will be caught */
+    } /* end if */
+    else if(*rt_key_changed && H5F_addr_defined(bt->right)) {
+        HDassert(type->critical_key == H5B_RIGHT);
+        HDassert(level > 0);
+
+        /* Update the lefttmost key in the right sibling */
+        if(NULL == (sibling = (H5B_t *)H5AC_protect(f, dxpl_id, H5AC_BT,
+                bt->right, type, udata, H5AC_WRITE)))
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to unlink node from tree")
+
+        HDmemcpy(H5B_NKEY(sibling, shared, 0),
+                H5B_NKEY(bt, shared, bt->nchildren), type->sizeof_nkey);
+
+        if(H5AC_unprotect(f, dxpl_id, H5AC_BT, bt->right, sibling,
+                H5AC__DIRTIED_FLAG) < 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
+        sibling = NULL;   /* Make certain future references will be caught */
+    } /* end else */
 
 done:
     if(bt && H5AC_unprotect(f, dxpl_id, H5AC_BT, addr, bt, bt_flags) < 0)
@@ -1509,8 +1587,6 @@ H5B_remove(H5F_t *f, hid_t dxpl_id, const H5B_class_t *type, haddr_t addr, void
     uint8_t	*rt_key = (uint8_t*)_rt_key;	/*right key*/
     hbool_t	lt_key_changed = FALSE;		/*left key changed?*/
     hbool_t	rt_key_changed = FALSE;		/*right key changed?*/
-    unsigned	bt_flags = H5AC__NO_FLAGS_SET;
-    H5B_t	*bt = NULL;			/*btree node */
     herr_t      ret_value=SUCCEED;       /* Return value */
 
     FUNC_ENTER_NOAPI(H5B_remove, FAIL)
@@ -1526,22 +1602,6 @@ H5B_remove(H5F_t *f, hid_t dxpl_id, const H5B_class_t *type, haddr_t addr, void
 			  udata, rt_key, &rt_key_changed) == H5B_INS_ERROR)
 	HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to remove entry from B-tree")
 
-    /*
-     * If the B-tree is now empty then make sure we mark the root node as
-     * being at level zero
-     */
-    if(NULL == (bt = (H5B_t *)H5AC_protect(f, dxpl_id, H5AC_BT, addr, type, udata, H5AC_WRITE)))
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree root node")
-
-    if(0 == bt->nchildren && 0 != bt->level) {
-	bt->level = 0;
-        bt_flags |= H5AC__DIRTIED_FLAG;
-    } /* end if */
-
-    if(H5AC_unprotect(f, dxpl_id, H5AC_BT, addr, bt, bt_flags) < 0)
-        HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release node")
-    bt = NULL;    /* Make certain future references will be caught */
-
 #ifdef H5B_DEBUG
     H5B_assert(f, dxpl_id, addr, type, udata);
 #endif
diff --git a/src/H5Bprivate.h b/src/H5Bprivate.h
index 716b608..b0ffa07 100644
--- a/src/H5Bprivate.h
+++ b/src/H5Bprivate.h
@@ -78,6 +78,13 @@ typedef enum H5B_ins_t {
     H5B_INS_REMOVE	 = 5	/*remove current node			     */
 } H5B_ins_t;
 
+/* Enum for specifying the direction of the critical key in relation to the
+ * child */
+typedef enum H5B_dir_t {
+    H5B_LEFT            = 0,    /* Critical key is to the left */
+    H5B_RIGHT           = 1     /* Critical key is to the right */
+} H5B_dir_t;
+
 /* Define the operator callback function pointer for H5B_iterate() */
 typedef int (*H5B_operator_t)(H5F_t *f, hid_t dxpl_id, const void *_lt_key, haddr_t addr,
                                         const void *_rt_key, void *_udata);
@@ -123,6 +130,9 @@ typedef struct H5B_class_t {
     hbool_t	follow_min;
     hbool_t	follow_max;
 
+    /* The direction of the key that is intrinsically associated with each node */
+    H5B_dir_t   critical_key;
+
     /* remove existing data */
     H5B_ins_t	(*remove)(H5F_t*, hid_t, haddr_t, void*, hbool_t*, void*, void*,
 			  hbool_t*);
diff --git a/src/H5Dbtree.c b/src/H5Dbtree.c
index c12865f..89d2596 100644
--- a/src/H5Dbtree.c
+++ b/src/H5Dbtree.c
@@ -189,9 +189,10 @@ H5B_class_t H5B_BTREE[1] = {{
     H5D_btree_cmp3,		/*cmp3			*/
     H5D_btree_found,		/*found			*/
     H5D_btree_insert,		/*insert		*/
+    H5B_LEFT,                   /*critical key          */
     FALSE,			/*follow min branch?	*/
     FALSE,			/*follow max branch?	*/
-    H5D_btree_remove,          /*remove		*/
+    H5D_btree_remove,           /*remove		*/
     H5D_btree_decode_key,	/*decode		*/
     H5D_btree_encode_key,	/*encode		*/
     H5D_btree_debug_key,	/*debug			*/
diff --git a/src/H5Gnode.c b/src/H5Gnode.c
index 18125df..4bd8a29 100644
--- a/src/H5Gnode.c
+++ b/src/H5Gnode.c
@@ -95,6 +95,7 @@ H5B_class_t H5B_SNODE[1] = {{
     H5G_node_cmp3,		/*cmp3			*/
     H5G_node_found,		/*found			*/
     H5G_node_insert,		/*insert		*/
+    H5B_RIGHT,                  /*critical key          */
     TRUE,			/*follow min branch?	*/
     TRUE,			/*follow max branch?	*/
     H5G_node_remove,		/*remove		*/
@@ -860,14 +861,11 @@ H5G_node_remove(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_lt_key/*in,out*/,
         /* Remove the entry from the symbol table node */
         if(1 == sn->nsyms) {
             /*
-             * We are about to remove the only symbol in this node. Copy the left
-             * key to the right key and mark the right key as dirty.  Free this
+             * We are about to remove the only symbol in this node.  Free this
              * node and indicate that the pointer to this node in the B-tree
              * should be removed also.
              */
             HDassert(0 == idx);
-            *rt_key = *lt_key;
-            *rt_key_changed = TRUE;
             sn->nsyms = 0;
             sn_flags |= H5AC__DIRTIED_FLAG | H5AC__DELETED_FLAG | H5AC__FREE_FILE_SPACE_FLAG;
             ret_value = H5B_INS_REMOVE;
@@ -925,13 +923,10 @@ H5G_node_remove(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_lt_key/*in,out*/,
         } /* end for */
 
         /*
-         * We are about to remove all the symbols in this node. Copy the left
-         * key to the right key and mark the right key as dirty.  Free this
+         * We are about to remove all the symbols in this node.  Free this
          * node and indicate that the pointer to this node in the B-tree
          * should be removed also.
          */
-        *rt_key = *lt_key;
-        *rt_key_changed = TRUE;
         sn->nsyms = 0;
         sn_flags |= H5AC__DIRTIED_FLAG | H5AC__DELETED_FLAG | H5AC__FREE_FILE_SPACE_FLAG;
         ret_value = H5B_INS_REMOVE;