B-Tree Concept

A B-tree's efficiency comes not just from its tree structure, but from the careful organization of individual nodes. Each node is designed to maximize the useful information retrieved in a single disk read while maintaining the ability to efficiently search within the node.

Understanding node structure is essential because it connects abstract B-tree theory to concrete implementation. How many keys can fit in a node? Where are child pointers stored? How do we handle variable-length keys? These questions determine the practical performance of any B-tree implementation.

At the conceptual level, every B-tree node contains:

1. A count of keys currently stored (n)
2. The keys themselves (K₁, K₂, ..., Kₙ)
3. Child pointers (C₀, C₁, ..., Cₙ) — for internal nodes only
4. A flag indicating leaf or internal node status
5. Optional: data associated with each key (in classic B-trees)

Let's visualize this structure:

Key Array Organization

The keys array holds keys in sorted order, with the first n positions occupied and remaining positions empty (or containing placeholder values). This fixed-size allocation makes index calculations simple:

• Key at position i: node.keys[i]
• Child before key i: node.children[i]
• Child after key i: node.children[i+1]

The Interleaving Pattern

Keys and child pointers interleave in a specific pattern:

Position:  0    1    2    3    4    5    6
           C₀   K₁   C₁   K₂   C₂   K₃   C₃
           ↓    ↓    ↓    ↓    ↓    ↓    ↓
         child key child key child key child

Or equivalently:
           C₀ | K₁ | C₁ | K₂ | C₂ | K₃ | C₃

This interleaving ensures that for any key Kᵢ, the left child (containing smaller keys) is immediately before it and the right child (containing larger keys) is immediately after.

B-tree nodes fall into two categories with distinctly different roles and structures:

Internal Nodes (Non-leaf Nodes)

Internal nodes serve as routing nodes. Their purpose is to direct searches toward the correct subtree. They contain:

• Keys that act as separator/pivot values
• Child pointers leading to subtrees
• No actual data records (the keys are just for navigation)

Leaf Nodes

Leaf nodes are where data resides. Depending on the B-tree variant:

• Classic B-tree: Keys with associated data records
• B⁺-tree: Keys with pointers to data records
• Leaf nodes have no children (or null child pointers)

Space Allocation Differences

Because internal and leaf nodes store different content, they often have different effective capacities:

Internal Node (4KB page):
- Keys: 4 bytes × 200 keys = 800 bytes
- Child pointers: 8 bytes × 201 = 1,608 bytes
- Overhead: 100 bytes (header, etc.)
- Total: ~2,508 bytes → fits in 4KB

Leaf Node (4KB page, with data):
- Keys: 4 bytes × 100 keys = 400 bytes
- Data records: 30 bytes × 100 = 3,000 bytes
- Overhead: 100 bytes
- Total: ~3,500 bytes → fits in 4KB

Result: Internal nodes hold 200 keys, leaves hold 100 keys

This is why B⁺-trees store data only in leaves—it allows internal nodes to have maximum fanout while leaves optimize for data storage.

When B-tree nodes are persisted to disk, they must be serialized into a fixed-size block (page). The layout must balance several requirements:

1. Fast key search within the node
2. Efficient insertion and deletion
3. Space efficiency (minimal wasted bytes)
4. Alignment with hardware (sector boundaries, cache lines)

Typical Page Layout

Page Header Components

Fixed vs Variable Layout

For fixed-size keys (integers, fixed char), layout is straightforward:

• Keys occupy positions [header_size + i × key_size]
• Child pointers at [key_section_end + i × pointer_size]
• Binary search uses direct index calculation

For variable-size keys (varchar, text), a more complex layout is needed:

• Slot directory: array of offsets pointing to each key
• Keys stored compactly at end of page, growing toward middle
• Slot directory grows from header toward middle
• More complex but handles arbitrary key sizes

Most production databases use a slot directory (or slotted page) layout that elegantly handles variable-length keys and enables efficient reorganization.

Structure Overview

How It Works

1. Slot array grows downward from the header (fixed slot size, typically 4 bytes)
2. Records are inserted from the end of the page upward
3. Free space is the gap between slots and records
4. When inserting, add a slot entry and place record in free space
5. When deleting, mark slot as empty; optionally compact later

Benefits of This Layout

For B-tree Nodes

In a B-tree context:

• Each 'record' is a (key, child_pointer) pair for internal nodes
• Each 'record' is a (key, data) pair for leaf nodes
• Slots remain in sorted key order for binary search
• When node splits, half the slots/records move to new page

Child pointers in B-tree nodes need to identify the disk location of child pages. Different systems use different representations:

Option 1: Page Numbers (Block IDs)

Simplest approach—child pointer is just a page number:

Child pointer = 4 bytes (32-bit page number)
Addressable pages = 2³² = 4 billion pages
At 4KB per page = 16 TB maximum file size

The storage engine translates page number to physical disk offset via: disk_offset = page_number × page_size

Option 2: File ID + Page Number

For systems with multiple files per database:

Child pointer = [file_id (2 bytes) | page_number (4 bytes)]
Total = 6 bytes

Option 3: Full Disk Address

For complex storage layouts:

Child pointer = [tablespace | file | segment | page]
Total = 8+ bytes

Fanout Impact

Pointer size directly affects fanout:

Page size: 4096 bytes
Key size: 8 bytes
Overhead: 100 bytes
Usable space: 3996 bytes

With 4-byte pointers:
  Entry size = 8 + 4 = 12 bytes
  Fanout ≈ 3996 / 12 = 333 children

With 8-byte pointers:
  Entry size = 8 + 8 = 16 bytes
  Fanout ≈ 3996 / 16 = 249 children

Difference: 333 vs 249 (25% reduction in fanout)

Lower fanout means taller trees and more I/O. This is why compact pointer representations matter.

NULL Pointers

Leaf nodes often use special NULL pointer values:

• All zeros: indicates no child
• Special sentinel: often 0xFFFFFFFF or similar
• Type flag: first bit indicates leaf vs internal

Some implementations save space by not storing child pointers at all in leaf nodes, using the page type field to know the node is a leaf.

How keys are stored within nodes significantly impacts both space efficiency and search performance.

Fixed-Length Keys

For simple types (integers, fixed-size char), keys are stored directly:

INTEGER key:     [4 bytes of value]
BIGINT key:      [8 bytes of value]
CHAR(10) key:    [10 bytes, null-padded if shorter]
UUID key:        [16 bytes of value]

Fixed-length keys enable direct offset calculation:

key_offset = base_offset + (key_index × key_size)

Variable-Length Keys

For VARCHAR, TEXT, or composite keys:

Storage format: [length (1-4 bytes) | actual key bytes]

Example 'hello' (VARCHAR):
  [05 | 68 65 6C 6C 6F]
   ↑    ↑
   len  'h' 'e' 'l' 'l' 'o'

Requires indirection (slot directory) or offset table for random access.

Key Compression Techniques

Production B-trees often compress keys to increase fanout:

1. Prefix Compression Store only the distinguishing prefix of each key:

Full keys: 'application', 'application_id', 'application_name'
With prefix compression:
  'application' (full)
  '_id' (prefix 'application' implied)
  '_name' (prefix 'application' implied)

Savings: 11 + 3 + 5 = 19 bytes vs 11 + 14 + 16 = 41 bytes

2. Suffix Truncation In internal nodes, only store enough of the key to distinguish subtrees:

Separating 'alexander' from 'benjamin':
Full separator: 'benjamin' (8 bytes)
Truncated: 'b' (1 byte) — sufficient to separate 'a*' from 'b*'

3. Dictionary Encoding For repeated key patterns (esp. composite keys), store dictionary + codes:

Keys: (USA, NY, 10001), (USA, NY, 10002), (USA, CA, 90210)
Dictionary: {0: USA, 1: NY, 2: CA}
Encoded: (0, 1, 10001), (0, 1, 10002), (0, 2, 90210)

Beyond keys and pointers, B-tree nodes contain metadata that supports operations, concurrency, and recovery.

Essential Metadata Fields

Concurrency Control Metadata

For concurrent access, nodes track locking state:

struct BTreePageHeader {
    // Standard fields
    uint32_t page_id;
    uint8_t  page_type;
    uint16_t num_keys;
    
    // Concurrency control
    uint32_t btpo_prev;      // Left sibling (for deadlock-free locking)
    uint32_t btpo_next;      // Right sibling
    uint16_t btpo_level;     // Level in tree
    uint16_t btpo_flags;     // State flags:
                              //   BTP_LEAF (0x01)
                              //   BTP_ROOT (0x02)
                              //   BTP_DELETED (0x04)
                              //   BTP_META (0x08)
                              //   BTP_HALF_DEAD (0x10)
                              //   BTP_SPLIT_END (0x20)
    
    // Recovery
    uint64_t btpo_lsn;       // Last modification LSN
};

Flags Explained

• BTP_LEAF: This is a leaf node
• BTP_ROOT: This is the root node
• BTP_DELETED: Node was deleted, pending cleanup
• BTP_HALF_DEAD: Mid-deletion state (for crash recovery)
• BTP_SPLIT_END: Marks end of split chain

Choosing the right node (page) size is a critical design decision. It involves trade-offs between I/O efficiency, memory usage, and concurrency.

Common Page Sizes

Factors Influencing Page Size

Larger Pages (16-64 KB)

• ✅ Higher fanout (more keys per node)
• ✅ Fewer I/Os for sequential scans
• ✅ Better compression ratios
• ❌ More wasted space if pages are sparse
• ❌ Larger buffer pool entries (fewer pages cached)
• ❌ More lock contention (coarser locking granularity)

Smaller Pages (4-8 KB)

• ✅ Less wasted space per page
• ✅ More pages fit in buffer pool
• ✅ Finer-grained locking
• ❌ Lower fanout (taller trees)
• ❌ More I/Os for large scans
• ❌ Higher metadata overhead percentage

Matching Hardware Characteristics

Optimal page size depends on storage:

Calculating Expected Fanout

Given your key and pointer sizes, estimate fanout:

Fanout = (page_size - header_overhead - footer) / (key_size + pointer_size + slot_overhead)

Example:
  page_size = 8192 bytes
  overhead = 100 bytes
  key_size = 8 bytes (BIGINT)
  pointer_size = 6 bytes (TID)
  slot_overhead = 4 bytes

  Fanout = (8192 - 100) / (8 + 6 + 4) = 8092 / 18 ≈ 449

For 1 billion keys:
  Height = ⌈log₄₄₉(10⁹)⌉ = ⌈9 / 2.65⌉ = 4 levels

This calculation helps predict tree height and I/O requirements before implementation.

We've examined B-tree node structure from concept to implementation. Let's consolidate the key insights:

What's Next

With node structure understood, we move to the balanced property—how B-trees maintain perfect balance through splits and merges, and why this guarantees logarithmic height regardless of insertion patterns.