18. B-Trees

Exercises

18.1-1

By property 5.a, such a tree could have "empty" nodes, which makes no sense.

18.1-2

Only for $t \in \{2,3\}$ the lower and upper bounds are valid by property 5.

18.1-3

The allowed configurations are:

1. Tree 1 (Root [2]): Left child [1] (1 key), Right child [3, 4, 5] (3 keys).

2. Tree 2 (Root [3]): Left child [1, 2] (2 keys), Right child [4, 5] (2 keys).

3. Tree 3 (Root [4]): Left child [1, 2, 3] (3 keys), Right child [5] (1 key).

4. Tree 4 (Root [2, 4]): Left child [1] (1 key), Middle child [3] (1 key), Right child [5] (1 key).

18.1-4

We must assume that every single node in the tree is packed to its absolute maximum capacity. This gives

$$n = \underbrace{(2t-1)}_{\text{Keys per node}} \times \underbrace{\sum_{i=0}^{h} (2t)^i}_{\text{Total nodes}}= (2t)^{h+1} - 1.$$

18.1-5

It is a 2-3-4 tree (see Exercise 13.1-4).

18.2-1

Use the Data Structure Visualizations tool and select the options Max. Degree 4 (corresponds to minimum degree 2) and Preemptive Split / Merge. Insert the keys in oder from the book and watch how the initially empty B-tree grows.

18.2-2

There is only one redundant Disk-Read in a scenario where the root node is split. Namely, after splitting it, the B-Tree-Insert procedure calls B-Tree-Insert-Nonfull with the new root. Since it is not a leaf node, the helper function blindly fetches one of the freshly split halves from the disk, even though it was just manipulated in memory a moment prior.

Because a Disk-Write is only ever issued immediately following a mutation of the specific node's data, the algorithm never writes a block to disk that is identical to what is already stored there.

18.2-3

According to Exercise 18.1-4, the minimum height would be 1. Notice that insertion can never reduce the height of a B-tree. The book uses the preemptive split strategy, which forces the split of the root as soon as it becomes full (contains 3 keys). To insert 15 keys into a tree we would need 4 full leaves as direct children of the root. Just prior to putting anything into the 4th child, the root will be split, since it would have 3 keys. Therefore, the height would increase to 2.

★ 18.2-4

We may expect between $\lfloor n/3 \rfloor$ and $\lceil n/2 \rceil$ nodes if the keys were inserted in a random order, distributing the keys evenly and keeping the nodes relatively full. However, sequential insertions completely break normal expectations.

Suppose we insert keys in a strictly increasing order. Consequently, each new key will be placed into the rightmost leaf. Let $h$ be the height of the resulting B-tree. The nodes on the rightmost path (which there are $h + 1$ of) will contain 2 or 3 keys, but the rest of the tree will strictly contain 1 key per node. Therefore, the number of nodes in the tree will be $n-\Theta(\lg n)=O(n)$.

Follow Exercise 18.2-1 and insert the keys $\{1,\dots,15\}$ in sequential order. The final B-tree will have 11 nodes most of them having a single key.

18.2-5

To implement this, let $t$ be the minimum degree for internal nodes (as before) and $t'$ (where $t' > t$) be the minimum degree for leaf nodes. Since the definition of a full node now depends on its type, we first define a quick helper function to abstract the capacity limit:

Min-Degree(x)
 1  if x.leaf
 2      return t'
 3  else
 4      return t

The other procedures are depicted below (only changes are listed). We don't need to alter the tree creation code.

B-Tree-Insert(T, k)
 ...
 2  if r.n == 2 * Min-Degree(r) - 1
 ...

B-Tree-Insert-Nonfull(x, k)
 ...
13      if x.c[i].n == 2 * Min-Degree(x.c[i]) - 1
...

B-Tree-Split-Child(x, i)
 ...
 4  m = Min-Degree(y)  
 5  z.n = m - 1                       
 6  for j = 1 to m - 1                
 7      z.key[j] = y.key[j + m]      
 8  if not y.leaf                     
 9      for j = 1 to m
10          z.c[j] = y.c[j + m]          
11  y.n = m - 1                       
...

18.2-6

In this case, the while loop of lines 2–3 would take $O(\lg t)$ time within each node, and the total CPU time becomes $O((\lg t)h) = O((\lg t) (\log_t n))=O((\lg t) (\lg n/\lg t))=O(\lg n)$.

18.2-7

Assume that the CPU time was optimized based on the previous exercise. The total disk read time $T$ can be approximated by

$$T(t) \approx \log_t n \cdot (a + bt)= \ln n \underbrace{\left( \frac{a + bt}{\ln t} \right)}_{f(t)}.$$

To minimize $T$ we need to minimize $f(t)$, thus

$$f'(t) = \frac{b \ln t - (a + bt)\left(\frac{1}{t}\right)}{(\ln t)^2} = 0 \implies \boxed{\ln t - 1 = \frac{a}{bt}}.$$

This is the general equation we would use to numerically solve for the optimal $t$ given any constants $a$ and $b$. We can use WolframAlpha to solve this equation with concrete values for these constants. An optimal value of $t$ for the case in which $a = 5$ milliseconds and $b = 10$ microseconds is $t=129$.

18.3-1

The results of deleting C, P, and V, in order, from the tree of Figure 18.8(f).

18.3-2

GeeksforGeeks has a nice article about the delete operation in B-tree that contains a full implementation in various programming languages. It completely follows the algorithm from the book. The only difference is that disk operations are not included; these should be inserted to bring nodes into memory or write changes back to disk.

Problems

18-1 Stacks on secondary storage

a.

The worst-case number of disk accesses is $\Theta(n)$, since each stack operation accesses a disk. The CPU time is $\Theta(nm)$.

b.

The worst-case number of disk accesses required for $n$ PUSH operations is $\Theta(\lceil n/m \rceil)$. The CPU time is $\Theta(n)$.

c.

The asymptotic times fall back to those from part (a). The worst-case sequence is $m+1$ PUSH operations, followed by a pattern of POP, POP, PUSH, PUSH, POP, POP, etc. The single block kept in memory is continuously invalidated.

d.

Let the two consecutive blocks be $B_1$ and $B_2$. Whenever the top of the stack moves beyond $B_2$, then write $B_1$ to disk, let $B_2$ become $B_1$ and read the new $B_2$ from disk.Whenever the top of stack moves before $B_1$, then write $B_2$ to disk, let $B_1$ become $B_2$ and read the new $B_1$ from disk. Obviously, a disk read/write occurs only after $m$ stack operations in the worst-case, which ensures amortized costs as specified.

18-2 Joining and splitting 2-3-4 trees

a.

Define $x.height$ as follows:

$$x.height = \begin{cases} 0 &\text{if } x \text{ is a leaf, }\\ 1+x.c_1.height &\text{otherwise}. \end{cases}$$

Recall that all leaves of a B-tree are at the same depth, so the heights of all children of a node are the same. The property can be easily maintained in $O(1)$ time for all operations:

• Node creation: When a new leaf is allocated during insertion, its height is immediately set to 0.

• Splitting: When a node is split, the newly allocated sibling simply copies the height of the original node. If the root splits, the newly allocated parent root evaluates the above formula to get a height of .

• Merging: When two nodes are merged, the resulting node just retains the height of the original siblings.

b.

The core idea is to attach the shorter tree to the taller tree at the exact level where their heights match. If both trees are exactly the same height, the join is trivial and takes $O(1)$ time:

• Allocate a new root node $T.root$ and set $k$ as its only key.

• Make $T'.root$ its left child and $T''.root$ its right child.

• Set $T.root.height = h' + 1$.

• Return $T$ as the new B-tree.

Otherwise, assume $h'>h''$ (the other direction is symmetrical). We must attach $T''$ to the rightmost edge of $T'$.

1. Traverse the Right Spine: Start at $T'.root$ and walk down the rightmost child pointers.

2. Preemptive Split: As you descend, check if the child you are about to step into is full. If it is, immediately call B-Tree-Splt-Child on it. This guarantees that whatever node we eventually insert $k$ into will have enough room.

3. Stop at the Correct Height: Use the $x.height$ attribute to stop your descent exactly when you reach a node $x$ that is at height $h'' + 1$.

4. Insert and Attach:

   1. Because of the preemptive splits, node $x$ is guaranteed to have at most 2 keys.

   2. Append $k$ to the end of node $x$'s keys.

   3. Append $T''.root$ to the end of node $x$'s child pointers (so it sits to the right of $k$).

5. Return $T'$.

There is one edge case that must be handled separately, as in B-Tree-Insert. We should split the root if it is full before step 1.

c.

Let's trace the path $p$ from the root down to $k$. At any given node $x$ along this path, the algorithm determines it must descend into a specific child pointer $x.c_j$ to find $k$. By the definition of a B-tree, everything to the left of $x.c_j$ is strictly less than any key inside $x.c_j$. Therefore:

• The keys $x.key_1, \dots, x.key_{j-1}$ belong to $S'$.

• The subtrees $x.c_1, \dots, x.c_{j-1}$ belong entirely to $S'$.

Because the path continues down into $x.c_j$, all elements found further down the path will be strictly greater than the left-hanging subtrees and keys of the current node $x.c_j$. Therefore, to form the sequence $\{T'_0, T'_1, \dots, T'_m\}$ and $\{k'_1, k'_2, \dots, k'_m\}$ in strictly increasing order $y < k'_i < z$, we simply collect the left-hanging subtrees and keys top-down as we walk path $p$.

• The leftmost subtree of the root becomes $T'_0$.

• It is followed by $k'_1$ (which is $root.key_1$).

• We continue collecting left-to-right at the root, and then proceed down the path, appending the left-hanging components of each subsequent node.

Because we collect the trees $\{T'_0, T'_1, \dots, T'_m\}$ top-down along path $p$, their heights are monotonically decreasing, that is $height(T'_i) \le height(T'_{i-1})$.

The set $S''$ (keys greater than $k$) is formed by the exact symmetrical logic, but the collection direction must be reversed to maintain the increasing order. We must collect the right-hanging subtrees and keys bottom-up, hence $height(T''_i) \ge height(T''_{i-1})$.

d.

Based on part (c), we can form the subtrees and keys to construct $S'$ and $S''$. The process is the same for both of them, so we describe it only for $S'$:

1. Let $T'=T_m$

2. For $i=m\dots1$

   1. Let $T'=\text{Join}(T', T_{i-1},k_i)$

3. Return $T'$

Observe that the total running time is $O(\lg n)$, since the differences in heights telescope.