Comparison with B-Tree

B-trees and B+-trees are closely related—the B+-tree evolved directly from the B-tree, inheriting its core concepts of balance and high fanout. Yet the differences between them are profound enough that virtually every modern database system chooses B+-trees exclusively for their primary index structures.

This page provides a comprehensive comparison, synthesizing everything we've learned about B+-trees and contrasting it with B-tree characteristics. By the end, you'll understand not just what differs, but why those differences matter for database workloads, and when (rarely) a B-tree might still be preferred.

The structural differences between B-trees and B+-trees are fundamental. They affect every aspect of tree behavior.

Visual Comparison:

B-Tree:
              [40, R40, 80, R80]
             /         |        
    [10, R10, 30, R30] [60, R60] [90, R90]
    
(R = Record/Data; data mixed with navigation)


B+-Tree:
                  [40, 80]
                 /    |    
          [10, 30] [40, 60] [80, 90]
             ↑         ↑         ↑
           Data      Data      Data
             ↔─────────↔─────────↔
            (Linked leaves)

(Internal nodes: navigation only; Leaves: all data, all linked)

The B+-tree has a clear separation: navigation above, storage below. The B-tree interleaves navigation and storage at every level.

The difference in data location fundamentally changes how searches work.

Why Predictable Depth Matters:

1. Query Optimization:

-- The optimizer needs to estimate:
SELECT * FROM orders WHERE order_id = 12345;

With B+-trees: Cost = tree height = exactly 3 I/Os (for example)

With B-trees: Cost = between 1 and 4 I/Os depending on whether 12345 is at root, mid-level, or leaf. The optimizer must maintain statistics about key distribution across levels—complexity that rarely pays off.

2. SLA Guarantees:

For applications requiring consistent latency (financial trading, real-time systems), B+-trees provide predictable performance. B-trees have variance that may violate latency guarantees.

3. Cache Behavior:

With B+-trees, caching internal nodes benefits all queries equally. With B-trees, caching patterns are less predictable—some queries get lucky (finding data near root), others don't.

Range queries expose the most dramatic difference between B-trees and B+-trees. The linked leaf structure of B+-trees fundamentally changes how ranges are processed.

In-Order Traversal Cost (B-Tree):

To visit all keys in order in a B-tree:

visit(node):
    if node is leaf:
        output all keys
    else:
        for each (pointer, key) pair:
            visit(child via pointer)
            output key
        visit(rightmost child)

This traversal constantly moves between levels. After visiting a subtree, you must return to the parent to continue. Each 'return' may require re-reading a page that's no longer cached.

Leaf Scan (B+-Tree):

To visit all keys in order in a B+-tree:

leaf = leftmost_leaf
while leaf exists:
    output all keys in leaf
    leaf = leaf.next

No tree traversal needed after finding the start. Pure sequential access through leaf pages. The OS and disk can prefetch aggressively.

Space efficiency is nuanced: B+-trees duplicate some keys in internal nodes, but their overall space usage is often better than B-trees. Here's why:

Key Duplication in B+-Trees:

When a leaf splits, the middle key is copied to the parent. This means some keys appear twice (or more times, if at multiple split boundaries).

However:

• Only split boundary keys are duplicated
• Keys in internal nodes can be compressed (prefix/suffix truncation)
• Internal nodes are a tiny fraction of total tree size

Fanout Impact on Tree Size:

Consider storing 1 million records with 8-byte keys and 200-byte data:

B-Tree (fanout ~35):

• Height: 4 levels
• Internal nodes: ~30,000 nodes × 8KB = 240 MB
• Leaves: ~30,000 nodes × 8KB = 240 MB
• Total: ~480 MB

B+-Tree (fanout ~500):

• Height: 3 levels
• Internal nodes: ~2,000 nodes × 8KB = 16 MB
• Leaves: ~10,000 nodes × 8KB = 80 MB
• Total: ~96 MB

The B+-tree is 5× smaller despite key duplication, because higher fanout dramatically reduces the number of nodes needed.

Fanout directly determines tree height, which in turn determines I/O cost per search. This is perhaps the most critical performance factor.

Fanout Calculation:

With 8KB pages, 8-byte keys, 8-byte pointers, and 200-byte records:

B-Tree Internal Node:

Entry = key + data + pointer = 8 + 200 + 8 = 216 bytes
Fanout = 8192 / 216 ≈ 37

B+-Tree Internal Node:

Entry = key + pointer = 8 + 8 = 16 bytes
Fanout = 8192 / 16 ≈ 500

That's a 13.5× difference in fanout!

Impact Analysis:

Consider a database with 100 million records running 10,000 queries per second:

B-Tree (height 5): 50,000 disk reads/second

B+-Tree (height 4): 40,000 disk reads/second

Savings: 10,000 disk reads/second = 20% reduction in I/O load

This 20% improvement translates directly to:

• 20% higher throughput (more queries at same hardware)
• 20% lower latency (each query faster)
• 20% fewer servers needed (cost savings)

Over a year of operation, this single level of height difference saves millions of dollars in infrastructure for large systems.

The structural differences between B-trees and B+-trees significantly affect concurrent access and maintenance operations.

Concurrency Implications:

B-Tree Challenges:

• Data modifications can occur at any level
• Internal nodes are write hotspots (updates to frequently accessed keys)
• Locks on internal nodes block all queries to that subtree
• In-order traversal requires complex lock coupling across levels

B+-Tree Advantages:

• Data modifications only at leaf level
• Internal nodes change only during splits/merges (rare)
• Optimistic traversal: read internals without locks, lock only at leaf
• Range scans hold locks on leaves only, not internal nodes

Maintenance Operations:

Index Defragmentation:

• B+-trees: Simply rebuild leaves sequentially; internal nodes follow
• B-trees: Must carefully preserve data at all levels during rebuild

Bulk Loading:

• B+-trees: Sort data, write leaves, build internals bottom-up—very efficient
• B-trees: Similar, but more complex due to data in internal nodes

Online Reorganization:

• B+-trees: Can relocate leaves independently if sibling pointers updated
• B-trees: Moving internal nodes risks losing data

Despite B+-trees' clear advantages for databases, there are niche scenarios where B-trees might be considered:

Reality Check:

In practice, these scenarios rarely favor B-trees enough to overcome B+-trees' advantages:

1. Even point-query-only workloads benefit from B+-tree fanout
2. When datasets are small enough for B-trees to work well, B+-trees work equally well
3. Modern databases store large records out-of-line regardless of index type
4. In-memory databases often use entirely different structures (radix trees, hash tables)

The Result: B+-trees are used in virtually all production database systems. B-trees remain primarily in textbooks and historical contexts.