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.

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

                [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

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

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
}