[svn-r26191] Description:

    Track the min & max keys for a v2 B-tree, so it can more efficiently
determine if a key is present in the B-tree.

Tested on:
    Mac OSX/64 10.10.2 (amazon) w/parallel & serial
    Linux/32 2.6.x (jam) w/serial

6 files changed, 359 insertions, 125 deletions

diff --git a/src/H5B2.c b/src/H5B2.c
index a2b218d..7d7345e 100644
--- a/src/H5B2.c
+++ b/src/H5B2.c
@@ -128,11 +128,11 @@ H5FL_DEFINE_STATIC(H5B2_t);
 H5B2_t *
 H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_create_t *cparam, void *ctx_udata)
 {
-    H5B2_t	*bt2 = NULL;            /* Pointer to the B-tree */
-    H5B2_hdr_t	*hdr = NULL;            /* Pointer to the B-tree header */
+    H5B2_t      *bt2 = NULL;            /* Pointer to the B-tree */
+    H5B2_hdr_t  *hdr = NULL;            /* Pointer to the B-tree header */
     H5B2_hdr_cache_ud_t cache_udata;    /* User-data for callback */
     haddr_t     hdr_addr;               /* B-tree header address */
-    H5B2_t	*ret_value;             /* Return value */
+    H5B2_t      *ret_value;             /* Return value */
 
     FUNC_ENTER_NOAPI(NULL)
 
@@ -147,7 +147,7 @@ H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_create_t *cparam, void *ctx_udat
 
     /* Create shared v2 B-tree header */
     if(HADDR_UNDEF == (hdr_addr = H5B2_hdr_create(f, dxpl_id, cparam, ctx_udata)))
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, NULL, "can't create v2 B-tree header")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, NULL, "can't create v2 B-tree header")
 
     /* Create v2 B-tree wrapper */
     if(NULL == (bt2 = H5FL_MALLOC(H5B2_t)))
@@ -157,7 +157,7 @@ H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_create_t *cparam, void *ctx_udat
     cache_udata.f = f;
     cache_udata.ctx_udata = ctx_udata;
     if(NULL == (hdr = (H5B2_hdr_t *)H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, hdr_addr, &cache_udata, H5AC_WRITE)))
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, NULL, "unable to load B-tree header")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, NULL, "unable to load B-tree header")
 
     /* Point v2 B-tree wrapper at header and bump it's ref count */
     bt2->hdr = hdr;
@@ -166,7 +166,7 @@ H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_create_t *cparam, void *ctx_udat
 
     /* Increment # of files using this v2 B-tree header */
     if(H5B2_hdr_fuse_incr(bt2->hdr) < 0)
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, "can't increment file reference count on shared v2 B-tree header")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, "can't increment file reference count on shared v2 B-tree header")
 
     /* Set file pointer for this v2 B-tree open context */
     bt2->f = f;
@@ -299,11 +299,11 @@ H5B2_insert(H5B2_t *bt2, hid_t dxpl_id, void *udata)
 
     /* Attempt to insert record into B-tree */
     if(hdr->depth > 0) {
-        if(H5B2_insert_internal(hdr, dxpl_id, hdr->depth, NULL, &hdr->root, udata) < 0)
+        if(H5B2_insert_internal(hdr, dxpl_id, hdr->depth, NULL, &hdr->root, H5B2_POS_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(hdr, dxpl_id, &hdr->root, udata) < 0)
+        if(H5B2_insert_leaf(hdr, dxpl_id, &hdr->root, H5B2_POS_ROOT, udata) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree leaf node")
     } /* end else */
 
@@ -420,12 +420,13 @@ htri_t
 H5B2_find(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_found_t op,
     void *op_data)
 {
-    H5B2_hdr_t	*hdr;                   /* Pointer to the B-tree header */
+    H5B2_hdr_t  *hdr;                   /* Pointer to the B-tree header */
     H5B2_node_ptr_t curr_node_ptr;      /* Node pointer info for current node */
     unsigned    depth;                  /* Current depth of the tree */
     int         cmp;                    /* Comparison value of records */
     unsigned    idx;                    /* Location of record which matches key */
-    htri_t	ret_value = TRUE;       /* Return value */
+    H5B2_nodepos_t curr_pos;            /* Position of the current node */
+    htri_t      ret_value = TRUE;       /* Return value */
 
     FUNC_ENTER_NOAPI(FAIL)
 
@@ -441,16 +442,39 @@ H5B2_find(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_found_t op,
     /* Make copy of the root node pointer to start search with */
     curr_node_ptr = hdr->root;
 
-    /* Current depth of the tree */
-    depth = hdr->depth;
-
     /* Check for empty tree */
     if(curr_node_ptr.node_nrec == 0)
         HGOTO_DONE(FALSE)
 
+    /* Check record against min & max records in tree, to attempt to quickly
+     *  find candidates or avoid further searching.
+     */
+    if(hdr->min_native_rec != NULL) {
+	if((cmp = (hdr->cls->compare)(udata, hdr->min_native_rec)) < 0)
+	    HGOTO_DONE(FALSE) 	/* Less than the least record--not found */ 
+	else if(cmp == 0) { /* Record is found */
+	    if(op && (op)(hdr->min_native_rec, op_data) < 0)
+                HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "'found' callback failed for B-tree find operation")
+	    HGOTO_DONE(TRUE)
+	} /* end if */
+    } /* end if */
+    if(hdr->max_native_rec != NULL) {
+	if((cmp = (hdr->cls->compare)(udata, hdr->max_native_rec)) > 0)
+	    HGOTO_DONE(FALSE) 	/* Greater than the greatest record--not found */
+	else if(cmp == 0) { /* Record is found */
+	    if(op && (op)(hdr->max_native_rec, op_data) < 0)
+                HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "'found' callback failed for B-tree find operation")
+	    HGOTO_DONE(TRUE)
+	} /* end if */
+    } /* end if */
+
+    /* Current depth of the tree */
+    depth = hdr->depth;
+
     /* Walk down B-tree to find record or leaf node where record is located */
     cmp = -1;
-    while(depth > 0 && cmp != 0) {
+    curr_pos = H5B2_POS_ROOT;
+    while(depth > 0) {
         H5B2_internal_t *internal;          /* Pointer to internal node in B-tree */
         H5B2_node_ptr_t next_node_ptr;      /* Node pointer info for next node */
 
@@ -467,6 +491,24 @@ H5B2_find(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_found_t op,
             /* Get node pointer for next node to search */
             next_node_ptr=internal->node_ptrs[idx];
 
+            /* Set the position of the next node */
+            if(H5B2_POS_MIDDLE != curr_pos) {
+                if(idx == 0) {
+                    if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                        curr_pos = H5B2_POS_LEFT;
+                    else
+                        curr_pos = H5B2_POS_MIDDLE;
+                } /* end if */
+                else if(idx == internal->nrec) {
+                    if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                        curr_pos = H5B2_POS_RIGHT;
+                    else
+                        curr_pos = H5B2_POS_MIDDLE;
+                } /* end if */
+                else
+                    curr_pos = H5B2_POS_MIDDLE;
+            } /* end if */
+
             /* Unlock current node */
             if(H5AC_unprotect(hdr->f, dxpl_id, H5AC_BT2_INT, curr_node_ptr.addr, internal, H5AC__NO_FLAGS_SET) < 0)
                 HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
@@ -523,6 +565,27 @@ H5B2_find(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_found_t op,
 
                 HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "'found' callback failed for B-tree find operation")
             } /* end if */
+
+            /* Check for record being the min or max for the tree */
+            /* (Don't use 'else' for the idx check, to allow for root leaf node) */
+            if(H5B2_POS_MIDDLE != curr_pos) {
+                if(idx == 0) {
+                    if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                        if(hdr->min_native_rec == NULL)
+                            if(NULL == (hdr->min_native_rec = (uint8_t *)HDmalloc(hdr->cls->nrec_size)))
+                                HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for v2 B-tree min record info")
+                        HDmemcpy(hdr->min_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size);
+                    } /* end if */
+                } /* end if */
+                if(idx == (unsigned)(leaf->nrec - 1)) {
+                    if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                        if(hdr->max_native_rec == NULL)
+                            if(NULL == (hdr->max_native_rec = (uint8_t *)HDmalloc(hdr->cls->nrec_size)))
+                                HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for v2 B-tree max record info")
+                        HDmemcpy(hdr->max_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size);
+                    } /* end if */
+                } /* end if */
+            } /* end if */
         } /* end else */
 
         /* Unlock current node */
@@ -577,9 +640,6 @@ H5B2_index(H5B2_t *bt2, hid_t dxpl_id, H5_iter_order_t order, hsize_t idx,
     /* Make copy of the root node pointer to start search with */
     curr_node_ptr = hdr->root;
 
-    /* Current depth of the tree */
-    depth = hdr->depth;
-
     /* Check for empty tree */
     if(curr_node_ptr.node_nrec == 0)
         HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree has no records")
@@ -588,6 +648,9 @@ H5B2_index(H5B2_t *bt2, hid_t dxpl_id, H5_iter_order_t order, hsize_t idx,
     if(idx >= curr_node_ptr.all_nrec)
         HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree doesn't have that many records")
 
+    /* Current depth of the tree */
+    depth = hdr->depth;
+
     /* Check for reverse indexing and map requested index to appropriate forward index */
     if(order == H5_ITER_DEC)
         idx = curr_node_ptr.all_nrec - (idx + 1);
@@ -736,7 +799,7 @@ H5B2_remove(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_remove_t op,
         hbool_t depth_decreased = FALSE;  /* Flag to indicate whether the depth of the B-tree decreased */
 
         if(H5B2_remove_internal(hdr, dxpl_id, &depth_decreased, NULL, hdr->depth,
-                &(hdr->cache_info), NULL, &hdr->root, udata, op, op_data) < 0)
+                &(hdr->cache_info), NULL, H5B2_POS_ROOT, &hdr->root, udata, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node")
 
         /* Check for decreasing the depth of the B-tree */
@@ -754,7 +817,7 @@ H5B2_remove(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_remove_t op,
         } /* end for */
     } /* end if */
     else {
-        if(H5B2_remove_leaf(hdr, dxpl_id, &hdr->root, udata, op, op_data) < 0)
+        if(H5B2_remove_leaf(hdr, dxpl_id, &hdr->root, H5B2_POS_ROOT, udata, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node")
     } /* end else */
 
@@ -818,7 +881,7 @@ H5B2_remove_by_idx(H5B2_t *bt2, hid_t dxpl_id, H5_iter_order_t order,
         hbool_t depth_decreased = FALSE;  /* Flag to indicate whether the depth of the B-tree decreased */
 
         if(H5B2_remove_internal_by_idx(hdr, dxpl_id, &depth_decreased, NULL, hdr->depth,
-                &(hdr->cache_info), NULL, &hdr->root, idx, op, op_data) < 0)
+                &(hdr->cache_info), NULL, &hdr->root, H5B2_POS_ROOT, idx, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node")
 
         /* Check for decreasing the depth of the B-tree */
@@ -836,7 +899,7 @@ H5B2_remove_by_idx(H5B2_t *bt2, hid_t dxpl_id, H5_iter_order_t order,
         } /* end for */
     } /* end if */
     else {
-        if(H5B2_remove_leaf_by_idx(hdr, dxpl_id, &hdr->root, (unsigned)idx, op, op_data) < 0)
+        if(H5B2_remove_leaf_by_idx(hdr, dxpl_id, &hdr->root, H5B2_POS_ROOT, (unsigned)idx, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node")
     } /* end else */
 
@@ -970,6 +1033,7 @@ H5B2_modify(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_modify_t op,
 {
     H5B2_hdr_t	*hdr;                   /* Pointer to the B-tree header */
     H5B2_node_ptr_t curr_node_ptr;      /* Node pointer info for current node */
+    H5B2_nodepos_t curr_pos;            /* Position of current node */
     unsigned    depth;                  /* Current depth of the tree */
     int         cmp;                    /* Comparison value of records */
     unsigned    idx;                    /* Location of record which matches key */
@@ -990,16 +1054,17 @@ H5B2_modify(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_modify_t op,
     /* Make copy of the root node pointer to start search with */
     curr_node_ptr = hdr->root;
 
-    /* Current depth of the tree */
-    depth = hdr->depth;
-
     /* Check for empty tree */
     if(0 == curr_node_ptr.node_nrec)
         HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree has no records")
 
+    /* Current depth of the tree */
+    depth = hdr->depth;
+
     /* Walk down B-tree to find record or leaf node where record is located */
     cmp = -1;
-    while(depth > 0 && cmp != 0) {
+    curr_pos = H5B2_POS_ROOT;
+    while(depth > 0) {
         unsigned internal_flags = H5AC__NO_FLAGS_SET;
         H5B2_internal_t *internal;          /* Pointer to internal node in B-tree */
         H5B2_node_ptr_t next_node_ptr;      /* Node pointer info for next node */
@@ -1017,6 +1082,24 @@ H5B2_modify(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_modify_t op,
             /* Get node pointer for next node to search */
             next_node_ptr = internal->node_ptrs[idx];
 
+            /* Set the position of the next node */
+            if(H5B2_POS_MIDDLE != curr_pos) {
+                if(idx == 0) {
+                    if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                        curr_pos = H5B2_POS_LEFT;
+                    else
+                        curr_pos = H5B2_POS_MIDDLE;
+                } /* end if */
+                else if(idx == internal->nrec) {
+                    if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                        curr_pos = H5B2_POS_RIGHT;
+                    else
+                        curr_pos = H5B2_POS_MIDDLE;
+                } /* end if */
+                else
+                    curr_pos = H5B2_POS_MIDDLE;
+            } /* end if */
+
             /* Unlock current node */
             if(H5AC_unprotect(hdr->f, dxpl_id, H5AC_BT2_INT, curr_node_ptr.addr, internal, H5AC__NO_FLAGS_SET) < 0)
                 HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
@@ -1092,6 +1175,27 @@ H5B2_modify(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_modify_t op,
 
                 HGOTO_ERROR(H5E_BTREE, H5E_CANTMODIFY, FAIL, "'modify' callback failed for B-tree find operation")
             } /* end if */
+
+            /* Check for modified record being the min or max for the tree */
+            /* (Don't use 'else' for the idx check, to allow for root leaf node) */
+            if(H5B2_POS_MIDDLE != curr_pos) {
+                if(idx == 0) {
+                    if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                        if(hdr->min_native_rec == NULL)
+                            if(NULL == (hdr->min_native_rec = (uint8_t *)HDmalloc(hdr->cls->nrec_size)))
+                                HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for v2 B-tree min record info")
+                        HDmemcpy(hdr->min_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size);
+                    } /* end if */
+                } /* end if */
+                if(idx == (unsigned)(leaf->nrec - 1)) {
+                    if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                        if(hdr->max_native_rec == NULL)
+                            if(NULL == (hdr->max_native_rec = (uint8_t *)HDmalloc(hdr->cls->nrec_size)))
+                                HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for v2 B-tree max record info")
+                        HDmemcpy(hdr->max_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size);
+                    } /* end if */
+                } /* end if */
+            } /* end if */
         } /* end else */
 
         /* Mark the node as dirty if it changed */
diff --git a/src/H5B2cache.c b/src/H5B2cache.c
index 1554501..1e2a6a3 100644
--- a/src/H5B2cache.c
+++ b/src/H5B2cache.c
@@ -15,11 +15,11 @@
 
 /*-------------------------------------------------------------------------
  *
- * Created:		H5B2cache.c
- *			Jan 31 2005
- *			Quincey Koziol <koziol@ncsa.uiuc.edu>
+ * Created:     H5B2cache.c
+ *              Jan 31 2005
+ *              Quincey Koziol <koziol@hdfgroup.org>
  *
- * Purpose:		Implement v2 B-tree metadata cache methods.
+ * Purpose:     Implement v2 B-tree metadata cache methods.
  *
  *-------------------------------------------------------------------------
  */
@@ -174,7 +174,7 @@ H5B2__cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_udata)
 
     /* Allocate new B-tree header and reset cache info */
     if(NULL == (hdr = H5B2_hdr_alloc(udata->f)))
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "allocation failed for B-tree header")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "allocation failed for B-tree header")
 
     /* Wrap the local buffer for serialized header info */
     if(NULL == (wb = H5WB_wrap(hdr_buf, sizeof(hdr_buf))))
@@ -186,7 +186,7 @@ H5B2__cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_udata)
 
     /* Read header from disk */
     if(H5F_block_read(f, H5FD_MEM_BTREE, addr, hdr->hdr_size, dxpl_id, buf) < 0)
-	HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree header")
+        HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree header")
 
     /* Get temporary pointer to serialized header */
     p = buf;
@@ -203,7 +203,7 @@ H5B2__cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_udata)
     /* B-tree class */
     id = (H5B2_subid_t)*p++;
     if(id >= H5B2_NUM_BTREE_ID)
-	HGOTO_ERROR(H5E_BTREE, H5E_BADTYPE, NULL, "incorrect B-tree type")
+        HGOTO_ERROR(H5E_BTREE, H5E_BADTYPE, NULL, "incorrect B-tree type")
 
     /* Node size (in bytes) */
     UINT32DECODE(p, cparam.node_size);
@@ -234,12 +234,12 @@ H5B2__cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_udata)
 
     /* Verify checksum */
     if(stored_chksum != computed_chksum)
-	HGOTO_ERROR(H5E_BTREE, H5E_BADVALUE, NULL, "incorrect metadata checksum for v2 B-tree header")
+        HGOTO_ERROR(H5E_BTREE, H5E_BADVALUE, NULL, "incorrect metadata checksum for v2 B-tree header")
 
     /* Initialize B-tree header info */
     cparam.cls = H5B2_client_class_g[id];
     if(H5B2_hdr_init(hdr, &cparam, udata->ctx_udata, depth) < 0)
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, NULL, "can't initialize B-tree header info")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, NULL, "can't initialize B-tree header info")
 
     /* Set the B-tree header's address */
     hdr->addr = addr;
@@ -342,17 +342,17 @@ H5B2__cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr,
         /* Metadata checksum */
         UINT32ENCODE(p, metadata_chksum);
 
-	/* Write the B-tree header. */
+        /* Write the B-tree header. */
         HDassert((size_t)(p - buf) == hdr->hdr_size);
-	if(H5F_block_write(f, H5FD_MEM_BTREE, addr, hdr->hdr_size, dxpl_id, buf) < 0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFLUSH, FAIL, "unable to save B-tree header to disk")
+        if(H5F_block_write(f, H5FD_MEM_BTREE, addr, hdr->hdr_size, dxpl_id, buf) < 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTFLUSH, FAIL, "unable to save B-tree header to disk")
 
-	hdr->cache_info.is_dirty = FALSE;
+        hdr->cache_info.is_dirty = FALSE;
     } /* end if */
 
     if(destroy)
         if(H5B2__cache_hdr_dest(f, hdr) < 0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree header")
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree header")
 
 done:
     /* Release resources */
@@ -445,17 +445,17 @@ done:
 
 
 /*-------------------------------------------------------------------------
- * Function:	H5B2__cache_hdr_size
+ * Function:    H5B2__cache_hdr_size
  *
- * Purpose:	Compute the size in bytes of a B-tree header
- *		on disk, and return it in *size_ptr.  On failure,
- *		the value of *size_ptr is undefined.
+ * Purpose:     Compute the size in bytes of a B-tree header
+ *              on disk, and return it in *size_ptr.  On failure,
+ *              the value of *size_ptr is undefined.
  *
- * Return:	Non-negative on success/Negative on failure
+ * Return:      SUCCEED (Can't fail)
  *
- * Programmer:	Quincey Koziol
- *		koziol@ncsa.uiuc.edu
- *		Feb 1 2005
+ * Programmer:  Quincey Koziol
+ *              koziol@hdfgroup.org
+ *              Feb 1 2005
  *
  *-------------------------------------------------------------------------
  */
@@ -466,6 +466,7 @@ H5B2__cache_hdr_size(const H5F_t UNUSED *f, const H5B2_hdr_t *hdr, size_t *size_
 
     /* check arguments */
     HDassert(f);
+    HDassert(hdr);
     HDassert(size_ptr);
 
     /* Set size value */
@@ -519,14 +520,14 @@ H5B2__cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_udata)
 
     /* Increment ref. count on B-tree header */
     if(H5B2_hdr_incr(udata->hdr) < 0)
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, "can't increment ref. count on B-tree header")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, "can't increment ref. count on B-tree header")
 
     /* Share B-tree information */
     internal->hdr = udata->hdr;
 
     /* Read header from disk */
     if(H5F_block_read(f, H5FD_MEM_BTREE, addr, udata->hdr->node_size, dxpl_id, udata->hdr->page) < 0)
-	HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree internal node")
+        HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree internal node")
 
     p = udata->hdr->page;
 
@@ -541,7 +542,7 @@ H5B2__cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_udata)
 
     /* B-tree type */
     if(*p++ != (uint8_t)udata->hdr->cls->id)
-	HGOTO_ERROR(H5E_BTREE, H5E_BADTYPE, NULL, "incorrect B-tree type")
+        HGOTO_ERROR(H5E_BTREE, H5E_BADTYPE, NULL, "incorrect B-tree type")
 
     /* Allocate space for the native keys in memory */
     if(NULL == (internal->int_native = (uint8_t *)H5FL_FAC_MALLOC(udata->hdr->node_info[udata->depth].nat_rec_fac)))
@@ -593,7 +594,7 @@ H5B2__cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_udata)
 
     /* Verify checksum */
     if(stored_chksum != computed_chksum)
-	HGOTO_ERROR(H5E_BTREE, H5E_BADVALUE, NULL, "incorrect metadata checksum for v2 internal node")
+        HGOTO_ERROR(H5E_BTREE, H5E_BADVALUE, NULL, "incorrect metadata checksum for v2 internal node")
 
     /* Set return value */
     ret_value = internal;
@@ -853,7 +854,7 @@ H5B2__cache_leaf_load(H5F_t UNUSED *f, hid_t dxpl_id, haddr_t addr, void *_udata
 
     /* Allocate new leaf node and reset cache info */
     if(NULL == (leaf = H5FL_MALLOC(H5B2_leaf_t)))
-	HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed")
+        HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed")
     HDmemset(&leaf->cache_info, 0, sizeof(H5AC_info_t));
 
     /* Set the B-tree header's file context for this operation */
@@ -861,33 +862,33 @@ H5B2__cache_leaf_load(H5F_t UNUSED *f, hid_t dxpl_id, haddr_t addr, void *_udata
 
     /* Increment ref. count on B-tree header */
     if(H5B2_hdr_incr(udata->hdr) < 0)
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, "can't increment ref. count on B-tree header")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, "can't increment ref. count on B-tree header")
 
     /* Share B-tree header information */
     leaf->hdr = udata->hdr;
 
     /* Read header from disk */
     if(H5F_block_read(udata->f, H5FD_MEM_BTREE, addr, udata->hdr->node_size, dxpl_id, udata->hdr->page) < 0)
-	HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree leaf node")
+        HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree leaf node")
 
     p = udata->hdr->page;
 
     /* Magic number */
     if(HDmemcmp(p, H5B2_LEAF_MAGIC, (size_t)H5_SIZEOF_MAGIC))
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree leaf node signature")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree leaf node signature")
     p += H5_SIZEOF_MAGIC;
 
     /* Version */
     if(*p++ != H5B2_LEAF_VERSION)
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree leaf node version")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree leaf node version")
 
     /* B-tree type */
     if(*p++ != (uint8_t)udata->hdr->cls->id)
-	HGOTO_ERROR(H5E_BTREE, H5E_BADTYPE, NULL, "incorrect B-tree type")
+        HGOTO_ERROR(H5E_BTREE, H5E_BADTYPE, NULL, "incorrect B-tree type")
 
     /* Allocate space for the native keys in memory */
     if(NULL == (leaf->leaf_native = (uint8_t *)H5FL_FAC_MALLOC(udata->hdr->node_info[0].nat_rec_fac)))
-	HGOTO_ERROR(H5E_BTREE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree leaf native keys")
+        HGOTO_ERROR(H5E_BTREE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree leaf native keys")
 
     /* Set the number of records in the leaf */
     leaf->nrec = udata->nrec;
diff --git a/src/H5B2hdr.c b/src/H5B2hdr.c
index 443a2e5..452a35d 100644
--- a/src/H5B2hdr.c
+++ b/src/H5B2hdr.c
@@ -166,7 +166,7 @@ HDmemset(hdr->page, 0, hdr->node_size);
     hdr->node_info[0].cum_max_nrec = hdr->node_info[0].max_nrec;
     hdr->node_info[0].cum_max_nrec_size = 0;
     if(NULL == (hdr->node_info[0].nat_rec_fac = H5FL_fac_init(hdr->cls->nrec_size * hdr->node_info[0].max_nrec)))
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't create node native key block factory")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't create node native key block factory")
     hdr->node_info[0].node_ptr_fac = NULL;
 
     /* Allocate array of pointers to internal node native keys */
@@ -250,7 +250,7 @@ H5B2_hdr_alloc(H5F_t *f)
 
     /* Allocate space for the shared information */
     if(NULL == (hdr = H5FL_CALLOC(H5B2_hdr_t)))
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for B-tree header")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for B-tree header")
 
     /* Assign non-zero information */
     hdr->f = f;
@@ -298,19 +298,19 @@ H5B2_hdr_create(H5F_t *f, hid_t dxpl_id, const H5B2_create_t *cparam,
 
     /* Allocate v2 B-tree header */
     if(NULL == (hdr = H5B2_hdr_alloc(f)))
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, HADDR_UNDEF, "allocation failed for B-tree header")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, HADDR_UNDEF, "allocation failed for B-tree header")
 
     /* Initialize shared B-tree info */
     if(H5B2_hdr_init(hdr, cparam, ctx_udata, (uint16_t)0) < 0)
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, HADDR_UNDEF, "can't create shared B-tree info")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, HADDR_UNDEF, "can't create shared B-tree info")
 
     /* Allocate space for the header on disk */
     if(HADDR_UNDEF == (hdr->addr = H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)hdr->hdr_size)))
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, HADDR_UNDEF, "file allocation failed for B-tree header")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, HADDR_UNDEF, "file allocation failed for B-tree header")
 
     /* Cache the new B-tree node */
     if(H5AC_insert_entry(f, dxpl_id, H5AC_BT2_HDR, hdr->addr, hdr, H5AC__NO_FLAGS_SET) < 0)
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, HADDR_UNDEF, "can't add B-tree header to cache")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, HADDR_UNDEF, "can't add B-tree header to cache")
 
     /* Set address of v2 B-tree header to return */
     ret_value = hdr->addr;
@@ -398,15 +398,15 @@ done:
 
 
 /*-------------------------------------------------------------------------
- * Function:	H5B2_hdr_fuse_incr
+ * Function:    H5B2_hdr_fuse_incr
  *
- * Purpose:	Increment file reference count on shared v2 B-tree header
+ * Purpose:     Increment file reference count on shared v2 B-tree header
  *
- * Return:	Non-negative on success/Negative on failure
+ * Return:      SUCCEED (Can't fail)
  *
- * Programmer:	Quincey Koziol
- *		koziol@hdfgroup.org
- *		Oct 27 2009
+ * Programmer:  Quincey Koziol
+ *              koziol@hdfgroup.org
+ *              Oct 27 2009
  *
  *-------------------------------------------------------------------------
  */
@@ -426,15 +426,15 @@ H5B2_hdr_fuse_incr(H5B2_hdr_t *hdr)
 
 
 /*-------------------------------------------------------------------------
- * Function:	H5B2_hdr_fuse_decr
+ * Function:    H5B2_hdr_fuse_decr
  *
- * Purpose:	Decrement file reference count on shared v2 B-tree header
+ * Purpose:     Decrement file reference count on shared v2 B-tree header
  *
- * Return:	Non-negative on success/Negative on failure
+ * Return:      The file's reference count after the decrement. (Can't fail)
  *
- * Programmer:	Quincey Koziol
- *		koziol@hdfgroup.org
- *		Oct 27 2009
+ * Programmer:  Quincey Koziol
+ *              koziol@hdfgroup.org
+ *              Oct 27 2009
  *
  *-------------------------------------------------------------------------
  */
@@ -542,6 +542,16 @@ H5B2_hdr_free(H5B2_hdr_t *hdr)
         hdr->node_info = H5FL_SEQ_FREE(H5B2_node_info_t, hdr->node_info);
     } /* end if */
 
+    /* Release the min & max record info, if set */
+    if(hdr->min_native_rec) {
+	HDfree(hdr->min_native_rec);
+	hdr->min_native_rec = NULL;
+    } /* end if */
+    if(hdr->max_native_rec) {
+	HDfree(hdr->max_native_rec);
+	hdr->max_native_rec = NULL;
+    } /* end if */
+
     /* Free B-tree header info */
     hdr = H5FL_FREE(H5B2_hdr_t, hdr);
 
diff --git a/src/H5B2int.c b/src/H5B2int.c
index 630ff98..ef83e93 100644
--- a/src/H5B2int.c
+++ b/src/H5B2int.c
@@ -172,9 +172,9 @@ H5B2_locate_record(const H5B2_class_t *type, unsigned nrec, size_t *rec_off,
  *-------------------------------------------------------------------------
  */
 static herr_t
-H5B2_split1(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, H5B2_node_ptr_t *curr_node_ptr,
-    unsigned *parent_cache_info_flags_ptr, H5B2_internal_t *internal,
-    unsigned *internal_flags_ptr, unsigned idx)
+H5B2_split1(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth,
+    H5B2_node_ptr_t *curr_node_ptr, unsigned *parent_cache_info_flags_ptr,
+    H5B2_internal_t *internal, unsigned *internal_flags_ptr, unsigned idx)
 {
     const H5AC_class_t *child_class;    /* Pointer to child node's class info */
     haddr_t left_addr, right_addr;      /* Addresses of left & right child nodes */
@@ -214,7 +214,7 @@ H5B2_split1(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, H5B2_node_ptr_t *cur
         left_addr = internal->node_ptrs[idx].addr;
         right_addr = internal->node_ptrs[idx + 1].addr;
 
-        /* Protect both leafs */
+        /* Protect both leaves */
         if(NULL == (left_int = H5B2_protect_internal(hdr, dxpl_id, left_addr, internal->node_ptrs[idx].node_nrec, (depth - 1), H5AC_WRITE)))
             HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node")
         if(NULL == (right_int = H5B2_protect_internal(hdr, dxpl_id, right_addr, internal->node_ptrs[idx + 1].node_nrec, (depth - 1), H5AC_WRITE)))
@@ -243,7 +243,7 @@ H5B2_split1(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, H5B2_node_ptr_t *cur
         left_addr = internal->node_ptrs[idx].addr;
         right_addr = internal->node_ptrs[idx + 1].addr;
 
-        /* Protect both leafs */
+        /* Protect both leaves */
         if(NULL == (left_leaf = H5B2_protect_leaf(hdr, dxpl_id, left_addr, internal->node_ptrs[idx].node_nrec, H5AC_WRITE)))
             HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node")
         if(NULL == (right_leaf = H5B2_protect_leaf(hdr, dxpl_id, right_addr, internal->node_ptrs[idx + 1].node_nrec, H5AC_WRITE)))
@@ -341,7 +341,7 @@ done:
         HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree leaf node")
 
     FUNC_LEAVE_NOAPI(ret_value)
-} /* end H5B2_split1 */
+} /* end H5B2_split1() */
 
 
 /*-------------------------------------------------------------------------
@@ -646,7 +646,7 @@ done:
         HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree child node")
 
     FUNC_LEAVE_NOAPI(ret_value)
-} /* end H5B2_redistribute2 */
+} /* end H5B2_redistribute2() */
 
 
 /*-------------------------------------------------------------------------
@@ -1033,7 +1033,7 @@ done:
         HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree child node")
 
     FUNC_LEAVE_NOAPI(ret_value)
-} /* end H5B2_redistribute3 */
+} /* end H5B2_redistribute3() */
 
 
 /*-------------------------------------------------------------------------
@@ -1505,7 +1505,7 @@ done:
         HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree child node")
 
     FUNC_LEAVE_NOAPI(ret_value)
-} /* end H5B2_swap_leaf */
+} /* end H5B2_swap_leaf() */
 
 
 /*-------------------------------------------------------------------------
@@ -1523,7 +1523,7 @@ done:
  */
 herr_t
 H5B2_insert_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr,
-    void *udata)
+    H5B2_nodepos_t curr_pos, void *udata)
 {
     H5B2_leaf_t *leaf;                  /* Pointer to leaf node */
     int         cmp;                    /* Comparison value of records */
@@ -1574,6 +1574,27 @@ H5B2_insert_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr,
     /* Update record count for current node */
     leaf->nrec++;
 
+    /* Check for new record being the min or max for the tree */
+    /* (Don't use 'else' for the idx check, to allow for root leaf node) */
+    if(H5B2_POS_MIDDLE != curr_pos) {
+        if(idx == 0) {
+            if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                if(hdr->min_native_rec == NULL)
+                    if(NULL == (hdr->min_native_rec = (uint8_t *)HDmalloc(hdr->cls->nrec_size)))
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for v2 B-tree min record info")
+                HDmemcpy(hdr->min_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size);
+            } /* end if */
+        } /* end if */
+        if(idx == (unsigned)(leaf->nrec - 1)) {
+            if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                if(hdr->max_native_rec == NULL)
+                    if(NULL == (hdr->max_native_rec = (uint8_t *)HDmalloc(hdr->cls->nrec_size)))
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for v2 B-tree max record info")
+                HDmemcpy(hdr->max_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size);
+            } /* end if */
+        } /* end if */
+    } /* end if */
+
 done:
     /* Release the B-tree leaf node (marked as dirty) */
     if(leaf && H5AC_unprotect(hdr->f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr->addr, leaf, H5AC__DIRTIED_FLAG) < 0)
@@ -1599,11 +1620,12 @@ done:
 herr_t
 H5B2_insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth,
     unsigned *parent_cache_info_flags_ptr, H5B2_node_ptr_t *curr_node_ptr,
-    void *udata)
+    H5B2_nodepos_t curr_pos, void *udata)
 {
-    H5B2_internal_t *internal;          /* Pointer to internal node */
+    H5B2_internal_t *internal = NULL;   /* Pointer to internal node */
     unsigned internal_flags = H5AC__NO_FLAGS_SET;
     unsigned    idx;                    /* Location of record which matches key */
+    H5B2_nodepos_t next_pos = H5B2_POS_MIDDLE;    /* Position of node */
     herr_t	ret_value = SUCCEED;    /* Return value */
 
     FUNC_ENTER_NOAPI_NOINIT
@@ -1618,7 +1640,7 @@ H5B2_insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth,
     if(NULL == (internal = H5B2_protect_internal(hdr, dxpl_id, curr_node_ptr->addr, curr_node_ptr->node_nrec, depth, H5AC_WRITE)))
         HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node")
 
-/* Split or redistribute child node pointers, if necessary */
+    /* Split or redistribute child node pointers, if necessary */
     {
         int         cmp;        /* Comparison value of records */
         unsigned retries;       /* Number of times to attempt redistribution */
@@ -1691,13 +1713,25 @@ H5B2_insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth,
         } /* end while */
     } /* end block */
 
+    /* Check if this node is left/right-most */
+    if(H5B2_POS_MIDDLE != curr_pos) {
+        if(idx == 0) {
+            if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                next_pos = H5B2_POS_LEFT;
+        } /* end if */
+        else if(idx == internal->nrec) {
+            if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                next_pos = H5B2_POS_RIGHT;
+        } /* end else */
+    } /* end if */
+
     /* Attempt to insert node */
     if(depth > 1) {
-        if(H5B2_insert_internal(hdr, dxpl_id, (depth - 1), &internal_flags, &internal->node_ptrs[idx], udata) < 0)
+        if(H5B2_insert_internal(hdr, dxpl_id, (depth - 1), &internal_flags, &internal->node_ptrs[idx], next_pos, 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(hdr, dxpl_id, &internal->node_ptrs[idx], udata) < 0)
+        if(H5B2_insert_leaf(hdr, dxpl_id, &internal->node_ptrs[idx], next_pos, udata) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree leaf node")
     } /* end else */
 
@@ -2074,7 +2108,7 @@ done:
  */
 herr_t
 H5B2_remove_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr,
-    void *udata, H5B2_remove_t op, void *op_data)
+    H5B2_nodepos_t curr_pos, void *udata, H5B2_remove_t op, void *op_data)
 {
     H5B2_leaf_t *leaf;                  /* Pointer to leaf node */
     haddr_t     leaf_addr = HADDR_UNDEF;  /* Leaf address on disk */
@@ -2102,6 +2136,27 @@ H5B2_remove_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr,
     if(H5B2_locate_record(hdr->cls, leaf->nrec, hdr->nat_off, leaf->leaf_native, udata, &idx) != 0)
         HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree")
 
+    /* Check for invalidating the min/max record for the tree */
+    if(H5B2_POS_MIDDLE != curr_pos) {
+        /* (Don't use 'else' for the idx check, to allow for root leaf node) */
+        if(idx == 0) {
+            if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                if(hdr->min_native_rec) {
+                    HDfree(hdr->min_native_rec);
+                    hdr->min_native_rec = NULL;
+                } /* end if */
+            } /* end if */
+        } /* end if */
+        if(idx == (unsigned)(leaf->nrec - 1)) {
+            if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                if(hdr->max_native_rec) {
+                    HDfree(hdr->max_native_rec);
+                    hdr->max_native_rec = NULL;
+                } /* end if */
+            } /* end if */
+        } /* end if */
+    } /* end if */
+
     /* Make 'remove' callback if there is one */
     if(op)
         if((op)(H5B2_LEAF_NREC(leaf, hdr, idx), op_data) < 0)
@@ -2154,13 +2209,14 @@ done:
 herr_t
 H5B2_remove_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, hbool_t *depth_decreased,
     void *swap_loc, unsigned depth, H5AC_info_t *parent_cache_info,
-    unsigned *parent_cache_info_flags_ptr, H5B2_node_ptr_t *curr_node_ptr,
-    void *udata, H5B2_remove_t op, void *op_data)
+    unsigned *parent_cache_info_flags_ptr, H5B2_nodepos_t curr_pos,
+    H5B2_node_ptr_t *curr_node_ptr, void *udata, H5B2_remove_t op, void *op_data)
 {
     H5AC_info_t *new_cache_info;        /* Pointer to new cache info */
     unsigned *new_cache_info_flags_ptr = NULL;
     H5B2_node_ptr_t *new_node_ptr;      /* Pointer to new node pointer */
     H5B2_internal_t *internal;          /* Pointer to internal node */
+    H5B2_nodepos_t next_pos = H5B2_POS_MIDDLE;  /* Position of next node */
     unsigned internal_flags = H5AC__NO_FLAGS_SET;
     haddr_t internal_addr;              /* Address of internal node */
     size_t      merge_nrec;             /* Number of records to merge node at */
@@ -2211,6 +2267,9 @@ H5B2_remove_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, hbool_t *depth_decreased,
 
         /* Set flag to indicate root was collapsed */
         collapsed_root = TRUE;
+
+        /* Indicate position of next node */
+        next_pos = H5B2_POS_ROOT;
     } /* end if */
     /* Merge or redistribute child node pointers, if necessary */
     else {
@@ -2306,16 +2365,28 @@ H5B2_remove_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, hbool_t *depth_decreased,
         new_cache_info_flags_ptr = &internal_flags;
         new_cache_info = &internal->cache_info;
         new_node_ptr = &internal->node_ptrs[idx];
+
+        /* Indicate position of next node */
+        if(H5B2_POS_MIDDLE != curr_pos) {
+            if(idx == 0) {
+                if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                    next_pos = H5B2_POS_LEFT;
+            } /* end if */
+            else if(idx == internal->nrec) {
+                if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                    next_pos = H5B2_POS_RIGHT;
+            } /* end if */
+        } /* end if */
     } /* end else */
 
     /* Attempt to remove record from child node */
     if(depth > 1) {
         if(H5B2_remove_internal(hdr, dxpl_id, depth_decreased, swap_loc, depth - 1,
-                new_cache_info, new_cache_info_flags_ptr, new_node_ptr, udata, op, op_data) < 0)
+                new_cache_info, new_cache_info_flags_ptr, next_pos, new_node_ptr, udata, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node")
     } /* end if */
     else {
-        if(H5B2_remove_leaf(hdr, dxpl_id, new_node_ptr, udata, op, op_data) < 0)
+        if(H5B2_remove_leaf(hdr, dxpl_id, new_node_ptr, next_pos, udata, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node")
     } /* end else */
 
@@ -2355,8 +2426,8 @@ done:
  */
 herr_t
 H5B2_remove_leaf_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
-    H5B2_node_ptr_t *curr_node_ptr, unsigned idx, H5B2_remove_t op,
-    void *op_data)
+    H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos,
+    unsigned idx, H5B2_remove_t op, void *op_data)
 {
     H5B2_leaf_t *leaf;                  /* Pointer to leaf node */
     haddr_t     leaf_addr = HADDR_UNDEF;  /* Leaf address on disk */
@@ -2380,6 +2451,27 @@ H5B2_remove_leaf_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
     HDassert(leaf->nrec == curr_node_ptr->node_nrec);
     HDassert(idx < leaf->nrec);
 
+    /* Check for invalidating the min/max record for the tree */
+    if(H5B2_POS_MIDDLE != curr_pos) {
+        /* (Don't use 'else' for the idx check, to allow for root leaf node) */
+        if(idx == 0) {
+            if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                if(hdr->min_native_rec) {
+                    HDfree(hdr->min_native_rec);
+                    hdr->min_native_rec = NULL;
+                } /* end if */
+            } /* end if */
+        } /* end if */
+        if(idx == (unsigned)(leaf->nrec - 1)) {
+            if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                if(hdr->max_native_rec) {
+                    HDfree(hdr->max_native_rec);
+                    hdr->max_native_rec = NULL;
+                } /* end if */
+            } /* end if */
+        } /* end if */
+    } /* end if */
+
     /* Make 'remove' callback if there is one */
     if(op)
         if((op)(H5B2_LEAF_NREC(leaf, hdr, idx), op_data) < 0)
@@ -2434,13 +2526,14 @@ herr_t
 H5B2_remove_internal_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
     hbool_t *depth_decreased, void *swap_loc, unsigned depth,
     H5AC_info_t *parent_cache_info, unsigned *parent_cache_info_flags_ptr,
-    H5B2_node_ptr_t *curr_node_ptr, hsize_t n, H5B2_remove_t op,
-    void *op_data)
+    H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos, hsize_t n,
+    H5B2_remove_t op, void *op_data)
 {
     H5AC_info_t *new_cache_info;        /* Pointer to new cache info */
     unsigned *new_cache_info_flags_ptr = NULL;
     H5B2_node_ptr_t *new_node_ptr;      /* Pointer to new node pointer */
     H5B2_internal_t *internal;          /* Pointer to internal node */
+    H5B2_nodepos_t next_pos = H5B2_POS_MIDDLE;  /* Position of next node */
     unsigned internal_flags = H5AC__NO_FLAGS_SET;
     haddr_t internal_addr;              /* Address of internal node */
     size_t      merge_nrec;             /* Number of records to merge node at */
@@ -2494,6 +2587,9 @@ H5B2_remove_internal_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
 
         /* Set flag to indicate root was collapsed */
         collapsed_root = TRUE;
+
+        /* Indicate position of next node */
+        next_pos = H5B2_POS_ROOT;
     } /* end if */
     /* Merge or redistribute child node pointers, if necessary */
     else {
@@ -2641,16 +2737,28 @@ H5B2_remove_internal_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
         new_cache_info_flags_ptr = &internal_flags;
         new_cache_info = &internal->cache_info;
         new_node_ptr = &internal->node_ptrs[idx];
+
+        /* Indicate position of next node */
+        if(H5B2_POS_MIDDLE != curr_pos) {
+            if(idx == 0) {
+                if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                    next_pos = H5B2_POS_LEFT;
+            } /* end if */
+            else if(idx == internal->nrec) {
+                if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                    next_pos = H5B2_POS_RIGHT;
+            } /* end if */
+        } /* end if */
     } /* end else */
 
     /* Attempt to remove record from child node */
     if(depth > 1) {
         if(H5B2_remove_internal_by_idx(hdr, dxpl_id, depth_decreased, swap_loc, depth - 1,
-                new_cache_info, new_cache_info_flags_ptr, new_node_ptr, n, op, op_data) < 0)
+                new_cache_info, new_cache_info_flags_ptr, new_node_ptr, next_pos, n, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node")
     } /* end if */
     else {
-        if(H5B2_remove_leaf_by_idx(hdr, dxpl_id, new_node_ptr, (unsigned)n, op, op_data) < 0)
+        if(H5B2_remove_leaf_by_idx(hdr, dxpl_id, new_node_ptr, next_pos, (unsigned)n, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node")
     } /* end else */
 
diff --git a/src/H5B2pkg.h b/src/H5B2pkg.h
index b820853..7a538bd 100644
--- a/src/H5B2pkg.h
+++ b/src/H5B2pkg.h
@@ -172,6 +172,8 @@ typedef struct H5B2_hdr_t {
     uint8_t	*page;	        /* Common disk page for I/O */
     size_t      *nat_off;       /* Array of offsets of native records */
     H5B2_node_info_t *node_info; /* Table of node info structs for current depth of B-tree */
+    uint8_t     *min_native_rec;   /* Pointer to minimum native record                  */
+    uint8_t     *max_native_rec;   /* Pointer to maximum native record                  */
 
     /* Client information (not stored) */
     const H5B2_class_t *cls;	/* Class of B-tree client */
@@ -208,6 +210,14 @@ struct H5B2_t {
     H5F_t      *f;              /* Pointer to file for v2 B-tree */
 };
 
+/* Node position, for min/max determination */
+typedef enum H5B2_nodepos_t {
+    H5B2_POS_ROOT,              /* Node is root (i.e. both right & left-most in tree) */
+    H5B2_POS_RIGHT,             /* Node is right-most in tree, at a given depth */
+    H5B2_POS_LEFT,              /* Node is left-most in tree, at a given depth */
+    H5B2_POS_MIDDLE             /* Node is neither right or left-most in tree */
+} H5B2_nodepos_t;
+
 /* Callback info for loading a free space header into the cache */
 typedef struct H5B2_hdr_cache_ud_t {
     H5F_t *f;                   /* File that v2 b-tree header is within */
@@ -304,9 +314,9 @@ H5_DLL herr_t H5B2_internal_free(H5B2_internal_t *i);
 /* Routines for inserting records */
 H5_DLL herr_t H5B2_insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id,
     unsigned depth, unsigned *parent_cache_info_flags_ptr,
-    H5B2_node_ptr_t *curr_node_ptr, void *udata);
+    H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos, void *udata);
 H5_DLL herr_t H5B2_insert_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id,
-    H5B2_node_ptr_t *curr_node_ptr, void *udata);
+    H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos, void *udata);
 
 /* Routines for iterating over nodes/records */
 H5_DLL herr_t H5B2_iterate_node(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth,
@@ -326,19 +336,21 @@ H5_DLL herr_t H5B2_neighbor_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id,
 
 /* Routines for removing records */
 H5_DLL herr_t H5B2_remove_internal(H5B2_hdr_t *hdr, hid_t dxpl_id,
-    hbool_t *depth_decreased, void *swap_loc, unsigned depth, H5AC_info_t *parent_cache_info,
-    hbool_t * parent_cache_info_dirtied_ptr, H5B2_node_ptr_t *curr_node_ptr, void *udata,
+    hbool_t *depth_decreased, void *swap_loc, unsigned depth,
+    H5AC_info_t *parent_cache_info, hbool_t * parent_cache_info_dirtied_ptr,
+    H5B2_nodepos_t curr_pos, H5B2_node_ptr_t *curr_node_ptr, void *udata,
     H5B2_remove_t op, void *op_data);
 H5_DLL herr_t H5B2_remove_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id,
-    H5B2_node_ptr_t *curr_node_ptr, void *udata, H5B2_remove_t op,
-    void *op_data);
+    H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos,
+    void *udata, H5B2_remove_t op, void *op_data);
 H5_DLL herr_t H5B2_remove_internal_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
-    hbool_t *depth_decreased, void *swap_loc, unsigned depth, H5AC_info_t *parent_cache_info,
-    hbool_t * parent_cache_info_dirtied_ptr, H5B2_node_ptr_t *curr_node_ptr, hsize_t idx,
+    hbool_t *depth_decreased, void *swap_loc, unsigned depth,
+    H5AC_info_t *parent_cache_info, hbool_t * parent_cache_info_dirtied_ptr,
+    H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos, hsize_t idx,
     H5B2_remove_t op, void *op_data);
 H5_DLL herr_t H5B2_remove_leaf_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
-    H5B2_node_ptr_t *curr_node_ptr, unsigned idx, H5B2_remove_t op,
-    void *op_data);
+    H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos,
+    unsigned idx, H5B2_remove_t op, void *op_data);
 
 /* Routines for deleting nodes */
 H5_DLL herr_t H5B2_delete_node(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth,
diff --git a/src/H5B2stat.c b/src/H5B2stat.c
index 5e48a6f..5d159ed 100644
--- a/src/H5B2stat.c
+++ b/src/H5B2stat.c
@@ -13,10 +13,10 @@
  * access to either file, you may request a copy from help@hdfgroup.org.     *
  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 
-/* Programmer:  Quincey Koziol <koziol@ncsa.uiuc.edu>
+/* Programmer:  Quincey Koziol <koziol@hdfgroup.org>
  *              Monday, March  6, 2006
  *
- * Purpose:	v2 B-tree metadata statistics functions.
+ * Purpose:     v2 B-tree metadata statistics functions.
  *
  */
 
@@ -24,15 +24,15 @@
 /* Module Setup */
 /****************/
 
-#define H5B2_PACKAGE		/*suppress error about including H5B2pkg  */
+#define H5B2_PACKAGE        /* Suppress error about including H5B2pkg   */
 
 
 /***********/
 /* Headers */
 /***********/
-#include "H5private.h"		/* Generic Functions			*/
-#include "H5B2pkg.h"		/* v2 B-trees				*/
-#include "H5Eprivate.h"		/* Error handling		  	*/
+#include "H5private.h"      /* Generic Functions                        */
+#include "H5B2pkg.h"        /* v2 B-trees                               */
+#include "H5Eprivate.h"     /* Error handling                           */
 
 
 /****************/
@@ -71,14 +71,13 @@
 
 
 /*-------------------------------------------------------------------------
- * Function:	H5B2_stat_info
+ * Function:    H5B2_stat_info
  *
- * Purpose:	Retrieve metadata statistics for a v2 B-tree
+ * Purpose:     Retrieve metadata statistics for a v2 B-tree
  *
- * Return:	Success:	non-negative
- *		Failure:	negative
+ * Return:      SUCCEED (Can't fail)
  *
- * Programmer:	Quincey Koziol
+ * Programmer:  Quincey Koziol
  *              Monday, March  6, 2006
  *
  *-------------------------------------------------------------------------
@@ -105,7 +104,7 @@ H5B2_stat_info(H5B2_t *bt2, H5B2_stat_t *info)
  * Purpose:     Iterate over all the records in the B-tree, collecting
  *              storage info.
  *
- * Return:      non-negative on success, negative on error
+ * Return:      SUCCEED/FAIL
  *
  * Programmer:  Vailin Choi
  *              June 19 2007
@@ -115,7 +114,7 @@ H5B2_stat_info(H5B2_t *bt2, H5B2_stat_t *info)
 herr_t
 H5B2_size(H5B2_t *bt2, hid_t dxpl_id, hsize_t *btree_size)
 {
-    H5B2_hdr_t	*hdr;                   /* Pointer to the B-tree header */
+    H5B2_hdr_t  *hdr;                   /* Pointer to the B-tree header */
     herr_t      ret_value = SUCCEED;    /* Return value */
 
     FUNC_ENTER_NOAPI(FAIL)