Search in B+-tree

Every time you execute a SQL query with a WHERE clause on an indexed column, you're invoking one of the most elegant search algorithms in computer science: the B+-tree search. This operation transforms what would be a linear scan through millions of records into a graceful descent through a handful of tree levels, delivering results in milliseconds regardless of table size.

Understanding B+-tree search isn't merely academic—it's the foundation for comprehending query performance, predicting I/O costs, and making informed decisions about index design. A Principal Engineer doesn't just use indexes; they understand precisely how the search algorithm navigates the tree structure and why this navigation is extraordinarily efficient.

Before diving into the algorithm, let's precisely formulate what we're trying to accomplish. The B+-tree search problem has two distinct variants:

Point Query (Equality Search): Given a search key K, find all records where the indexed attribute equals K. For example: SELECT * FROM employees WHERE employee_id = 12345.

Range Query: Given a range [K₁, K₂], find all records where the indexed attribute falls within this range. For example: SELECT * FROM orders WHERE order_date BETWEEN '2024-01-01' AND '2024-03-31'.

This page focuses on the point query mechanics. Range queries build upon this foundation and are covered in the next page.

Formal Problem Statement:

Given:

• A B+-tree with order n (maximum n children per node, minimum ⌈n/2⌉ children for non-root nodes)
• A search key K

Find:

• The leaf node L that would contain key K if it exists
• Whether K exists in L
• If K exists, return the associated record pointer(s)

The algorithm must guarantee:

• Correct navigation through internal nodes
• Arrival at the correct leaf node
• O(log n) I/O operations where N is the number of entries

To understand search, we must first crystallize the B+-tree structure that the search algorithm navigates:

Internal Node Structure: Each internal node contains:

• Keys: K₁, K₂, ..., Kₘ₋₁ (where m is the number of children)
• Pointers: P₁, P₂, ..., Pₘ (pointers to child nodes)

The separator key invariant holds:

• All keys in subtree P₁ are < K₁
• All keys in subtree Pᵢ satisfy Kᵢ₋₁ ≤ keys < Kᵢ (for 1 < i < m)
• All keys in subtree Pₘ are ≥ Kₘ₋₁

Leaf Node Structure: Each leaf node contains:

• Keys: K₁, K₂, ..., Kₖ (actual indexed values)
• Record Pointers: corresponding pointers to data records or RIDs
• Sibling Pointer: pointer to the next leaf node (for range scans)

The B+-tree search algorithm is elegantly simple yet powerful. It consists of two phases:

Phase 1: Tree Descent (Finding the Leaf) Starting from the root, traverse down through internal nodes, selecting the appropriate child pointer at each level until reaching a leaf node.

Phase 2: Leaf Search (Finding the Key) Within the leaf node, search for the target key using binary search and return the associated record pointer(s) if found.

Let's trace a complete search operation through a concrete B+-tree example. Consider a B+-tree of order 4 (maximum 4 children per internal node, maximum 3 keys per leaf node) indexing employee IDs:

Tree Structure:

Search for Key = 42:

Step 1: Start at Root

• Current Node: Root with keys [30, 60]
• Search Key: 42
• Comparison: 42 ≥ 30 and 42 < 60
• Decision: Follow second child pointer P₂ (between keys 30 and 60)

Step 2: At Internal Node B

• Current Node: Internal Node B with keys [40, 50]
• Search Key: 42
• Comparison: 42 ≥ 40 and 42 < 50
• Decision: Follow second child pointer P₂

Step 3: At Leaf Node 5

• Current Node: Leaf 5 with keys [40, 42, 45]
• Binary search for 42
• Found at position 2!
• Return: (TRUE, record_pointer_for_42)

Search for Key = 25 (Not Present):

Step 1: Start at Root

• Keys [30, 60], Search Key 25
• 25 < 30, follow first child pointer P₁

Step 2: At Internal Node A

• Keys [10, 20], Search Key 25
• 25 ≥ 20, follow third child pointer P₃

Step 3: At Leaf Node 3

• Keys [20, 22, 28], Search Key 25
• Binary search: 25 not found (would fall between 22 and 28)
• Return: (FALSE, NULL)

Notice that the search correctly navigates to Leaf 3, which is where 25 would be stored if it existed. This property is crucial for insertions.

The B+-tree search algorithm's efficiency stems from its logarithmic depth. Let's derive the time and I/O complexity rigorously.

Height Analysis:

For a B+-tree of order n (max n children per node):

• Minimum children per non-root internal node: ⌈n/2⌉
• Minimum keys in leaf: ⌊(n-1)/2⌋

With N total keys, the maximum height h satisfies:

N ≤ (n-1) × n^(h-1)

Solving for h:

h ≤ 1 + log_n(N/(n-1))
h = O(log_n N)

For typical B+-trees where n = 100-200:

• 1 million records: height ≈ 3-4
• 1 billion records: height ≈ 5-6

I/O Complexity:

Each level traversed requires one disk I/O to read a node. The search reads exactly h nodes where h is the tree height.

I/O Cost = O(log_n N) = O(height)

This is remarkably efficient. Searching among 1 billion records requires only 5 disk reads. At 10ms per random disk seek, that's 50ms—fast enough for interactive queries.

CPU Complexity:

At each internal node, we perform binary search on up to n-1 keys:

• Time per node: O(log n)
• Total time: O(h × log n) = O(log_n N × log n) = O(log N)

Since disk I/O dominates, the O(log N) CPU time is negligible.

Production database systems implement several optimizations to make B+-tree search even faster:

Adaptive Search Strategies:

Some advanced systems employ adaptive techniques:

Hybrid Search: For very wide nodes (high fanout), systems may use a hybrid of binary search and linear probe. Binary search narrows to a cache-line-sized region, then linear scan identifies the exact position.

Branching Hints: After traversing to a leaf, the search path can be cached as a "hint" for subsequent searches with nearby keys. This is particularly effective for range queries and sequential access patterns.

NUMA-Aware Placement: In multi-socket systems, B+-tree nodes are placed in memory close to the processor that most frequently accesses them, reducing memory access latency.

To appreciate B+-tree search, compare it with alternative index structures:

Why B+-trees Win for General-Purpose Indexing:

1. Guaranteed Balance: Unlike BSTs, B+-trees cannot become unbalanced. Every leaf is exactly the same distance from the root, ensuring consistent O(log N) performance regardless of insertion order.

2. Disk-Optimized Fanout: By storing hundreds of keys per node (matching disk block size), B+-trees minimize the number of disk accesses. A binary tree would require one disk access per comparison—catastrophic for large datasets.

3. Range Query Support: Unlike hash indexes, B+-trees maintain sorted order within leaves and link leaves together. After finding a start key, range queries simply follow sibling pointers—no additional tree traversals needed.

4. Mature Implementations: Decades of optimization have produced B+-tree implementations that exploit CPU caches, SIMD, and modern storage hierarchies. The simple algorithm enables sophisticated engineering.