[svn-r10135] Purpose:

    Bug fix & new feature

Description:
    Fix problem with inserting existing keys into B-tree corrupting record
counts along the path to the failed insertion.

    Add more support for removing records, it's now handling removing records
from leaves of level-1 B-trees.

Platforms tested:
    FreeBSD 4.11 (sleipnir) w/parallel
    Solaris 2.9 (shanti)

1 files changed, 676 insertions, 248 deletions

diff --git a/src/H5B2.c b/src/H5B2.c
index 6dbb52c..04109ad 100644
--- a/src/H5B2.c
+++ b/src/H5B2.c
@@ -71,6 +71,11 @@ static herr_t H5B2_split2(H5F_t *f, hid_t dxpl_id, unsigned depth,
     H5B2_internal_t *internal, unsigned idx);
 static herr_t H5B2_redistribute3(H5F_t *f, hid_t dxpl_id, unsigned depth,
     H5B2_internal_t *internal, unsigned idx);
+static herr_t H5B2_insert_internal(H5F_t *f, hid_t dxpl_id,
+    H5RC_t *bt2_shared, unsigned depth, H5AC_info_t *parent_cache_info,
+    H5B2_node_ptr_t *curr_node_ptr, void *udata);
+static herr_t H5B2_insert_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
+    H5B2_node_ptr_t *curr_node_ptr, void *udata);
 static herr_t H5B2_iterate_node(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
     unsigned depth, const H5B2_node_ptr_t *curr_node, H5B2_operator_t op,
     void *op_data);
@@ -1798,301 +1803,298 @@ done:
 
 
 /*-------------------------------------------------------------------------
- * Function:	H5B2_insert
+ * Function:	H5B2_insert_leaf
  *
- * Purpose:	Adds a new record to the B-tree.
+ * Purpose:	Adds a new record to a B-tree leaf node.
  *
  * Return:	Non-negative on success/Negative on failure
  *
  * Programmer:	Quincey Koziol
  *		koziol@ncsa.uiuc.edu
- *		Feb  2 2005
+ *		Mar  3 2005
  *
  *-------------------------------------------------------------------------
  */
-herr_t
-H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
-           void *udata)
+static herr_t
+H5B2_insert_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
+    H5B2_node_ptr_t *curr_node_ptr, void *udata)
 {
-    H5B2_t	*bt2=NULL;              /* Pointer to the B-tree header */
-    H5RC_t      *bt2_shared=NULL;       /* Pointer to ref-counter for shared B-tree info */
-    hbool_t     incr_rc=FALSE;          /* Flag to indicate that we've incremented the B-tree's shared info reference count */
+    H5B2_leaf_t *leaf;                  /* Pointer to leaf node */
     H5B2_shared_t *shared;              /* Pointer to B-tree's shared information */
-    H5B2_node_ptr_t leaf_ptr;           /* Node pointer info for leaf node */
-    H5B2_leaf_t *leaf=NULL;             /* Pointer to leaf node */
-    unsigned    leaf_nrec;              /* Number of records in leaf to modify */
     int         cmp;                    /* Comparison value of records */
     unsigned    idx;                    /* Location of record which matches key */
     herr_t	ret_value = SUCCEED;
 
-    FUNC_ENTER_NOAPI(H5B2_insert, FAIL)
+    FUNC_ENTER_NOAPI(H5B2_insert_leaf, FAIL)
 
     /* Check arguments. */
     HDassert(f);
-    HDassert(type);
-    HDassert(H5F_addr_defined(addr));
+    HDassert(bt2_shared);
+    HDassert(curr_node_ptr);
+    HDassert(H5F_addr_defined(curr_node_ptr->addr));
 
-    /* Look up the b-tree header */
-    if (NULL == (bt2 = H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, addr, type, NULL, H5AC_WRITE)))
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree header")
+    /* Lock current B-tree node */
+    if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr->addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE)))
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree leaf node")
 
     /* Get the pointer to the shared B-tree info */
-    shared=H5RC_GET_OBJ(bt2->shared);
+    shared=H5RC_GET_OBJ(bt2_shared);
     HDassert(shared);
 
-    /* Safely grab pointer to reference counted shared B-tree info, so we can release the B-tree header if necessary */
-    bt2_shared=bt2->shared;
-    H5RC_INC(bt2_shared);
-    incr_rc=TRUE;
-
-    /* Check if the root node is allocated yet */
-    if(!H5F_addr_defined(bt2->root.addr)) {
-        /* Create root node as leaf node in B-tree */
-        if(H5B2_create_leaf(f, dxpl_id, bt2_shared, &(bt2->root))<0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create root node")
-
-        /* Mark B-tree header as dirty, since we updated the address of the root node */
-        bt2->cache_info.is_dirty = TRUE;
-    } /* end if */
-    /* Check if we need to split the root node */
-    else if((bt2->depth==0 && bt2->root.node_nrec==shared->split_leaf_nrec) ||
-            (bt2->depth>0 && bt2->root.node_nrec==shared->split_int_nrec)) {
-        /* Split root node */
-        if(H5B2_split_root(f, dxpl_id, bt2, bt2_shared)<0)
-            HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split root node")
-    } /* end if */
-        
-    /* Check for non-trivial B-tree */
-    if(bt2->depth>0) {
-        H5B2_internal_t *internal;          /* Pointer to internal node in B-tree */
-        H5AC_info_t *parent_cache_info;     /* Parent node's cache info */
-        haddr_t     parent_addr;            /* Address of parent which contain's node pointer to current node */
-        void        *parent_ptr;            /* Pointer to parent structure in memory */
-        H5AC_info_t *curr_cache_info=NULL;  /* Current node's cache info */
-        H5B2_node_ptr_t *curr_node_ptr;     /* Pointer to node pointer info for current node (in parent node) */
-        haddr_t curr_addr=HADDR_UNDEF;      /* Address of current node */
-        void        *curr_ptr=NULL;         /* Pointer to current structure in memory */
-        H5B2_node_ptr_t *child_node_ptr=NULL;   /* Pointer to node pointer info for child node */
-        unsigned    depth;                  /* Depth of current node */
-
-        /* Track the depth of current node (leaves are depth 0) */
-        depth=bt2->depth;
-
-        /* Set initial "parent" information to the B-tree header */
-        parent_cache_info=&(bt2->cache_info);
-        parent_addr=addr;
-        parent_ptr=bt2;
+    /* Must have a leaf node with enough space to insert a record now */
+    HDassert(curr_node_ptr->node_nrec < shared->split_leaf_nrec);
 
-        /* Set initial node pointer for "current" node */
-        curr_node_ptr=&(bt2->root);
+    /* Sanity check number of records */
+    HDassert(curr_node_ptr->all_nrec == curr_node_ptr->node_nrec);
+    HDassert(leaf->nrec == curr_node_ptr->node_nrec);
 
-        /* Find correct leaf to insert node into */
-        while(depth>0) {
-            unsigned retries;
+    /* Check for inserting into empty leaf */
+    if(leaf->nrec==0)
+        idx=0;
+    else {
+        /* Find correct location to insert this record */
+        if((cmp = H5B2_locate_record(shared->type,leaf->nrec,shared->nat_off,leaf->leaf_native,udata,&idx)) == 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
+        if(cmp > 0)
+            idx++;
 
-            /* Lock B-tree current node */
-            if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE)))
-                HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
+        /* Make room for new record */
+        if((unsigned)idx<leaf->nrec)
+            HDmemmove(H5B2_LEAF_NREC(leaf,shared,idx+1),H5B2_LEAF_NREC(leaf,shared,idx),shared->type->nrec_size*(leaf->nrec-idx));
+    } /* end else */
 
-#ifdef H5B2_DEBUG
-            H5B2_assert_internal((hsize_t)0,shared,internal);
-#endif /* H5B2_DEBUG */
+    /* Make callback to store record in native form */
+    if((shared->type->store)(H5B2_LEAF_NREC(leaf,shared,idx),udata)<0)
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into leaf node")
 
-            /* Set information for current (root) node */
-            curr_cache_info=&(internal->cache_info);
-            curr_addr=curr_node_ptr->addr;
-            curr_ptr=internal;
+    /* Update record count for node pointer to current node */
+    curr_node_ptr->all_nrec++;
+    curr_node_ptr->node_nrec++;
 
-            /* Locate node pointer for child */
-            if((cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx)) == 0)
-                HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
-            if(cmp>0)
-                idx++;
+    /* Update record count for current node */
+    leaf->nrec++;
 
-            /* Get node pointer for child */
-            child_node_ptr=&(internal->node_ptrs[idx]);
+    /* Mark node as dirty */
+    leaf->cache_info.is_dirty = TRUE;
 
-            /* Set the number of redistribution retries */
-            /* This takes care of the case where a B-tree node needs to be
-             * redistributed, but redistributing the node causes the index
-             * for insertion to move to another node, which also needs to be
-             * redistributed.  Now, we loop trying to redistribute and then
-             * eventually force a split */
-            retries = 2;
+done:
+    /* Release the B-tree leaf node */
+    if (leaf && H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0)
+        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release leaf B-tree node")
 
-            /* Preemptively split/redistribute a node we will enter */
-            while((depth==1 && child_node_ptr->node_nrec==shared->split_leaf_nrec) ||
-                    (depth>1 && child_node_ptr->node_nrec==shared->split_int_nrec)) {
-                /* Attempt to redistribute records among children */
-                if(idx==0) {    /* Left-most child */
-                    if(retries>0 && ((depth==1 && internal->node_ptrs[idx+1].node_nrec<shared->split_leaf_nrec) ||
-                            (depth>1 && internal->node_ptrs[idx+1].node_nrec<shared->split_int_nrec))) {
-                        if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)idx)<0)
-                            HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
-                    } /* end if */
-                    else {
-                        if(H5B2_split2(f,dxpl_id,depth,curr_node_ptr,parent_cache_info,internal,(unsigned)idx)<0)
-                            HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
-                    } /* end else */
-                } /* end if */
-                else if((unsigned)idx==internal->nrec) { /* Right-most child */
-                    if(retries>0 && ((depth==1 && internal->node_ptrs[idx-1].node_nrec<shared->split_leaf_nrec) ||
-                            (depth>1 && internal->node_ptrs[idx-1].node_nrec<shared->split_int_nrec))) {
-                        if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)(idx-1))<0)
-                            HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
-                    } /* end if */
-                    else {
-                        if(H5B2_split2(f,dxpl_id,depth,curr_node_ptr,parent_cache_info,internal,(unsigned)(idx-1))<0)
-                            HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
-                    } /* end else */
-                } /* end if */
-                else { /* Middle child */
-                    if(retries>0 && ((depth==1 &&
-                                ((internal->node_ptrs[idx+1].node_nrec<shared->split_leaf_nrec) ||
-                                (internal->node_ptrs[idx-1].node_nrec<shared->split_leaf_nrec))) ||
-                            (depth>1 && 
-                                ((internal->node_ptrs[idx+1].node_nrec<shared->split_int_nrec) ||
-                                (internal->node_ptrs[idx-1].node_nrec<shared->split_int_nrec))))) {
-                        if(H5B2_redistribute3(f,dxpl_id,depth,internal,(unsigned)idx)<0)
-                            HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
-                    } /* end if */
-                    else {
-                        if(H5B2_split3(f,dxpl_id,depth,curr_node_ptr,parent_cache_info,internal,(unsigned)idx)<0)
-                            HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
-                    } /* end else */
-                } /* end else */
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_insert_leaf() */
 
-                /* Locate node pointer for child (after split redistribute) */
-/* Actually, this can be easily updated (for 2-node redistrib.) and shouldn't require re-searching */
-                if((cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx)) == 0)
-                    HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
-                if(cmp > 0)
-                    idx++;
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_insert_internal
+ *
+ * Purpose:	Adds a new record to a B-tree node.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Mar  2 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B2_insert_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
+    unsigned depth, H5AC_info_t *parent_cache_info,
+    H5B2_node_ptr_t *curr_node_ptr, void *udata)
+{
+    H5B2_internal_t *internal;          /* Pointer to internal node */
+    H5B2_shared_t *shared;              /* Pointer to B-tree's shared information */
+    unsigned    idx;                    /* Location of record which matches key */
+    herr_t	ret_value = SUCCEED;
 
-                /* Update child_node_ptr (to reflect change in location from split/redistribution) */
-                child_node_ptr=&(internal->node_ptrs[idx]);
+    FUNC_ENTER_NOAPI(H5B2_insert_internal, FAIL)
 
-                /* Decrement the number of redistribution retries left */
-                retries--;
-            } /* end if */
+    /* Check arguments. */
+    HDassert(f);
+    HDassert(bt2_shared);
+    HDassert(depth>0);
+    HDassert(parent_cache_info);
+    HDassert(curr_node_ptr);
+    HDassert(H5F_addr_defined(curr_node_ptr->addr));
 
-            /* Update record count (in parent) */
-            curr_node_ptr->all_nrec++;
+    /* Lock current B-tree node */
+    if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE)))
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
 
-            /* Mark parent node as dirty */
-            parent_cache_info->is_dirty = TRUE;
+    /* Get the pointer to the shared B-tree info */
+    shared=H5RC_GET_OBJ(bt2_shared);
+    HDassert(shared);
 
-#ifdef H5B2_DEBUG
-            if(parent_cache_info->type==H5AC_BT2_INT)
-                H5B2_assert_internal((hsize_t)0,shared,parent_ptr);
-#endif /* H5B2_DEBUG */
+/* Split or redistribute child node pointers, if necessary */
+    {
+        int         cmp;                /* Comparison value of records */
+        unsigned retries;               /* Number of times to attempt redistribution */
 
-            /* Unlock parent node (possibly the B-tree header) */
-            if (H5AC_unprotect(f, dxpl_id, parent_cache_info->type, parent_addr, parent_ptr, H5AC__NO_FLAGS_SET) < 0)
-                HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree info")
+        /* Locate node pointer for child */
+        if((cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx)) == 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
+        if(cmp>0)
+            idx++;
 
-            /* Transition "current" info into "parent" info */
-            parent_cache_info = curr_cache_info;
-            parent_addr = curr_addr;
-            parent_ptr = curr_ptr;
+        /* Set the number of redistribution retries */
+        /* This takes care of the case where a B-tree node needs to be
+         * redistributed, but redistributing the node causes the index
+         * for insertion to move to another node, which also needs to be
+         * redistributed.  Now, we loop trying to redistribute and then
+         * eventually force a split */
+        retries = 2;
+
+        /* Preemptively split/redistribute a node we will enter */
+        while((depth==1 && internal->node_ptrs[idx].node_nrec==shared->split_leaf_nrec) ||
+                (depth>1 && internal->node_ptrs[idx].node_nrec==shared->split_int_nrec)) {
+            /* Attempt to redistribute records among children */
+            if(idx==0) {    /* Left-most child */
+                if(retries>0 && ((depth==1 && internal->node_ptrs[idx+1].node_nrec<shared->split_leaf_nrec) ||
+                        (depth>1 && internal->node_ptrs[idx+1].node_nrec<shared->split_int_nrec))) {
+                    if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)idx)<0)
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
+                } /* end if */
+                else {
+                    if(H5B2_split2(f,dxpl_id,depth,curr_node_ptr,parent_cache_info,internal,(unsigned)idx)<0)
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
+                } /* end else */
+            } /* end if */
+            else if((unsigned)idx==internal->nrec) { /* Right-most child */
+                if(retries>0 && ((depth==1 && internal->node_ptrs[idx-1].node_nrec<shared->split_leaf_nrec) ||
+                        (depth>1 && internal->node_ptrs[idx-1].node_nrec<shared->split_int_nrec))) {
+                    if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)(idx-1))<0)
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
+                } /* end if */
+                else {
+                    if(H5B2_split2(f,dxpl_id,depth,curr_node_ptr,parent_cache_info,internal,(unsigned)(idx-1))<0)
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
+                } /* end else */
+            } /* end if */
+            else { /* Middle child */
+                if(retries>0 && ((depth==1 &&
+                            ((internal->node_ptrs[idx+1].node_nrec<shared->split_leaf_nrec) ||
+                            (internal->node_ptrs[idx-1].node_nrec<shared->split_leaf_nrec))) ||
+                        (depth>1 && 
+                            ((internal->node_ptrs[idx+1].node_nrec<shared->split_int_nrec) ||
+                            (internal->node_ptrs[idx-1].node_nrec<shared->split_int_nrec))))) {
+                    if(H5B2_redistribute3(f,dxpl_id,depth,internal,(unsigned)idx)<0)
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
+                } /* end if */
+                else {
+                    if(H5B2_split3(f,dxpl_id,depth,curr_node_ptr,parent_cache_info,internal,(unsigned)idx)<0)
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
+                } /* end else */
+            } /* end else */
 
-            /* Transition "child" node pointer to "current" node pointer */
-            curr_node_ptr = child_node_ptr;
+            /* Locate node pointer for child (after split/redistribute) */
+/* Actually, this can be easily updated (for 2-node redistrib.) and shouldn't require re-searching */
+            if((cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx)) == 0)
+                HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
+            if(cmp > 0)
+                idx++;
 
-            /* Decrement depth of current node */
-            depth--;
+            /* Decrement the number of redistribution retries left */
+            retries--;
         } /* end while */
+    } /* end block */
 
-        /* Update record count for leaf (in current node) */
-        HDassert(curr_node_ptr);
-        curr_node_ptr->all_nrec++;
-        curr_node_ptr->node_nrec++;
-
-        /* Mark parent node as dirty */
-        curr_cache_info->is_dirty = TRUE;
-
-        /* Copy node pointer info for leaf */
-        leaf_ptr = *curr_node_ptr;
-
-#ifdef H5B2_DEBUG
-        if(curr_cache_info->type==H5AC_BT2_INT)
-            H5B2_assert_internal((hsize_t)0,shared,curr_ptr);
-#endif /* H5B2_DEBUG */
-
-        /* Release current node */
-        if (H5AC_unprotect(f, dxpl_id, curr_cache_info->type, curr_addr, curr_ptr, H5AC__NO_FLAGS_SET) < 0)
-            HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
+    /* Attempt to insert node */
+    if(depth>1) {
+        if(H5B2_insert_internal(f,dxpl_id,bt2_shared,depth-1,&internal->cache_info,&internal->node_ptrs[idx],udata)<0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree internal node")
     } /* end if */
     else {
-        /* Update record count for root node */
-        bt2->root.all_nrec++;
-        bt2->root.node_nrec++;
+        if(H5B2_insert_leaf(f,dxpl_id,bt2_shared,&internal->node_ptrs[idx],udata)<0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree leaf node")
+    } /* end else */
 
-        /* Mark parent node as dirty */
-        bt2->cache_info.is_dirty = TRUE;
+    /* Update record count for node pointer to current node */
+    curr_node_ptr->all_nrec++;
 
-        /* Copy node pointer info for leaf */
-        leaf_ptr = bt2->root;
+    /* Mark node as dirty */
+    internal->cache_info.is_dirty = TRUE;
 
-        /* Release parent node */
-        if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0)
-            HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree header info")
-        bt2=NULL;
-    } /* end else */
+done:
+    /* Release the B-tree internal node */
+    if (internal && H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, internal, H5AC__NO_FLAGS_SET) < 0)
+        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release internal B-tree node")
 
-    /* Get the actual # of records in leaf */
-    leaf_nrec = leaf_ptr.node_nrec - 1;
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_insert_internal() */
 
-    /* Must have a leaf node with enough space to insert a record now */
-    HDassert(H5F_addr_defined(leaf_ptr.addr));
-    HDassert(leaf_nrec < shared->split_leaf_nrec);
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_insert
+ *
+ * Purpose:	Adds a new record to the B-tree.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb  2 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
+           void *udata)
+{
+    H5B2_t	*bt2=NULL;              /* Pointer to the B-tree header */
+    H5B2_shared_t *shared;              /* Pointer to B-tree's shared information */
+    herr_t	ret_value = SUCCEED;
 
-    /* Look up the B-tree leaf node */
-    if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, &leaf_nrec, bt2_shared, H5AC_WRITE)))
-        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree leaf node")
+    FUNC_ENTER_NOAPI(H5B2_insert, FAIL)
 
-    /* Sanity check number of records */
-    HDassert(leaf_ptr.all_nrec == leaf_ptr.node_nrec);
-    HDassert(leaf->nrec == leaf_nrec);
+    /* Check arguments. */
+    HDassert(f);
+    HDassert(type);
+    HDassert(H5F_addr_defined(addr));
 
-    /* Check for inserting into empty leaf */
-    if(leaf->nrec==0)
-        idx=0;
-    else {
-        /* Find correct location to insert this record */
-        if((cmp = H5B2_locate_record(shared->type,leaf->nrec,shared->nat_off,leaf->leaf_native,udata,&idx)) == 0)
-            HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
-        if(cmp > 0)
-            idx++;
+    /* Look up the b-tree header */
+    if (NULL == (bt2 = H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, addr, type, NULL, H5AC_WRITE)))
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree header")
 
-        /* Make room for new record */
-        if((unsigned)idx<leaf->nrec)
-            HDmemmove(H5B2_LEAF_NREC(leaf,shared,idx+1),H5B2_LEAF_NREC(leaf,shared,idx),shared->type->nrec_size*(leaf->nrec-idx));
-    } /* end else */
+    /* Get the pointer to the shared B-tree info */
+    shared=H5RC_GET_OBJ(bt2->shared);
+    HDassert(shared);
 
-    /* Make callback to store record in native form */
-    if((shared->type->store)(H5B2_LEAF_NREC(leaf,shared,idx),udata)<0)
-        HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into leaf node")
+    /* Check if the root node is allocated yet */
+    if(!H5F_addr_defined(bt2->root.addr)) {
+        /* Create root node as leaf node in B-tree */
+        if(H5B2_create_leaf(f, dxpl_id, bt2->shared, &(bt2->root))<0)
+	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create root node")
 
-    /* Update number of records in node */
-    leaf->nrec++;
+        /* Mark B-tree header as dirty, since we updated the address of the root node */
+        bt2->cache_info.is_dirty = TRUE;
+    } /* end if */
+    /* Check if we need to split the root node (equiv. to a 1->2 leaf node split) */
+    else if((bt2->depth==0 && bt2->root.node_nrec==shared->split_leaf_nrec) ||
+            (bt2->depth>0 && bt2->root.node_nrec==shared->split_int_nrec)) {
+        /* Split root node */
+        if(H5B2_split_root(f, dxpl_id, bt2, bt2->shared)<0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split root node")
+    } /* end if */
+        
+    /* Attempt to insert record into B-tree */
+    if(bt2->depth>0) {
+        if(H5B2_insert_internal(f,dxpl_id,bt2->shared,bt2->depth,&(bt2->cache_info),&bt2->root,udata)<0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree internal node")
+    } /* end if */
+    else {
+        if(H5B2_insert_leaf(f,dxpl_id,bt2->shared,&bt2->root,udata)<0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree leaf node")
+    } /* end else */
 
-    /* Mark leaf node as dirty also */
-    leaf->cache_info.is_dirty = TRUE;
+    /* Mark parent node as dirty */
+    bt2->cache_info.is_dirty = TRUE;
 
 done:
-    /* Release the B-tree leaf node */
-    if (leaf) {
-#ifdef H5B2_DEBUG
-H5B2_assert_leaf(shared,leaf);
-#endif /* H5B2_DEBUG */
-        if(H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0)
-            HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree leaf node")
-    } /* end if */
-
-    /* Check if we need to decrement the reference count for the B-tree's shared info */
-    if(incr_rc)
-        H5RC_DEC(bt2_shared);
+    /* Release the B-tree header info */
+    if (bt2 && H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0)
+        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree header info")
 
     FUNC_LEAVE_NOAPI(ret_value)
 } /* H5B2_insert() */
@@ -2266,7 +2268,7 @@ done:
  *
  *-------------------------------------------------------------------------
  */
-herr_t
+static herr_t
 H5B2_iterate_node(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, unsigned depth,
     const H5B2_node_ptr_t *curr_node, H5B2_operator_t op, void *op_data)
 {
@@ -2761,6 +2763,7 @@ done:
     FUNC_LEAVE_NOAPI(ret_value)
 } /* H5B2_index() */
 
+#ifdef OLD_WAY
 
 /*-------------------------------------------------------------------------
  * Function:	H5B2_remove
@@ -2829,24 +2832,150 @@ H5B2_remove(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
         HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree")
     } /* end if */
 
+    /* Set initial "parent" information to the B-tree header */
+    parent_cache_info=&(bt2->cache_info);
+    parent_addr=addr;
+    parent_ptr=bt2;
+
+    /* Set initial node pointer for "current" node */
+    curr_node_ptr=&(bt2->root);
+
     /* Check for non-trivial B-tree */
-    if(bt2->depth>0) {
-HDfprintf(stderr,"%s: Deleting record in non-trival B-tree!\n",FUNC);
+    if(depth>0) {
+        H5B2_internal_t *internal;          /* Pointer to internal node in B-tree */
+        H5AC_info_t *curr_cache_info=NULL;  /* Current node's cache info */
+        haddr_t curr_addr=HADDR_UNDEF;      /* Address of current node */
+        void        *curr_ptr=NULL;         /* Pointer to current structure in memory */
+        H5B2_node_ptr_t *child_node_ptr=NULL;   /* Pointer to node pointer info for child node */
+
+        /* Find correct leaf to remove node from */
+        while(depth>0) {
+            unsigned retries;               /* Number of times to attempt redistribution */
+
+            /* Lock B-tree current node */
+            if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE)))
+                HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
+
+#ifdef H5B2_DEBUG
+            H5B2_assert_internal((hsize_t)0,shared,internal);
+#endif /* H5B2_DEBUG */
+
+            /* Set information for current (root) node */
+            curr_cache_info=&(internal->cache_info);
+            curr_addr=curr_node_ptr->addr;
+            curr_ptr=internal;
+
+            /* Locate node pointer for child */
+            cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx);
+            if(cmp>0)
+                idx++;
+
+            /* Handle deleting a record from an internal node */
+            if(cmp==0) {
+HDfprintf(stderr,"%s: Deleting record in internal node of non-trival B-tree!\n",FUNC);
 HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree")
-    } /* end if */
-    else {
-        /* Set initial "parent" information to the B-tree header */
-        parent_cache_info=&(bt2->cache_info);
-        parent_addr=addr;
-        parent_ptr=bt2;
+            } /* end if */
 
-        /* Set initial node pointer for "current" node */
-        curr_node_ptr=&(bt2->root);
-    } /* end else */
+            /* Get node pointer for child */
+            child_node_ptr=&(internal->node_ptrs[idx]);
+
+            /* Set the number of redistribution retries */
+            /* This takes care of the case where a B-tree node needs to be
+             * redistributed, but redistributing the node causes the index
+             * for insertion to move to another node, which also needs to be
+             * redistributed.  Now, we loop trying to redistribute and then
+             * eventually force a merge */
+            retries = 2;
+
+            /* Preemptively merge/redistribute a node we will enter */
+            while((depth==1 && child_node_ptr->node_nrec==shared->merge_leaf_nrec) ||
+                    (depth>1 && child_node_ptr->node_nrec==shared->merge_int_nrec)) {
+                /* Attempt to redistribute records among children */
+                if(idx==0) {    /* Left-most child */
+                    if(retries>0 && ((depth==1 && internal->node_ptrs[idx+1].node_nrec>shared->merge_leaf_nrec) ||
+                            (depth>1 && internal->node_ptrs[idx+1].node_nrec>shared->merge_int_nrec))) {
+HDfprintf(stderr,"%s: Performing 2 node redistribution in B-tree!\n",FUNC);
+                        if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)idx)<0)
+                            HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
+                    } /* end if */
+                    else {
+HDfprintf(stderr,"%s: Need to perform 2->1 node merge in B-tree!\n",FUNC);
+HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree")
+                    } /* end else */
+                } /* end if */
+                else if((unsigned)idx==internal->nrec) { /* Right-most child */
+                    if(retries>0 && ((depth==1 && internal->node_ptrs[idx-1].node_nrec>shared->merge_leaf_nrec) ||
+                            (depth>1 && internal->node_ptrs[idx-1].node_nrec>shared->merge_int_nrec))) {
+HDfprintf(stderr,"%s: Performing 2 node redistribution in B-tree!\n",FUNC);
+                        if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)(idx-1))<0)
+                            HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
+                    } /* end if */
+                    else {
+HDfprintf(stderr,"%s: Need to perform 2->1 node merge in B-tree!\n",FUNC);
+HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree")
+                    } /* end else */
+                } /* end if */
+                else { /* Middle child */
+                    if(retries>0 && ((depth==1 &&
+                                ((internal->node_ptrs[idx+1].node_nrec>shared->merge_leaf_nrec) ||
+                                (internal->node_ptrs[idx-1].node_nrec>shared->merge_leaf_nrec))) ||
+                            (depth>1 && 
+                                ((internal->node_ptrs[idx+1].node_nrec>shared->merge_int_nrec) ||
+                                (internal->node_ptrs[idx-1].node_nrec>shared->merge_int_nrec))))) {
+HDfprintf(stderr,"%s: Performing 3 node redistribution in B-tree!\n",FUNC);
+                        if(H5B2_redistribute3(f,dxpl_id,depth,internal,(unsigned)idx)<0)
+                            HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
+                    } /* end if */
+                    else {
+HDfprintf(stderr,"%s: Need to perform 3->2 node merge in B-tree!\n",FUNC);
+HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree")
+                    } /* end else */
+                } /* end else */
+
+                /* Locate node pointer for child (after merge/redistribute) */
+/* Actually, this can be easily updated (for 2-node redistrib.) and shouldn't require re-searching */
+                cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx);
+                if(cmp > 0)
+                    idx++;
+
+                /* Update child_node_ptr (to reflect change in location from merge/redistribution) */
+                child_node_ptr=&(internal->node_ptrs[idx]);
+
+                /* Decrement the number of redistribution retries left */
+                retries--;
+            } /* end while */
+
+            /* Update record count (in parent) */
+            curr_node_ptr->all_nrec--;
+
+            /* Mark parent node as dirty */
+            parent_cache_info->is_dirty = TRUE;
+
+#ifdef H5B2_DEBUG
+            if(parent_cache_info->type==H5AC_BT2_INT)
+                H5B2_assert_internal((hsize_t)0,shared,parent_ptr);
+#endif /* H5B2_DEBUG */
+
+            /* Unlock parent node (possibly the B-tree header) */
+            if (H5AC_unprotect(f, dxpl_id, parent_cache_info->type, parent_addr, parent_ptr, H5AC__NO_FLAGS_SET) < 0)
+                HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree info")
+
+            /* Transition "current" info into "parent" info */
+            parent_cache_info = curr_cache_info;
+            parent_addr = curr_addr;
+            parent_ptr = curr_ptr;
+
+            /* Transition "child" node pointer to "current" node pointer */
+            curr_node_ptr = child_node_ptr;
+
+            /* Decrement depth of current node */
+            depth--;
+        } /* end while */
+    } /* end if */
 
     /* Must have a leaf node with enough space to insert a record now */
     HDassert(H5F_addr_defined(curr_node_ptr->addr));
-    /* Root only B-tree must break a few rules */
+    /* "Root only" B-tree allowed to have less records in it's node */
     if(depth>0)
         HDassert(curr_node_ptr->node_nrec > shared->merge_leaf_nrec);
 
@@ -2923,6 +3052,305 @@ H5B2_assert_leaf(shared,leaf);
 
     FUNC_LEAVE_NOAPI(ret_value)
 } /* H5B2_remove() */
+#else /* OLD_WAY */
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_remove_leaf
+ *
+ * Purpose:	Removes a record from a B-tree leaf node.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Mar  3 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B2_remove_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
+    H5B2_node_ptr_t *curr_node_ptr, void *udata)
+{
+    H5B2_leaf_t *leaf;                  /* Pointer to leaf node */
+    haddr_t     leaf_addr=HADDR_UNDEF;  /* Leaf address on disk */
+    unsigned    leaf_unprotect_flags=H5C__NO_FLAGS_SET; /* Flags for unprotecting leaf node */
+    H5B2_shared_t *shared;              /* Pointer to B-tree's shared information */
+    int         cmp;                    /* Comparison value of records */
+    unsigned    idx;                    /* Location of record which matches key */
+    herr_t	ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI(H5B2_remove_leaf, FAIL)
+
+    /* Check arguments. */
+    HDassert(f);
+    HDassert(bt2_shared);
+    HDassert(curr_node_ptr);
+    HDassert(H5F_addr_defined(curr_node_ptr->addr));
+
+    /* Lock current B-tree node */
+    leaf_addr = curr_node_ptr->addr;
+    if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, leaf_addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE)))
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree leaf node")
+
+    /* Get the pointer to the shared B-tree info */
+    shared=H5RC_GET_OBJ(bt2_shared);
+    HDassert(shared);
+
+    /* Sanity check number of records */
+    HDassert(curr_node_ptr->all_nrec == curr_node_ptr->node_nrec);
+    HDassert(leaf->nrec == curr_node_ptr->node_nrec);
+
+    /* Find correct location to remove this record */
+    if((cmp = H5B2_locate_record(shared->type,leaf->nrec,shared->nat_off,leaf->leaf_native,udata,&idx)) != 0)
+        HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree")
+
+    /* Make callback to retrieve record in native form */
+    if((shared->type->retrieve)(udata,H5B2_LEAF_NREC(leaf,shared,idx))<0)
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record into leaf node")
+
+    /* Update number of records in node */
+    leaf->nrec--;
+
+    /* Mark leaf node as dirty also */
+    leaf->cache_info.is_dirty = TRUE;
+
+    if(leaf->nrec > 0) {
+        /* Pack record out of leaf */
+        HDmemmove(H5B2_LEAF_NREC(leaf,shared,idx),H5B2_LEAF_NREC(leaf,shared,idx+1),shared->type->nrec_size*(leaf->nrec-idx));
+    } /* end if */
+    else {
+        /* Release space for B-tree node on disk */
+        if (H5MF_xfree(f, H5FD_MEM_BTREE, dxpl_id, leaf_addr, (hsize_t)shared->node_size)<0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to free B-tree leaf node")
+    
+        /* Let the cache know that the object is deleted */
+        leaf_unprotect_flags = H5C__DELETED_FLAG;
+
+        /* Reset address of parent node pointer */
+        curr_node_ptr->addr = HADDR_UNDEF;
+    } /* end else */
+
+    /* Update record count for parent of leaf node */
+    curr_node_ptr->all_nrec--;
+    curr_node_ptr->node_nrec--;
+
+done:
+    /* Release the B-tree leaf node */
+    if (leaf && H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_addr, leaf, leaf_unprotect_flags) < 0)
+        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release leaf B-tree node")
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_remove_leaf() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_remove_internal
+ *
+ * Purpose:	Removes a record from a B-tree node.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Mar  3 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
+    unsigned depth, H5AC_info_t *parent_cache_info,
+    H5B2_node_ptr_t *curr_node_ptr, void *udata)
+{
+    H5B2_internal_t *internal;          /* Pointer to internal node */
+    H5B2_shared_t *shared;              /* Pointer to B-tree's shared information */
+    unsigned    idx;                    /* Location of record which matches key */
+    herr_t	ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI(H5B2_remove_internal, FAIL)
+
+    /* Check arguments. */
+    HDassert(f);
+    HDassert(bt2_shared);
+    HDassert(depth>0);
+    HDassert(parent_cache_info);
+    HDassert(curr_node_ptr);
+    HDassert(H5F_addr_defined(curr_node_ptr->addr));
+
+    /* Lock current B-tree node */
+    if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE)))
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
+
+    /* Get the pointer to the shared B-tree info */
+    shared=H5RC_GET_OBJ(bt2_shared);
+    HDassert(shared);
+
+/* Merge or redistribute child node pointers, if necessary */
+    {
+        int         cmp;                /* Comparison value of records */
+        unsigned retries;               /* Number of times to attempt redistribution */
+
+        /* Locate node pointer for child */
+        cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx);
+        if(cmp>0)
+            idx++;
+
+        /* Handle deleting a record from an internal node */
+        if(cmp==0) {
+HDfprintf(stderr,"%s: Deleting record in internal node of non-trival B-tree!\n",FUNC);
+HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree")
+        } /* end if */
+
+
+        /* Set the number of redistribution retries */
+        /* This takes care of the case where a B-tree node needs to be
+         * redistributed, but redistributing the node causes the index
+         * for removal to move to another node, which also needs to be
+         * redistributed.  Now, we loop trying to redistribute and then
+         * eventually force a merge */
+        retries = 2;
+
+        /* Preemptively merge/redistribute a node we will enter */
+        while((depth==1 && internal->node_ptrs[idx].node_nrec==shared->merge_leaf_nrec) ||
+                (depth>1 && internal->node_ptrs[idx].node_nrec==shared->merge_int_nrec)) {
+            /* Attempt to redistribute records among children */
+            if(idx==0) {    /* Left-most child */
+                if(retries>0 && ((depth==1 && internal->node_ptrs[idx+1].node_nrec>shared->merge_leaf_nrec) ||
+                        (depth>1 && internal->node_ptrs[idx+1].node_nrec>shared->merge_int_nrec))) {
+HDfprintf(stderr,"%s: Performing 2 node redistribution in B-tree!\n",FUNC);
+                    if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)idx)<0)
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
+                } /* end if */
+                else {
+HDfprintf(stderr,"%s: Need to perform 2->1 node merge in B-tree!\n",FUNC);
+HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree")
+                } /* end else */
+            } /* end if */
+            else if((unsigned)idx==internal->nrec) { /* Right-most child */
+                if(retries>0 && ((depth==1 && internal->node_ptrs[idx-1].node_nrec>shared->merge_leaf_nrec) ||
+                        (depth>1 && internal->node_ptrs[idx-1].node_nrec>shared->merge_int_nrec))) {
+HDfprintf(stderr,"%s: Performing 2 node redistribution in B-tree!\n",FUNC);
+                    if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)(idx-1))<0)
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
+                } /* end if */
+                else {
+HDfprintf(stderr,"%s: Need to perform 2->1 node merge in B-tree!\n",FUNC);
+HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree")
+                } /* end else */
+            } /* end if */
+            else { /* Middle child */
+                if(retries>0 && ((depth==1 &&
+                            ((internal->node_ptrs[idx+1].node_nrec>shared->merge_leaf_nrec) ||
+                            (internal->node_ptrs[idx-1].node_nrec>shared->merge_leaf_nrec))) ||
+                        (depth>1 && 
+                            ((internal->node_ptrs[idx+1].node_nrec>shared->merge_int_nrec) ||
+                            (internal->node_ptrs[idx-1].node_nrec>shared->merge_int_nrec))))) {
+HDfprintf(stderr,"%s: Performing 3 node redistribution in B-tree!\n",FUNC);
+                    if(H5B2_redistribute3(f,dxpl_id,depth,internal,(unsigned)idx)<0)
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
+                } /* end if */
+                else {
+HDfprintf(stderr,"%s: Need to perform 3->2 node merge in B-tree!\n",FUNC);
+HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree")
+                } /* end else */
+            } /* end else */
+
+            /* Locate node pointer for child (after merge/redistribute) */
+/* Actually, this can be easily updated (for 2-node redistrib.) and shouldn't require re-searching */
+            cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx);
+            if(cmp > 0)
+                idx++;
+
+            /* Decrement the number of redistribution retries left */
+            retries--;
+        } /* end while */
+    } /* end block */
+
+    /* Attempt to remove node */
+    if(depth>1) {
+        if(H5B2_remove_internal(f,dxpl_id,bt2_shared,depth-1,&internal->cache_info,&internal->node_ptrs[idx],udata)<0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to remove record from B-tree internal node")
+    } /* end if */
+    else {
+        if(H5B2_remove_leaf(f,dxpl_id,bt2_shared,&internal->node_ptrs[idx],udata)<0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to remove record from B-tree leaf node")
+    } /* end else */
+
+    /* Update record count for node pointer to current node */
+    curr_node_ptr->all_nrec--;
+
+    /* Mark node as dirty */
+    internal->cache_info.is_dirty = TRUE;
+
+done:
+    /* Release the B-tree internal node */
+    if (internal && H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, internal, H5AC__NO_FLAGS_SET) < 0)
+        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release internal B-tree node")
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_remove_internal() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_remove
+ *
+ * Purpose:	Removes a record from a B-tree.
+ *              
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb 25 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_remove(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
+           void *udata)
+{
+    H5B2_t	*bt2=NULL;              /* Pointer to the B-tree header */
+    H5B2_shared_t *shared;              /* Pointer to B-tree's shared information */
+    herr_t	ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI(H5B2_remove, FAIL)
+
+    /* Check arguments. */
+    HDassert(f);
+    HDassert(type);
+    HDassert(H5F_addr_defined(addr));
+
+    /* Look up the b-tree header */
+    if (NULL == (bt2 = H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, addr, type, NULL, H5AC_WRITE)))
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree header")
+
+    /* Get the pointer to the shared B-tree info */
+    shared=H5RC_GET_OBJ(bt2->shared);
+    HDassert(shared);
+
+    /* Check for empty B-tree */
+    if(bt2->root.all_nrec==0)
+        HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree")
+
+    /* Attempt to remove record from B-tree */
+    if(bt2->depth>0) {
+        if(H5B2_remove_internal(f,dxpl_id,bt2->shared,bt2->depth,&(bt2->cache_info),&bt2->root,udata)<0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to remove record from B-tree internal node")
+    } /* end if */
+    else {
+        if(H5B2_remove_leaf(f,dxpl_id,bt2->shared,&bt2->root,udata)<0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to remove record from B-tree leaf node")
+    } /* end else */
+
+    /* Mark parent node as dirty */
+    bt2->cache_info.is_dirty = TRUE;
+
+done:
+    /* Release the B-tree header info */
+    if (bt2 && H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0)
+        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree header info")
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_remove() */
+#endif /* OLD_WAY */
 
 
 /*-------------------------------------------------------------------------