B+-Tree Structure

B+-trees present a fascinating duality: from above, they appear as a tree structure optimized for logarithmic search; from the bottom, they appear as a linked list of sorted data pages. This dual nature is not accidental—it's the source of B+-trees' power for database workloads.

The key mechanism enabling this duality is leaf node linking: each leaf maintains a pointer to its next sibling (and often to its previous sibling as well). This seemingly simple addition transforms the B+-tree from a point lookup structure into a sequential access powerhouse, capable of efficiently handling range queries, sorted output, and aggregate operations.

In a B+-tree, all leaf nodes are connected through sibling pointers, forming a chain that preserves key ordering. The structure can be visualized as:

                    [Root]
                   /      \
            [Internal]    [Internal]
           /    |    \      /    \
        [L1] ↔ [L2] ↔ [L3] ↔ [L4] ↔ [L5]
         ↑                              ↑
      Head                            Tail

Each leaf node contains:

• The actual key-value pairs (data records or pointers to them)
• A 'next' pointer to the right sibling leaf
• Optionally, a 'prev' pointer to the left sibling leaf (doubly-linked)

Invariant: The leaves form a sorted sequence. If you traverse from the leftmost leaf to the rightmost leaf following sibling pointers, you visit all keys in sorted order.

The primary motivation for leaf linking is efficient range query execution. Consider the query:

SELECT * FROM employees WHERE salary BETWEEN 50000 AND 75000;

Without Leaf Linking (B-Tree approach):

1. Find the first matching record (salary = 50000) via tree traversal
2. Return to parent, find next in-order key
3. If next key is in a different subtree, navigate back up and down
4. Repeat until salary > 75000

This yo-yo traversal is expensive: each record might require navigating multiple levels.

With Leaf Linking (B+-Tree approach):

1. Find the first matching record via tree traversal (one root-to-leaf path)
2. Follow 'next' pointer to subsequent records
3. Continue following links until salary > 75000

The entire scan stays at the leaf level—no tree navigation during the range portion.

Algorithm: Range Scan

RangeScan(tree, low_key, high_key):
    // Phase 1: Find starting point (logarithmic)
    leaf = tree.root
    while leaf is not a leaf node:
        leaf = find_child(leaf, low_key)
    
    // Find first key >= low_key within leaf
    position = binary_search(leaf, low_key)
    
    // Phase 2: Sequential scan (linear in result size)
    results = []
    while true:
        while position < leaf.entry_count:
            if leaf.keys[position] > high_key:
                return results  // Done
            results.append(leaf.entries[position])
            position++
        
        // Move to next leaf
        if leaf.next == null:
            return results  // No more leaves
        leaf = fetch_page(leaf.next)
        position = 0
    
    return results

Time Complexity:

• Finding start: O(log n)
• Scanning k results: O(k/entries_per_page)
• Total: O(log n + k/B) where B = entries per leaf

Range queries are just one instance of sequential access. Leaf linking enables efficient execution of many common database operations:

ORDER BY Optimization:

Without leaf linking, a query like:

SELECT * FROM employees ORDER BY last_name;

...would require either:

1. Full table scan followed by sort (expensive for large tables)
2. Complex in-order tree traversal with backtracking

With leaf linking on a last_name index:

1. Start at leftmost leaf
2. Follow next pointers to the end
3. Data arrives pre-sorted—no sorting phase needed!

This is why database query optimizers often choose index scans even when most rows are selected: the free ordering avoids an expensive sort operation.

Reverse Scans (ORDER BY DESC):

With doubly-linked leaves:

SELECT * FROM employees ORDER BY last_name DESC;

1. Start at rightmost leaf
2. Follow prev pointers to the beginning
3. Still O(n) and still avoids sorting

The true power of leaf linking is revealed when considering physical disk characteristics. Modern storage devices have drastically different performance for sequential vs. random access:

Why Sequential Matters:

1. Disk Head Movement (HDD): Random reads require moving the disk head to different tracks, taking ~5-10ms each. Sequential reads keep the head in place, limited only by rotational speed.

2. Read Prefetching: Operating systems and disk controllers detect sequential patterns and read ahead, fetching multiple pages before they're requested.

3. SSD Parallelism: SSDs read faster when accessing consecutive blocks—internal parallelism is better utilized.

Prefetch Optimization:

Because leaves are linked, databases can:

• Detect that a range scan is in progress
• Issue prefetch requests for upcoming leaf pages
• Achieve near-sequential throughput even with some internal fragmentation

Current read: Leaf 47
Asynchronously prefetching: Leaves 48, 49, 50, 51
By the time we need Leaf 48, it's already in buffer pool

This prefetching is only possible because leaf linking reveals the access pattern predictably.

Leaf links must be maintained during insertions and deletions. Understanding this maintenance is crucial for both implementing B+-trees and understanding their performance characteristics.

Leaf Split (during insert):

Before split:
  ... ↔ [A] ↔ [B overflowing] ↔ [C] ↔ ...
                    ↓
              (insert causes split)
                    ↓
After split:
  ... ↔ [A] ↔ [B left half] ↔ [B right half] ↔ [C] ↔ ...

Algorithm:

1. Create new right sibling page
2. Move upper half of entries to new page
3. Set new_page.next = old_page.next
4. Set new_page.prev = old_page (if doubly-linked)
5. Set old_page.next = new_page
6. If old_page.original_next exists, set its prev = new_page
7. Copy separator key to parent

Link updates are local—only adjacent leaves are affected.

Leaf Merge (during delete):

Before merge:
  ... ↔ [A] ↔ [B underfull] ↔ [C underfull] ↔ [D] ↔ ...
                    ↓
            (delete causes merge)
                    ↓
After merge:
  ... ↔ [A] ↔ [B + C combined] ↔ [D] ↔ ...

Algorithm:

1. Combine entries from both pages into one page
2. Set merged_page.next = right_sibling.next
3. If right_sibling.next exists, set its prev = merged_page
4. Deallocate the emptied page
5. Remove separator from parent (may cascade)

Key Insight: Sibling pointer updates are part of the atomic split/merge operation. If the operation fails midway, crash recovery must restore consistent sibling links.

Leaf linking introduces interesting concurrency challenges. When a reader is traversing leaves via sibling pointers, a concurrent writer might split or merge a leaf in the reader's path.

The B-Link Tree Protocol:

Lehman and Yao's B-link tree (1981) solves these problems elegantly:

1. Each node stores a high key—the maximum key that can appear in that subtree
2. Sibling links are updated before parent pointers during splits
3. If a reader arrives at a node where search_key > high_key, the node must have split
4. Reader simply follows the right-link to the correct sibling

Example:

Reader searching for key K = 50
Arrives at leaf with keys [30, 35, 40] and high_key = 45
50 > 45, so this leaf was split
Follow right-link to sibling [45, 50, 55, 60]
Find K = 50 here

This protocol allows readers to traverse leaves without blocking on splits—they may take an extra hop but will always find the correct data.

Logical sibling links and physical disk layout interact in important ways. Ideally, logically adjacent leaves would be physically adjacent on disk, maximizing sequential I/O benefits.

The Fragmentation Problem:

Initially, B+-tree leaves may be written sequentially. But after many splits:

• New leaves are allocated wherever free space exists
• Logically adjacent leaves may be physically scattered
• Following next pointers becomes random I/O

Mitigation Strategies:

1. Pre-allocation Pools: Allocate pages in large contiguous chunks. When splits occur, the new page comes from the same chunk, likely near its sibling.

2. Periodic Reorganization (REORG): Periodically rebuild the index from scratch, writing leaves in sequential order:

-- PostgreSQL
REINDEX INDEX my_index;

-- MySQL
ALTER TABLE my_table ENGINE=InnoDB;  -- Rebuilds all indexes

-- SQL Server
ALTER INDEX my_index ON my_table REBUILD;

3. Online Defragmentation: Some databases can relocate pages incrementally without locking the entire index.

4. Bulk Loading: When initially loading data, build leaves in sorted order:

• Sort all data externally
• Write leaves left-to-right
• Build internal nodes bottom-up

This produces perfectly sequential layout.

Leaf node linking is the feature that transforms B+-trees from a dictionary structure into a sequential access powerhouse. Let's consolidate the key insights:

What's Next:

We've examined leaf nodes in depth. The next page explores internal nodes—the navigation layer that routes searches to the correct leaves. We'll examine their structure, how they're maintained during splits and merges, and various optimization techniques used in production databases.