B-Trees

The previous lesson showed that increasing the number of keys per node shortens the tree. This lesson asks: why stop that number at two or three?

The answer depends on where the data resides. If the data is in memory, the difference is small — memory access is already cheap. If the data is on disk, the situation changes, and this change has led an entire family of data structures to be designed around that condition.

The Block Reality

The memory hierarchy in the How Computers Work course placed persistent storage at the lowest layer: access is orders of magnitude slower than main memory.

The second, more decisive fact is that persistent storage is read at the block level. Even when only a single byte is requested, the entire block — on the order of kilobytes — is fetched. What determines the cost, therefore, is not the number of bytes read but how many blocks are read.

This directly changes tree design. In an in-memory tree, the goal is to reduce the number of comparisons; in a tree on disk, the goal is to reduce the number of node visits. Every node visit is a block read.

The consequence is clear: a node should be large enough to fill a block. If the node is smaller than the block, part of the fetched block goes to waste; if it is larger, a single node requires reading multiple blocks. Either way, the number of reads increases unnecessarily.

The B-Tree

A B-tree is the generalized form of the 2-3 tree. A parameter $t$ (the minimum degree) is chosen, and the following rules hold:

• Every node except the root holds at least $t-1$ and at most $2t-1$ keys.
• An internal node with $k$ keys has $k+1$ children.
• All leaves are at the same depth.

Setting $t = 2$ yields the 2-3-4 tree; in practice, $t$ is chosen as the largest value for which the node still fits in a block — on the order of hundreds.

Insertion and deletion follow the same split and merge rules as the previous lesson. An overflowing node is split in two and the middle key is promoted; a node left without a key either borrows from a sibling or merges with one.

The Consequence for Height

A high branching factor reduces height dramatically:

$$h \approx \log_{b} n$$

Here $b$ is the average branching factor.

import math

def height(record_count: int, branching: int) -> int:
    """Approximate tree height given a branching factor."""
    return math.ceil(math.log(record_count, branching))


for branching in (2, 3, 100, 500):
    print(branching, height(1_000_000, branching), height(1_000_000_000, branching))

# 2   20 30
# 3   13 19
# 100 3  5
# 500 3  4

One million records require twenty node visits in a binary tree, and three in a B-tree with a branching factor of one hundred. When disk access is the dominant cost, that is the difference between twenty block reads and three.

Even with a billion records, the depth is five. Once the root and upper levels are cached in memory, the actual number of disk accesses typically drops to one or two blocks.

The B+ Tree

The commonly used variant is the B+ tree, and it introduces two changes:

Records are kept only in the leaves. Internal nodes carry only routing keys. This lets internal nodes fit more keys — the branching factor increases and the tree becomes even shorter.

Leaves are linked to one another. Each leaf points to the next, so the leaves form a sorted linked list.

The second change transforms range queries. A query such as “all records with a value between 100 and 200” would require repeatedly traversing a plain B-tree. In a B+ tree, the starting point is searched for once, and the leaf chain is then followed in order.

This is why nearly all database indexes are B+ trees: both point lookups and range scans are handled efficiently by the same structure. Index design in the Databases curriculum builds directly on this structure.

Comparison

Metric	Balanced binary tree	B-tree / B+ tree
Node size	Small (a few links)	Block-sized
Height ($10^6$ records)	~20	~3
Suitable environment	Memory	Disk, network, block-based storage
Range query	Tree traversal	Leaf chain in a B+ tree
Search within a node	None	Binary search or linear scan

The last row reveals a detail: the total number of comparisons in a B-tree is not lower than in a binary tree. Keys are also searched within each node, and the total number of comparisons ends up similar. What is gained is not comparisons but the number of block reads.

This is the clearest example that choosing a data structure cannot be separated from its hardware context: the same algorithm makes a different structure correct in a different memory hierarchy.

Search Within a Node

When a node holds hundreds of keys, choosing the correct child within that node becomes a search problem in its own right. Two options exist, and the choice is guided by observations from earlier courses.

Binary search makes the number of comparisons logarithmic. Linear scan performs more comparisons but reads keys contiguously and takes full advantage of cache lines.

Since the node fits in a block and the block is already in memory, the difference between the two methods is small; implementations often combine them — linear search for small nodes, binary search for large ones.

This detail illustrates, once more, a lesson the course keeps repeating: the number of comparisons alone is not a sufficient metric; how many times each level of memory is accessed must also be counted.

Write Overhead and Durability

The second fact of block-based storage is that writing is more expensive than reading. Even if a single key in a node changes, the entire block is rewritten.

This gives rise to two design decisions. Keeping nodes more than half full reduces how often splits and merges occur. Batching writes lets successive changes to the same block combine into a single write.

The durability requirement follows from the same fact: if the system halts during a split, the structure can be left inconsistent. Databases manage this risk by writing changes to a log first — the data-structure-level counterpart of the write-ahead log idea from the How Computers Work course.

Uses

• Database indexes. Primary and secondary indexes are kept as B+ trees.
• File systems. Storing directory entries and block mappings.
• Key-value stores. Implementations that require ordered access.
• File formats. Index blocks embedded in large data files.

What these structures share is that the memory hierarchy layer they are designed for is known explicitly; the same tree is built with different parameters for a different layer.

For write-heavy workloads, an alternative family — log-structured merge trees — may be preferred: they batch writes and write them to disk sequentially. Comparing the two families is a topic of the Databases curriculum.

Summary

• Persistent storage is read at the block level; the number of blocks read determines the cost.
• In a B-tree, node size is matched to the block; the branching factor reaches the order of hundreds.
• Height is proportional to $\log_b n$; three node visits suffice for a million records.
• The rules are the generalized form of the 2-3 tree: splitting, promotion, borrowing, and merging.
• In a B+ tree, records are kept only in the leaves and the leaves are chained; range queries reduce to a sequential scan.
• The gain lies not in the number of comparisons but in the number of block reads.

Next Step

The trees covered so far preserved full ordering. In some problems, however, only fast access to the smallest (or largest) element is needed; full ordering is an unnecessary cost. The next lesson covers the heap structure, which works under this relaxed condition, and the priority queue it implements.