# B Plus Tree Search

# B Plus Tree Search

B+ tree search operates on a multiway balanced tree where internal nodes store only routing keys, and all actual records reside in leaf nodes.

Leaves are linked in sorted order. This design improves range queries and sequential access while keeping search depth low.

## Problem

Given a B+ tree root `root` and a target key `x`, locate the record associated with `x`.

If the key does not exist, return null.

## Structure

Internal nodes contain sorted separator keys:

$$
k_0 < k_1 < \cdots < k_{m-1}
$$

and child pointers:

$$
c_0, c_1, \ldots, c_m
$$

Leaf nodes contain all data entries and are linked left to right.

The key ranges follow:

| child | key range                      |
| ----- | ------------------------------ |
| `c0`  | keys smaller than `k0`         |
| `ci`  | keys between `k{i-1}` and `ki` |
| `cm`  | keys greater than `k{m-1}`     |

## Algorithm

Traverse internal nodes to locate the correct leaf. Then search inside the leaf.

```text id="v2k8yx"
bplus_tree_search(node, x):
    while node.is_leaf == false:
        i = upper_bound(node.keys, x)
        node = node.children[i]

    i = lower_bound(node.keys, x)

    if i < length(node.keys) and node.keys[i] == x:
        return node.values[i]

    return null
```

## Example

```text id="n5x3ra"
            [20 | 40]
          /     |     \
     [5 10]  [20 25 30]  [40 50 60]
```

Search for `25`:

| step | node                | action               |
| ---- | ------------------- | -------------------- |
| 1    | `[20, 40]`          | move to middle child |
| 2    | leaf `[20, 25, 30]` | find 25              |

## Correctness

Internal nodes guide the search by partitioning key ranges. At each level, exactly one child can contain the target key.

All actual keys are stored in leaves. Once the correct leaf is reached, searching that node determines existence.

If the key is found, the returned value matches the target. If it is not found in the leaf, no other node can contain it.

## Complexity

Let $B$ be the branching factor.

| measure       | cost          |
| ------------- | ------------- |
| height        | $O(\log_B n)$ |
| node accesses | $O(\log_B n)$ |

Search inside a node:

| method        | cost        |
| ------------- | ----------- |
| binary search | $O(\log B)$ |
| linear scan   | $O(B)$      |

Total time:

$$
O(\log n)
$$

Space complexity:

| version   | space         |
| --------- | ------------- |
| iterative | $O(1)$        |
| recursive | $O(\log_B n)$ |

## When to Use

B+ tree search is widely used in database systems and storage engines.

It is appropriate when:

* range queries and scans are frequent
* data resides on disk or SSD
* high fanout reduces tree height
* sequential leaf traversal is needed

Compared to B trees, B+ trees store all data in leaves and link leaves together, which improves range performance and cache locality.

## Implementation

```python id="t4m8zy"
from bisect import bisect_left, bisect_right

class BPlusNode:
    def __init__(self, keys=None, children=None, values=None, is_leaf=True):
        self.keys = keys or []
        self.children = children or []
        self.values = values or []
        self.is_leaf = is_leaf

def bplus_tree_search(root, x):
    node = root

    while not node.is_leaf:
        i = bisect_right(node.keys, x)
        node = node.children[i]

    i = bisect_left(node.keys, x)

    if i < len(node.keys) and node.keys[i] == x:
        return node.values[i]

    return None
```

```go id="r9q6vm"
type BPlusNode struct {
	Keys     []int
	Children []*BPlusNode
	Values   []int
	IsLeaf   bool
}

func lowerBound(keys []int, x int) int {
	lo, hi := 0, len(keys)
	for lo < hi {
		mid := lo + (hi-lo)/2
		if keys[mid] < x {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	return lo
}

func upperBound(keys []int, x int) int {
	lo, hi := 0, len(keys)
	for lo < hi {
		mid := lo + (hi-lo)/2
		if keys[mid] <= x {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	return lo
}

func BPlusTreeSearch(root *BPlusNode, x int) (int, bool) {
	node := root

	for !node.IsLeaf {
		i := upperBound(node.Keys, x)
		node = node.Children[i]
	}

	i := lowerBound(node.Keys, x)

	if i < len(node.Keys) && node.Keys[i] == x {
		return node.Values[i], true
	}

	return 0, false
}
```