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. |