Assume that you have just built a dense B+ tree index using Alternative(2) on a
ID: 671610 • Letter: A
Question
Assume that you have just built a dense B+ tree index using Alternative(2) on a heap file containing 100,000 records of 1,000 bytes each. The key field for this B+ tree index is a 100-byte string. Pointers (i.e., record ids and page ids) are (at most) 10-byte values. The size of one disk page is 4096 bytes. The index was built in a bottom-up fashion using the bulk-loading algorithm, and the nodes at each level were filled up as much as possible. Part A What is the fanout of the tree? How many entries does a leaf node have? How many levels does the resulting tree have? For each level of the tree, how many nodes are at that level? [Level 1 denotes the root level] Level 1 Level 3 Leaf node level Part B How many levels would the resulting tree have if Alternative 1 is used? What would the fanout of the tree be in that case? How many leaf nodes would the tree have? Part C How many levels would the resulting tree (from Part B) with all pages 75 percent full? How many entries would a leaf node have in this situation? How many leaf nodes would the tree have?Explanation / Answer
1.
B+ trees can store a relatively large number of pointers to child nodes in each node. "Fanout" in this context refers to this number of pointers per node. B+ trees minimize the depth of the tree (and therefore the number of hops to reach a leaf node) by employing high fanout: linking many children from each node.
Fanout refers to the number of children for an internal node. High fanout would make the tree bushy and hence have a low height. Since the time to operate on a B+ tree is proportional to the height of the tree, a high fanout would make the tree more efficient.
2.
Leaf nodes have no children, but are constrained so that the number of keys must be at least(b/2) and at most b - 1 . In the situation where a B+ tree is nearly empty, it only contains one node, which is a leaf node. (The root is also the single leaf, in this case.) This node is permitted to have as little as one key if necessary, and at most b.
3.
All leaves appear in the same level. At each level, the search chooses the child pointer (subtree) whose separation values are on either side of the search value.