B-trees and B+ trees

Use a B-tree when one node can hold many keys and fetching a node is expensive. Database and storage indexes often organize keys this way.

Put several separators in one node

                   [20 | 40]
                 /     |     \
          [5 | 10] [25 | 30] [50 | 60]

lookup 30: compare with 20 and 40 -> middle child -> find 30

A B-tree is a balanced search tree with multiple keys and children per node. It is not a binary tree. Within a node, keys are sorted. The keys separate its children's ranges. Every leaf has the same depth.

An ordered set stores keys; an ordered map also stores values. A B-tree can implement either interface. Library names such as BTreeSet and BTreeMap describe that combination. A hash set or hash map implements the same membership or association operations with different ordering and performance tradeoffs.

Trace a split

Use a B-tree with minimum degree t = 2. Each node holds at most 2t − 1 = 3 keys. Each non-root node holds at least t − 1 = 1 key. An internal node with k keys has k + 1 children. The root has special minimum-occupancy rules.

Insert 5, 10, and 20 into an empty leaf. Before inserting 6, split the full root:

[5 | 10 | 20]       ->       [10]
                            /  \
                          [5]  [20]

insert 6           ->       [10]
                            /  \
                       [5 | 6] [20]

Promote the median key, 10, to a new root. The smaller and larger keys form separate children. This raises every leaf's depth together, preserving balance.

A common insertion algorithm splits full children before descending into them. The parent then has room for the promoted key. Reaching a non-full leaf lets you insert the new key in sorted order.

Trace deletion repair

Start with root [10] and leaves [5] and [20 | 30]. Deleting 5 would leave its leaf empty. Borrow through the parent: move 10 down to the left leaf and move 20 up to replace it.

Before:        [10]           After:        [20]
              /    \                      /    \
            [5]  [20 | 30]              [10]   [30]

If a sibling has no spare key, merge two children with their parent separator. With root [10] and leaves [5] and [20], deleting 5 can leave a single root leaf [10 | 20]. An empty root is replaced by its only child, reducing every leaf's depth together.

Deleting an internal key also needs a predecessor, successor, or merge before completing the removal. A production implementation must repair occupancy and move child pointers as well as keys. The search example below intentionally does not implement those repairs.

B+ trees keep records at the leaves

In a B+ tree, internal keys guide searches; records live in leaves. Leaves are usually linked in sorted order. After locating a range's first key, a scan can continue from leaf to leaf.

In a conventional B-tree, records can also live in internal nodes. Both keep logarithmic height; their record placement and range-scan behavior differ. Exact occupancy and split rules vary between implementations.

With fanout B, height is O(log_B n). Search touches that many nodes; binary search within nodes gives O(log n) comparisons overall. Reading a page-sized node can bring many separators into memory at once. Insertions and deletions may shift O(B) entries per affected node, so fewer node visits do not mean free updates. Storage is O(n) under the occupancy rules.

Balanced binary trees use smaller nodes and fewer local shifts. Sorted arrays are compact but shift O(n) items for updates. B-trees trade larger local edits for a shallower tree and nearby keys.

Predict and modify

1. How many children does an internal node with three keys have?
2. Why can't one leaf grow deeper without changing the others?
3. Add a validator for sorted keys, child ranges, occupancy, and equal leaf depth.

from bisect import bisect_left


class Node:
    def __init__(self, keys, children=None):
        self.keys = keys
        self.children = children or []


def contains(node, key):
    while True:
        index = bisect_left(node.keys, key)
        if index < len(node.keys) and node.keys[index] == key:
            return True
        if not node.children:
            return False
        node = node.children[index]


root = Node([20, 40], [Node([5, 10]), Node([25, 30]), Node([50, 60])])
for key in [5, 10, 20, 25, 30, 40, 50, 60]:
    assert contains(root, key)
for key in [0, 19, 21, 39, 41, 61]:
    assert not contains(root, key)
assert not contains(Node([]), 1)

Next: Heaps and priority queues.