Broot, Bnodes, and Chunks

`Broot`, `Bnodes`, and `Chunks`

Let's examine the b-tree structures in Listings 6.9 and 6.10.

Listing 6.9. `q4> fields struct broot`

 We start off with a pointer to the root (first) bnode and  record the depth of the b-tree  0 0 4 0 *     b_root  4 0 4 0 int   b_depth Next we find the number of pages mapped and the number of swap pages reserved for this tree  8 0 4 0 int   b_npages 12 0 4 0 int   b_rpages The page list pointer directs us to this region's page list,  and nfrag points to the next available chunk (required if we need to grow the tree) 16 0 4 0 *     b_list 20 0 4 0 int   b_nfrag This pointer gets us back to the region structure this b-tree  serves 24 0 4 0 *     b_rp 28 0 4 0 int   b_protoidx There are two sets of prototype dbd structures used when the  b-tree is being initialized or grown; the protoidx gives an  index into the tree where we switch from using the first  prototype to the second 32 0 0 3 u_int b_proto1.dbd_type 32 3 3 5 u_int b_proto1.dbd_data 36 0 0 3 u_int b_proto2.dbd_type 36 3 3 5 u_int b_proto2.dbd_data This array stores information about ranges of pages that need to have their copy-on-write bit set 40 0 4 0 int   b_vproto.v_start[0] 44 0 4 0 int   b_vproto.v_start[1] 48 0 4 0 int   b_vproto.v_start[2] 52 0 4 0 int   b_vproto.v_start[3] 56 0 4 0 int   b_vproto.v_start[4] 60 0 4 0 int   b_vproto.v_end[0] 64 0 4 0 int   b_vproto.v_end[1] 68 0 4 0 int   b_vproto.v_end[2] 72 0 4 0 int   b_vproto.v_end[3] 76 0 4 0 int   b_vproto.v_end[4] To speed up repetitive references, the two most recent key/ value data pairs are cached here 80 0 4 0 int   b_key_cache[0] 84 0 4 0 int   b_key_cache[1] 88 0 4 0 *     b_val_cache[0] 92 0 4 0 *     b_val_cache[1]

Listing 6.10. `q4> fields struct bnode`

 For a 29th order b-tree each bnode contains 30 keys and 31  values. The value array contains either pointers to actual  chunk structures or pointers to the next lower level of the b- tree structure   0 0 4 0 int b_key[0]   4 0 4 0 int b_key[1]   -------------------- 112 0 4 0 int b_key[28] 116 0 4 0 int b_key[29] number of valid key/values in this bnode 120 0 4 0 int b_nelem 124 0 4 0 *   b_down[0] 128 0 4 0 *   b_down[1]   -------------------- 240 0 4 0 *   b_down[29] 244 0 4 0 *   b_down[30] pads to align the structure 248 0 4 0 int pad[0] 252 0 4 0 int pad[1]

Now that we have defined the various parts of the b-tree, we need to assemble them.

Table of content