B-tree: find

From Algowiki
Jump to: navigation, search

General Information

Algorithmic problem: Sorted sequence: find

Type of algorithm: loop

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

Abstract View

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

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

Variant: [math]i[/math] is increased by [math]1[/math].

Break condition:

  1. [math]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]p[/math] points.

Remark: For example, the height of the subtree rooted at the node to which [math]p[/math] 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 [math]N[/math] denote the node to which [math]p[/math] currently points.
  2. If the searched key is in [math]N[/math], terminate the algorithm and return true.
  3. Otherwise, if [math]N[/math] is a leaf, terminate the algorithm and return false.
  4. Otherwise, let [math]p[/math] point the child of [math]N[/math] such that the searched key is in the range of that child.

Implementation:

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

Correctness: Obvious.

Complexity

Statement: The asymptotic complexity is in [math]\Theta(T\cdot\log n)[/math] in the worst case, where [math]T[/math] is the complexity of the comparison and [math]n[/math] 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 ix.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)