# B-tree: find

## General Information

Algorithmic problem: Sorted sequence: find

Type of algorithm: loop

Auxiliary data: A pointer $p$ of type "pointer to a B-tree node of key type $\mathcal{K}$".

## Abstract View

Invariant: After $i\geq 0$ iterations:

1. pointer $p$ points to some node of the B-tree on height level $i$ and
2. the searched key is in the range of that node.

Variant: $i$ is increased by $1$.

Break condition:

1. $p$ points to a leaf of the B-tree or (that is, inclusive-or)
2. the searched key is in the node to which $p$ points.

Remark: For example, the height of the subtree rooted at the node to which $p$ points may be chosen as the induction parameter. For conciseness, the induction parameter is omitted in the following.

## Induction Basis

Abstract view: p is initialized so as to point to the root of the B-tree.

Implementation: Obvious.

Proof: Obvious.

## Induction Step

Abstract view:

1. Let $N$ denote the node to which $p$ currently points.
2. If the searched key is in $N$, terminate the algorithm and return true.
3. Otherwise, if $N$ is a leaf, terminate the algorithm and return false.
4. Otherwise, let $p$ point the child of $N$ such that the searched key is in the range of that child.

Implementation:

1. If $K$ is one of the values $p$.keys$[1],\dots,p$.keys$[p.n]$, terminate the algorithm and return true.
2. If $p$.children$[0] =$ void (that is, the current node is a leaf), terminate the algorithm and return false.
3. If $K \lt p$.keys$[1]$ set $p := p$.children$[0]$.
4. Otherwise, if $K \gt p$.keys$[p.n]$ set $p := p$.children$[p.n]$.
5. Otherwise, there is exactly one $i \in \{1,\dots,p.n-1\}$ such that $p$.keys$[i] \lt K \lt p$.keys$[i+1]$.
6. Set $p := p$.children$[i]$.

Correctness: Obvious.

## Complexity

Statement: The asymptotic complexity is in $\Theta(T\cdot\log n)$ in the worst case, where $T$ is the complexity of the comparison and $n$ the total number of keys in the B-tree.

Proof: Follows immediately from the the maximum height of the B-tree.

## Pseudocode

 

 B-TREE-FIND(x,k) 1 i = 1 2 while i ≤ x.n and k > x.keyi 3 i = i + 1 4 if i ≤ x.n and k == x.keyi 5 return (x.i) 6 elseif x.leaf 7 return NIL 8 else DISK-READ(x.ci) 9 return B-TREE-FIND(x.ci,k)