Search Algorithm

Every database query that benefits from an index ultimately relies on B-tree search. When you execute a query like SELECT * FROM orders WHERE order_id = 12345, the database doesn't scan millions of rows—it navigates a B-tree, making precisely calculated decisions at each node to locate the target record with logarithmic efficiency.

The B-tree search algorithm is deceptively simple in concept yet profound in its implications. Understanding it deeply reveals why B-trees dominate database indexing and how seemingly minor implementation choices cascade into massive performance differences at scale.

B-tree search is a generalized binary search extended to multi-way branching. While a binary search tree compares a key against a single node value and chooses left or right, a B-tree compares against an ordered list of keys within each node and selects the appropriate child pointer from among multiple options.

The Core Invariant:

A B-tree maintains the following ordering invariant that makes search possible:

For every internal node with keys K₁, K₂, ..., Kₙ and child pointers P₀, P₁, ..., Pₙ:

• All keys in the subtree pointed to by P₀ are less than K₁
• All keys in the subtree pointed to by Pᵢ (for 1 ≤ i < n) are between Kᵢ and Kᵢ₊₁
• All keys in the subtree pointed to by Pₙ are greater than or equal to Kₙ

This invariant is the foundation upon which all B-tree operations rest. Search exploits it to eliminate entire subtrees from consideration at each level.

Visual Understanding:

Consider a B-tree node with keys [20, 40, 60] and four child pointers:

           [20 | 40 | 60]
            /   |   |   
          P₀   P₁  P₂   P₃
          ↓    ↓   ↓    ↓
      keys   keys  keys  keys
      < 20   20-39 40-59  ≥ 60

• Searching for key 15: Compare against 20 → 15 < 20 → follow P₀
• Searching for key 35: Compare against 20 → 35 > 20; Compare against 40 → 35 < 40 → follow P₁
• Searching for key 60: Compare against 20 → 60 > 20; Compare against 40 → 60 > 40; Compare against 60 → 60 = 60 → found (or follow P₃ in separator-only B+-trees)

At each node, we perform a within-node search (typically binary search for efficiency) to determine which path to follow.

Let's formalize the B-tree search algorithm with precise pseudocode and then analyze each component:

Algorithm: B-Tree Search

BTREE-SEARCH(node, key):
    Input: node - current B-tree node being examined
           key  - the search key we're looking for
    Output: (node, index) pair if key found, or NULL if not found

    1.  i ← 0
    2.  // Find the smallest index where key ≤ node.keys[i]
    3.  WHILE i < node.numKeys AND key > node.keys[i]:
    4.      i ← i + 1
    5.  
    6.  // Check if we found the key at position i
    7.  IF i < node.numKeys AND key = node.keys[i]:
    8.      RETURN (node, i)    // Key found at position i
    9.  
   10.  // Key not found in this node
   11.  IF node.isLeaf:
   12.      RETURN NULL         // Key doesn't exist in tree
   13.  ELSE:
   14.      // Read child from disk if not in memory
   15.      DISK-READ(node.children[i])
   16.      RETURN BTREE-SEARCH(node.children[i], key)

This recursive algorithm captures the essence of B-tree search. Let's examine each phase:

The within-node search (finding the correct key position within a single node) is a crucial optimization point. While the number of disk I/Os dominates overall cost, the CPU time for within-node searches becomes significant with large fan-outs or under high query loads.

Linear Search:

The naive approach scans keys sequentially:

• Time complexity: O(n) where n = number of keys in node
• Simple to implement, cache-friendly sequential access
• Works well for small n (e.g., n ≤ 8)

Binary Search:

For larger nodes, binary search reduces comparisons:

• Time complexity: O(log n)
• More complex logic with potential cache misses
• Dominant choice for nodes with many keys

Interpolation Search:

When keys are uniformly distributed:

• Expected complexity: O(log log n)
• Requires numeric keys with known distribution
• Rarely used in practice due to distribution assumptions

SIMD-Accelerated Search:

Modern database systems exploit Single Instruction, Multiple Data (SIMD) instructions for within-node search:

// Conceptual SIMD search within a node
__m256i key_vec = _mm256_set1_epi32(search_key);
__m256i node_keys = _mm256_loadu_si256((__m256i*)node->keys);
__m256i cmp_result = _mm256_cmpgt_epi32(key_vec, node_keys);
int mask = _mm256_movemask_ps((__m256)cmp_result);
int pos = __builtin_popcount(mask);  // Count keys < search_key

This compares 8 keys simultaneously, reducing search time dramatically for fixed-size integer keys. Production systems like PostgreSQL and MySQL leverage such optimizations.

Understanding B-tree search complexity requires separating two cost models: disk I/O (the dominant factor) and CPU operations (significant under high load).

Height of a B-Tree:

For a B-tree with minimum degree t (each node has at least t-1 keys and at most 2t-1 keys):

• Minimum keys per node (except root): t - 1
• Maximum keys per node: 2t - 1
• For n total keys, the height h satisfies:

$$h \leq \log_t \left( \frac{n+1}{2} \right)$$

This means a B-tree with t = 100 (typical for disk-based systems) containing 1 billion keys has height at most:

$$h \leq \log_{100}(500,000,000) \approx 4.35$$

So at most 5 disk reads locate any key among 1 billion!

Why Disk I/O Dominates:

Consider typical access times:

• Disk seek + rotational latency: ~5-10 ms (HDD)
• SSD random read: ~0.1-0.2 ms
• Main memory access: ~100 ns
• L1 cache access: ~1 ns
• CPU comparison: ~1 ns

A single disk read is 1,000,000× slower than a CPU comparison. This is why B-trees optimize for fewer disk reads (by maximizing node size) even at the cost of more CPU work per node.

Practical Example:

Searching a B-tree with t = 200 for a key among 10⁹ keys:

• Height: ⌈log₂₀₀(10⁹)⌉ = 4 levels
• Disk I/Os: 4 reads
• Time at 0.1ms per SSD read: 0.4 ms
• Alternative (linear scan of 10⁹ keys): ~11 days of sequential reading

The B-tree transforms an impossible problem into a trivial one.

While the basic search algorithm is similar for B-trees and B+-trees, there are critical differences that affect implementation and performance:

B-Tree (Classic):

• Keys can appear in any node (internal or leaf)
• Search may terminate at an internal node if the key is found
• Associated data (record pointers) stored with keys at all levels
• Node structure: [P₀, K₁, D₁, P₁, K₂, D₂, P₂, ...] where Dᵢ is data pointer

B+-Tree (Database Standard):

• Keys in internal nodes are separators only (copies or routing keys)
• Search always descends to a leaf, even if separator matches
• Data pointers exist only in leaf nodes
• Leaf nodes linked for sequential access
• Internal node structure: [P₀, K₁, P₁, K₂, P₂, ...] (no data pointers)

B+-Tree Search Modification:

BPLUS-TREE-SEARCH(node, key):
    WHILE NOT node.isLeaf:
        i ← FindChildIndex(node, key)  // Binary search for position
        DISK-READ(node.children[i])
        node ← node.children[i]
    
    // Now at leaf level - search for exact key
    i ← BinarySearch(node.keys, key)
    IF i < node.numKeys AND node.keys[i] = key:
        RETURN (node, i)  // Found: return leaf and index
    ELSE:
        RETURN NULL       // Not found

Note that B+-tree search is inherently iterative rather than recursive—we descend until reaching a leaf, then perform a final lookup. This simplifies implementation and reduces stack usage.

While point queries (finding a single key) are important, database workloads often involve range queries: WHERE age BETWEEN 25 AND 35 or WHERE date >= '2024-01-01'. B+-trees excel at range queries due to their leaf-level structure.

Range Query Algorithm:

BPLUS-TREE-RANGE-SEARCH(tree, lowKey, highKey):
    // Step 1: Find the starting leaf
    leaf ← FindLeaf(tree.root, lowKey)
    
    // Step 2: Collect results by scanning leaves sequentially
    results ← []
    WHILE leaf ≠ NULL:
        FOR i ← 0 TO leaf.numKeys - 1:
            IF leaf.keys[i] > highKey:
                RETURN results  // Past range, done
            IF leaf.keys[i] >= lowKey:
                results.append((leaf.keys[i], leaf.data[i]))
        leaf ← leaf.nextLeaf  // Follow sibling pointer
    
    RETURN results

The key insight: once we find the starting position, we traverse linked leaves without ever ascending the tree. This turns range queries into sequential I/O, which is dramatically faster than random I/O.

Sequential I/O Advantage:

Hard drives and SSDs have vastly different performance characteristics for sequential vs. random access:

Even on fast NVMe storage, sequential reads are 7× faster. For HDDs, the difference is 200×. B+-tree leaf linking transforms range queries from random access nightmares into fast sequential scans.

Bidirectional Pointers:

Advanced implementations maintain both nextLeaf and prevLeaf pointers, enabling efficient backward scans for:

• ORDER BY ... DESC queries
• Finding the maximum key in a range
• Cursor repositioning in both directions

Real database systems implement B-tree search with numerous practical considerations that textbook algorithms omit. Let's examine production-grade patterns:

1. Buffer Pool Integration:

Search doesn't directly perform disk I/O—it requests pages from a buffer pool manager:

Node* getNode(PageID pid) {
    // Check if page is already in memory
    Frame* frame = bufferPool.lookup(pid);
    if (frame != nullptr) {
        frame->pinCount++;  // Prevent eviction during use
        return frame->page;
    }
    
    // Page miss: fetch from disk
    frame = bufferPool.evictAndFetch(pid);
    return frame->page;
}

This allows the upper levels of the tree (frequently accessed) to remain in memory while leaves are fetched on demand.

2. Latching for Concurrency:

Concurrent access requires protecting nodes during traversal:

Record* search(Key key) {
    Node* current = root;
    current->latch.lockShared();  // Shared latch - multiple readers OK
    
    while (!current->isLeaf) {
        int i = findChildIndex(current, key);
        Node* child = getNode(current->children[i]);
        child->latch.lockShared();
        current->latch.unlock();  // Release parent before descending (latch coupling)
        current = child;
    }
    
    // Search within leaf...
    current->latch.unlock();
}

This latch coupling (or crabbing) pattern ensures we hold latches on at most two nodes at any time.