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\ge 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<p$.keys$[1]$ set $p:=p$.children$[0]$.
4. Otherwise, if $K>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]<K<p$.keys$[i+1]$.
6. Set $p:=p$.children$[i]$.

Correctness: Obvious.

Complexity

Statement: The asymptotic complexity is in $\mathrm{\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)