B-Trees

1Order m: many keys in one node

A B-tree of order m is a multi-way search tree. Every node has at most m children and therefore at most m-1 keys, stored in sorted order. Every node except the root has at least \lceil m/2 \rceil children and \lceil m/2 \rceil - 1 keys. All leaves sit at the same depth, so the tree is perfectly balanced in levels even though a node may hold one key or many.

The root is the occupancy exception: it may have as few as one key and two children (or be a single leaf when the tree is tiny). That is how a B-tree is allowed to start.

This topic uses the children convention for m. Some books call m the maximum number of keys instead — count children before you count keys.

Figure. Order-3 B-tree used for the rest of the topic. Root holds 10 and 20; three leaves hold 5, then 15, then 25 and 30. All leaves at one depth.

What order 3 allows

1. CapAt most 3 children and 2 keys in any node.
2. Floor (non-root)At least 2 children and 1 key.
3. Same depthEvery leaf is at the same level — there is no AVL-style zigzag spine.

2Search follows one child per node

Search in a B-tree is binary-search-tree search with a wider node. At a node you scan (or binary-search) the sorted keys. If the target equals a key, you are done — in a classical B-tree the record pointer may sit right there. If the target is less than the first key you take the leftmost child; if it sits between two keys you take the child between them; if it is larger than the last key you take the rightmost child.

You visit O(\log_m n) nodes. Work inside a node is O(m) for a linear scan, or O(\log m) if you binary-search the keys. For disk, the node count is the I/O count, which is why a large m is the point.

Figure. Search for 25: root says go right of 20; the right leaf holds 25. Same tree as the occupancy figure — two nodes on the path.

Search for 25

1. At the rootKeys 10, 20. 25 > 20, so take the right child.
2. At the right leafKeys 25, 30. 25 is present — hit.
3. A missSearch for 17 would take the middle child [15] and die there. Insert would hang 17 in that leaf.

3Insert splits an overfull node at its median

Insert searches to a leaf and writes the new key in sorted order. If the leaf then has m keys it is overfull. Split: take the median key, push it into the parent, and leave the keys left of the median in the old node and the keys right of the median in a new sibling. The parent gains one key and one child. If the parent overflows, split it the same way.

A split at the root is the only way the tree grows a new level — B-trees grow at the top. Leaves do not sprout downward.

Insert 30 into [10, 20]

1. Write in the leafThe only node is [10,20]. 30 belongs at the end: [10,20,30].
2. OverflowOrder 3 allows 2 keys. Three keys is illegal.
3. Median upMedian 20 becomes a new root. Left leaf [10], right leaf [30].

Split a full child

def split_child(parent, i, full):
    mid = len(full.keys) // 2
    median = full.keys[mid]
    right = Node(keys=full.keys[mid + 1:],
                 children=full.children[mid + 1:])
    full.keys = full.keys[:mid]
    full.children = full.children[: mid + 1]
    parent.keys.insert(i, median)
    parent.children.insert(i + 1, right)

Coding lab. Split the overfull order-3 leaf runs in the app, with checks on your output.

4Delete: borrow through the parent, or merge

Delete starts by locating the key. If it sits in an internal node, replace it by its in-order predecessor (or successor) in a leaf and delete that leaf copy — the same idea as BST delete, but the replacement lives in a leaf. After the leaf loses a key, check occupancy.

If the leaf still has at least \lceil m/2 \rceil - 1 keys, stop. If it underflows, try to borrow: a sibling with a spare key rotates one key through the parent separator. If no sibling can spare a key, merge the underflowing node with a sibling and pull the parent separator down into the merged node. A merge can underflow the parent, so delete walks up just as AVL delete does.

Delete 15 (borrow from the right)

1. Drop the leaf key[15] becomes empty — below the 1-key floor.
2. Left cannot lend[5] already has the minimum one key.
3. Right can lend[25,30] has a spare. Separator 20 moves down; 25 moves up. Leaves become [5], [20], [30]; root becomes [10,25].

5Fan-out cuts I/O, not just pointer hops

A binary AVL of a million keys has height about 20. A B-tree of order m = 101 (100 keys per node) has height about \log_{101}(10^6) \approx 3. On disk each node is a page, so those numbers are page reads. That is the whole reason B-trees exist: one I/O should move you across many keys.

Pick m from the page size, not from taste. A 4 KiB page holding 8-byte keys and 8-byte child pointers supports on the order of a hundred children. Shrinking m to 3 for a disk index throws the I/O advantage away.

Figure. Nodes visited to search 10^6 keys: about 20 in a binary tree, 3 in an order-101 B-tree. On disk those bars are page reads.

Height for n = 10^6

1. Binary\lceil \log_2 10^6 \rceil \approx 20 levels.
2. Order 101\lceil \log_{101} 10^6 \rceil = 3 because 101^2 = 10201 and 101^3 \approx 1.03 \times 10^6.
3. Read as I/OThree page reads versus twenty, assuming one node per page.

6Filesystems and databases, and the B+ fork

B-trees (and their B+ cousins) sit under filesystems and database indexes because a node is sized to a disk page and a search is a handful of I/Os. That is a different job from an in-memory AVL: same word balanced, different unit of cost.

A classical B-tree may store a record pointer with a key at any level, so a hit can stop early. A B+ tree keeps every record pointer in the leaves, uses internal nodes only as a router, and usually links the leaves so a range scan walks a list instead of re-descending. Production databases almost always pick B+. This topic stays with the classical B-tree algorithms; the B-versus-B+ structural split is the indexing lesson, not a second copy of it.

Figure. Qualitative fit, not a shared unit: AVL for RAM maps, B-tree for disk point lookups, B+ when the workload is range scans on disk.

Which tree for which store

1. RAM, ordered mapAVL or red-black — pointer hops are cheap.
2. Disk pagesB-tree or B+ tree — fan-out sized to the page.
3. Range scans on diskB+ tree, because leaves are linked and hold every key.