B-tree Definition - B-Tree Concept | OneNoughtOne

0/278

Database Management SystemsB-Trees & B+-Trees

B-Tree Concept

LevelIntermediate

Duration60 mins

TopicB-Trees & B+-Trees

1 / 5

B-tree Definition

The Data Structure That Powers All Databases

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.

What You Will Learn

By the end of this page, you will understand what a B-tree is, why it was invented, how it differs from binary search trees, and why its design principles remain optimal for disk-based storage systems. You'll gain the formal definition that underpins all B-tree variants used in modern databases.

The Problem B-trees Solve

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:

Storage Type	Random Access Time	Relative Speed
CPU Cache (L1)	~1 nanosecond	1×
Main Memory (RAM)	~100 nanoseconds	100× slower
SSD (NVMe)	~100 microseconds	100,000× slower
Hard Disk (HDD)	~10 milliseconds	10,000,000× slower

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

The Critical Insight

For disk-based systems, the number of disk accesses (I/O operations) dominates performance—not CPU cycles. An algorithm that does 1,000 more CPU operations but requires 1 fewer disk access will almost always be faster. B-trees are designed to minimize disk I/O above all else.

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.

The B-tree Design Principle

•Maximize node fanout — Each node can have hundreds or thousands of children, not just 2
•Match node size to disk block — One disk I/O retrieves an entire node worth of keys
•Minimize tree height — With high fanout, the tree becomes extremely shallow
•Guarantee balance — Unlike BSTs, every leaf is at the same depth
•Optimize for block access patterns — Sequential reading and writing are prioritized

What is a B-tree?

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.

Order vs. Minimum Degree

Different textbooks use different conventions. Some define 'order' as the maximum number of children (m), others as the minimum degree (t = ⌈m/2⌉). We use the maximum children convention throughout. Always clarify which definition is being used when reading other sources.

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.

Formal Definition

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:

B-tree Formal Properties

•Property 1 (Bounded Children): Every node has at most m children.
•Property 2 (Minimum Children): Every internal node (except the root) has at least ⌈m/2⌉ children.
•Property 3 (Root Minimum): If the tree is non-empty and the root is not a leaf, the root has at least 2 children.
•Property 4 (Key Count): A node with k children contains exactly k-1 keys.
•Property 5 (Key Ordering): Keys within each node are stored in sorted (non-decreasing) order: key₁ ≤ key₂ ≤ ... ≤ keyₖ₋₁.
•Property 6 (Subtree Ordering): For a node with keys key₁, key₂, ..., keyₖ₋₁ and children c₀, c₁, ..., cₖ₋₁: All keys in subtree cᵢ are greater than keyᵢ and less than keyᵢ₊₁.
•Property 7 (Leaf Property): All leaves appear on the same level (the tree has uniform depth).

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.

Why These Constraints?

Each property exists for a reason: (1-2) ensure nodes are neither too full nor too empty, maintaining balance; (3) allows the tree to grow from a single node; (4-6) enable binary search within nodes and correct navigation; (7) guarantees O(log n) height. These constraints work together to achieve provable performance bounds.

B-tree Node Constraints by Order
Order (m)	Min Keys (non-root)	Max Keys	Min Children (non-root)	Max Children
3	1	2	2	3
4	1	3	2	4
5	2	4	3	5
100	49	99	50	100
1000	499	999	500	1000

B-trees vs Binary Search Trees

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.

BST vs B-tree Comparison
Characteristic	Binary Search Tree	B-tree (order m)
Max children per node	2	m (typically 100-1000+)
Keys per node	1	up to m-1
Tree height for n keys	O(log₂ n)	O(log_m n)
Disk accesses per search	O(log₂ n)	O(log_m n)
Balance guarantee	Requires AVL/Red-Black	Built-in (always balanced)
Node size	Fixed (small)	Variable (fills disk block)
Cache/disk efficiency	Poor	Excellent
Insertion complexity	O(log n) amortized	O(log n) worst-case

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:

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.
Prefetching: Modern CPUs and disk controllers prefetch sequential data. B-tree nodes contain contiguous keys, enabling efficient prefetching.
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 Key Advantage

B-trees trade CPU work (more comparisons within a node) for reduced I/O (fewer nodes accessed). Since I/O is 100,000× slower than CPU operations, this tradeoff is overwhelmingly beneficial for disk-based systems.

The Power of High Fanout

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.

Height vs Fanout for 1 Billion Keys
Fanout (t)	Maximum Height	Disk Accesses
2 (BST)	30	30
10	10	10
100	5	5
500	4	4
1000	3	3

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.

The Root is Always Cached

Production databases keep the B-tree root node (and often the first 1-2 levels) permanently in memory. For a billion-record table, this means most searches require only 2-3 disk accesses, not 5. This optimization is essentially free since the upper levels represent a tiny fraction of total index size.

Why B-trees Endure

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:

B-tree Strengths

•Guaranteed logarithmic height: Unlike BSTs, balance is automatic—no rotations needed during normal operations
•Efficient range queries: Keys are sorted; scanning a range requires visiting contiguous nodes
•Good space utilization: Nodes are at least 50% full (often higher with optimizations)
•Excellent worst-case performance: No pathological cases like unbalanced BSTs
•Natural concurrency support: Node-level locking works well due to large nodes
•Incremental modification: Insertions and deletions don't require rebuilding the structure

Alternatives and Trade-offs

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

Structure	What It Improves	What It Sacrifices
Hash Index	O(1) point lookups	Range queries impossible
Skip List	Simpler implementation	Higher memory overhead
LSM-Tree	Write performance	Read performance, space amplification
Trie	Prefix queries	Space efficiency, general-purpose use

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.

Standing the Test of Time

B-trees are a rare case of an algorithm that was essentially 'right' from the start. The basic design from 1972 is still optimal. Improvements like B+-trees (which we'll study next) are refinements, not replacements. This stability is a testament to the elegance of the original design.

Common Misconceptions

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

Misconceptions

•"B-tree means Binary tree" — No! 'B' stands for 'Balanced', not 'Binary'. B-trees can have hundreds of children per node.
•"B-trees are only for databases" — While optimized for disk I/O, B-trees are used in file systems, network routers, and anywhere sorted data with range queries is needed.
•"Higher order is always better" — Past a certain point, larger nodes hurt cache performance. Optimal order depends on hardware characteristics.
•"B-trees are hard to implement" — The basic insert/delete operations are actually straightforward. Production implementations are complex due to concurrency and recovery, not the core algorithm.

Clarifications

•B-tree is a generalization of balanced binary trees to n-ary trees, optimized for block-access storage.
•B-trees are general-purpose sorted containers with excellent performance for both point and range queries.
•Order selection is a tuning parameter — it should match disk block size and access patterns.
•The core algorithm is elegant — it maintains invariants through simple split and merge operations during insert and delete.

B-tree vs B+-tree

A critical distinction: Classic B-trees store data in ALL nodes. B+-trees (covered in subsequent modules) store data ONLY in leaves. Most databases use B+-trees, but call them 'B-trees'. When reading database documentation, assume B+-tree unless explicitly stated otherwise.

Summary: B-tree Definition

We've established the foundational understanding of what B-trees are and why they matter. Let's consolidate the key concepts:

Key Takeaways

•B-trees solve the disk I/O problem — By packing many keys per node, they minimize the number of disk accesses required for search operations.
•High fanout creates shallow trees — With hundreds of keys per node, even billions of records require only a handful of disk accesses.
•Balance is guaranteed — Unlike BSTs, B-trees maintain perfect balance automatically through their insertion and deletion algorithms.
•The formal definition is precise — Properties on node sizes, key ordering, and child relationships ensure consistent, predictable behavior.
•B-trees outperform BSTs for disk-based storage — The tradeoff of more CPU work for less I/O is overwhelmingly beneficial.
•B-trees remain dominant after 50 years — No competing structure matches their combination of efficiency, flexibility, and reliability.

What's Next

Now that we understand what a B-tree is, the next page explores the specific properties that make B-trees work—the constraints on node sizes, key counts, and structural relationships that together guarantee logarithmic performance. These properties are the rules that maintain balance as the tree grows and shrinks.

Page Complete

You now understand the B-tree definition: a self-balancing, high-fanout tree designed to minimize disk I/O. You can explain why B-trees replaced binary search trees for disk-based indexing and state the formal properties that define a valid B-tree. Next, we'll dive deeper into these properties and understand how they work together to guarantee performance.