18.2 Basic operations on B-trees
18.2-1
Show the results of inserting the keys
$$F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E$$
in order into an empty B-tree with minimum degree $2$. Draw only the configurations of the tree just before some node must split, and also draw the final configuration.
(Omit!)
18.2-2
Explain under what circumstances, if any, redundant $\text{DISK-READ}$ or $\text{DISK-WRITE}$ operations occur during the course of executing a call to $\text{B-TREE-INSERT}$. (A redundant $\text{DISK-READ}$ is a $\text{DISK-READ}$ for a page that is already in memory. A redundant $\text{DISK-WRITE}$ writes to disk a page of information that is identical to what is already stored there.)
In order to insert the key into a full child node but without its parent being full, we need the following operations:
- $\text{DISK-READ}$: Key placement
- $\text{DISK-WRITE}$: Split nodes
- $\text{DISK-READ}$: Get to the parent
- $\text{DISK-WRITE}$: Fill parent
If both were full, we'd have to do the same, but instead of the final step, repeat the above to split the parent node and write into the child nodes. With both considerations in mind, there should never be a redundant $\text{DISK-READ}$ or $\text{DISK-WRITE}$ on a $\text{B-TREE-INSERT}$.
18.2-3
Explain how to find the minimum key stored in a B-tree and how to find the predecessor of a given key stored in a B-tree.
-
Finding the minimum in a B-tree is quite similar to finding a minimum in a binary search tree. We need to find the left most leaf for the given root, and return the first key.
- PRE: $x$ is a node on the B-tree $T$. The top level call is $\text{B-TREE-FIND-MIN}(T.root)$.
- POST: $\text{FCTVAL}$ is the minimum key stored in the subtree rooted at $x$.
-
Finding the predecessor of a given key $x.key_i$ is according to the following rules:
- If $x$ is not a leaf, return the maximum key in the $i$-th child of $x$, which is also the maximum key of the subtree rooted at $x.c_i$.
- If $x$ is a leaf and $i > 1$, return the $(i - 1)$st key of $x$, i.e., $x.key_{i - 1}$.
-
Otherwise, look for the last node y (from the bottom up) and $j > 0$, such that $x.key_i$ is the leftmost key in $y.c_j$; if $j = 1$, return $\text{NIL}$ since $x.key_i$ is the minimum key in the tree; otherwise we return $y.key_{j - 1}$.
- PRE: $x$ is a node on the B-tree $T$. $i$ is the index of the key.
- POST: $\text{FCTVAL}$ is the predecessor of $x.key_i$.
B-TREE-FIND-PREDECESSOR(x, i) if !x.leaf DISK-READ(x.c[i]) return B-TREE-FIND-MAX(x.c[i]) else if i > 1 // x is a leaf and i > 1 return x.key[i - 1] else z = x while true if z.p == NIL // z is root return NIL // z.key[i] is the minimum key in T; no predecessor y = z.p j = 1 DISK-READ(y.c[1]) while y.c[j] != x j = j + 1 DISK-READ(y.c[j]) if j == 1 z = y else return y.key[j - 1]- PRE: $x$ is a node on the B-tree $T$. The top level call is $\text{B-TREE-FIND-MAX}(T.root)$.
- POST: $\text{FCTVAL}$ is the maximum key stored in the subtree rooted at $x$.
18.2-4 $\star$
Suppose that we insert the keys $\{1, 2, \ldots, n\}$ into an empty B-tree with minimum degree 2. How many nodes does the final B-tree have?
The final tree can have as many as $n - 1$ nodes. Unless $n = 1$ there cannot ever be $n$ nodes since we only ever insert a key into a non-empty node, so there will always be at least one node with $2$ keys.
Next observe that we will never have more than one key in a node which is not a right spine of our B-tree. This is because every key we insert is larger than all keys stored in the tree, so it will be inserted into the right spine of the tree. Nodes not in the right spine are a result of splits, and since $t = 2$, every split results in child nodes with one key each. The fewest possible number of nodes occurs when every node in the right spine has $3$ keys. In this case, $n = 2h + 2^{h + 1} - 1$ where $h$ is the height of the B-tree, and the number of nodes is $2^{h + 1} - 1$. Asymptotically these are the same, so the number of nodes is $\Theta(n)$.
18.2-5
Since leaf nodes require no pointers to children, they could conceivably use a different (larger) $t$ value than internal nodes for the same disk page size. Show how to modify the procedures for creating and inserting into a B-tree to handle this variation.
You would modify the insertion procedure by, in $\text{B-TREE-INSERT}$, check if the node is a leaf, and if it is, only split it if there twice as many keys stored as expected. Also, if an element needs to be inserted into a full leaf, we would split the leaf into two separate leaves, each of which doesn't have too many keys stored in it.
18.2-6
Suppose that we were to implement $\text{B-TREE-SEARCH}$ to use binary search rather than linear search within each node. Show that this change makes the CPU time required $O(\lg n)$, independently of how $t$ might be chosen as a function of $n$.
As in the $\text{TREE-SEARCH}$ procedure for binary search trees, the nodes encountered during the recursion form a simple path downward from the root of the tree. Thus, the $\text{B-TREE-SEARCH}$ procedure needs $O(h) = O(\log_t n)$ CPU time to search along the path, where $h$ is the height of the B-tree and $n$ is the number of keys in the B-tree, and we know that $h \le \log_t \frac{n + 1}{2}$. Since the number of keys in each nodeis less than $2t - 1$, a binary search within each node is $O(\lg t)$. So the total time is:
$$ \begin{aligned} O(\lg t \cdot \log_t n) & = O(\lg t \cdot \frac{\lg n}{\lg t}) & \text{by changing the base of the logarithm.} \\ & = O(\lg n). \end{aligned} $$
Thus, the CPU time required is $O(\lg n)$.
18.2-7
Suppose that disk hardware allows us to choose the size of a disk page arbitrarily, but that the time it takes to read the disk page is $a + bt$, where $a$ and $b$ are specified constants and $t$ is the minimum degree for a B-tree using pages of the selected size. Describe how to choose $t$ so as to minimize (approximately) the B-tree search time. Suggest an optimal value of $t$ for the case in which $a = 5$ milliseconds and $b = 10$ microseconds.
$$\min \log_t n \cdot (a + bt) = \min \frac{a + bt}{\ln t}$$
$$\frac{\partial}{\partial t} (\frac{a + bt}{\ln t}) = - \frac{a + bt - bt \ln t}{t \ln^2 t}$$
$$ \begin{aligned} a + bt & = bt \ln t \\ 5 + 10t & = 10t \ln t \\ t & = e^{W \left(\frac{1}{2e} \right) + 1}, \\ \end{aligned} $$
where $W$ is the LambertW function, and we should choose $t = 3$.