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.

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

                [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

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

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
}