Questions: B-Trees and Multi-Way Search Trees

Question 1

A database engineer doubles the branching factor of a B-tree from m=100 to m=200. What is the primary performance benefit for a dataset stored on disk?

• A. Each node now stores more keys, so the tree height decreases and fewer disk reads are needed per search
• B. Node splits become more frequent, keeping the tree more balanced
• C. Insertions no longer require propagating splits upward to the root
• D. The tree can now store twice as many keys in the same number of nodes

Answer: (A)

The height of a B-tree is O(log_m n). Doubling m roughly halves the height for large datasets: log_200(n) < log_100(n). Since each level corresponds to one disk read, fewer levels means fewer disk I/Os per search — and disk I/Os dominate the cost. This is why m is tuned to be as large as a disk block can hold: the branching factor directly determines how many disk reads a lookup requires.

Question 2

Why does the B-tree minimum occupancy rule require internal nodes to have at least ⌈m/2⌉ children?

• A. To prevent any single node from holding more keys than fit in a disk block
• B. To guarantee the tree remains balanced so all leaves stay at the same depth
• C. To ensure the tree never needs to perform node splits during insertion
• D. To match the number of keys in each node to the number of disk sectors

Answer: (B)

Without a minimum occupancy rule, deletions could leave nodes nearly empty, degenerating the tree into something resembling a linked list with O(n) height. The minimum of ⌈m/2⌉ children ensures that even after many deletions, nodes stay at least half full, bounding the height at O(log_m n). Crucially, this rule also guarantees balance: since every leaf is at the same depth and internal nodes must have enough children, the tree cannot become lopsided.

Question 3

In a B-tree, all leaves are always at the same depth because the tree grows upward by splitting the root when it overflows.

• T. True
• F. False

Answer: True

True. Unlike binary search trees that grow at the bottom (insertions always go to a leaf), B-trees grow at the top. Insertions find the appropriate leaf and insert there; if the leaf overflows, it splits and the median key is promoted to the parent. This split propagation can reach the root, and when the root splits, a new root is created — increasing the tree height by one. Because height increases only at the root and all new leaves are created at the current leaf level, every leaf stays at the same depth. This 'perfect balance' is the invariant that gives B-trees their guaranteed O(log_m n) performance.

Question 4

B-trees are mainly useful for database indexing and have no advantage in other contexts.

• T. True
• F. False

Answer: False

False. B-trees are valuable for any external-memory algorithm — any situation where data lives on a slower storage medium than the processor's cache. This includes file system directory structures (many OS file systems use B-tree variants), external sorting, geographic information systems, and any large-scale key-value store. The core principle — minimize the number of slow storage accesses by maximizing branching factor — applies wherever there is a significant latency gap between two storage layers, whether disk vs. RAM, RAM vs. cache, or even across network boundaries.

Question 5

Why is the branching factor m in a B-tree typically chosen to match the disk block size rather than, say, optimizing for CPU cache performance?

Model answer: Each disk read fetches an entire block regardless of how much data you actually need from it. By making B-tree nodes exactly the size of a disk block, each read fills one node completely — all m−1 keys and m child pointers are loaded in a single I/O. Binary search within the node happens in memory (fast), and only one more disk read is needed per level. This maximizes the 'useful work' per disk I/O. If nodes were smaller than a disk block, each read would waste most of the fetched bytes; if larger, one node access would require multiple disk reads.

The design principle is to match the data structure's unit of access (one node traversal) to the hardware's unit of access (one disk block). When these are aligned, the tree minimizes the number of disk I/Os, which dominate performance by a factor of ~100,000 over RAM accesses. This is a general principle in systems design: identify the bottleneck (disk I/O here), then design the data structure to minimize operations at that bottleneck.