Recitation 2: 2-3 Trees and B-Trees

What this lecture covers

This recitation covers B-trees, generalized balanced search trees where each node holds multiple keys and has multiple children, starting from the simplest case, the 2-3 tree. The TA motivates B-trees with the memory hierarchy: unlike a plain binary search tree, a B-tree can be tuned so each node fits one disk block, cutting the number of expensive disk accesses needed for a search.

After watching, you can state the structural rules for a B-tree with branching factor B, walk through searching a B-tree, and carry out the split operation used for insertion and the rotation and merge operations used for deletion, including how overflow and underflow can propagate up toward the root.

Key ideas

• B-tree structure: each non-root node has between B and 2B - 1 children and between B - 1 and 2B - 2 keys; the root is exempt from the lower bound; all leaves sit at the same depth.
• Why B-trees over binary search trees: both give Theta(log n) depth, but B-trees are designed around the memory hierarchy, letting one disk access fetch a whole node (sized to match a cache/disk block) instead of one key at a time.
• Search: at each node, scan its sorted keys to find where the target fits, either finding it directly or descending into the appropriate child interval, giving Theta(log n) time overall.
• Insertion and overflow: inserting a key can push a node's key count to 2B - 1, one over the limit; the fix is a split, removing the middle key, dividing the remaining keys into two nodes, and inserting the middle key into the parent, which may itself overflow and require splitting, potentially all the way to the root.
• Deletion at an internal node: deleting a key that isn't in a leaf is handled by swapping it with the rightmost key of its left subtree or leftmost key of its right subtree (both of which are leaves), reducing the problem to deleting from a leaf.
• Deletion and underflow: removing a key from a leaf can drop a node below the minimum key count; the fix is either a rotation (borrowing a key from a sibling that has more than the minimum, via the parent) or a merge (combining the node, a sibling, and a parent key into one node), and a merge can propagate underflow upward just as a split propagates overflow.

Walkthrough

Why use B-trees over binary search trees (0:00)

The TA defines the 2-3 tree, where each node has one or two keys and two or three children, sorted so an in-order traversal yields sorted keys, exactly like a binary search tree but with more branching per node. He then poses the motivating question: since both structures give logarithmic depth, why prefer B-trees? The answer is the memory hierarchy, described with a simplified two-level model of a fast, finite-size cache holding fixed-size blocks and a slower, effectively infinite disk. Accessing disk brings in a whole block at once, so a data structure whose nodes are sized to match a block lets each disk access do useful work across many keys, unlike a binary search tree, which is stored one key per node.

B-tree specification (2:16)

The branching factor B bounds the number of children per node between B and 2B - 1, and correspondingly the number of keys between B - 1 and 2B - 2; the root is exempt from the lower bound. All leaves are required to sit at the same depth, and only leaves have no children. Searching a B-tree mirrors binary search tree search but scans each node's sorted list of keys to decide which child interval to descend into, giving Theta(log n) time.

Insertion and the split operation (13:40)

Inserting a key can leave a node with 2B - 1 keys, one too many. The split operation removes the middle key, divides the remaining keys evenly into two new nodes, and inserts the middle key (with pointers to the two new nodes) into the parent. This can cause the parent to overflow in turn, requiring another split, and the process can chain all the way up to the root; if the root itself overflows, a new root is created. The recitation works through inserting keys 16 and then 2 into a B = 4 example tree, showing a split propagate one level up to the parent.

Deletion, rotation, and merge (21:27)

Deletion has two stages. First, if the key to delete is in an internal node, it is swapped with the rightmost key of its left subtree or leftmost key of its right subtree, both leaves, reducing the problem to deleting from a leaf. Second, once a leaf loses a key it may become underful. If a sibling has more than the minimum number of keys, a rotation borrows one: a key moves from the sibling up into the parent, and the corresponding key moves from the parent down into the underful node. If no sibling can spare a key, a merge combines the underful node, a sibling, and the separating key from the parent into a single node; this shrinks the parent, which can itself become underful and require the same fix one level up. The recitation demonstrates both cases: deleting 38 and then 41 triggers a chain of merges that propagates up two levels, while deleting 20 and 24 later triggers a straightforward rotation.

Before you watch

• Review binary search tree operations (search, insertion, deletion) since this recitation builds directly on that model.
• Familiarity with the two lectures on divide and conquer earlier in the week is helpful context for the course, though not required to follow this session on B-trees.

Check your understanding

1. Why does a B-tree reduce the number of disk accesses compared to a binary search tree, even though both have Theta(log n) depth?
2. What are the minimum and maximum number of keys a non-root node can hold in a B-tree with branching factor B, and why is the root exempt from the minimum?
3. Walk through what happens when inserting a key causes a node to overflow: what does a split do, and under what condition does the overflow propagate further up the tree?
4. Why does deleting a key from an internal node get converted into deleting a key from a leaf, and which leaf is chosen?
5. What distinguishes the rotation case from the merge case when a node becomes underful after deletion, and why can a merge cause underflow to propagate upward?