[svn-r9939] Purpose:

    New feature

Description:
    Expand v2 B-tree code to support splitting the root node when enough
records are inserted and move metadata cache callbacks into their own source
file.

Platforms tested:
    FreeBSD 4.11 (sleipnir) w/parallel
    Too minor for h5committest

1 files changed, 326 insertions, 681 deletions

diff --git a/src/H5B2.c b/src/H5B2.c
index 1307c07..99f43c4 100644
--- a/src/H5B2.c
+++ b/src/H5B2.c
@@ -38,16 +38,6 @@
 
 /* Local macros */
 
-/* B-tree version #'s */
-#define H5B2_HDR_VERSION 0              /* Header */
-#define H5B2_LEAF_VERSION 0             /* Leaf node */
-
-/* Size of storage for number of records per node (on disk) */
-#define H5B2_SIZEOF_RECORDS_PER_NODE    2
-
-/* Size of a "node pointer" (on disk) */
-#define H5B2_NODE_POINTER_SIZE(f)       (H5F_SIZEOF_ADDR(f)+H5B2_SIZEOF_RECORDS_PER_NODE+H5F_SIZEOF_SIZE(f))
-
 /* Format overhead for each node (on disk) */
 #define H5B2_OVERHEAD_SIZE              (H5B2_SIZEOF_MAGIC+1)   /* Signature + version # */
 
@@ -57,21 +47,9 @@
 /* Number of records that fit into leaf node */
 #define H5B2_NUM_LEAF_REC(n,r)          (((n)-H5B2_OVERHEAD_SIZE)/(r))
 
-/* Size of the B-tree header on disk */
-#define H5B2_HEADER_SIZE(f)     (                                             \
-    4 + /* Signature */                                                       \
-    1 + /* Version */                                                         \
-    1 + /* Tree type */                                                       \
-    4 + /* Node size, in bytes */                                             \
-    2 + /* Key size, in bytes */                                              \
-    2 + /* Depth of tree */                                                   \
-    2 + /* Split % of full (as integer, ie. "98" means 98%) */                \
-    2 + /* Merge % of full (as integer, ie. "98" means 98%) */                \
-    H5B2_NODE_POINTER_SIZE(f))  /* Node pointer to root node in tree */
-
 /* Macro to retrieve pointer to i'th native key for leaf node */
-#define H5B2_INT_NKEY(i,shared,idx)  ((i)->int_native+(shared)->int_nat_off[(idx)])
-#define H5B2_LEAF_NKEY(l,shared,idx)  ((l)->leaf_native+(shared)->leaf_nat_off[(idx)])
+#define H5B2_INT_NKEY(i,shared,idx)  ((i)->int_native+(shared)->nat_off[(idx)])
+#define H5B2_LEAF_NKEY(l,shared,idx)  ((l)->leaf_native+(shared)->nat_off[(idx)])
 
 
 /* Local typedefs */
@@ -79,69 +57,39 @@
 /* Local prototypes */
 
 /* Helper functions */
-static herr_t H5B2_shared_free (void *_shared);
-static herr_t H5B2_shared_init (H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type,
-    size_t node_size, size_t rkey_size, unsigned split_percent, unsigned merge_percent);
 static herr_t H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node_ptr);
 static int H5B2_locate_record(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
     unsigned nrec, size_t *rec_off, const uint8_t *native,
     const void *udata);
+static herr_t H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2,
+    const H5B2_shared_t *shared);
+static herr_t H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2,
+    H5B2_node_ptr_t *node_ptr);
 
-/* Metadata cache callbacks */
-static H5B2_t *H5B2_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void *udata);
-static herr_t H5B2_cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_t *b);
-static herr_t H5B2_cache_hdr_dest(H5F_t *f, H5B2_t *b);
-static herr_t H5B2_cache_hdr_clear(H5F_t *f, H5B2_t *b, hbool_t destroy);
-static herr_t H5B2_cache_hdr_size(const H5F_t *f, const H5B2_t *bt, size_t *size_ptr);
-static H5B2_leaf_t *H5B2_cache_leaf_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void *udata);
-static herr_t H5B2_cache_leaf_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_leaf_t *l);
-static herr_t H5B2_cache_leaf_dest(H5F_t *f, H5B2_leaf_t *l);
-static herr_t H5B2_cache_leaf_clear(H5F_t *f, H5B2_leaf_t *l, hbool_t destroy);
-static herr_t H5B2_cache_leaf_size(const H5F_t *f, const H5B2_leaf_t *l, size_t *size_ptr);
 
-/* Static variables */
+/* Package variables */
+
+/* Declare a free list to manage the H5B2_t struct */
+H5FL_DEFINE(H5B2_t);
+
+/* Declare a free list to manage the H5B2_internal_t struct */
+H5FL_DEFINE(H5B2_internal_t);
+
+/* Declare a free list to manage the H5B2_leaf_t struct */
+H5FL_DEFINE(H5B2_leaf_t);
+
 
-/* H5B2 inherits cache-like properties from H5AC */
-const H5AC_class_t H5AC_BT2_HDR[1] = {{
-    H5AC_BT2_HDR_ID,
-    (H5AC_load_func_t)H5B2_cache_hdr_load,
-    (H5AC_flush_func_t)H5B2_cache_hdr_flush,
-    (H5AC_dest_func_t)H5B2_cache_hdr_dest,
-    (H5AC_clear_func_t)H5B2_cache_hdr_clear,
-    (H5AC_size_func_t)H5B2_cache_hdr_size,
-}};
-
-/* H5B2 inherits cache-like properties from H5AC */
-static const H5AC_class_t H5AC_BT2_LEAF[1] = {{
-    H5AC_BT2_LEAF_ID,
-    (H5AC_load_func_t)H5B2_cache_leaf_load,
-    (H5AC_flush_func_t)H5B2_cache_leaf_flush,
-    (H5AC_dest_func_t)H5B2_cache_leaf_dest,
-    (H5AC_clear_func_t)H5B2_cache_leaf_clear,
-    (H5AC_size_func_t)H5B2_cache_leaf_size,
-}};
-
-
-/* Declare a free list to manage B-tree header data to/from disk */
-H5FL_BLK_DEFINE_STATIC(header_block);
+/* Static variables */
 
 /* Declare a free list to manage B-tree node pages to/from disk */
 H5FL_BLK_DEFINE_STATIC(node_page);
 
-/* Declare a free list to manage the 'H5B2_node_ptr_t' sequence information */
-H5FL_SEQ_DEFINE_STATIC(H5B2_node_ptr_t);
-
 /* Declare a free list to manage the 'size_t' sequence information */
 H5FL_SEQ_DEFINE_STATIC(size_t);
 
-/* Declare a free list to manage the H5B2_t struct */
-H5FL_DEFINE_STATIC(H5B2_t);
-
 /* Declare a free list to manage the H5B2_shared_t struct */
 H5FL_DEFINE_STATIC(H5B2_shared_t);
 
-/* Declare a free list to manage the H5B2_leaf_t struct */
-H5FL_DEFINE_STATIC(H5B2_leaf_t);
 
 
 /*-------------------------------------------------------------------------
@@ -157,7 +105,7 @@ H5FL_DEFINE_STATIC(H5B2_leaf_t);
  *
  *-------------------------------------------------------------------------
  */
-static herr_t
+herr_t
 H5B2_shared_init (H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type,
     size_t node_size, size_t rkey_size,
     unsigned split_percent, unsigned merge_percent)
@@ -207,28 +155,12 @@ H5B2_shared_init (H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type,
 	HGOTO_ERROR (H5E_RESOURCE, H5E_CANTINIT, NULL, "can't create internal node node pointer block factory")
 
     /* Allocate array of pointers to internal node native keys */
-    if((shared->int_nat_off=H5FL_SEQ_MALLOC(size_t,shared->internal_nrec))==NULL)
+    if((shared->nat_off=H5FL_SEQ_MALLOC(size_t,MAX(shared->internal_nrec,shared->leaf_nrec)))==NULL)
         HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
 
-    /* Allocate array of pointers to leaf node native keys */
-    if((shared->leaf_nat_off=H5FL_SEQ_MALLOC(size_t,shared->leaf_nrec))==NULL)
-        HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
-
-    /* Allocate array of pointers to internal node node pointers */
-    if((shared->node_ptr_off=H5FL_SEQ_MALLOC(H5B2_node_ptr_t,(shared->internal_nrec+1)))==NULL)
-        HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
-
-    /* Initialize offsets in internal node native key block */
-    for(u=0; u<shared->internal_nrec; u++)
-        shared->int_nat_off[u]=type->nkey_size*u;
-
-    /* Initialize offsets in leaf node native key block */
-    for(u=0; u<shared->leaf_nrec; u++)
-        shared->leaf_nat_off[u]=type->nkey_size*u;
-
-    /* Initialize offsets in internal node node pointer block */
-    for(u=0; u<(shared->internal_nrec+1); u++)
-        shared->node_ptr_off[u]=sizeof(H5B2_node_ptr_t)*u;
+    /* Initialize offsets in native key block */
+    for(u=0; u<MAX(shared->internal_nrec,shared->leaf_nrec); u++)
+        shared->nat_off[u]=type->nkey_size*u;
 
     /* Make shared B-tree info reference counted */
     if(NULL==(bt2->shared=H5RC_create(shared,H5B2_shared_free)))
@@ -256,7 +188,7 @@ done:
  *
  *-------------------------------------------------------------------------
  */
-static herr_t
+herr_t
 H5B2_shared_free (void *_shared)
 {
     H5B2_shared_t *shared = (H5B2_shared_t *)_shared;
@@ -286,17 +218,9 @@ H5B2_shared_free (void *_shared)
         if(H5FL_fac_term(shared->node_ptr_fac)<0)
             HGOTO_ERROR (H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy internal node node pointer block factory")
 
-    /* Free the array of offsets into the internal node native key block */
-    if(shared->int_nat_off)
-        H5FL_SEQ_FREE(size_t,shared->int_nat_off);
-
-    /* Free the array of offsets into the leaf node native key block */
-    if(shared->leaf_nat_off)
-        H5FL_SEQ_FREE(size_t,shared->leaf_nat_off);
-
-    /* Free the array of offsets into the internal node node pointer block */
-    if(shared->node_ptr_off)
-        H5FL_SEQ_FREE(H5B2_node_ptr_t,shared->node_ptr_off);
+    /* Free the array of offsets into the native key block */
+    if(shared->nat_off)
+        H5FL_SEQ_FREE(size_t,shared->nat_off);
 
     /* Free the shared B-tree info itself */
     H5FL_FREE(H5B2_shared_t,shared);
@@ -378,340 +302,158 @@ done:
 
 
 /*-------------------------------------------------------------------------
- * Function:	H5B2_cache_hdr_load
+ * Function:	H5B2_locate_record
  *
- * Purpose:	Loads a B-tree header from the disk.
+ * Purpose:	Performs a binary search to locate a record in a sorted
+ *              array of records.
  *
- * Return:	Success:	Pointer to a new B-tree.
+ * Return:	Success:	Non-negative array index where new record
+ *                              should be inserted
  *
- *		Failure:	NULL
+ *		Failure:	Negative, if record already is in array of
+ *                              records.
  *
  * Programmer:	Quincey Koziol
  *		koziol@ncsa.uiuc.edu
- *		Feb 1 2005
+ *		Feb  3 2005
  *
  *-------------------------------------------------------------------------
  */
-static H5B2_t *
-H5B2_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void UNUSED *udata)
+static int
+H5B2_locate_record(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
+    unsigned nrec, size_t *rec_off, const uint8_t *native,
+    const void *udata)
 {
-    const H5B2_class_t	*type = (const H5B2_class_t *) _type;
-    size_t node_size, rkey_size;        /* Size info for B-tree */
-    unsigned split_percent, merge_percent;      /* Split & merge info for B-tree */
-    H5B2_t		*bt2 = NULL;
-    size_t		size;
-    uint8_t		*buf = NULL;
-    uint8_t		*p;             /* Pointer into raw data buffer */
-    H5B2_t		*ret_value;
-
-    FUNC_ENTER_NOAPI(H5B2_cache_hdr_load, NULL)
-
-    /* Check arguments */
-    HDassert(f);
-    HDassert(H5F_addr_defined(addr));
-    HDassert(type);
-
-    if (NULL==(bt2 = H5FL_MALLOC(H5B2_t)))
-	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed")
-    HDmemset(&bt2->cache_info,0,sizeof(H5AC_info_t));
-
-    /* Compute the size of the B-tree header on disk */
-    size = H5B2_HEADER_SIZE(f);
-
-    /* Allocate temporary buffer */
-    if ((buf=H5FL_BLK_MALLOC(header_block,size))==NULL)
-        HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
-
-    /* Read header from disk */
-    if (H5F_block_read(f, H5FD_MEM_BTREE, addr, size, dxpl_id, buf)<0)
-	HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree header")
-
-    p = buf;
-
-    /* magic number */
-    if (HDmemcmp(p, H5B2_HDR_MAGIC, H5B2_SIZEOF_MAGIC))
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree header signature")
-    p += H5B2_SIZEOF_MAGIC;
-
-    /* version */
-    if (*p++ != H5B2_HDR_VERSION)
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree header version")
-
-    /* B-tree type */
-    if (*p++ != (uint8_t)type->id)
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "incorrect B-tree type")
-
-    /* node size (in bytes) */
-    UINT32DECODE(p, node_size);
-
-    /* raw key size (in bytes) */
-    UINT16DECODE(p, rkey_size);
-
-    /* depth of tree */
-    UINT16DECODE(p, bt2->depth);
-
-    /* split & merge %s */
-    UINT16DECODE(p, split_percent);
-    UINT16DECODE(p, merge_percent);
-
-    /* root node pointer */
-    H5F_addr_decode(f, (const uint8_t **)&p, &(bt2->root.addr));
-    UINT16DECODE(p, bt2->root.node_nrec);
-    H5F_DECODE_LENGTH(f, p, bt2->root.all_nrec);
+    unsigned	lo = 0, hi;     /* Low & high index values */
+    int         idx = 0;        /* Final index value */
+    int         cmp = -1;       /* Key comparison value */
 
-    /* Initialize shared B-tree info */
-    if(H5B2_shared_init(f, bt2, type, node_size, rkey_size, split_percent, merge_percent)<0)
-	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "can't create shared B-tree info")
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_locate_record)
 
-    /* Set return value */
-    ret_value = bt2;
+    hi = nrec;
+    while (lo < hi && cmp) {
+	idx = (lo + hi) / 2;
+	if ((cmp = (type->compare)(f, dxpl_id, udata, native+rec_off[idx])) < 0)
+	    hi = idx;
+	else
+	    lo = idx + 1;
+    }
+    if(cmp==0)
+        idx=(-1);
+    else if(cmp>0)
+        idx++;
 
-done:
-    if(buf)
-        H5FL_BLK_FREE(header_block,buf);
-    if (!ret_value && bt2)
-        (void)H5B2_cache_hdr_dest(f,bt2);
-    FUNC_LEAVE_NOAPI(ret_value)
-} /*lint !e818 Can't make udata a pointer to const */
+    FUNC_LEAVE_NOAPI(idx);
+} /* end H5B2_locate_record */
 
 
 /*-------------------------------------------------------------------------
- * Function:	H5B2_cache_hdr_flush
+ * Function:	H5B2_split_root
  *
- * Purpose:	Flushes a dirty B-tree header to disk.
+ * Purpose:	Split the root node
  *
- * Return:	Non-negative on success/Negative on failure
+ * Return:	Success:	Non-negative
+ *
+ *		Failure:	Negative
  *
  * Programmer:	Quincey Koziol
  *		koziol@ncsa.uiuc.edu
- *		Feb 1 2005
+ *		Feb  3 2005
  *
  *-------------------------------------------------------------------------
  */
 static herr_t
-H5B2_cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_t *bt2)
+H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, const H5B2_shared_t *shared)
 {
-    herr_t      ret_value = SUCCEED;    /* Return value */
+    herr_t ret_value=SUCCEED;           /* Return value */
 
-    FUNC_ENTER_NOAPI(H5B2_cache_hdr_flush, FAIL)
+    FUNC_ENTER_NOAPI_NOINIT(H5B2_split_root)
 
-    /* check arguments */
     HDassert(f);
-    HDassert(H5F_addr_defined(addr));
     HDassert(bt2);
+    HDassert(shared);
 
-    if (bt2->cache_info.is_dirty) {
-        H5B2_shared_t *shared;      /* Shared B-tree information */
-        uint8_t	*buf = NULL;
-        uint8_t *p;                 /* Pointer into raw data buffer */
-        size_t	size;
-
-        /* Get the pointer to the shared B-tree info */
-        shared=H5RC_GET_OBJ(bt2->shared);
-        HDassert(shared);
-
-        /* Compute the size of the B-tree header on disk */
-        size = H5B2_HEADER_SIZE(f);
-
-        /* Allocate temporary buffer */
-        if ((buf=H5FL_BLK_MALLOC(header_block,size))==NULL)
-            HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed");
-
-        p = buf;
-
-        /* magic number */
-        HDmemcpy(p, H5B2_HDR_MAGIC, H5B2_SIZEOF_MAGIC);
-        p += H5B2_SIZEOF_MAGIC;
-
-        /* version # */
-        *p++ = H5B2_HDR_VERSION;
-
-        /* b-tree type */
-        *p++ = shared->type->id;
-
-        /* node size (in bytes) */
-        UINT32ENCODE(p, shared->node_size);
-
-        /* raw key size (in bytes) */
-        UINT16ENCODE(p, shared->rkey_size);
+    if(bt2->depth==0) {
+        H5B2_internal_t *new_int=NULL;  /* Pointer to new internal node */
+        H5B2_leaf_t *old_leaf=NULL, *new_leaf=NULL;       /* Pointers to old & new leaf nodes */
+        H5B2_node_ptr_t new_int_ptr;    /* Node pointer to manage new internal node */
+        H5B2_node_ptr_t new_leaf_ptr;   /* Node pointer to manage new leaf node */
+        unsigned mid_record;            /* Index of "middle" record in current node */
 
-        /* depth of tree */
-        UINT16ENCODE(p, bt2->depth);
+        /* Create new leaf node */
+        new_leaf_ptr.all_nrec=new_leaf_ptr.node_nrec=0;
+        if(H5B2_create_leaf(f, dxpl_id, bt2, &new_leaf_ptr)<0)
+	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new leaf node")
 
-        /* split & merge %s */
-        UINT16ENCODE(p, shared->split_percent);
-        UINT16ENCODE(p, shared->merge_percent);
+        /* Determine "middle" record to promote to new root */
+        mid_record = shared->split_leaf_nrec/2;
 
-        /* root node pointer */
-        H5F_addr_encode(f, &p, bt2->root.addr);
-        UINT16ENCODE(p, bt2->root.node_nrec);
-        H5F_ENCODE_LENGTH(f, p, bt2->root.all_nrec);
+        /* Protect both leafs */
+        if (NULL == (old_leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, bt2->root.addr, shared->type, &(bt2->root), H5AC_WRITE)))
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node")
+        if (NULL == (new_leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, new_leaf_ptr.addr, shared->type, &new_leaf_ptr, H5AC_WRITE)))
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node")
 
-	/* Write the B-tree header. */
-	if (H5F_block_write(f, H5FD_MEM_BTREE, addr, size, dxpl_id, buf) < 0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFLUSH, FAIL, "unable to save B-tree header to disk")
+        /* Copy "upper half" of records to new leaf */
+        HDmemcpy(new_leaf->leaf_native,H5B2_LEAF_NKEY(old_leaf,shared,mid_record+1),shared->type->nkey_size*(shared->split_leaf_nrec-(mid_record+1)));
 
-        H5FL_BLK_FREE(header_block,buf);
+        /* Create new internal node */
+        new_int_ptr.all_nrec=new_int_ptr.node_nrec=0;
+        if(H5B2_create_internal(f, dxpl_id, bt2, &new_int_ptr)<0)
+	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new internal node")
 
-	bt2->cache_info.is_dirty = FALSE;
-    } /* end if */
+        /* Protect new internal node */
+        if (NULL == (new_int = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, new_int_ptr.addr, shared->type, &new_int_ptr, H5AC_WRITE)))
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree internal node")
 
-    if (destroy)
-        if (H5B2_cache_hdr_dest(f,bt2) < 0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree header")
+        /* Copy "middle" record to new internal node */
+        HDmemcpy(new_int->int_native,H5B2_LEAF_NKEY(old_leaf,shared,mid_record),shared->type->nkey_size);
 
-done:
-    FUNC_LEAVE_NOAPI(ret_value)
-} /* H5B2_cache_hdr_flush() */
+        /* Update record counts in leaf nodes */
+        bt2->root.all_nrec=bt2->root.node_nrec=old_leaf->nrec=mid_record;
+        new_leaf_ptr.all_nrec=new_leaf_ptr.node_nrec=new_leaf->nrec=shared->split_leaf_nrec-(mid_record+1);
 
-
-/*-------------------------------------------------------------------------
- * Function:	H5B_cache_hdr_dest
- *
- * Purpose:	Destroys a B-tree header in memory.
- *
- * Return:	Non-negative on success/Negative on failure
- *
- * Programmer:	Quincey Koziol
- *		koziol@ncsa.uiuc.edu
- *		Feb 1 2005
- *
- *-------------------------------------------------------------------------
- */
-/* ARGSUSED */
-static herr_t
-H5B2_cache_hdr_dest(H5F_t UNUSED *f, H5B2_t *bt2)
-{
-    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_hdr_dest)
+        /* Mark leaf nodes as dirty */
+        old_leaf->cache_info.is_dirty = TRUE;
+        new_leaf->cache_info.is_dirty = TRUE;
 
-    /*
-     * Check arguments.
-     */
-    HDassert(bt2);
+        /* Release leaf nodes */
+        if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, bt2->root.addr, old_leaf, H5AC__NO_FLAGS_SET) < 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node")
+        if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, new_leaf_ptr.addr, new_leaf, H5AC__NO_FLAGS_SET) < 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node")
 
-    /* Decrement reference count on shared B-tree info */
-    if(bt2->shared)
-        H5RC_DEC(bt2->shared);
+        /* Set internal node pointers to leaf nodes */
+        new_int->node_ptrs[0]=bt2->root;
+        new_int->node_ptrs[1]=new_leaf_ptr;
 
-    /* Free B-tree header info */
-    H5FL_FREE(H5B2_t,bt2);
+        /* Update record count in new internal node */
+        new_int->nrec = 1;
 
-    FUNC_LEAVE_NOAPI(SUCCEED)
-} /* end H5B2_cache_hdr_dest() */
+        /* Mark new internal node as dirty */
+        new_int->cache_info.is_dirty = TRUE;
 
-
-/*-------------------------------------------------------------------------
- * Function:	H5B2_cache_hdr_clear
- *
- * Purpose:	Mark a B-tree header in memory as non-dirty.
- *
- * Return:	Non-negative on success/Negative on failure
- *
- * Programmer:	Quincey Koziol
- *		koziol@ncsa.uiuc.edu
- *		Feb  1 2005
- *
- *-------------------------------------------------------------------------
- */
-static herr_t
-H5B2_cache_hdr_clear(H5F_t *f, H5B2_t *bt2, hbool_t destroy)
-{
-    herr_t ret_value = SUCCEED;
+        /* Release new internal node */
+        if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, new_int_ptr.addr, new_int, H5AC__NO_FLAGS_SET) < 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree internal node")
 
-    FUNC_ENTER_NOAPI_NOINIT(H5B2_cache_hdr_clear)
+        /* Update depth of B-tree */
+        bt2->depth++;
 
-    /*
-     * Check arguments.
-     */
-    HDassert(bt2);
+        /* Update pointer to B-tree's root node to pointer to new internal node */
+        bt2->root = new_int_ptr;
 
-    /* Reset the dirty flag.  */
-    bt2->cache_info.is_dirty = FALSE;
- 
-    if (destroy)
-        if (H5B2_cache_hdr_dest(f, bt2) < 0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree header")
+        /* Mark B-tree header as dirty */
+        bt2->cache_info.is_dirty = TRUE;
+    } /* end if */
+    else {
+HDfprintf(stderr,"%s: Need to split internal root! shared->split_int_nrec=%Zu\n",FUNC,shared->split_int_nrec);
+HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split internal root node yet")
+    } /* end else */
 
 done:
-    FUNC_LEAVE_NOAPI(ret_value)
-} /* end H5B2_cache_hdr_clear() */
-
-
-/*-------------------------------------------------------------------------
- * 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.
- *
- * Return:	Non-negative on success/Negative on failure
- *
- * Programmer:	Quincey Koziol
- *		koziol@ncsa.uiuc.edu
- *		Feb 1 2005
- *
- *-------------------------------------------------------------------------
- */
-static herr_t
-H5B2_cache_hdr_size(const H5F_t *f, const H5B2_t UNUSED *bt2, size_t *size_ptr)
-{
-    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_hdr_size)
-
-    /* check arguments */
-    HDassert(f);
-    HDassert(size_ptr);
-
-    /* Set size value */
-    *size_ptr = H5B2_HEADER_SIZE(f);
-
-    FUNC_LEAVE_NOAPI(SUCCEED)
-} /* H5B2_cache_hdr_size() */
-
-
-/*-------------------------------------------------------------------------
- * Function:	H5B2_locate_record
- *
- * Purpose:	Performs a binary search to locate a record in a sorted
- *              array of records.
- *
- * Return:	Success:	Non-negative array index where new record
- *                              should be inserted
- *
- *		Failure:	Negative, if record already is in array of
- *                              records.
- *
- * Programmer:	Quincey Koziol
- *		koziol@ncsa.uiuc.edu
- *		Feb  3 2005
- *
- *-------------------------------------------------------------------------
- */
-static int
-H5B2_locate_record(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
-    unsigned nrec, size_t *rec_off, const uint8_t *native,
-    const void *udata)
-{
-    unsigned	lo = 0, hi;     /* Low & high index values */
-    int         idx = 0;        /* Final index value */
-    int         cmp = -1;       /* Key comparison value */
-
-    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_locate_record)
-
-    hi = nrec;
-    while (lo < hi && cmp) {
-	idx = (lo + hi) / 2;
-	if ((cmp = (type->compare)(f, dxpl_id, udata, native+rec_off[idx])) < 0)
-	    hi = idx;
-	else
-	    lo = idx + 1;
-    }
-    if(cmp==0)
-        idx=(-1);
-    else if(cmp>0)
-        idx++;
-
-    FUNC_LEAVE_NOAPI(idx);
-} /* end H5B2_locate_record */
+    FUNC_LEAVE_NOAPI(ret_value);
+} /* end H5B2_split_root */
 
 
 /*-------------------------------------------------------------------------
@@ -733,11 +475,11 @@ herr_t
 H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
            void *udata)
 {
-    H5AC_info_t *cache_info;            /* Parent node's cache info */
     H5B2_t	*bt2=NULL;              /* Pointer to the B-tree header */
     H5B2_shared_t *shared;              /* Pointer to B-tree's shared information */
-    H5B2_node_ptr_t *node_ptr;          /* Pointer to node pointer info for current node */
-    unsigned    depth;                  /* Current depth of node */
+    H5B2_node_ptr_t leaf_ptr;           /* Node pointer info for leaf node */
+    H5B2_leaf_t *leaf=NULL;             /* Pointer to leaf node */
+    int         idx;                    /* Location of record which matches key */
     herr_t	ret_value = SUCCEED;
 
     FUNC_ENTER_NOAPI(H5B2_insert, FAIL)
@@ -764,71 +506,174 @@ H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
         /* Mark B-tree header as dirty, since we updated the address of the root node */
         bt2->cache_info.is_dirty = TRUE;
     } /* end if */
-depth=bt2->depth;
-node_ptr=&(bt2->root);
-cache_info=&(bt2->cache_info);
+    /* 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, 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;
+
+        /* Set initial node pointer for "current" node */
+        curr_node_ptr=&(bt2->root);
+
+        /* Find correct leaf to insert node into */
+        while(depth>0) {
+            /* Lock B-tree current node */
+            if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, shared->type, curr_node_ptr, H5AC_WRITE)))
+                HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree internal node")
+
+            /* 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 */
+            if((idx=H5B2_locate_record(f,dxpl_id,shared->type,internal->nrec,shared->nat_off,internal->int_native,udata))<0)
+                HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
 
-    /* Check if we are inserting in internal or leaf node */
-    if(depth==0) {
-        H5B2_leaf_t *leaf=NULL;      /* Pointer to leaf node */
-        int         idx;             /* Location of record which matches key */
+            /* Get node pointer for child */
+            child_node_ptr=&(internal->node_ptrs[idx]);
+
+            /* Preemptively split/redistribute a node we will enter */
+            if((depth==1 && child_node_ptr->node_nrec==shared->split_leaf_nrec) ||
+                    (depth>1 && child_node_ptr->node_nrec==shared->split_int_nrec)) {
+HDfprintf(stderr,"%s: need to split child node!, depth=%u\n",FUNC,depth);
+HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
+                /* Attempt to redistribute records among children */
+                /* Split children, if can't redistribute */
+                    /* Update record count info for current node to reflect new # of records (in parent) */
+                /* Update child_node_ptr (to reflect change in location from split/redistribution) */
+            } /* end if */
 
-        /* Look up the B-tree leaf node */
-        if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, shared->type, node_ptr, H5AC_WRITE)))
-            HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node")
+            /* Update record count (in parent) */
+            curr_node_ptr->all_nrec++;
 
-        /* Check for inserting into empty leaf */
-        if(node_ptr->node_nrec==0)
-            idx=0;
-        else {
-            /* Find correct location to insert this record and make room for it */
-            if((idx=H5B2_locate_record(f,dxpl_id,shared->type,leaf->nrec,shared->leaf_nat_off,leaf->leaf_native,udata))<0) {
-                /* Release the B-tree leaf node */
-                if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0)
-                    HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node")
+            /* Mark parent node as dirty */
+            parent_cache_info->is_dirty = TRUE;
 
-                HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
-            } /* end if */
+            /* 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_PROTECT, FAIL, "unable to release B-tree info")
 
-            /* Make room for new record */
-            if((unsigned)idx<leaf->nrec)
-                HDmemmove(H5B2_LEAF_NKEY(leaf,shared,idx+1),H5B2_LEAF_NKEY(leaf,shared,idx),shared->type->nkey_size*(leaf->nrec-idx));
-        } /* end else */
+            /* Transition "current" info into "parent" info */
+            parent_cache_info = curr_cache_info;
+            parent_addr = curr_addr;
+            parent_ptr = curr_ptr;
 
-        /* Make callback to store record in native form */
-        if((shared->type->store)(f,dxpl_id,udata,H5B2_LEAF_NKEY(leaf,shared,idx))<0) {
-            /* Release the B-tree leaf node */
-            if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0)
-                HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node")
+            /* Transition "child" node pointer to "current" node pointer */
+            curr_node_ptr = child_node_ptr;
 
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into leaf node")
-        } /* end if */
+            /* Decrement depth of current node */
+            depth--;
+        } /* end while */
+
+        /* 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;
+
+        /* 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_PROTECT, FAIL, "unable to release B-tree node")
+    } /* end if */
+    else {
+        /* Update record count for root node */
+        bt2->root.all_nrec++;
+        bt2->root.node_nrec++;
+
+        /* Mark parent node as dirty */
+        bt2->cache_info.is_dirty = TRUE;
+
+        /* Copy node pointer info for leaf */
+        leaf_ptr = bt2->root;
 
-        /* Update record # info in node pointer */
-        node_ptr->all_nrec++;
-        node_ptr->node_nrec++;
+        /* Release parent node */
+        if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree header info")
+        bt2=NULL;
+    } /* end else */
+
+    /* Must have a leaf node with enough space to insert a record now */
+    HDassert(H5F_addr_defined(leaf_ptr.addr));
+    HDassert((leaf_ptr.node_nrec-1)<shared->split_leaf_nrec); /* node pointer to leaf has already been incremented */
+
+    /* Look up the B-tree leaf node */
+    if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, shared->type, &leaf_ptr, H5AC_WRITE)))
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node")
+
+    /* Sanity check number of records */
+    HDassert(leaf_ptr.all_nrec==leaf_ptr.node_nrec);
+    HDassert(leaf->nrec==(leaf_ptr.node_nrec-1)); /* node pointer to leaf has already been incremented */
+
+    /* Check for inserting into empty leaf */
+    if(leaf->nrec==0)
+        idx=0;
+    else {
+        /* Sanity check for the leaf node being full */
+        HDassert(leaf->nrec!=shared->split_leaf_nrec);
 
-        /* Update number of records in node */
-        leaf->nrec++;
-        HDassert(node_ptr->node_nrec==leaf->nrec);
+        /* Find correct location to insert this record and make room for it */
+        if((idx=H5B2_locate_record(f,dxpl_id,shared->type,leaf->nrec,shared->nat_off,leaf->leaf_native,udata))<0) {
+            /* Release the B-tree leaf node */
+            if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0)
+                HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node")
 
-        /* Mark parent's node as dirty now */
-        cache_info->is_dirty = TRUE;
+            HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
+        } /* end if */
 
-        /* Mark leaf node as dirty also */
-        leaf->cache_info.is_dirty = TRUE;
+        /* Make room for new record */
+        if((unsigned)idx<leaf->nrec)
+            HDmemmove(H5B2_LEAF_NKEY(leaf,shared,idx+1),H5B2_LEAF_NKEY(leaf,shared,idx),shared->type->nkey_size*(leaf->nrec-idx));
+    } /* end else */
 
+    /* Make callback to store record in native form */
+    if((shared->type->store)(f,dxpl_id,udata,H5B2_LEAF_NKEY(leaf,shared,idx))<0) {
         /* Release the B-tree leaf node */
-        if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0)
+        if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node")
+
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into leaf node")
     } /* end if */
-    else {
-    } /* end else */
 
-done:
-    if (bt2 && H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0)
-        HDONE_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree header")
+    /* Update number of records in node */
+    leaf->nrec++;
+
+    /* Mark leaf node as dirty also */
+    leaf->cache_info.is_dirty = TRUE;
+
+    /* Release the B-tree leaf node */
+    if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0)
+        HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node")
 
+done:
     FUNC_LEAVE_NOAPI(ret_value)
 } /* H5B2_insert() */
 
@@ -847,7 +692,7 @@ done:
  *
  *-------------------------------------------------------------------------
  */
-herr_t
+static herr_t
 H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node_ptr)
 {
     H5B2_leaf_t *leaf=NULL;     /* Pointer to new leaf node created */
@@ -886,7 +731,7 @@ H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node_ptr
 
     /* Allocate space on disk for the leaf */
     if (HADDR_UNDEF==(node_ptr->addr=H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)shared->node_size)))
-	HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "file allocation failed for B-tree header")
+	HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "file allocation failed for B-tree leaf node")
 
     /* Cache the new B-tree node */
     if (H5AC_set(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0)
@@ -903,274 +748,74 @@ done:
 
 
 /*-------------------------------------------------------------------------
- * Function:	H5B2_cache_leaf_load
+ * Function:	H5B2_create_internal
  *
- * Purpose:	Loads a B-tree leaf from the disk.
- *
- * Return:	Success:	Pointer to a new B-tree leaf node.
+ * Purpose:	Creates empty internal node of a B-tree and update node pointer
+ *              to point to it.
  *
- *		Failure:	NULL
+ * Return:	Non-negative on success/Negative on failure
  *
  * Programmer:	Quincey Koziol
  *		koziol@ncsa.uiuc.edu
- *		Feb 2 2005
+ *		Feb  3 2005
  *
  *-------------------------------------------------------------------------
  */
-static H5B2_leaf_t *
-H5B2_cache_leaf_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_bt2, void *_node_ptr)
+static herr_t
+H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node_ptr)
 {
-    const H5B2_t	*bt2 = (const H5B2_t *)_bt2;
-    H5B2_node_ptr_t     *node_ptr = (H5B2_node_ptr_t *)_node_ptr;
-    H5B2_leaf_t		*leaf = NULL;
-    H5B2_shared_t 	*shared;      /* Shared B-tree information */
-    uint8_t		*p;             /* Pointer into raw data buffer */
-    H5B2_leaf_t		*ret_value;
+    H5B2_internal_t *internal=NULL;     /* Pointer to new internal node created */
+    H5B2_shared_t *shared;              /* Shared B-tree information */
+    herr_t	ret_value = SUCCEED;
 
-    FUNC_ENTER_NOAPI(H5B2_cache_leaf_load, NULL)
+    FUNC_ENTER_NOAPI(H5B2_create_internal, FAIL)
 
-    /* Check arguments */
+    /* Check arguments. */
     HDassert(f);
-    HDassert(H5F_addr_defined(addr));
     HDassert(bt2);
+    HDassert(node_ptr);
 
-    if (NULL==(leaf = H5FL_MALLOC(H5B2_leaf_t)))
-	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed")
-    HDmemset(&leaf->cache_info,0,sizeof(H5AC_info_t));
+    /* Allocate memory for internal node information */
+    if (NULL==(internal = H5FL_MALLOC(H5B2_internal_t)))
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal info")
+
+    /* Set metadata cache info */
+    HDmemset(&internal->cache_info,0,sizeof(H5AC_info_t));
+    internal->cache_info.is_dirty = TRUE;
 
     /* Share common B-tree information */
-    leaf->shared = bt2->shared;
-    H5RC_INC(leaf->shared);
+    internal->shared = bt2->shared;
+    H5RC_INC(internal->shared);
 
     /* Get the pointer to the shared B-tree info */
-    shared=H5RC_GET_OBJ(leaf->shared);
+    shared=H5RC_GET_OBJ(internal->shared);
     HDassert(shared);
 
-    /* Read header from disk */
-    if (H5F_block_read(f, H5FD_MEM_BTREE, addr, shared->node_size, dxpl_id, shared->page)<0)
-	HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree leaf node")
-
-    p = shared->page;
-
-    /* magic number */
-    if (HDmemcmp(p, H5B2_LEAF_MAGIC, H5B2_SIZEOF_MAGIC))
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree leaf node signature")
-    p += H5B2_SIZEOF_MAGIC;
-
-    /* version */
-    if (*p++ != H5B2_LEAF_VERSION)
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree header version")
-
-    /* B-tree type */
-    if (*p++ != (uint8_t)shared->type->id)
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "incorrect B-tree type")
-
     /* Allocate space for the native keys in memory */
-    if((leaf->leaf_native=H5FL_FAC_MALLOC(shared->leaf_fac))==NULL)
-	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree leaf native keys")
-
-HDfprintf(stderr,"%s: Deserialize leaf node records here!, node_ptr->node_nrec=%u\n",FUNC,node_ptr->node_nrec);
-
-    /* Set return value */
-    ret_value = leaf;
-
-done:
-    if (!ret_value && leaf)
-        (void)H5B2_cache_leaf_dest(f,leaf);
-    FUNC_LEAVE_NOAPI(ret_value)
-} /* H5B2_cache_leaf_load() */ /*lint !e818 Can't make udata a pointer to const */
-
-
-/*-------------------------------------------------------------------------
- * Function:	H5B2_cache_leaf_flush
- *
- * Purpose:	Flushes a dirty B-tree leaf node to disk.
- *
- * Return:	Non-negative on success/Negative on failure
- *
- * Programmer:	Quincey Koziol
- *		koziol@ncsa.uiuc.edu
- *		Feb 2 2005
- *
- *-------------------------------------------------------------------------
- */
-static herr_t
-H5B2_cache_leaf_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_leaf_t *leaf)
-{
-    herr_t      ret_value = SUCCEED;    /* Return value */
-
-    FUNC_ENTER_NOAPI(H5B2_cache_leaf_flush, FAIL)
-
-    /* check arguments */
-    HDassert(f);
-    HDassert(H5F_addr_defined(addr));
-    HDassert(leaf);
-
-    if (leaf->cache_info.is_dirty) {
-        H5B2_shared_t *shared;  /* Shared B-tree information */
-        uint8_t *p;             /* Pointer into raw data buffer */
-        uint8_t *native;        /* Pointer to native keys */
-        unsigned u;             /* Local index variable */
-
-        /* Get the pointer to the shared B-tree info */
-        shared=H5RC_GET_OBJ(leaf->shared);
-        HDassert(shared);
-
-        p = shared->page;
-
-        /* magic number */
-        HDmemcpy(p, H5B2_HDR_MAGIC, H5B2_SIZEOF_MAGIC);
-        p += H5B2_SIZEOF_MAGIC;
+    if((internal->int_native=H5FL_FAC_MALLOC(shared->int_fac))==NULL)
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal native keys")
 
-        /* version # */
-        *p++ = H5B2_LEAF_VERSION;
+    /* Allocate space for the node pointers in memory */
+    if((internal->node_ptrs=H5FL_FAC_MALLOC(shared->node_ptr_fac))==NULL)
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal node pointers")
 
-        /* b-tree type */
-        *p++ = shared->type->id;
-
-        /* Serialize records for leaf node */
-        native=leaf->leaf_native;
-        for(u=0; u<leaf->nrec; u++) {
-            /* Encode record */
-            if((shared->type->encode)(f,p,native)<0)
-                HGOTO_ERROR(H5E_BTREE, H5E_CANTENCODE, FAIL, "enable to encode B-tree record");
-
-            /* Move to next record */
-            p += shared->rkey_size;
-            native += shared->type->nkey_size;
-        } /* end for */
-
-	/* Write the B-tree leaf node */
-	if (H5F_block_write(f, H5FD_MEM_BTREE, addr, shared->node_size, dxpl_id, shared->page) < 0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFLUSH, FAIL, "unable to save B-tree leaf node to disk")
+    /* Set number of records */
+    internal->nrec=0;
 
-	leaf->cache_info.is_dirty = FALSE;
-    } /* end if */
+    /* Allocate space on disk for the internal node */
+    if (HADDR_UNDEF==(node_ptr->addr=H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)shared->node_size)))
+	HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "file allocation failed for B-tree internal node")
 
-    if (destroy)
-        if (H5B2_cache_leaf_dest(f,leaf) < 0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree leaf node")
+    /* Cache the new B-tree node */
+    if (H5AC_set(f, dxpl_id, H5AC_BT2_INT, node_ptr->addr, internal, H5AC__NO_FLAGS_SET) < 0)
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B-tree internal node to cache")
 
 done:
-    FUNC_LEAVE_NOAPI(ret_value)
-} /* H5B2_cache_leaf_flush() */
-
-
-/*-------------------------------------------------------------------------
- * Function:	H5B_cache_leaf_dest
- *
- * Purpose:	Destroys a B-tree leaf node in memory.
- *
- * Return:	Non-negative on success/Negative on failure
- *
- * Programmer:	Quincey Koziol
- *		koziol@ncsa.uiuc.edu
- *		Feb 2 2005
- *
- *-------------------------------------------------------------------------
- */
-/* ARGSUSED */
-static herr_t
-H5B2_cache_leaf_dest(H5F_t UNUSED *f, H5B2_leaf_t *leaf)
-{
-    H5B2_shared_t *shared;      /* Shared B-tree information */
-
-    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_leaf_dest)
-
-    /*
-     * Check arguments.
-     */
-    HDassert(leaf);
-
-    /* Get the pointer to the shared B-tree info */
-    shared=H5RC_GET_OBJ(leaf->shared);
-    HDassert(shared);
-
-    /* Release leaf's native key buffer */
-    if(leaf->leaf_native)
-        H5FL_FAC_FREE(shared->leaf_fac,leaf->leaf_native);
-
-    /* Decrement reference count on shared B-tree info */
-    if(leaf->shared)
-        H5RC_DEC(leaf->shared);
-
-    /* Free B-tree leaf node info */
-    H5FL_FREE(H5B2_leaf_t,leaf);
-
-    FUNC_LEAVE_NOAPI(SUCCEED)
-} /* end H5B2_cache_leaf_dest() */
-
-
-/*-------------------------------------------------------------------------
- * Function:	H5B2_cache_leaf_clear
- *
- * Purpose:	Mark a B-tree leaf node in memory as non-dirty.
- *
- * Return:	Non-negative on success/Negative on failure
- *
- * Programmer:	Quincey Koziol
- *		koziol@ncsa.uiuc.edu
- *		Feb  2 2005
- *
- *-------------------------------------------------------------------------
- */
-static herr_t
-H5B2_cache_leaf_clear(H5F_t *f, H5B2_leaf_t *leaf, hbool_t destroy)
-{
-    herr_t ret_value = SUCCEED;
-
-    FUNC_ENTER_NOAPI_NOINIT(H5B2_cache_leaf_clear)
-
-    /*
-     * Check arguments.
-     */
-    HDassert(leaf);
-
-    /* Reset the dirty flag.  */
-    leaf->cache_info.is_dirty = FALSE;
- 
-    if (destroy)
-        if (H5B2_cache_leaf_dest(f, leaf) < 0)
-	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree leaf node")
+    if (ret_value<0) {
+	if (internal)
+            (void)H5B2_cache_internal_dest(f,internal);
+    } /* end if */
 
-done:
     FUNC_LEAVE_NOAPI(ret_value)
-} /* end H5B2_cache_leaf_clear() */
-
-
-/*-------------------------------------------------------------------------
- * Function:	H5B2_cache_leaf_size
- *
- * Purpose:	Compute the size in bytes of a B-tree leaf node
- *		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
- *
- * Programmer:	Quincey Koziol
- *		koziol@ncsa.uiuc.edu
- *		Feb 2 2005
- *
- *-------------------------------------------------------------------------
- */
-static herr_t
-H5B2_cache_leaf_size(const H5F_t UNUSED *f, const H5B2_leaf_t *leaf, size_t *size_ptr)
-{
-    H5B2_shared_t *shared;      /* Shared B-tree information */
-
-    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_leaf_size)
-
-    /* check arguments */
-    HDassert(leaf);
-    HDassert(size_ptr);
-
-    /* Get the pointer to the shared B-tree info */
-    shared=H5RC_GET_OBJ(leaf->shared);
-    HDassert(shared);
-
-    /* Set size value */
-    *size_ptr = shared->node_size;
-
-    FUNC_LEAVE_NOAPI(SUCCEED)
-} /* H5B2_cache_leaf_size() */
+} /* H5B2_create_internal() */