# B Star Tree Search

# B Star Tree Search

B* tree search is the same lookup procedure used by a B tree. The difference lies in how the tree is maintained during insertion and deletion.

A B* tree keeps nodes more densely filled than a standard B tree. Before splitting a full node, it tries to redistribute keys with a sibling. When splitting is unavoidable, it often splits two full nodes into three nodes. This raises storage utilization and can reduce tree height.

## 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

Each internal node stores sorted keys:

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

and child pointers:

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

The child ranges are ordered by the separator keys.

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

## Algorithm

At each node, search the sorted key array. If the key is found, return it. Otherwise descend into the child whose range contains the target.

```text id="n4c8zy"
b_star_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="f8m1qb"
                [30 | 60]
              /     |      \
     [5 | 12 | 20] [35 | 45] [70 | 80 | 90]
```

Search for `45`:

| step | node keys  | action                                                   |
| ---- | ---------- | -------------------------------------------------------- |
| 1    | `[30, 60]` | `45` lies between `30` and `60`; descend to middle child |
| 2    | `[35, 45]` | found `45`; return                                       |

## Correctness

A B* tree preserves the same key ordering invariant as a B tree. The keys inside a node are sorted, and the child pointers partition all possible key ranges.

At each internal node, the algorithm either finds the target directly or chooses the only child whose range can contain it. Repeating this step from root to leaf preserves the invariant that no possible match is discarded.

If the algorithm returns a key, that key equals the target. If it reaches a leaf and does not find the key, no lower subtree exists, so the target is absent from the tree.

## Complexity

Let $B$ be the maximum number of children per node.

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

Total comparison cost with binary search inside nodes is $O(\log n)$.

Space complexity:

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

## When to Use

B* trees are useful when storage density matters. They are close to B trees in lookup behavior but tend to keep pages fuller, which can reduce the number of pages and sometimes the tree height.

Use B* trees when:

* data is stored in fixed size blocks or pages
* high page utilization matters
* ordered lookup and range traversal are needed
* insertion and deletion cost can tolerate redistribution with siblings

## Implementation

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

class BStarNode:
    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_star_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="z6v3qp"
type BStarNode struct {
	Keys     []int
	Children []*BStarNode
	IsLeaf   bool
}

func bstarLowerBound(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 BStarTreeSearch(root *BStarNode, x int) (int, bool) {
	node := root

	for node != nil {
		i := bstarLowerBound(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
}
```