# B Tree Search

# B Tree Search

B tree search generalizes binary search tree search from two children per node to many children per node. Each node stores several sorted keys and several child pointers.

This structure reduces tree height. That makes B trees useful for databases, filesystems, and storage engines where reading one large node from disk or cache is cheaper than following many small pointers.

## Problem

Given a B tree root `root` and a target key `x`, find a key equal to `x`.

If no such key exists, return null.

## Structure

A B tree node contains sorted keys:

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

and, for an internal node, child pointers:

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

The children split the key ranges:

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

## Algorithm

At each node, search inside the node's sorted key array. If the target is present, return it. Otherwise choose the child interval where the target must lie.

```text id="p7f2kx"
b_tree_search(node, x):
    while node != null:
        i = lower_bound(node.keys, x)

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

        if node.is_leaf:
            return null

        node = node.children[i]

    return null
```

## Example

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

Search for `30`:

| step | node keys  | result inside node              | next         |
| ---- | ---------- | ------------------------------- | ------------ |
| 1    | `[20, 40]` | `30` lies between `20` and `40` | middle child |
| 2    | `[25, 30]` | `30` found                      | return       |

## Correctness

Within each B tree node, keys are sorted and child pointers partition the key space. A node search either finds the target directly or identifies exactly one child whose range can contain the target.

The algorithm repeats this argument from the root downward. If it returns a key, that key equals the target. If it reaches a leaf and the key is absent from that leaf, then no remaining child can contain the key, so the target is absent from the tree.

## Complexity

Let `B` be the maximum number of children per node. The height is logarithmic in the number of stored keys.

| measure                                     | cost            |
| ------------------------------------------- | --------------- |
| tree height                                 | $O(\log_B n)$   |
| node visits                                 | $O(\log_B n)$   |
| comparisons with binary search inside nodes | $O(\log n)$     |
| comparisons with linear scan inside nodes   | $O(B \log_B n)$ |

Space complexity:

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

## When to Use

B tree search is appropriate when data is stored in blocks or pages, such as database indexes and filesystems. A single node is designed to fit a page, so each tree level often costs one page read.

Use B trees when:

* data is too large for simple pointer based trees
* storage locality matters
* range scans and ordered lookup are both needed
* insertions and deletions must preserve balanced height

## Implementation

```python id="q3m9rz"
from bisect import bisect_left

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

def b_tree_search(root, x):
    node = root

    while node is not None:
        i = bisect_left(node.keys, x)

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

        if node.is_leaf:
            return None

        node = node.children[i]

    return None
```

```go id="mw2s6c"
type BTreeNode struct {
	Keys     []int
	Children []*BTreeNode
	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 BTreeSearch(root *BTreeNode, x int) (int, bool) {
	node := root

	for node != nil {
		i := lowerBound(node.Keys, x)

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

		if node.IsLeaf {
			return 0, false
		}

		node = node.Children[i]
	}

	return 0, false
}
```