B-tree Definition

In 1972, Rudolf Bayer and Edward McCreight at Boeing Scientific Research Labs published a paper that would fundamentally transform how computers store and retrieve information. They introduced the B-tree—a self-balancing tree data structure designed specifically for systems that read and write large blocks of data, such as disk storage systems.

Fifty years later, some variation of B-trees powers virtually every relational database management system in production. From MySQL to PostgreSQL, Oracle to SQL Server, MongoDB to SQLite—the B-tree and its descendants form the backbone of data indexing. Understanding B-trees isn't just academic knowledge; it's understanding how databases actually work at their core.

Before we can appreciate B-trees, we must understand the fundamental problem they were designed to solve. This problem remains just as relevant today—perhaps more so—as when B-trees were invented.

The Disk I/O Bottleneck

When databases store millions or billions of records, they cannot fit entirely in main memory (RAM). Data must reside on persistent storage—traditionally hard disks, now often SSDs. Accessing data from disk is orders of magnitude slower than accessing data in memory:

This latency gap between memory and disk is the central challenge. Every disk access represents a massive performance penalty compared to in-memory computation.

Why Binary Search Trees Fail

Binary Search Trees (BSTs) provide O(log₂ n) search time—seemingly efficient. But consider what happens with disk-based storage:

• Each tree node typically resides on a different disk page
• Traversing from root to a leaf requires accessing log₂ n different pages
• For 1 billion records: log₂(10⁹) ≈ 30 disk accesses
• At 10ms per access: 300 milliseconds for a single lookup

This is catastrophically slow. A database serving thousands of queries per second cannot afford 300ms per query.

The Block Access Model

Here's the key insight that motivates B-trees: when you access data from disk, you don't read a single byte—you read an entire block (typically 4KB to 16KB). Reading 1 byte costs the same as reading 4,000 bytes in terms of seek time and rotational latency.

This suggests a radical redesign: instead of one key per node (as in BSTs), why not pack many keys into each node—filling an entire disk block? Each node access would then provide much more information, reducing total disk accesses.

A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. Unlike binary trees where each node has at most 2 children, B-tree nodes can have many children—often hundreds or thousands—making the tree extremely shallow.

Etymology and Naming

The 'B' in B-tree has been a source of endless speculation. Bayer and McCreight never explicitly stated its meaning. Common theories include:

• Balanced (all leaves are at the same depth)
• Bayer (one of the inventors)
• Bushy (high branching factor)
• Boeing (where it was invented)
• Broad (wide nodes)

Most computer scientists accept 'Balanced' as the most fitting interpretation, as perfect balance is the B-tree's defining characteristic.

Informal Definition

Now let's define a B-tree informally:

A B-tree of order m (also called a B-tree of degree m or an m-way tree) is a tree where:

• Every node has at most m children
• Every non-leaf node (except root) has at least ⌈m/2⌉ children
• The root has at least 2 children (if it is not a leaf)
• All leaves appear at the same level (perfect balance)
• A non-leaf node with k children contains k-1 keys

The keys within each node are sorted, and they act as separators that guide searches to the appropriate subtree.

Visual Understanding

Consider a B-tree of order 5 (maximum 5 children per node):

                    [40 | 70]
                   /    |    
                  /     |     
    [10 | 20 | 30]  [50 | 60]  [80 | 90 | 100]

In this example:

• The root has 2 keys (40 and 70) and 3 children
• Keys less than 40 are in the left subtree
• Keys between 40 and 70 are in the middle subtree
• Keys greater than 70 are in the right subtree
• All leaves are at the same depth (level 1)

Each key acts as a separator: it divides the key space into regions, each covered by a different child pointer. This is the fundamental navigation mechanism in B-trees.

Now let's state the formal definition with mathematical precision. This definition is what you'll find in academic literature and database internals documentation.

Definition: B-tree of Order m

A B-tree of order m (where m ≥ 3) is a rooted tree satisfying the following properties:

Mathematical Notation

Let's formalize the node structure. For a B-tree node N:

• n[N] = number of keys currently stored in node N
• key₁[N], key₂[N], ..., keyₙ[N] = the keys in sorted order
• c₀[N], c₁[N], ..., cₙ[N] = pointers to child nodes
• leaf[N] = boolean indicating if N is a leaf

The search invariant can be stated formally:

For any key k in the subtree rooted at cᵢ[N]:

• If i = 0: k < key₁[N]
• If 0 < i < n[N]: keyᵢ[N] ≤ k < keyᵢ₊₁[N]
• If i = n[N]: k ≥ keyₙ[N]

This invariant is what makes efficient searching possible—we can eliminate entire subtrees with each comparison.

To fully appreciate B-trees, let's systematically compare them with binary search trees—the data structure most programmers learn first.

Structural Comparison

Binary Search Trees constrain each node to have at most 2 children and store exactly 1 key. B-trees generalize this to m children and m-1 keys. This seemingly simple change has profound implications.

Height Comparison Example

Consider storing 1 billion records (n = 10⁹):

Binary Search Tree (balanced):

• Height = log₂(10⁹) ≈ 30 levels
• Each level requires a disk access
• 30 disk accesses per search

B-tree (order 1000):

• Height = log₁₀₀₀(10⁹) ≈ 3 levels
• Each level is one disk access
• Only 3 disk accesses per search

This is a 10× reduction in disk I/O. In practical terms, the difference between 300ms and 30ms response time—the difference between usable and unusable.

Memory Hierarchy Efficiency

B-trees are designed around how memory hierarchies actually work:

1. Block-oriented access: Reading one byte from disk costs almost the same as reading 4,096 bytes. B-tree nodes are sized to match disk blocks, so each I/O retrieves maximum useful data.

2. Prefetching: Modern CPUs and disk controllers prefetch sequential data. B-tree nodes contain contiguous keys, enabling efficient prefetching.

3. Cache efficiency: Once a node is loaded into memory, searching within it (using binary search) is extremely fast—pure CPU work with no additional I/O.

The fanout of a tree node is the number of children it has. In B-trees, high fanout is the source of their power. Let's explore why mathematically.

Fanout and Height Relationship

For a B-tree with minimum degree t (where each non-root node has at least t children):

• At depth 0 (root): at least 1 node
• At depth 1: at least 2 nodes (root has ≥ 2 children)
• At depth 2: at least 2t nodes
• At depth d: at least 2t^(d-1) nodes

For a tree with n keys and height h:

n ≥ 1 + (t-1) × Σᵢ₌₁ʰ 2t^(i-1) = 1 + 2(t-1) × (t^h - 1)/(t-1) = 2t^h - 1

Solving for h:

h ≤ log_t((n+1)/2)

This proves that height grows logarithmically with base t, not base 2.

Real-World Fanout Calculation

Let's calculate realistic fanout for a database system:

Assumptions:

• Disk block size: 4,096 bytes (4KB)
• Key size: 8 bytes (64-bit integer)
• Pointer size: 8 bytes (disk page address)
• Node overhead: 16 bytes (metadata)

Available space per node: 4,096 - 16 = 4,080 bytes

Each key-pointer pair: 8 + 8 = 16 bytes

Maximum entries per node: 4,080 / 16 = 255 entries

With a fanout of 255:

• 1,000 keys: height 2
• 1,000,000 keys: height 4
• 1,000,000,000 keys: height 5

This means a billion-record table can be searched with just 5 disk accesses. The root node is almost always cached in memory, reducing this to 4 disk accesses in practice.

B-trees were invented in 1972—over 50 years ago. In that time, we've seen revolutions in hardware, storage technology, and algorithm design. Yet B-trees remain the dominant index structure. Why?

Adaptability to Hardware Evolution

B-trees have proven remarkably adaptable:

• Magnetic disks → SSDs: B-trees still minimize I/O, which matters even for SSDs (just less dramatically)
• Increasing memory: Higher-level nodes cached in RAM; leaf accesses reduced
• Larger block sizes: Simply increase fanout; fundamental algorithm unchanged
• Multi-core processors: B-tree nodes parallelize naturally for in-memory search

Optimal Balance of Properties

B-trees hit a sweet spot that no other data structure matches:

Alternatives and Trade-offs

Other index structures exist, but each sacrifices something B-trees provide:

For general-purpose indexing where both point queries and range scans are needed, B-trees remain unmatched.

Engineering Maturity

Fifty years of implementation have produced extremely optimized B-tree libraries. Every edge case has been encountered, every bug has been fixed, every optimization has been discovered. This accumulated engineering wisdom makes B-trees not just theoretically sound but also practically proven.

Understanding what B-trees are requires dispelling what they are not. Let's address common misconceptions that can hinder learning.