B-tree: find

From Algowiki
Revision as of 13:46, 3 March 2017 by Weihe (talk | contribs) (→‎Abstract View)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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 K".

Abstract View

Invariant: After i0 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],,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{1,,p.n1} 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 Θ(Tlogn) 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 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)