B-tree: find

General Information

Algorithmic problem: Sorted sequence: find

Type of algorithm: loop

Auxiliary data: A pointer [math]\displaystyle{ p }[/math] of type "pointer to a B-tree node of key type [math]\displaystyle{ \mathcal{K} }[/math]".

Abstract View

Invariant: After [math]\displaystyle{ i\geq 0 }[/math] iterations:

1. Pointer [math]\displaystyle{ p }[/math] points to some node of the B-tree on height level [math]\displaystyle{ i }[/math] and
2. the searched key is in the range of that node.

Variant: [math]\displaystyle{ i }[/math] is increased by [math]\displaystyle{ 1 }[/math].

Break condition:

1. [math]\displaystyle{ p }[/math] points to a leaf of the B-tree or (that is, inclusive-or)
2. the searched key is in the node to which [math]\displaystyle{ p\lt math\gt points. == 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: === # Let '''''N''''' denote the node to which '''''p''''' currently points. # If the searched key is in '''''N''''', terminate the algorithm and return '''''true'''''. # Otherwise, if '''''N''''' is a leaf, terminate the algorithm and return '''''false'''''. # Otherwise, let '''''p''''' point the child of '''''N''''' such that the searched key is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of that child === Implementation: === # If '''''K''''' is one of the values \lt math\gt p.keys[1],\dots,p.keys[p.n] }[/math], terminate the algorithm and return true.
3. If [math]\displaystyle{ p.children[0] = void }[/math] (that is, the current node is a leaf), terminate the algorithm and return false.
4. If [math]\displaystyle{ K \lt p.keys[1] }[/math] set [math]\displaystyle{ p := p.children[p.n] }[/math].
5. Otherwise, if [math]\displaystyle{ K \gt p.keys[p.n]\lt /math set \lt math\gt p := p.children[p.n] }[/math].
6. Otherwise, there is exactly one [math]\displaystyle{ i \in \{1,\dots,p.n-1\} }[/math] such that [math]\displaystyle{ p.keys[i] \lt K \lt p.keys[i+1] }[/math].
7. Set [math]\displaystyle{ p := p.children[i] }[/math].

Correctness:

Obvious.

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)

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(T\cdot\log n) }[/math] in the worst case, where [math]\displaystyle{ T }[/math] is the complexity of the comparison.

Proof: Follows immediately from the fact that the height of B-tree with [math]\displaystyle{ n }[/math] nodes is in [math]\displaystyle{ \Theta(\log n) }[/math] (cf. the remark clause of the B-Trees page).